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.
International Journal of Advanced Operations Management, 2009 Vol.1 No.1, pp.30 - 69
Published online: 18 Jun 2009 *Full-text access for editors Access for subscribers Purchase this article Comment on this article