Heuristics for the early/tardy scheduling problem with release dates

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

Autores

Jorge M S Valente (Autor) FEP; Rui A F S Alves (Autor) FEP

Revista

Título: International Journal of Production Economics

Vol. 106

Páginas: 261-274

ISSN: 0925-5273

Editora: Elsevier

Indexação

ISI Web of Knowledge - 16 Citações

Scopus - 20 Citações

Classificação Científica

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

Outras Informações

ID Authenticus: P-004-BG8

DOI: 10.1016/j.ijpe.2006.06.006

Abstract (EN): In this paper, we consider the single machine earliness/tardiness scheduling problem with release dates and no unforced idle time. We analyse the performance of a varied set of heuristics. This set includes simple scheduling rules, early/tardy dispatching heuristics, a greedy procedure and a decision theory heuristic. Two different approaches are considered to calculate a lookahead parameter used in the early/tardy dispatching heuristics, and extensive experiments were performed to determine an appropriate value for this parameter. We also propose an improvement procedure that uses some dominance rules to improve the solution obtained by the heuristics. The computational results show that the use of the improvement step is recommended, since it reduces the objective function value with little additional computational effort. The best results were given by the decision theory heuristic, but this procedure is computationally expensive and therefore limited to small and medium size instances. For large instances, one of the early/tardy dispatching heuristics is then the heuristic of choice.

Idioma: Inglês

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

Nº de páginas: 14