In recent years, a great deal of research has been focused on preventing deadlock in Flexible Manufacturing Systems. Policies based largely on Petri net models have been presented in the literature. Recently, a quite different approach has been developed based on supervisory control theory, and it has been adapted to solve the nonblocking maximally permissive control problem in various resource allocation systems, such as an Automatic Guided Vehicle system and a Production Cell. In this chapter, the authors obtain the corresponding control policy for a Flexible Manufacturing System, and from it derive an equivalent distributed control using the recent theory of supervisor localization.
Top1. Introduction
Manufacturing has undergone a fundamental shift from mass production markets to the diverse, quality oriented markets of today. With this shift, small batch manufacturing has become increasingly important, and manufacturing flexibility has emerged as a key competitive organization feature. Technology-based attempts to achieve manufacturing flexibility include the Flexible Manufacturing System (FMS), a set of manufacturing machines serviced by an automated material handling system, all under computer control. An FMS is intended to combine the efficiency of highly automated mass production with job shop flexibility (Li, Zhou & Wu, 2008; Lawley, Reveliotis & Ferreira, 1997).
In an FMS, different types of raw parts enter the system at ‘random’ times and are processed concurrently, sharing a limited number of resources such as machines, robots, buffers. A raw part follows a pre-established production sequence through a set of system resources. These sequences are executed concurrently, and therefore have to compete for resources. Such competition can cause deadlocks, resulting in production delays that are highly undesirable (Banaszak & Krogh, 1990; Fanti & Zhou, 2004; Viswanadham, Narahari & Johnson, 1990; Zhou & Venkatesh, 1998). Additionally, since the sizes of buffers are limited, we must ensure that buffers will not be subject to overflow or underflow.
Deadlocks in resource allocation systems are extensively investigated in the literature (Coffman, Elphick & Shoshani, 1971; Gold, 1978; Singhal, 1989). Petri nets (Murata, 1989) are a widely used mathematical tool for handling deadlock problems in the FMS (Commoner, 1972; D’souza & Khator, 1994; Fanti, Maione & Turchiano, 2000; Silva & Teruel, 1997; Zhou & DiCesare, 1993; Zhou & Venkatesh, 1998). The methods derived from a Petri net formalism for dealing with deadlocks either preclude the possibility of deadlock occurrence by preventing some necessary condition or detect and resolve a deadlock when it occurs. Generally, these methods are classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention (Li, et al. 2008). (1) The deadlock detection and recovery approach permits the occurrence of deadlocks; when a deadlock occurs, it is detected, and then, the system is put back to a deadlock-free state, by simply reallocating the sources. (2) In deadlock avoidance, at each system state, an online control policy is used to make a correct decision to proceed among the feasible evolution; the main purpose of this approach is to keep the system away from deadlock states. (3) Deadlock prevention is considered to be a well-defined problem in discrete event systems literature, which is usually achieved by using an offline computational mechanism to control the request for resources to ensure that deadlocks never occur; the goal of a deadlock prevention approach is to impose constraints on a system to prevent it from reaching deadlock states. In (Li, et al., 2008), the authors compare the different polices in terms of structural complexity, behavior permissiveness, and computational complexity.