A Genetic Algorithm for the Single Machine Maximum Lateness Problem
AbstractWe consider the problem of scheduling a number of jobs, each job having a release time, a processing time and a due date, on a single machine with the objective of minimizing the maximum lateness or tardiness. This problem often occurs as a sub-problem in solving other scheduling environments such as flow shops or job shops. We developed a genetic algorithm and compared its performance with alternative methods on diverse data sets. Based on a literature study on genetic algorithms in single machine scheduling, a fair comparison of genetic operators was made. We performed an extensive study of local search algorithms, based on the trade-off between the intensification and diversification strategy. Computational results further revealed that combining different neighborhoods in an intelligent manner can remarkably improve the solution quality.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Ghent University, Faculty of Economics and Business Administration in its series Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium with number 09/613.
Length: 2 pages
Date of creation: Sep 2009
Date of revision:
This paper has been announced in the following NEP Reports:
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Nathalie Verhaeghe).
If references are entirely missing, you can add them using this form.