Scheduling unrelated parallel machines to minimize total weighted tardiness

Scheduling unrelated parallel machines to minimize total weighted tardiness

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

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.

Reviews

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