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

Authors: Jorge M.S. Valente, Jeffrey E. Schaller

Addresses: LIAAD – INESC Porto LA, Faculdade de Economia, Universidade do Porto, Rua Dr. Roberto Frias, 4200–464 Porto, Portugal. ' Department of Business Administration, Eastern Connecticut State University, 83 Windham St., Willimantic, CT 06226-2295, USA

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.

DOI: 10.1504/EJIE.2010.029572

European Journal of Industrial Engineering, 2010 Vol.4 No.1, pp.99 - 129

Published online: 30 Nov 2009 *

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