A Computationally Improved Control Policy for FMS Using Crucial Marking/Transition-Separation Instances

Introduction

While sharing a finite number of resources in a Flexible Manufacturing System (FMS), e.g., robots and machines, each part has a particular operation flow that determines the order in which resources are needed. However, the complex operations are executed concurrently and compete for shared resources explaining why they may lead to a system deadlock. A deadlock occurs in an FMS when parts are blocked waiting for shared resources held by others that will never be granted. A system deadlock or related blocking phenomena often incur unnecessary overhead cost, e.g., a long downtime and low utilization rate of some critical and expensive resources, possibly leading to a catastrophic outcome in some highly complex FMS. Therefore, an efficient FMS control policy must be developed to ensure that system deadlocks do not occur. Having received considerable attention in literature, deadlock is normally prevented by using an offline computational mechanism to control the resource requests in order to avert deadlocks. Fanti and Zhou (2004) introduce three fundamental methods (i.e. prevention, detection and avoidance) to solve the deadlock problems. Deadlock prevention aims to impose system constraints to prevent a deadlock. Importantly, deadlock prevention algorithms do not require run-time costs since problems are solved in the system design and planning stages. This study belongs to the deadlock prevention field.

Petri nets (PN) Murata (1989) have been recognized as one of the most powerful formal methods for modeling FMS. The reason is that they are well suited to represent such FMS characteristics as precedence relations, concurrence, conflict and synchronization. Their analysis methods used for deadlock prevention in FMS include structural analysis and reachability graphs. Deadlock prevention avoidance schemes have been developed for controlling FMS Ezpeleta et al (1995), Jeng (1997), Huang et al (2001), Huang et al (2006), Huang (2007a), Huang (2007b), Li et al (2007), and Park and Revelioyis (2000) by using the former. In particular, deadlock prevention problems Ezpeleta et al (1995), Jeng (1997), Huang et al (2001), Huang et al (2006), Huang (2007a), and Huang (2007b) are solved using the concept of siphons. The siphon control algorithm requires only a few control places to rapidly revive the system. Additionally, Li and Zhou (2004), Li and Zhou (2008), and Li et al (2009) propose an elementary siphon control policy (ESCP) to reduce the redundant siphons to obtain economical deadlock prevention methods. However, those siphon control algorithms cannot obtain maximally permissive or optimal controlled systems. Reachability graph methods are used to obtain the live system behavior Cho et al. (2000), Uzam and Jones (2002), Ghaffari et al (2003a), Uzam (2002), Ghaffari et al.(2003b), Uzam (2004a), Uzam (2004b), and Uzam (2004c). Without confining to a certain class of FMS, they can provide an optimal (i.e. maximally permissive) deadlock prevention controller by adopting the theory of regions Badouel et al. (1995), Badouel and Darondeau (1998). The theory is originally developed for a transition system (TS). A state-based representation with arcs labeled with symbols from an alphabet of events in a TS can be mapped into a PN model Cortadella et al (1998). For an ETS (elementary TS) there exists a PN with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original TS. Moreover, the problem of synthesizing the nets equivalent to a given finite automaton is addressed by Ehrenfeucht and G. Rozenberg (1990). They show how to decide the feasibility of this problem for elementary nets by using the crucial concept of regions. In summary, the theory of regions is a synthesis method to derive PNs from automaton-based models. It uses the concept of regions to solve the event-state-separation-problems (ESSPs) Badouel and Darondeau (1996).