A Critical-Siphon Approach to Fastest Deadlock Controller for S3PR

A Critical-Siphon Approach to Fastest Deadlock Controller for S3PR

Daniel Yuh Chao (National Cheng Chi University, China)
Copyright: © 2013 |Pages: 27
DOI: 10.4018/978-1-4666-4034-4.ch011
OnDemand PDF Download:


The authors developed a theory to show that exactly one monitor is required for the set of siphons in the family of 2-compound siphons and how to assign its initial markings. This avoids redundant monitors and the unnecessary associated computational burden. Neither reachability graph nor minimal siphon needs to be computed to achieve polynomial complexity—essential for large systems. This chapter redevelops the theory more formally and further applies this approach to two well-known S3PR to obtain a controller full or near maximally permissive, where Weighted Control (WC) arcs are nevertheless necessary to keep the controlled model maximally permissive. However, optimal control for siphons involving WC arcs are still under research. As many as possible for simpler structures are desired to reduce WC arcs. In addition, fast computation is important for dynamic reconfiguration situations. The authors develop a single theorem to identify the condition where WC places cannot be replaced by Ordinary Control (OC) arcs, while others can be replaced.
Chapter Preview

1. Introduction

Flexible Manufacturing System (FMS) can adapt to swift changes of production requirements to provide various market segments with suitable customized products. Concurrent automated processes share some costly resources such as robots, machines, and logistic systems to work on some raw parts to manufacture mixed type products. It is well-known in operating systems that highly sharing of limited resources can lead to complete system shut down due to deadlocks.

Deadlock-freeness is essential for the automation of a Flexible Manufacturing System (FMS). Various deadlock resolution approaches (Cho et al. 1995; Hu et al. 2008; Iordache et al. 2001; Wysk et al. 1994; Visvanadham et al. 1990; Huang et al. 2006; Zhao et al. 2009) have been proposed to tackle deadlocks. Deadlock prevention has been popular to avoid deadlocks in FMS since it runs fast and statically to avoid run-time detection and computation.

In obtaining PN based monitors for deadlock prevention (or liveness enforcing) there are three main issues tackled within the literature: behavioral permissiveness, computational complexity, and structural complexity. Behavioral complexity is related to the performance in terms of the reachable good states. In the context of FMS the number of good states in a Petri net model of an FMS, which can be provided under the deadlock prevention or liveness-enforcing policies, has been regarded as a “quality measure.” In terms of the practical implementation of these policies, this quality measure implies high efficiency, throughput, and flexibility (Uzam et al., 2007). The highest quality can be provided by the maximally permissive (optimal) control policies. Computational complexity is related to the computational cost paid in order to obtain a liveness-enforcing supervisor (LES) for a given deadlock prevention FMS problem. In this case it is desirable to obtain an answer for a given problem in the least time possible. Structural complexity means extra cost in system verification, validation, and implementation. It is related with two aspects of a LES: the number of monitors and the type of monitors. In the former, it is desirable to obtain the least number of monitors possible. In the latter, there are two types of monitors: ordinary and general. Ordinary monitors are the ones with no weighted arcs. General monitors are the ones with weighted arcs. It is obvious that ordinary monitors are preferable to general monitors due to verification, validation, and implementation issues.

Classical approaches either suffer from adding too many monitors (Ezpeleta et al., 1995) (problematic siphons growing quickly with the size of the system) or reaching too few states (Li et al., 2004, 2007). Recently, maximally permissive control policies (Chen et al. 2011, Huang et al. 2009, Li et al. 2008, Piroddi et al. 2008, 2009, Uzam et al. 2006) with little redundancy have emerged. They however suffer from either complete state enumeration—based on region theory (Uzam et al. 2006; Huang et al. 2009; Li et al. 2008) or the time consuming computation of a large number of inequalities associated with the concept of selective-siphons (Piroddi et al., 2008, 2009). Both are NP-hard and take exponential amount of time.

Complete Chapter List

Search this Book: