Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time

• Tipo: Artigo em Revista Científica Internacional
• Data: 2005

Autores

Valente, JMS (Autor) FEP; Alves, RAFS (Autor) FEP

Revista

Título: Computers and Industrial Engineering

Vol. 48

Páginas: 363-375

ISSN: 0360-8352

Editora: Elsevier

Indexação

ISI Web of Knowledge - 43 Citações

ISI Web of Science

Scopus - 50 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia civil

CORDIS: Ciências Sociais > Economia > Estudos de gestão

Outras Informações

ID Authenticus: P-000-4D1

DOI: 10.1016/j.cie.2005.01.020

Abstract (EN): In this paper, we present filtered and recovering beam search algorithms for the single machine earliness/tardiness scheduling problem with no idle time, and compare them with existing neighbourhood search and dispatch rule heuristics. Filtering procedures using both priority evaluation functions and problem-specific properties have been considered. The computational results show that the recovering beam search algorithms outperform their filtered counterparts, while the priority-based filtering procedure proves superior to the rules-based alternative. The best solutions are given by the neighbourhood search algorithm, but this procedure is computationally intensive and can only be applied to small or medium size instances. The recovering beam search heuristic provides results that are close in solution quality and is significantly faster, so it can be used to solve even large problems.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13