Approximation algorithms for the multiprocessor open shop scheduling problem

P. Schuurman, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

27 Citations (Scopus)


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 .
Original languageEnglish
Pages (from-to)157-163
Number of pages7
JournalOperations Research Letters
Issue number4
Publication statusPublished - 1999


Dive into the research topics of 'Approximation algorithms for the multiprocessor open shop scheduling problem'. Together they form a unique fingerprint.

Cite this