Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups

Jorge M. S. Valente ()
Additional contact information
Jorge M. S. Valente: Faculdade de Economia, Universidade do Porto

FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto

Abstract: In this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths. Two new improvement procedures, based on adjacent pairwise interchanges and 3-swaps, are also presented. The computational results show that the beam search versions with a variable width are marginally superior to their fixed value counterparts, even when a lower average number of beam and filter nodes is used. The best results are given by the filtered beam search algorithms. For large problems, however, these procedures require excessive computation times. The priority beam search algorithms are much faster, and can therefore be used for the largest instances. The 3-swap method is the best of the improvement procedures, giving the largest relative improvement and decreasing the total cost for a larger number of instances.

Keywords: scheduling; weighted tardiness; sequence-dependent setups; beam search (search for similar items in EconPapers)
Pages: 28 pages
Date: 2005-08
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/05.08.10_WP186_jorge.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.fep.up.pt/investigacao/workingpapers/05.08.10_WP186_jorge.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/05.08.10_WP186_jorge.pdf)

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:por:fepwps:186

Access Statistics for this paper

More papers in FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto Contact information at EDIRC.
Bibliographic data for series maintained by ().