Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time

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

Autores

Jorge M S Valente (Autor) FEP

Revista

Título: Computers and Industrial Engineering

Vol. 55 Nº 3

Páginas: 663-675

ISSN: 0360-8352

Editora: Elsevier

Indexação

ISI Web of Knowledge - 10 Citações

ISI Web of Science

Scopus - 14 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-003-VPR

DOI: 10.1016/j.cie.2008.02.005

Abstract (EN): In this paper, we present beam search heuristics for the single machine early/tardy scheduling problem with job-independent penalties, and no machine idle time. These heuristics include priority and detailed classic beam search algorithms, as well as filtered and recovering procedures. Three dispatching rules are considered as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search heuristics. The computational results show that the performance of the beam search procedures does improve with the quality of the dispatching rule. The detailed and recovering algorithms clearly Outperform the best existing heuristic, and the improvement is particularly higher for the more difficult instances. The detailed beam search algorithm provides the best performance, and is recommended for small to medium size instances. For larger instances, however, this algorithm requires excessive computation times. The recovering beam search procedure is computationally more efficient, and is then the heuristic of choice for medium to large instances.

Idioma: Inglês

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

Nº de páginas: 13