A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: branch and bound, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.