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: | Liaw Ching-Fang |
Keywords: | programming: branch and bound |
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.