Resource title

Local search heuristics for the single machine total weighted tardiness scheduling problem

Resource image

image for OpenScout resource :: Local search heuristics for the single machine total weighted tardiness scheduling problem

Resource description

This paper presents several local search heuristics for the problems of scheduling a single machine to minimize total weighted tardiness. The authors introduce a new binary encoding scheme to represent solutions, together with a heurisitc 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 solution, especially when multi-start 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 neighbourhood 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 neighbourhood search methods, tabu search clearly dominates the others. Multi-start descent performs remarkably well relative to simulated annealing and threshold accepting.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://flora.insead.edu/fichiersti_wp/inseadwp1996/96-46.pdf

Resource license

Copyright INSEAD. All rights reserved