ALCOMFT-TR-03-192

Ann Vandevelde, Han Hoogeveen, Cor Hurkens and Jan Karel Lenstra
Lower bounds for the head-body-tail problem on parallel machines: a computational study of the multiprocessor flow shop
Utrecht. Work package 3. December 2003.

Abstract: The multiprocessor flow shop is the generalization of the flow shop in which each machine is replaced by a set of identical machines. As finding a minimum-length schedule is \mathcalNP-hard, we set out to find good lower and upper bounds. The lower bounds are based on relaxation of the capacities of all machine sets except one. This results in a parallel machine scheduling problem with release dates and delivery times, for which we derive a number of lower bounds. We pay special attention to the time complexity of algorithms for computing these bounds. To obtain the upper bounds a constructive algorithm in subsequent stages is used. We present an experimental comparison of the various lower and upper bounds for the multiprocessor flow shop problem.

Key words. Multiprocessor flow shop, parallel machine scheduling, head-body-tail problems, preemptive schedule, lower bound, computational study.

Postscript file: ALCOMFT-TR-03-192.ps.gz (234 kb).