Abstract:

A hybrid algorithm framework is proposed for job shop scheduling, with which heuristic rules are integrated with genetic algorithm by means of simulation. With the framework, the searching efficiency of genetic algorithm can be effectively improved due to the guidance of the heuristic rules properly designed for the specific problems. The hybrid algorithm is implemented by optimizing the first operation of each machine with GA, and arranging the succedent operations through a simulation process in which heuristic rules are employed to determine the processing priority of jobs. Based on the framework, an algorithm, GA\|SPTS, is developed for job shop scheduling problems with sequence dependent setup times, which shows high performance compared with the existing algorithms.

Key words: scheduling, genetic algorithm, heuristic, simulation, combinatorial optimization