Title: Lower bounds for parallel machine scheduling problems

Authors: Philippe Baptiste, Antoine Jouglet, David Savourey

Addresses: Ecole Polytechnique, UMR 7161 CNRS LIX, 91128 Palaiseau, France. ' Heudiasyc, UMR CNRS 6599, Universite de Technologie de Compiegne, BP 20529, 60205 Compiegne, France. ' Ecole Polytechnique, UMR 7161 CNRS LIX, 91128 Palaiseau, France

Abstract: We study the parallel machine scheduling problem with release dates and consider several |min-sum| objective functions including total weighted tardiness, total tardiness, total weighted completion time and total completion time. We describe several lower bounds for these problems, most of them being original ones. We provide experimental results to compare these lower bounds according to their quality and of their computational time requirement.

Keywords: identical parallel machines; lower bounds; parallel machine scheduling; total cost; release dates.

DOI: 10.1504/IJOR.2008.019731

International Journal of Operational Research, 2008 Vol.3 No.6, pp.643 - 664

Published online: 27 Jul 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article