Classification of part movements for deadlock avoidance in manufacturing systems

A method that classifies part movements to avoid deadlock in manufacturing systems which contain single capacity resources is presented. The proposed method determines whether a particular part movement is safe, unsafe, or undetermined. This classification is linear in complexity. Part movements that are classified as undetermined are analyzed using another procedure. This alternative procedure attempts to empty the system to determine whether the move is safe, unsafe, or undetermined. It is polynomial in complexity. By adjusting a simple parameter, the size of the set of possible undetermined classifications returned can be made arbitrarily small by increasing the order of the algorithm. Examples showing the application of the method are provided