An exact method for Pm/sds, ri/∑ni=1Ci problem

An exact method for Pm/sds, ri/∑ni=1Ci problem

0.00 Avg rating0 Votes
Article ID: iaor20083029
Country: United Kingdom
Volume: 34
Issue: 9
Start Page Number: 2840
End Page Number: 2848
Publication Date: Sep 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

This paper addresses an identical parallel machine scheduling problem, with sequence-dependent setup times and release dates to minimize total completion time. This problem is known to be strongly NP-hard. We prove a sufficient and necessary condition for local optimality which can also be considered as a priority rule. We then define a dominant subset based on this condition. We present efficient heuristic algorithms using this condition to build a schedule belonging to this subset. We also prove dominance theorem, and develop a lower bound that can be computed in polynomial time. We construct a branch-and-bound algorithm in which the heuristic, the lower bound and the dominance properties are incorporated. Computational experiments suggest that the algorithm can handle test problems with 40 jobs and 2 machines.

Reviews

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