Approximation algorithms for the multiprocessor open shop scheduling problem

P. Schuurman, G.J. Woeginger

Research output: Book/ReportReportAcademic

335 Downloads (Pure)


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.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages10
Publication statusPublished - 1997

Publication series

NameMemorandum COSOR
ISSN (Print)0926-4493


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

Cite this