Geodesic
Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 56-73.

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

We consider the cyclic job shop problem with no-wait constraints which consists in minimizing the cycle time. We assume that a single product is produced on a few machines. A job is processed by performing a given set of operations in a predetermined sequence. Each operation can be performed on exactly one machine. We consider the problem of minimization the cycle time with no-wait constraints between some pairs of sequential operations and investigate the complexity of the problem and some of its subproblems. In general, the problem is proved to be strongly NP-hard. In the case when the job is processed without downtime between operations, polynomial solvability is proved and the two algorithms are proposed. Also we develop an algorithm for the general case which is pseudopolynomial if the number of admissible downtime is fixed. The case of a single no-wait constraint is polynomially solvable. The problem with two no-wait constraints becomes NP-hard. We found effectively solvable cases and propose the corresponding algorithms. Illustr. 4, bibliogr. 14.
Keywords: scheduling theory, cyclic job shop, identical jobs, computational complexity theory
Mots-clés : polynomial algorithm, pseudopolynomial algorithm. 
@article{DA_2019_26_4_a3,
     author = {A. A. Romanova and V. V. Servakh},
     title = {Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {56--73},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_4_a3/}
}
TY  - JOUR
AU  - A. A. Romanova
AU  - V. V. Servakh
TI  - Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 56
EP  - 73
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_4_a3/
LA  - ru
ID  - DA_2019_26_4_a3
ER  - 
%0 Journal Article
%A A. A. Romanova
%A V. V. Servakh
%T Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 56-73
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_4_a3/
%G ru
%F DA_2019_26_4_a3
A. A. Romanova; V. V. Servakh. Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 56-73. http://geodesic.mathdoc.fr/item/DA_2019_26_4_a3/

[1] E. A. Bobrova, A. A. Romanova, V. V. Servakh, “The complexity of the cyclic job shop problem with identical jobs”, Diskretn. Anal. Issled. Oper., 20:4 (2013), 3–14 (Russian) | MR | Zbl

[2] A. A. Romanova, V. V. Servakh, “Optimization of identical jobs production on the base of cyclic schedules”, Diskretn. Anal. Issled. Oper., 15:5 (2008), 47–60 (Russian) | Zbl

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

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

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

[6] M. Middendorf, V. Timkovsky, “On scheduling cycle shops: classification, complexity and approximation”, J. Sched., 5 (2002), 135–169 | DOI | MR | Zbl

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

[8] K. A. Aldakhilallah, R. Ramesh, “Cyclic scheduling heuristics for a reentrant job shop manufacturing environment”, Int. J. Prod. Res., 39 (2001), 2635–2675 | DOI

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

[10] P. Brucker, T. Kampmeyer, “Tabu search algorithms for cyclic machine scheduling problems”, J. Sched., 8 (2005), 303–322 | DOI | MR | Zbl

[11] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[12] V. Kats, E. Levner, “Cyclic scheduling in a robotic production line”, J. Sched., 5 (2002), 23–41 | DOI | MR | Zbl

[13] V. S. Aizenshtat, “Multi-operator cyclic processes”, Dokl. Nats. Akad. Nauk Belarus, 7:4 (1963), 224–227 (Russian) | Zbl

[14] V. S. Tanaev, “A scheduling problem for a flowshop line with a single operator”, Inzh. Fiz. Zh., 7:3 (1964), 111–114 (Russian)