Article ID: | iaor19971354 |
Country: | Netherlands |
Volume: | 63 |
Issue: | 1 |
Start Page Number: | 397 |
End Page Number: | 414 |
Publication Date: | May 1996 |
Journal: | Annals of Operations Research |
Authors: | Haddock Jorge, Nagar Amit, Heragu Sundresh S. |
Keywords: | programming: branch and bound, heuristics |
In this paper, the authors study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm’s search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. The authors develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch- and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.