A tabu search algorithm for the open shop scheduling problem

A tabu search algorithm for the open shop scheduling problem

0.00 Avg rating0 Votes
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:
Keywords: heuristics
Abstract:

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.

Reviews

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