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 γ (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 threemachine problem by presenting a pseudo-polynomial algorithm for its solution. © 2019, Sobolev Institute of Mathematics.

Cite: Sevastyanov S.V.
Some positive news on the proportionate open shop problem
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2019. V.16. P.406-426. DOI: 10.33048/semi.2019.16.023 WOS Scopus OpenAlex

Identifiers:

Web of science:	WOS:000462734100001
Scopus:	2-s2.0-85071185670
OpenAlex:	W3015953147

Citing:

DB	Citing
Scopus	9
OpenAlex	8
Web of science	6

Altmetrics: