Geodesic
The complexity of cyclic scheduling for identical jobs
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 4, pp. 3-14 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2013},
     volume = {20},
     number = {4},
     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
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
%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