Improved Scheduling for the Three-Machine Proportionate Open Shop and Mixed Shop Minimum Makespan Problems

Open shop scheduling problems have many practical applications, in which the jobs can be in any order with the only restriction that their durations do not overlap with each other. In some cases, the order of a subset of jobs dictates the flow shop model while the remaining jobs can be processed in any order according to the open shop model, and the corresponding problem is called mixed shop scheduling. For every job, if its processing times on all machines are the same, then the shop is called proportionate shop. In this article we investigate the three-machine proportionate open shop and mixed shop minimum makespan problems proposed by Koulamas and Kyparisis. Our result improves the previous work in three ways. First, for both the open shop and the mixed shop scheduling problems, we derive additional sufficient conditions under which the corresponding problems are solvable in polynomial time. Second, for the non-solvable cases of the open shop scheduling problem we present an improved 13/12-approximation algorithm. Third, for the non-solvable cases of the mixed shop scheduling problem we present an improved approximation algorithm with the worst-case ratio bound of (7/6 + ϵ). All the algorithms proposed in this article run in polynomial time.