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

Jorge M. S. Valente () and Rui A. F. S. Alves ()
Additional contact information
Jorge M. S. Valente: LIACC/NIAAD, Faculdade de Economia, Universidade do Porto, Portugal
Rui A. F. S. Alves: Faculdade de Economia, Universidade do Porto, Portugal

FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto

Abstract: 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.

Keywords: scheduling; single machine; early/tardy; quadratic penalties; dispatching rules (search for similar items in EconPapers)
Pages: 35 pages
Date: 2007-02
New Economics Papers: this item is included in nep-cmp
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/06.09.22_WP229_silvateixeira.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.fep.up.pt/investigacao/workingpapers/06.09.22_WP229_silvateixeira.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/06.09.22_WP229_silvateixeira.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:por:fepwps:236

Access Statistics for this paper

More papers in FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto Contact information at EDIRC.
Bibliographic data for series maintained by ().