A systematic investigation of GA performance on jobshop scheduling problems.

Hart, Emma; Ross, Peter

Abstract

Although there has been a wealth of work reported in the literature on the application of genetic algorithms (GAs) to jobshop scheduling problems, much of it contains some gross over-generalisations, i.e that the observed performance of a GA on a small set of problems can be extrapolated to whole classes of other problems. In this work we present part of an ongoing investigation that aims to explore in depth the performance of one GA across a whole range of classes of jobshop scheduling problems, in order to try and characterise the strengths and weaknesses of the GA approach. To do this, we have designed a configurable problem generator which can generate problems of tunable difficulty, with a number of different features. We conclude that the GA tested is relatively robust over wide range of problems, in that it finds a reasonable solution to most of the problems most of the time, and is capable of finding the optimum solutions when run 3 or 4 times. This is promising for many real world scheduling applications, in which a reasonable solution that can be quickly produced is all that is required. The investigation also throws up some interesting trends in problem di_culty, worthy of further investigation

Citation

Hart, E., & Ross, P. (2000, April). A systematic investigation of GA performance on jobshop scheduling problems. Presented at EvoWorkshops 2000: EvoIASP, EvoSCONDI, EvoTel, EvoSTIM, EvoRob, and EvoFlight, Edinburgh

• Presentation Conference Type: Conference Paper (published)
• Conference Name: EvoWorkshops 2000: EvoIASP, EvoSCONDI, EvoTel, EvoSTIM, EvoRob, and EvoFlight
• Start Date: Apr 17, 2000
• End Date: Apr 17, 2000
• Publication Date: Feb 11, 2003
• Deposit Date: Sep 6, 2010
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 1803
• Pages: 280-289
• Book Title: Real-World Applications of Evolutionary Computing
• ISBN: 978-3-540-67353-8
• DOI: https://doi.org/10.1007/3-540-45561-2_27
• Keywords: genetic algorithms; jobshop scheduling; performance; problem generator; robust; real-world scheduling
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3172
• Publisher URL: http://dx.doi.org/10.1007/3-540-45561-2_27