Geodesic
Construction of cyclic schedules in presence of parallel machines
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 5-20 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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
Mots-clés : pseudopolynomial algorithm. 
@article{DA_2017_24_1_a0,
     author = {E. A. Bobrova and V. V. Servakh},
     title = {Construction of cyclic schedules in presence of parallel machines},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--20},
     year = {2017},
     volume = {24},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_1_a0/}
}
TY  - JOUR
AU  - E. A. Bobrova
AU  - V. V. Servakh
TI  - Construction of cyclic schedules in presence of parallel machines
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 5
EP  - 20
VL  - 24
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_1_a0/
LA  - ru
ID  - DA_2017_24_1_a0
ER  - 
%0 Journal Article
%A E. A. Bobrova
%A V. V. Servakh
%T Construction of cyclic schedules in presence of parallel machines
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 5-20
%V 24
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2017_24_1_a0/
%G ru
%F DA_2017_24_1_a0
E. A. Bobrova; V. V. Servakh. Construction of cyclic schedules in presence of parallel machines. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 5-20. http://geodesic.mathdoc.fr/item/DA_2017_24_1_a0/

[1] E. A. Bobrova, A. A. Romanova, V. V. Servakh, “The complexity of cyclic scheduling for identical jobs”, Diskretn. Anal. Issled. Oper., 20:4 (2013), 3–14 (Russian)

[2] A. A. Romanova, V. V. Servakh, “Optimization of processing identical jobs by means of cyclic schedules”, J. Appl. Ind. Math., 3:4 (2009), 496–504

[3] V. V. Servakh, “An effectively solvable case of a project scheduling problem with renewable resources”, Diskretn. Anal. Issled. Oper., 7:1 (2000), 75–82 (Russian)

[4] V. G. Timkovsky, “Approximate solution of schedule construction problem for cyclic system”, Ekon. Mat. Metody, 22:1 (1986), 171–174 (Russian)

[5] Boudoukh T., Penn M., Weiss G., “Job-shop — an application of fluid approximation”, Proc. 10th Conf. Ind. Eng. Management (Haifa, Israel, June 10–12, 1998), Isr. Inst. Technol., Haifa, Israel, 1998, 254–258 (Hebrew)

[6] Boudoukh T., Penn M., Weiss G., “Scheduling jobshops with some identical or similar jobs”, J. Sched., 4:4 (2001), 177–199

[7] Brucker P., Scheduling algorithms, Springer-Verl., Berlin–Heidelberg–New York, 2007, 371 pp.

[8] Hall N. G., Lee T. E., Posner M. E., “The complexity of cyclic shop scheduling problems”, J. Sched., 5:4 (2002), 307–327

[9] Hanen C., “Study of a NP-hard cyclic scheduling problem: The recurrent job-shop”, Eur. J. Oper. Res., 72:1 (1994), 82–101

[10] Kamoun H., Sriskandarajah C., “The complexity of scheduling jobs in repetitive manufacturing systems”, Eur. J. Oper. Res., 70:3 (1993), 350–364

[11] Levner E., Kats V., Pablo D., Cheng E., “Complexity of cyclic scheduling problems: A state-of-the-art survey”, Comput. Ind. Eng., 59:2 (2010), 352–361

[12] McCormick S. T., Rao U. S., “Some complexity results in cyclic scheduling”, Math. Comput. Model., 20:2 (1994), 107–122

[13] Rao U. S., Jackson P. L., Subproblems in identical jobs cyclic scheduling: properties, complexity, and solution approaches, Tech. Rep., Cornell Univ. Press, Ithaca, NY, 1993, 47 pp.

[14] Roundy R., “Cyclic schedules for job shops with identical jobs”, Math. Oper. Res., 17:4 (1992), 842–865

[15] Servakh V. V., “A dynamic algorithm for some project management problems”, Proc. Int. Workshop Discrete Optimization Methods in Scheduling and Computer-Aided Design (Minsk, Sept. 5–6, 2000), Inst. Eng. Cybern. NAS Belarus, Minsk, 2000, 90–92

[16] Timkovsky V. G., “Cycle shop scheduling”, Handbook of scheduling: algorithms, models, and performance analysis, ed. J.Y.-T. Leung, Chapman Hall/CRC, London, 2004, 127–148