Solving a real-world problem using an evolving heuristically driven schedule builder.

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.

    Item Type: Article
    Print ISSN: 1063-6560
    Electronic ISSN: 1530-9304
    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
    Item ID: 3177
    Depositing User: Computing Research
    Date Deposited: 01 Sep 2010 16:51
    Last Modified: 09 Mar 2015 16:37

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373