Scalable deadlock avoidance algorithms for flexible manufacturing systems
Existing deadlock prevention and avoidance methods for flexible manufacturing systems have either restricted the class of systems they apply to, or are conservative so that the approach has polynomial complexity. The problem with these restrictions is that the system is not allowed to enter many safe states that contribute to high resource utilization. This work has developed two deadlock avoidance algorithms for flexible manufacturing systems that allow both single capacity and multiple capacity resources. The model further allows choices in part routing; that is, there can be several resources to choose from to visit next at any step of a process plan. Process plans need not be sequential and fixed, but must be finite. Two types of choices have been considered: free choice, where the system controller can pick one of several possibilities; and conditional choice, where factors external to the system influence the choice. An example of conditional choice is routing based on the results of an inspection. The first algorithm developed allows free choices only. The second allows both types of choices. The main strategy of both algorithms is to analyze a potential part movement to determine whether such a move is safe, unsafe, or undetermined. This classification is linear in complexity. A part movement that is classified as undetermined is further analyzed using another procedure, which attempts to empty the system (virtually) to decide whether or not the original move is safe. In this case, the complexity involved in determining the final classification of the proposed part move increases to the cube of the system size L, that is,O( L ^3). The methods are proved to be correct, that is, they will not allow a live system to enter a deadlock state. The first method is compared to other popular deadlock detection and avoidance algorithms in the literature. The proposed method is less conservative than the existing algorithms. In addition, the system does not require any preprocessing; so that the mix of parts, as well as the system itself, can be changed on the fly. Examples showing the application of the method are provided.
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:scalable algorithms deadlock avoidance flexible manufacturing systems
Date of Publication:01/01/2000