Abstract: To recover from deadlocks which occur in bufferconstrained tools in the united automatic material handling system of 300mm semiconductor wafer fabrications， a twostage algorithm based on the graph theory was proposed. The mentioned deadlock problems were formulated， and then sufficient conditions of the deadlock happening and recovery were determined. A mathematical programming model was set up with the objective function of minimizing the deadlock recovery time of critical tools， and a heuristic algorithm for deadlock recovery was put forward. A stocker’s buffer was used to stock wafer lots to release deadlocked resources， and several parallel routes according to the graph theory were constructed to recover from deadlock. Simulation results indicated the effectiveness of the proposed method. It can reduce average deadlock recovery time and improve the utilization of critical tools， compared with other methods.

Key words: deadlock, automatic material handling system (AMHS), unified layout, graph theory, bufferconstraint