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

Authors: Jorge M.S. Valente

Addresses: LIAAD, Faculdade de Economia Universidade do Porto, Rua Dr. Roberto Frias, Porto 4200-464, Portugal

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.

DOI: 10.1504/EJIE.2007.015391

European Journal of Industrial Engineering, 2007 Vol.1 No.4, pp.431 - 448

Published online: 14 Oct 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article