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

• Type: Article in International Scientific Journal
• Date: 2009

Authors

Jorge M S Valente (Author) FEP; Jose Fernando Goncalves (Author) FEP

Journal

Title: Computers and Operations Research

Vol. 36

Pages: 2707-2715

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 36 Citations

ISI Web of Science

Scopus - 49 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-003-F6R

DOI: 10.1016/j.cor.2008.11.016

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 9