Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time

Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time

0.00 Avg rating0 Votes
Article ID: iaor19972314
Country: Netherlands
Volume: 70
Issue: 1
Start Page Number: 261
End Page Number: 279
Publication Date: Apr 1997
Journal: Annals of Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

Local search heuristics are developed for a problem of scheduling a single machine to minimize the total weighted completion time. The 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. Four alternative neighbourhood search methods are develped: multi-start descent, simulated annealing, threshold accepting and tabu search. The performance of these heuristics is evaluated on a large set of test problems, and the results are also compared with those obtained by a genetic algorithm. The best results are obtained with the tabu search method for smaller numbers of families and with the genetic algorithm for larger numbers of families. In combination, these methods generate high quality schedules at relatively modest computational expense.

Reviews

Required fields are marked *. Your email address will not be published.