Scheduling preemptive open shops to minimize total tardiness

Scheduling preemptive open shops to minimize total tardiness

0.00 Avg rating0 Votes
Article ID: iaor200683
Country: Netherlands
Volume: 162
Issue: 1
Start Page Number: 173
End Page Number: 183
Publication Date: Apr 2005
Journal: European Journal of Operational Research
Authors:
Keywords: programming: branch and bound
Abstract:

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.

Reviews

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