Manufacturing practitioners and researchers recognize the need to develop effective supervisory controllers for automated manufacturing systems. One active area of research has been developing deadlock avoidance methods for these systems. Almost all work to date has assumed that allocated resources do not fail. In this paper, we consider deadlock and blocking problems in systems with unreliable resources. Our objective is to develop supervisory control policies that allocate resources so the failure of any given resource does not propagate through blocking to effectively stall other portions of the system. To accomplish this, the supervisory controller must enforce liveness for the original system while avoiding states that do not serve as feasible initial states for the reduced system when an unreliable resource fails. The policy must then enforce liveness for the reduced system while avoiding states that do not serve as feasible initial states for the original system so transition to normal operation is smooth when the failed resource is restored.

Manufacturing practitioners and researchers have recognized the need to develop effective supervisory controllers for automated manufacturing systems. One active area of research has been developing deadlock avoidance methods for these systems. Almost all work to date has assumed that allocated resources do not fail. In this paper, we consider deadlock and blocking problems in systems with unreliable resources. Our objective is to develop supervisory control policies that allocate resources so that the failure of any given resource does not propagate through blocking to effectively stall other portions of the system. In other words, when a resource fails, we want the system to automatically continue producing all part types that do not require the failed resource. To accomplish this, the supervisory controller must ensure safety for the original system while avoiding states that do not serve as feasible initial states for the reduced system when an unreliable resource fails. The policy must then ensure safety for the reduced system while avoiding states that do not serve as feasible initial states for the original system so that transition to normal operation is smooth when the failed resource is restored. This paper illustrates this class of problems through several examples, identifies properties that controllers must satisfy to deal effectively with these problems, and develops two polynomial control policies that satisfy these properties.

Most deadlock avoidance work in manufacturing deals with systems where each part type requires a fixed sequence of operations. In contrast, the paper deals with those systems that support sequencing flexibility, that is, the operations required by the part are partially ordered. In this setting, the order in which operations are performed is not predetermined but becomes a real-time decision. Specifically, the paper presents a detailed resource allocation model and proves the NP-completeness of optimal deadlock avoidance for a highly flexible subclass of these systems. It also identifies several cases and conditions for which optimal deadlock avoidance is of polynomial complexity.

Deadlock avoidance policies guarantee deadlock-free resource allocation to concurrent competing processes in flexible manufacturing systems. Most deadlock avoidance work in manufacturing deals with systems where each part requires a fired sequence of operations. In contrast, this paper deals with those systems that support sequencing flexibility, that is, the operations required by the part are partially ordered. In this setting, the order in which operations are performed is not predetermined, but becomes a real-time decision. Specifically, the paper characterizes the deadlock detection and avoidance problems for these systems, presents a sub-optimal deadlock avoidance approach, and addresses two relevant special structures on the partial orders for which optimal deadlock avoidance is of polynomial complexity.