An Optimal Deadlock Recovery Algorithm for Special and Complex Flexible Manufacturing Systems-S₄PR

Abstract

Eliminating deadlocks and reserving maximal permissiveness together is an important and hot issue for all kinds of flexible manufacturing systems. Many experts are making much effort to obtain optimal control algorithms. However, most researchers cannot obtain the real optimal controllers even though their policy is maximally permissive, especially for special S4PR (Systems of Sequential Systems with Shared Resources) systems. Based on this reason, this paper tries to propose a novel recovery policy to recover systems’ all states based on control transitions (CT). Therefore, the system can hold the real maximal permissive states. Especially, we propose the concept of the shortest path selected marking (SPSM) so that we can hence obtain the recovery transition. Furthermore, our proposed concept avoids solving integer linear programming problems (ILPP) based on our algorithm method. Moreover, three examples of S4PR Petri net models (PNM) with deadlocks are illustrated in our proposed algorithm. Experimental data shows that our policy can not only prevent the deadlocks but reserve all initial markings in S4PR. Please notice that this proposed recovery policy seems the first one applied for S4PR by using control transitions and still obtaining the best permissiveness whatever their algorithms among existing literature belong to use control places or control transitions.

Keywords

• Flexible manufacturing systems
• Petri net
• deadlock recovery
• control transition