Article ID: | iaor2000810 |
Country: | United Kingdom |
Volume: | 26 |
Issue: | 2 |
Start Page Number: | 109 |
End Page Number: | 126 |
Publication Date: | Feb 1999 |
Journal: | Computers and Operations Research |
Authors: | Liaw Ching-Fang |
Keywords: | heuristics |
An approximation algorithm of finding a minimum makespan in a nonpreemptive open shop is presented. The algorithm is based on the tabu search technique with a neighborhood structure defined using blocks of operations on a critical path. An efficient procedure is also developed for evaluating a neighborhood. The algorithm is tested on 450 randomly generated problems and a set of 60 benchmarks. Computational results show that the algorithm finds extremely high-quality solutions for all of the test problems in a reasonable amount of computation time, and hence demonstrate the potential of the algorithm to efficiently schedule open shops.