Beam search heuristics for quadratic earliness and tardiness scheduling

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

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

Abstract: In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small to medium size instances. For larger instances, however, this procedure requires excessive computation times, and the recovering beam search algorithm then becomes the heuristic of choice.

Keywords: scheduling; heuristics; beam search; single machine; quadratic earliness; quadratic tardiness (search for similar items in EconPapers)
Pages: 31 pages
Date: 2008-06
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/08.06.12_wp279.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/08.06.12_wp279.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/08.06.12_wp279.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:279

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 ().