Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

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

Autores

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

Revista

Título: Computers and Operations Research

Vol. 35 Nº 11

Páginas: 3696-3713

ISSN: 0305-0548

Editora: Elsevier

Indexação

ISI Web of Knowledge - 18 Citações

ISI Web of Science

Scopus - 29 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-V2A

DOI: 10.1016/j.cor.2007.04.006

Abstract (EN): In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule. The computational experiments show that the best results are provided by the heuristics that explicitly consider both early and tardy costs, and the quadratic objective function. Therefore, it is indeed important to specifically address the quadratic feature of the cost function, instead of simply using procedures originally developed for a linear objective function. The heuristics are quite fast, and are capable of quickly solving even very large instances. The use of an improvement step is recommended, since it usually improves the solution quality with little additional computational effort.

Idioma: Inglês

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

Nº de páginas: 18