Hart, Emma, Ross, Peter and Nelson, Jeremy (1998) Solving a real-world problem using an evolving heuristically driven schedule builder. Evolutionary Computing, 6 (1). pp. 61-80. ISSN 1063-6560
Available under License Creative Commons Attribution Non-commercial.
Download (1260kB) | Preview
This work addresses the real-life scheduling problem of a Scottish company that must produce daily schedules for the catching and transportation of large numbers of live chickens. The problem is complex and highly constrained. We show that it can be successfully solved by division into two subproblems and solving each using a separate genetic algorithm (GA). We address the problem of whether this produces locally optimal solutions and how to overcome this. We extend the traditional approach of evolving a “permutation + schedule builder” by concentrating on evolving the schedule builder itself. This results in a unique schedule builder being built for each daily scheduling problem, each individually tailored to deal with the particular features of that problem. This results in a robust, fast, and flexible system that can cope with most of the circumstances imaginable at the factory. We also compare the performance of a GA approach to several other evolutionary methods and show that population-based methods are superior to both hill-climbing and simulated annealing in the quality of solutions produced. Population-based methods also have the distinct advantage of producing multiple, equally fit solutions, which is of particular importance when considering the practical aspects of the problem.
|Uncontrolled Keywords:||genetic algorithm; schedule builder; robust; flexible; population-based method; heuristics;|
|University Divisions/Research Centres:||Faculty of Engineering, Computing and Creative Industries > School of Computing|
|Dewey Decimal Subjects:||000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods > 006.3 Artificial intelligence|
|Library of Congress Subjects:||Q Science > QA Mathematics > QA75 Electronic computers. Computer science|
|Depositing User:||Computing Research|
|Date Deposited:||01 Sep 2010 16:51|
|Last Modified:||09 Mar 2015 16:37|
Actions (login required)