Article ID: | iaor2003201 |
Country: | Netherlands |
Volume: | 76 |
Issue: | 3 |
Start Page Number: | 265 |
End Page Number: | 279 |
Publication Date: | Jan 2002 |
Journal: | International Journal of Production Economics |
Authors: | Chu Chengbin, Yalaoui Farouk |
This paper addresses, using an exact method, the identical parallel machine scheduling problem to minimize total tardiness. In this problem, a set of jobs has to be scheduled, without preemption, on identical parallel machines. Each machine is able to treat only one job at a time. In order to prune the search tree, dominance properties are proved and lower and upper bounding schemes are proposed. A branch and bound (BAB) algorithm is developed taking into account these theoretical properties, lower and upper bounds. This BAB algorithm has been tested on a large set of randomly generated medium-sized problems. Computational results demonstrate the effectiveness of our approach over existing methods in the literature.