Article ID: | iaor20042588 |
Country: | United Kingdom |
Volume: | 30 |
Issue: | 12 |
Start Page Number: | 1777 |
End Page Number: | 1789 |
Publication Date: | Oct 2003 |
Journal: | Computers and Operations Research |
Authors: | Liaw Ching-Fang, Cheng Chun-Yuan, Lin Yang-Kuei, Chen Mingchin |
Keywords: | heuristics, programming: branch and bound |
This article considers the problem of scheduling a given set of independent jobs on unrelated parallel machines to minimize the total weighted tardiness. The problem is known to be NP-hard in the strong sense. Efficient lower and upper bounds are developed. The lower bound is based on the solution of an assignment problem, while the upper bound is obtained by a two-phase heuristic. A branch-and-bound algorithm that incorporates various dominance rules is presented. Computational experiments are conducted to demonstrate the performance of the proposed algorithm.