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

Author(s)

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

• Document type: Journal article
• Source: European Journal of Operational Research; v. 160, n. 1, p. 190-201, Jan. 2005.
• Field of knowledge: Engineering - Production Engineering

Abstract

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)

• FAPESP's process: 01/02972-2 - Theory and practice of cutting and packing problems
• Grantee: Marcos Nereu Arenales
• Support Opportunities: Research Projects - Thematic Grants