Polynomial time approximation algorithms for proportionate open-shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if n≥m, where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, m>n, we develop a polynomial time approximation algorithm with a worst‐case performance ratio of (2−1/n) that improves the bound existing for general open‐shops. Next, in the case of m>n, we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where m>n.