Geodesic
The complexity of cyclic scheduling for identical jobs
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 3-14.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the Cyclic Job Shop Problem for identical jobs with the criterion for cycle time minimization when the number of simultaneously processed tasks during the cycle time is limited by a constant $H$. We prove that this problem is NP-hard in the case $H\ge4$. For the case $H=2$, we propose an exact polynomial algorithm. Ill. 7, bibliogr. 16.
Keywords: identical tasks, cyclic scheduling. 
@article{DA_2013_20_4_a0,
     author = {E. A. Bobrova and A. A. Romanova and V. V. Servakh},
     title = {The complexity of cyclic scheduling for identical jobs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--14},
     publisher = {mathdoc},
     volume = {20},
     number = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_4_a0/}
}
TY  - JOUR
AU  - E. A. Bobrova
AU  - A. A. Romanova
AU  - V. V. Servakh
TI  - The complexity of cyclic scheduling for identical jobs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 3
EP  - 14
VL  - 20
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_4_a0/
LA  - ru
ID  - DA_2013_20_4_a0
ER  - 
%0 Journal Article
%A E. A. Bobrova
%A A. A. Romanova
%A V. V. Servakh
%T The complexity of cyclic scheduling for identical jobs
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 3-14
%V 20
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_4_a0/
%G ru
%F DA_2013_20_4_a0
E. A. Bobrova; A. A. Romanova; V. V. Servakh. The complexity of cyclic scheduling for identical jobs. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 3-14. http://geodesic.mathdoc.fr/item/DA_2013_20_4_a0/

[1] Mezhetskaya M. A., Zadachi vypuska partii odnotipnykh detalei s ogranicheniem na chislo odnovremenno obrabatyvaemykh detalei, Preprint, Izd-vo OmGU, Omsk, 2008, 35 pp.

[2] Romanova A. A., Servakh V. V., “Optimizatsiya vypuska odnotipnykh detalei na osnove tsiklicheskikh raspisanii”, Diskret. analiz i issled. operatsii, 15:5 (2008), 47–60 | MR | Zbl

[3] Servakh V. V., “O zadache Akersa–Fridmana”, Upravlyaemye sistemy, 23, 1983, 70–81 | MR | Zbl

[4] Timkovskii V. G., “Priblizhënnoe reshenie zadachi sostavleniya raspisaniya tsiklicheskoi sistemy”, Ekonomika i mat. metody, 22:1 (1986), 171–174 | MR

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

[6] Brucker P., Scheduling algorithms, Springer-Verl., Leipzig, 2007, 371 pp.

[7] Hall N. G., Lee T. E., Posner M. E., “The complexity of cyclic shop scheduling problems”, J. Sched., 5 (2002), 307–327 | DOI | MR | Zbl

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

[9] Hardgrave W. W., Nemhauser G. A., “Geometric model and graphical algorithm for a sequencing problem”, Oper. Res., 11:6 (1963), 889–900 | DOI | Zbl

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

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

[12] McCormick S. T., Rao U. S., “Some complexity results in cyclic scheduling”, Math. Comput. Modeling, 20 (1994), 107–122 | DOI | MR | Zbl

[13] Rao U., Jackson P., Identical jobs cyclic scheduling: subproblems, properties, complexity and solution approaches, Cornell Univ. Press, Ithaca, NY, 1993, 48 pp. | Zbl

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

[15] Sotskov Y. N., Shakhlevich N. V., “NP-hardness of shop-scheduling problems with three jobs”, Discrete Appl. Math., 59:3 (1995), 237–266 | MR | Zbl

[16] Timkovsky V. G., “Cyclic shop scheduling”, Handbook of scheduling: algorithms, models, and performance analysis, Chapman Hall/CRC, Boca Raton, 2004, 7.1–7.22 | MR