A comparison of local search methods for flow shop scheduling |
| |
Authors: | Celia A Glass Chris N Potts |
| |
Institution: | (1) Faculty of Mathematical Studies, University of Southampton, SO17 1BJ Southampton, U.K. |
| |
Abstract: | Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing. |
| |
Keywords: | Heuristics: local search descent genetic algorithms simulated annealing tabu search threshold accepting Scheduling: permutation flow shop |
本文献已被 SpringerLink 等数据库收录! |
|