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

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]