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

H.A.J. Crauwels, C.N. Potts and L.N. Van Wassenhove

Annals of Operations Research, 1997, vol. 70, issue 0, 279 pages

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 developed: 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. Copyright Kluwer Academic Publishers 1997

Keywords: Scheduling; single machine; batches; set-up time; local search heuristics; descent; simulated annealing; threshold accepting; tabu search (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018978322417 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:70:y:1997:i:0:p:261-279:10.1023/a:1018978322417

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018978322417

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().