Abstract: The JSSP (job shop scheduling problem) includes two coupling sub-problems, namely
“equipment allocation” and “process sequencing”. The current researches mainly focus on the
small-scale problems involving serial processing. The properties of the feasible domain will become
very complicated if there are complex correlative constraints such as parallel or even nested
relationships among processes. When the scale of problem is large, it is even difficult to obtain a
feasible solution. To solve the above difficult problems, on the basis of giving full play to the
advantages of genetic algorithm in solving “allocation problem” and ant colony optimization
algorithm in solving “sorting problem”, a two-level nested model and its basic ideas are proposed.
Through a series of improvement strategies, such as the integer encoding strategy based on process,
multi-node cross strategy based on machine type, mutation strategy of gene exchange in interval
section based on equipment type, feasible path forming strategy based on reverse traversal, as well as
pheromone spreading and updating strategy based on the shortest processing time, a two-level nested hybrid algorithm that integrates genetic algorithm and ant colony optimization algorithm in the same
loop is constructed. Aiming at medium-scale problems, comparative experiments are carried out by
respectively applying genetic algorithm, ant colony optimization algorithm, two-level nested ant
colony algorithm, and two-level nested hybrid algorithm in combination with genetic algorithm and
ant colony algorithm. The experimental results verify the reliability and superiority of the proposed
algorithm, and provide a new idea and method for solving JSSP with complex association constraints.

Key words: job shop scheduling problem, complex associated constraints, genetic algorithm, ant
colony optimization, hybrid algorithm