A Genetic Algorithm for Flow-Shop Scheduling Problems with Multiprocessor Tasks

In this talk, we propose a hybrid Genetic Algorithm for scheduling multiprocessor tasks in multi-stage ow-shop environments. The treatment for the multi-stage shops is more com-plex compared to the single-stage shops due to the dependency of the succeeding stage on the preceding stage. Hence, we propose a new Genetic Algorithm search scheme at the first stage where a population of solution schedules is randomly generated. The evaluation of fitness of each string is based on the maximum completion time. The population is reproduced through specially designed crossover and mutation operations. Since a fully random search may not be cost effective, especially in the later stages where large deviation from their first avail-able schedules may lead to long waiting time, we propose some strategic (insertion) moves. These strategic moves bring significant improvement in terms of efficiency and help avoiding being trapped repeatedly in some local minima. We further introduce an elite group into our Genetic Algorithm for better dynamic control over the relative rate between crossover and mutation operations. Partial Reshuffling Procedure is also implemented for allowing the good mature chromosomes to crossover with some newly generated ones so that both effi-ciency and accuracy can be further enhanced considerably. This procedure takes advantage of the fact that some strings, through the reproduction process, might have acquired some good attributes previously, and these strings having good potential are allowed to crossover with some new strings for further improvement in fitness. Clearly, there is a considerable time saving when comparing with the usual reshuffling procedure. We performed extensive computational experiments to test the average performance of the algorithm with different crossover and mutation operators as well as under different strategic moves for scheduling the jobs. The results show that, overall, the Genetic Algorithm we proposed is effective and efficient in solving the multi-stage ow-shop problems with multiprocessor tasks.

B.Hammer