Heuristics for the single machine scheduling problem with early and quadratic tardy penalties

Jorge M.S. Valente

European Journal of Industrial Engineering, 2007, vol. 1, issue 4, 431-448

Abstract: This paper considers the single machine scheduling problem with linear earliness and quadratic tardiness costs, 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 these rules. Linear early/quadratic tardy dispatching rules are also considered, as well as a greedy-type procedure. Extensive experiments are performed to determine appropriate values for the parameters required by some of the heuristics. The computational tests show that the best results are given by the linear early/quadratic tardy dispatching rule. This procedure is also quite efficient, and can quickly solve even very large instances. [Received 15 December 2006; Revised 20 July 2007; Accepted 24 July 2007]

Keywords: heuristics; single machine scheduling; linear early penalties; quadratic tardy penalties; no machine idle time; dispatching rules. (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.inderscience.com/link.php?id=15391 (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:1:y:2007:i:4:p:431-448

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 ().