Geodesic
Some positive news on the proportionate open shop problem
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 406-426.

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

The special case of the open shop problem in which every job has equal length operations on all machines is known as a proportionate open shop problem. The problem is NP-hard in the case of three machines, which makes topical such traditional research directions as designing efficient heuristics and searching for efficiently solvable cases. In this paper we found several new efficiently solvable cases (wider than known) and designed linear-time heuristics with good performance guarantees (better than those known from the literature). Besides, we computed the exact values of the power of preemption for the three-machine problem, being considered as a function of a parameter $\gamma$ (the ratio of two standard lower bounds on the optimum: the machine load and the maximum job length). We also found out that the worst-case power of preemption for the $m$-machine problem asymptotically converges to 1, as $m$ tends to infinity. Finally, we established the exact complexity status of the three-machine problem by presenting a pseudo-polynomial algorithm for its solution.
Keywords: open shop, proportionate, scheduling, makespan minimization, power of preemption, dynamic programming.
Mots-clés : polynomial time heuristic 
@article{SEMR_2019_16_a114,
     author = {Sergey Sevastyanov},
     title = {Some positive news on the proportionate open shop problem},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {406--426},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a114/}
}
TY  - JOUR
AU  - Sergey Sevastyanov
TI  - Some positive news on the proportionate open shop problem
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 406
EP  - 426
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a114/
LA  - en
ID  - SEMR_2019_16_a114
ER  - 
%0 Journal Article
%A Sergey Sevastyanov
%T Some positive news on the proportionate open shop problem
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 406-426
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a114/
%G en
%F SEMR_2019_16_a114
Sergey Sevastyanov. Some positive news on the proportionate open shop problem. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 406-426. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a114/

[1] Bárány I., Fiala T., “Nearly optimum solution of multimachine scheduling problems”, Szigma, 15:3 (1982), 177–191 (in Hungarian) | MR | Zbl

[2] I. Chernykh, S. Sevastyanov, “On the abnormality in open shop scheduling”, 17th Baikal International Triannual School-Seminar “Methods of Optimization and their Applications” (July 31–August 6, 2017, Maksimikha, Buryatia), 2017 http://isem.irk.ru/conferences/mopt2017/Abstracts/BAIKAL_2017_paper_95.pdf | Zbl

[3] I.G. Drobouchevitch, V.A. Strusevich, “A polynomial algorithm for the three-machine open shop with a bottleneck machine”, Ann. Oper. Res., 92 (1999), 185–214 | DOI | MR

[4] T. Fiala, “An Algorithm for the Open-Shop Problem”, Mathematics of Operations Research, 8:1 (1983), 100–109 | DOI | MR | Zbl

[5] T. Gonzalez, S. Sahni, “Open shop scheduling to minimize finish time”, J. Assoc. Comput. Mach., 23:4 (1976), 665–679 | DOI | MR | Zbl

[6] Kononov A., Sevastianov S., Tchernykh I., “When difference in machine loads leads to efficient scheduling in open shops”, Annals of Operations Research, 92 (1999), 211–239 | DOI | MR | Zbl

[7] Koulamas C., Kyparisis G. J., “The Three-Machine Proportionate Open Shop and Mixed Shop Minimum Makespan Problems”, European Journal of Operational Research, 243:1 (2015), 70–74 | DOI | MR | Zbl

[8] G.J. Kyparisis, C. Koulamas, “Open shop scheduling with maximal machines”, Discrete Applied Mathematics, 78 (1997), 175–187 | DOI | MR | Zbl

[9] C.Y. Liu, R.L. Bulfin, “Scheduling ordered open shops”, Computers and Operations Research, 14 (1987), 257–264 | DOI | MR | Zbl

[10] M.E. Matta, S.E. Elmaghraby, “Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop”, European Journal of Operational Research, 201:3 (2010), 720–728 | DOI | MR | Zbl

[11] B. Naderi, M. Zandieh, M. Yazdani, “Polynomial time approximation algorithms for proportionate open-shop scheduling”, International Transactions in Operational Research, 21:6 (2014), 1031–1044 | DOI | MR | Zbl

[12] S.V. Sevastyanov, “On the Compact Vector Summation”, Diskretnaya Matematika, 3:3 (1991), 66–72 (in Russian) | MR | Zbl

[13] S.V. Sevast'yanov, “A polynomial-time open-shop problem with an arbitrary number of machines”, Cybernetics and Systems Analysis, 28:6 (1992), 918–933 | DOI | MR | Zbl

[14] S.V. Sevastyanov, “Vector summation in Banach space and polynomial algorithms for flow shops and open shops”, Mathematics of Operations Research, 20:1 (1995), 90–103 | DOI | MR | Zbl

[15] Sevastianov S., “Nonstrict vector summation in multi-operation scheduling”, Annals of Operations Research, 83 (1998), 179–211 | DOI | MR | Zbl

[16] S.V. Sevastianov, I.D. Tchernykh, “Computer-Aided Way to Prove Theorems in Scheduling”, Algorithms - ESA'98, 6th Annual European Symposium, Proceedings (Venice, Italy, August 1998), Lecture Notes in Computer Science, 1461, eds. Bilardi, a.o., Springer-Verlag, 1998, 502–513 | DOI | MR | Zbl

[17] S.V. Sevastianov, G.J. Woeginger, “Makespan minimization in open shops: a polynomial time approximation scheme”, Mathematical Programming, 82:1–2 (1998), 191–198 | DOI | MR | Zbl

[18] Sevastianov S. V., Woeginger G. J., “Linear time approximation scheme for the multiprocessor open shop problem”, Discrete Applide Mathematics, 114 (2001), 273–288 | DOI | MR | Zbl