Abstract: Take the scheduling problems of the Job Shop with material handling equipment into consideration， we established the non-linear programming model and modified disjunctive graph model. Afterwards， a two-stage structural heuristic algorithm was constructed to minimize the makespan. In the first stage， a hierarchical heuristic algorithm was constructed by dividing the disjunctive graph into sub-graphs of scheduling problems for the machines and handling equipment， respectively. The sub-graphs of scheduling problems for the machines in the upper level were solved based on a branch method， while for the handling equipment in the second level were according to the upper level results. In the second stage， a heuristic algorithm based on the block theory was presented to optimize the scheduling solutions. Finally， simulation experiments were designed and indicated that the proposed algorithm is valid and feasible.

Key words: disjunctive graph, material handling, scheduling, Job Shop, heuristic algorithm