Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem
- 1 August 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 10 (3), 341-350
- https://doi.org/10.1287/ijoc.10.3.341
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- A genetic algorithm for the job shop problemComputers & Operations Research, 1995
- Single Machine Tardiness Sequencing HeuristicsIIE Transactions, 1991
- Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealingJournal of Computational Physics, 1990
- Tabu Search: A TutorialInforms Journal on Applied Analytics, 1990
- Simulated annealing: A tool for operational researchEuropean Journal of Operational Research, 1990
- A survey of algorithms for the single machine total weighted tardiness scheduling problemDiscrete Applied Mathematics, 1990
- Tabu Search—Part IINFORMS Journal on Computing, 1989
- A Branch and Bound Algorithm for the Total Weighted Tardiness ProblemOperations Research, 1985
- Complexity of Machine Scheduling ProblemsPublished by Elsevier BV ,1977
- A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total TardinessPublished by Elsevier BV ,1977