Improved heuristics for the single machine scheduling problem with linear early and quadratic tardy penalties

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

Autores

Jorge M S Valente (Autor) FEP; Jeffrey E Schaller (Autor) Outra

Revista

Título: European Journal of Industrial Engineering

Vol. 4

Páginas: 99-129

ISSN: 1751-5254

Editora: Inderscience Publishers

Indexação

ISI Web of Knowledge - 20 Citações

ISI Web of Science

Scopus - 21 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-ATD

DOI: 10.1504/ejie.2010.029572

Abstract (EN): This paper considers the single machine scheduling problem with linear earliness and quadratic tardiness costs. The research on the version with an inserted idle time focused on an exact approach, while several heuristics were already proposed for the version with no idle time. These heuristics were then the basis for the development of new heuristic procedures for the version with idle time. Some improvement procedures were also considered. The new heuristics outperformed the existing procedures. A genetic algorithm provides the best results in terms Of Solution quality, but is computationally intensive. One of the backward scheduling dispatching rules provides results of similar quality and can quickly solve even large instances. The new heuristics were also applied, with the appropriate modifications, to the version with no idle time. Again, the new procedures provided better results than the existing heuristics. Therefore, the procedures developed in this paper are the new heuristics of choice for both versions of the considered problem. [Received 09 October 2008; Revised 02 February 2009; Accepted 20 February 2009]

Idioma: Inglês

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

Nº de páginas: 31