Some positive news on the proportionate open shop problem

摘要

The special case of the open shop problem in which every jobhas equal length operations on all machines is known as a proportionateopen shop problem. The problem is NP-hard in the case of three machines,which makes topical such traditional research directions as designingefficient heuristics and searching for efficiently solvable cases. In thispaper 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 theexact values of the power of preemption for the three-machine problem,being considered as a function of a parameter (the ratio of two standardlower bounds on the optimum: the machine load and the maximum joblength). We also found out that the worst-case power of preemption forthe m-machine problem asymptotically converges to 1, as m tends toinfinity. Finally, we established the exact complexity status of the threemachineproblem by presenting a pseudo-polynomial algorithm for itssolution.