Full-text PDF (642 kB) Citations (8)

DOI: https://doi.org/10.33048/semi.2019.16.023

Abstract: 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, polynomial time heuristic, dynamic programming.

Funding agency	Grant number
Russian Foundation for Basic Research	17-07-00513_а
Siberian Branch of Russian Academy of Sciences	0314-2019-0014
The work is supported by the Russian Foundation for Basic Research (grant 17-07-00513) and by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014).

Received December 21, 2018, published March 29, 2019

Bibliographic databases:

Citation: Sergey Sevastyanov, “Some positive news on the proportionate open shop problem”, Sib. Èlektron. Mat. Izv., 16 (2019), 406–426

Citation in format AMSBIB

Linking options:

https://www.mathnet.ru/eng/semr1065

https://www.mathnet.ru/eng/semr/v16/p406

This publication is cited in the following articles:

1. Ilya Chernykh, Olga Krivonogova, Lecture Notes in Computer Science, 12095, Mathematical Optimization Theory and Operations Research, 2020, 274  
2. A. P. Khramova, I. Chernykh, “A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing”, J. Sched., 24:4 (2021), 405–412          
3. M. M. Ahmadian, M. Khatami, A. Salehipour, T. C. E. Cheng, “Four decades of research on the open-shop scheduling problem to minimize the makespan”, Eur. J. Oper. Res., 295:2 (2021), 399–426          
4. S. Gawiejnowicz, M. Kolinska, “Two- and three-machine open shop scheduling using LAPT-like rules”, Comput. Ind. Eng., 157 (2021), 107261        
5. Vitaly A. Strusevich, “Complexity and approximation of open shop scheduling to minimize the makespan: A review of models and approaches”, Computers & Operations Research, 144 (2022), 105732  
6. Wieslaw Kubiak, International Series in Operations Research & Management Science, 325, A Book of Open Shop Scheduling, 2022, 165  
7. Ilya Chernykh, Olga Krivonogova, Anna Shmyrina, Lecture Notes in Computer Science, 13930, Mathematical Optimization Theory and Operations Research, 2023, 197  
8. Abdennour Azerine, Mourad Boudhar, Djamal Rebaine, “On the complexity of proportionate open shop and job shop problems”, Optim Lett, 18:1 (2024), 365  

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles