Article ID: | iaor19991209 |
Country: | United States |
Volume: | 10 |
Issue: | 3 |
Start Page Number: | 341 |
End Page Number: | 350 |
Publication Date: | Jun 1998 |
Journal: | INFORMS Journal On Computing |
Authors: | Potts C.N., Wassenhove L.N. Van, Crauwels H.W. |
This paper presents several local search heuristics for the problem of scheduling a single machine to minimize total weighted tardiness. We introduce a new binary encoding scheme to represent solutions, together with a heuristic to decode the binary representations into actual sequences. This binary encoding scheme is compared to the usual ‘natural’ permutation representation for descent, simulated annealing, threshold accepting, tabu search and genetic algorithms on a large set of test problems. Computational results indicate that all of the heuristics which employ our binary encoding are very robust in that they consistently produce good quality solutions, especially when multistart implementations are used instead of a single long run. The binary encoding is also used in a new genetic algorithm which performs very well and requires comparatively little computation time. A comparison of neighborhood search methods which use the permutation and binary representations shows that the permutation-based methods have a higher likelihood of generating an optimal solution, but are less robust in that some poor solutions are obtained. Of the neighborhood search methods, tabu search clearly dominates the others. Multistart descent performs remarkably well relative to simulated annealing and threshold accepting.