Title :
A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
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 know to be strongly NP-hard. We propose two lower bounds. We present an efficient heuristic, we also propose some dominance properties. 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
Keywords :
job shop scheduling; parallel machines; tree searching; branch-bound algorithm; dominance properties; identical parallel machines; job release dates; scheduling problem; total weighted completion time; Dynamic programming; Heuristic algorithms; NP-hard problem; Open systems; Optimal scheduling; Parallel machines; Polynomials; Processor scheduling; Scheduling algorithm; Testing; Branch and bound; Dominance properties; Identical parallel machine; Lower bound; Release dates; Scheduling;
Conference_Titel :
Service Systems and Service Management, 2006 International Conference on
Conference_Location :
Troyes
Print_ISBN :
1-4244-0450-9
Electronic_ISBN :
1-4244-0451-7
DOI :
10.1109/ICSSSM.2006.320678
