Beam search heuristics for quadratic earliness and tardiness scheduling

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

Autores

Valente, JMS (Autor) FEP

Revista

Título: Journal of the Operational Research Society

Vol. 61 Nº 4

Páginas: 620-631

ISSN: 0160-5682

Editora: Taylor & Francis

Indexação

ISI Web of Knowledge - 14 Citações

ISI Web of Science

Scopus - 16 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Biotecnologia industrial

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

Outras Informações

ID Authenticus: P-003-80E

DOI: 10.1057/jors.2008.191

Abstract (EN): 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 (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small-to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice. Journal of the Operational Research Society (2010) 61, 620-631. doi: 10.1057/jors.2008.191 Published online 18 March 2009

Idioma: Inglês

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

Nº de páginas: 12