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

Jorge M. S. Valente () and José Fernando Gonçalves ()
Additional contact information
Jorge M. S. Valente: LIAAD, Faculdade de Economia, Universidade do Porto, Portugal
José Fernando Gonçalves: LIAAD, Faculdade de Economia, Universidade do Porto, Portugal

FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto

Abstract: 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 the best existing heuristic, 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 best existing heuristic, and the improvement in performance increases with both the size and difficulty of the instances. These procedures are also quite close to the optimum, and provided an optimal solution for most of the test instances.

Keywords: scheduling; single machine; linear earliness; quadratic tardiness; genetic algorithms (search for similar items in EconPapers)
Pages: 28 pages
Date: 2008-01
New Economics Papers: this item is included in nep-cmp and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/08.01.29_wp264.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.fep.up.pt/investigacao/workingpapers/08.01.29_wp264.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/08.01.29_wp264.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:por:fepwps:264

Access Statistics for this paper

More papers in FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto Contact information at EDIRC.
Bibliographic data for series maintained by ().