Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 17-25
Volume 24, No 1, 2017, P. 5-20
UDC 519.8
E. A. Bobrova and V. V. Servakh
Construction of cyclic schedules in presence of parallel machines
Abstract:
We consider the problem of processing some identical jobs with a complicated technological route on some production line in presence of parallel machines. Under some constraints on the number of jobs processed simultaneously, a cyclic schedule is desired with minimum cycle
duration. Some algorithm for construction of an exact solution is proposed and substantiated. Also, we found the case of pseudopolynomially solvable problem.
Illustr. 4, bibliogr. 16.
Keywords: cyclic schedule, dynamic programming, pseudopolynomial algorithm.
DOI: 10.17377/daio.2017.24.500
Ekaterina A. Bobrova 1
Vladimir V. Servakh 1
1. Omsk Branch of Sobolev Institute of Mathematics,
13 Pevtsov St., 644043 Omsk, Russia
e-mail: eabobrova88@gmail.com, svv_usa@rambler.ru
Received 3 July 2015
Revised 30 August 2016
References
[1] E. A. Bobrova, A. A. Romanova, and V. V. Servakh, The complexity of cyclic scheduling for identical jobs, Diskretn. Anal. Issled. Oper., 20, No. 4, 3–14, 2013 [Russian].[2] A. A. Romanova and V. V. Servakh, Optimization of processing identical jobs by means of cyclic schedules, Diskretn. Anal. Issled. Oper., 15, No. 5, 47–60, 2008 [Russian]. Translated in J. Appl. Ind. Math., 3, No. 4, 496–504, 2009.
[3] V. V. Servakh, An effectively solvable case of a project scheduling problem with renewable resources, Diskretn. Anal. Issled. Oper., Ser. 2, 7, No. 1, 75–82, 2000 [Russian].
[4] V. G. Timkovsky, Approximate solution of schedule construction problem for cyclic system, Ekon. Mat. Metody, 22, No. 1, 171–174, 1986 [Russian].
[5] T. Boudoukh, M. Penn, and G. Weiss, Job-shop — an application of fluid approximation, in Proc. 10th Conf. Ind. Eng. Manag., Haifa, Israel, June 10–12, 1998, pp. 254–258, Isr. Inst. Technol., Haifa, 1998 [Hebrew].
[6] T. Boudoukh, M. Penn, and G. Weiss, Scheduling jobshops with some identical or similar jobs, J. Sched., 4, No. 4, 177–199, 2001.
[7] P. Brucker, Scheduling Algorithms, Springer, Heidelberg, 2007.
[8] N. G. Hall, T. E. Lee, and M. E. Posner, The complexity of cyclic shop scheduling problems, J. Sched., 5, No. 4, 307–327, 2002.
[9] C. Hanen, Study of a NP-hard cyclic scheduling problem: The recurrent job-shop, Eur. J. Oper. Res., 72, No. 1, 82–101, 1994.
[10] H. Kamoun and C. Sriskandarajah, The complexity of scheduling jobs in repetitive manufacturing systems, Eur. J. Oper. Res., 70, No. 3, 350–364, 1993.
[11] E. Levner, V. Kats, D. Pablo, and E. Cheng, Complexity of cyclic scheduling problems: A state-of-the-art survey, Comput. Ind. Eng., 59, No. 2, 352–361, 2010.
[12] S. T. McCormick and U. S. Rao, Some complexity results in cyclic scheduling, Math. Comput. Model., 20, No. 2, 107–122, 1994.
[13] U. S. Rao and P. L. Jackson, Subproblems in identical jobs cyclic scheduling: Properties, complexity and solution approaches, Tech. Rep., Cornell Univ., Ithaca, NY, USA, 1993. Available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.3814. Accessed Oct. 5, 2016.
[14] R. Roundy, Cyclic schedules for job shops with identical jobs, Math. Oper. Res., 17, No. 4, 842–865, 1992.
[15] V. V. Servakh, A dynamic algorithm for some project management problems, in Proc. Int. Workshop “Discrete Optimization Methods in Scheduling and Computer-Aided Design”, Minsk, Belarus, Sept. 5–6, pp. 90–92, Inst. Eng. Cybern. NAS Belarus, Minsk, 2000.
[16] V. G. Timkovsky, Cycle shop scheduling, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp. 127–148, CRC Press, Boca Raton, 2004.
