Approximation algorithms for the multiprocessor open shop scheduling problem

We investigate the multiprocessor multistage open shop scheduling problem. In this variant of the open shop model, there are s stages, each consisting of a number of parallel identical machines. Each job consists of s operations, one for each stage, that can be executed in any order. The goal is to nd a nonpreemptive schedule that minimizes the makespan. We derive two approximation results for this NP-hard problem. First, we demonstrate the existence of a polynomial time approximation algorithm with worst case ratio 2 for the case that the number s of stages is part of the input. This algorithm is based on Racsmány's concept of dense schedules. Secondly, for the multiprocessor two stage open shop problem we derive a family of polynomialtime approximation algorithms whose worst case ratios can be made arbitrarily close to 3/2.