Normal view MARC view

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

Author: Potts, C. N. ; Crauwels, H. A. J ; Van Wassenhove, Luk N.INSEAD Area: Technology and Operations Management Series: Working Paper ; 96/46/TM Publisher: Fontainebleau : INSEAD, 1996.Language: EnglishDescription: 17 p.Type of document: INSEAD Working Paper Online Access: Click here Abstract: 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.
Tags: No tags from this library for this title. Add tag(s)
Log in to add tags.
Item type Current location Collection Call number Status Date due
INSEAD Working Paper Digital Library
PDF Available

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.

Digitized

There are no comments for this item.

Log in to your account to post a comment.
Koha 3.18 - INSEAD Library Catalogue
Library Home | Contact Us | What's Koha?