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

Jorge M.S. Valente and Jeffrey E. Schaller

European Journal of Industrial Engineering, 2010, vol. 4, issue 1, 99-129

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

Keywords: heuristics; single machine scheduling; linear earliness; quadratic tardiness; dispatching rules; genetic algorithms; idle time; backward scheduling; industrial engineering. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=29572 (text/html)
Access to full text is restricted to subscribers.

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:ids:eujine:v:4:y:2010:i:1:p:99-129

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().