Title: Scheduling on parallel identical machines to minimise the total weighted tardiness

Authors: Nizar Souayah, Imed Kacem, Mohamed Haouari, Chengbin Chu

Addresses: Ecole Polytechnique de Tunisie, 2078 La Marsa, Tunisie. ' University of Paul Verlaine – Metz, France. ' Faculty of Engineering, Ozyegin University, Istanbul, Turkey. ' Ecole Centrale Paris, France

Abstract: This paper considers the problem of scheduling n independent jobs on m identical parallel machines to minimise the total weighted tardiness. We propose several lower bounds and upper bounds. These bounding procedures are used in a new branch-and-bound (BAB) algorithm. We also propose a branch-and-cut algorithm which we compare with the branch-and-bound algorithm. Computational experiments are performed on a large set of instances and the obtained results show the effectiveness of our method.

Keywords: parallel machines; weighted tardiness; lower bounds; Lagrangian relaxation; parallel machine scheduling.

DOI: 10.1504/IJAOM.2009.026523

International Journal of Advanced Operations Management, 2009 Vol.1 No.1, pp.30 - 69

Published online: 18 Jun 2009 *

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