TY - BOOK

T1 - Approximation algorithms for the multiprocessor open shop scheduling problem

AU - Schuurman, P.

AU - Woeginger, G.J.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

M3 - Report

T3 - Memorandum COSOR

BT - Approximation algorithms for the multiprocessor open shop scheduling problem

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -