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

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

Autores

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

Revista

Título: Journal of Manufacturing Systems

Vol. 24

Páginas: 35-46

ISSN: 0278-6125

Editora: Elsevier

Indexação

ISI Web of Knowledge - 7 Citações

ISI Web of Science

Scopus - 5 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-636

DOI: 10.1016/s0278-6125(05)80005-6

Abstract (EN): This paper presents several beam search algorithms for the single-machine earliness/tardiness scheduling problem with release dates and no unforced idle time. 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 procedures. 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 beam search procedure with a total cost function provides very good results but is computationally expensive. The recovering algorithm is quite close in solution quality and is significantly faster, so it can be used to solve even large instances.

Idioma: Inglês

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

Nº de páginas: 12