A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties

In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs. and no machine idle time. We propose a genetic approach based on a random key alphabet. Several genetic algorithms based on this approach are presented. These versions differ on the generation of the initial population, as well as on the use of local search. The proposed procedures are compared with existing heuristics, as well as with optimal solutions for the smaller instance sizes. The computational results show that the performance of the proposed genetic approach is improved by the addition of a local search procedure, as well as by the insertion of simple heuristic solutions in the initial population. Indeed, the genetic versions that include either or both of these features not only provide significantly better results, but are also much faster. The genetic versions that use local search are clearly superior to the existing heuristics, and the improvement in performance over the best existing procedure increases with both the size and difficulty of the instances. These genetic procedures are also quite close to the optimum, and provided an optimal solution for most of the test instances. (C) 2008 Elsevier Ltd. All rights reserved.