Approximation algorithms for the multiprocessor open shop scheduling problem

We investigate the multiprocessor multi-stage 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 find a non-preemptive 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 polynomial-time approximation algorithms whose worst-case ratios can be made arbitrarily close to 3/2 .