In flexible manufacturing systems, deadlocks usually occur due to the limited resources. To cope with deadlock problems, Petri nets are widely used to model these systems. This chapter focuses on deadlock prevention for flexible manufacturing systems that are modeled with S4R nets, a subclass of generalized Petri nets. The analysis of S4R leads us to derive an iterative deadlock prevention approach. At each iteration step, a non-max-controlled siphon is derived by solving a mixed integer linear programming. A monitor is constructed for the siphon such that it is max-controlled. Finally, a liveness-enforcing Petri net supervisor can be derived without enumerating all the strict minimal siphons.
TopBackground
Due to fierce market competition, flexible manufacturing systems (FMS) have been widely accepted by manufacturers so that they may be able to quick respond to market changes. In an FMS, resources, such as machine tools, automated guided vehicles, robots, buffers, and fixtures, are always shared by a number of jobs such that they may be made the best of. While different jobs are executed concurrently, they have to compete for the limited resources. If each of a set of two or more jobs keeps waiting indefinitely for the other jobs in the set to release resources, the jobs might never be finished. This situation, called deadlock, is highly undesirable in an FMS (Zhou Venkatesh, 1998). Deadlock and related blocking phenomena often cause unnecessary costs, such as long downtime and low use of some critical and expensive resources, and may lead to catastrophic results in some highly automated manufacturing systems (Fanti & Zhou, 2004), such as semiconductor production systems. Therefore, it is necessary to develop an effective FMS control policy to make sure that deadlocks will never occur in such systems. The problem of deadlock in an FMS has attracted many researchers' attention (Abdallah & ElMaraghy, 1998)(Ferrarini & Maroni, 1998) (Giua & Seatzu, 2002)(Hsieh & Chang, 1994)(Huang, Jeng, Xie & Chung, 2001)(Jeng, Xie & Chung, 2004)(Lawley, Reveliotis & Ferreira, 1998)(Li & Shou, 2004)(Li, Zhou & Wu, 2008)(Park & Reveliotis, 2001)(Reveliotis, 2003)(Roszkowska, 2004)(Uzam, 2002).
Petri nets have been widely used to model a variety of resource allocation systems including FMS. They are well suited to depict the behavior of an FMS, such as concurrency, conflict and causal dependency. A powerful feature of Petri nets is their ability to represent good behavior properties of the system such as liveness and boundedness (Abdallah & ElMaraghy, 1998)(Chu & Xie, 1997). Using Petri nets, there are mainly three approaches to deal with the problem of deadlocks in FMS: deadlock detection and recovery (Leung & Sheen, 1993), deadlock avoidance (Fanti, Maione, Mascolo & Turchiano, 1997)(Ferrarini & Maroni, 1998) (Hsieh & Chang, 1994)(Lawley, Reveliotis & Ferreira, 1998)(Park & Reveliotis, 2001)(Roszkowska, 2004)(Wu & Zhou, 2001)(Yim, Kim & Woo, 1997), and deadlock prevention (Abdallah & ElMaraghy, 1998)(Ezpeleta, Colom, & Martinez, 1995)(Giua & Seatzu, 2002)(Huang, Jeng, Xie & Chung, 2001)(Li & Shou, 2004)(Li, Uzam & Zhou, 2004)(Li & Zhou, 2006)(Li, Zhang & Zhao, 2007)(Li, Zhou & Wu, 2008)(Li & Zhao, 2008)(Uzam, 2002)(Uzam, 2004)(Zhou & DiCesare, 1992). In this chapter we focus on deadlock prevention.
Deadlock prevention is usually achieved by using an off-line computational mechanism to control the requests for resources to ensure that deadlocks never occur. Hence a deadlock prevention approach is to impose constraints on a system such that it can never reach deadlock states. For the Petri net model of a system, monitors and related arcs are added to the original net to realize such a mechanism (Abdallah & ElMaraghy, 1998)(Ezpeleta, Colom, & Martinez, 1995)(Li & Shou, 2004)(Li, Zhou & Wu, 2008). This implies that both a plant model and its supervisor are in a Petri net formalism.