Article ID: | iaor2009982 |
Country: | United Kingdom |
Volume: | 35 |
Issue: | 4 |
Start Page Number: | 1176 |
End Page Number: | 1190 |
Publication Date: | Apr 2008 |
Journal: | Computers and Operations Research |
Authors: | Chu Chengbin, Yalaoui Farouk, Nessah Rabia |
Keywords: | programming: branch and bound, heuristics |
In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose some dominance properties and two lower bounds. We also present an efficient heuristic. A branch-and-bound algorithm, in which the heuristic, the lower bounds and the dominance properties are incorporated, is proposed and tested on a large set of randomly generated instances.