Performance Evaluation of Solution-Based GA and Rule-Based GA for Scheduling Problems

In this paper, we compare the performance of a solution-based schedule generation method and a rule-based schedule generation method, both of which are genetic-algorithm-based search algorithms. In the rule-based algorithm, a job permutation is determined by dispatching rules for scheduling problems. Therefore we call this algorithm a rule-based GA in this paper. We employ common dispatching rules such as SPT (Shortest Processing Time), EDD (Earliest Due Date), MST (Minimum Slack Time). We also employ a random rule, which select a job randomly from the remaining jobs. We employ a genetic algorithm to combine these dispatching rules to generate a schedule. On the other hand, a job permutation is directly treated as an individual in the solution-based schedule generation method using genetic algorithms. We apply the both genetic algorithms to flowshop scheduling problems with multiple machines in order to optimize an objective function. We employ one of three objectives in each experiment