Minimizing earliness and tardiness penalties in a single-machine problem with a common due date

Autor(es)

Hino, Celso M. ; Ronconi, Débora P. ; Mendes, André B.

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 160, n. 1, p. 190-201, Jan. 2005.
• Área do conhecimento: Engenharias - Engenharia de Produção
• Assunto(s): Automação industrial Heurística

Resumo

Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this paper we examine the single-machine scheduling problem with a common due date. Performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we propose a tabu search-based heuristic and a genetic algorithm which exploit specific properties of the optimal solution. Hybrid strategies are also analyzed to improve the performance of these methods. The proposed approaches are examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs. (AU)

• Processo FAPESP: 00/01715-3 - Aplicação de heurísticas e metaheurísticas na resolução de problemas de produção
• Beneficiário: Débora Pretti Ronconi
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 01/02972-2 - Teoria e prática dos problemas de corte e empacotamento
• Beneficiário: Marcos Nereu Arenales
• Modalidade de apoio: Auxílio à Pesquisa - Temático