Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties

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

Autores

Jorge M S Valente (Autor) FEP

Revista

Título: Computers and Industrial Engineering

Vol. 52 Nº 4

Páginas: 434-447

ISSN: 0360-8352

Editora: Elsevier

Indexação

ISI Web of Knowledge - 7 Citações

ISI Web of Science

Scopus - 9 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-004-A7Q

DOI: 10.1016/j.cie.2007.02.001

Abstract (EN): In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed. The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.

Idioma: Inglês

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

Nº de páginas: 14