Using data mining to find patterns in genetic algorithm solutions to a job shop schedule

This paper presents a novel use of data mining algorithms for the extraction of knowledge from a large set of job shop schedules. The purposes of this work is to apply data mining methodologies to explore the patterns in data generated by a genetic algorithm performing a scheduling operation and to develop a rule set scheduler which approximates the genetic algorithm's scheduler. Genetic algorithms are stochastic search algorithms based on the mechanics of genetics and natural selection. Because of genetic inheritance, the characteristics of the survivors after several generations should be similar. In using a genetic algorithm for job shop scheduling, the solution is an operational sequence for resource allocation. Among these optimal or near optimal solutions, similar relationships may exist between the characteristics of operations and sequential order. An attribute-oriented induction methodology was used to explore the relationship between an operations' sequence and its attributes and a set of rules has been developed. These rules can duplicate the genetic algorithm's performance on an identical problem and provide solutions that are generally superior to a simple dispatching rule for similar problems. (C) 2000 Elsevier Science Ltd. All rights reserved.