Beam search algorithms for the early/tardy scheduling problem with release dates

Jorge M. S. Valente () and Rui A. F. S. Alves ()
Additional contact information
Jorge M. S. Valente: Faculdade de Economia da Universidade do Porto
Rui A. F. S. Alves: Faculdade de Economia da Universidade do Porto

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

Abstract: In this paper we consider the single machine earliness/tardiness scheduling problem with di?erent release dates and no unforced idle time. We present several heuristic algorithms based on the beam search technique. These algorithms include classical beam search procedures, with both priority and total cost evaluation functions, as well as the filtered and recovering variants. Both priority evaluation functions and problem-specific properties were considered for the filtering step used in the filtered and recovering beam search heuristics. Extensive preliminary tests were performed to determine appropriate values for the parameters used by each algorithm. The computational results show that the recovering beam search algorithms outperform their filtered counterparts in both solution quality and computational requirements, while the priority-based filtering procedure proves superior to the rules-based alternative. The beam search procedure with a total cost evaluation function provides very good results, but is computationally expensive and can therefore only be applied to small or medium size instances. The recovering algorithm is quite close in solution quality and is significantly faster, so it can be used to solve even large instances.

Keywords: scheduling; early/tardy; beam search; heuristics (search for similar items in EconPapers)
Pages: 21 pages
Date: 2004-04
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/04 ... ge%20valente%202.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/04.04.28_wp143_Jorge%20valente%202.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/04.04.28_wp143_Jorge%20valente%202.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:143

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