Article ID: | iaor1999150 |
Country: | Netherlands |
Volume: | 90 |
Issue: | 2 |
Start Page Number: | 200 |
End Page Number: | 213 |
Publication Date: | Apr 1996 |
Journal: | European Journal of Operational Research |
Authors: | Potts C.N., Crauwels H.A.J., Wassenhove L.N. Van |
Keywords: | markov processes |
Local search heuristics are developed for a problem of scheduling jobs on a single machine. Jobs are partitioned into families, and a set-up time is necessary when there is a switch in processing jobs from one family to jobs of another family. The objective is to minimize the number of late jobs. Four alternative local search methods are proposed: multi-start descent, simulated annealing, tabu search and a genetic algorithm. The performance of these heuristics is evaluated on a large set of test problems. The best results are obtained with the genetic algorithm; multi-start descent also performs quite well.