Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems

This paper presents two iterative deadlock prevention policies for flexible manufacturing systems (FMSs). Both can find a maximally permissive liveness-enforcing supervisor with a small number of control places. A vector covering approach is used to obtain a minimal covering set of legal markings and a minimal covered set of first-met bad markings (FBMs), which are much smaller than the sets of legal markings and FBMs, respectively. At each iteration, by solving an integer linear programming problem (ILPP), a place invariant (PI) associated with a control place is designed to forbid as many FBMs as possible, and no markings in the minimal covering set of legal markings are forbidden. The objective function of the ILPP maximizes the number of FBMs that are forbidden by the PI. Then, the forbidden FBMs by the PI are removed from the minimal covered set of FBMs. This process is carried out until all FBMs are forbidden. Two ILPP design techniques are developed for the control policies. Though the proposed methods cannot in general guarantee the minimality of the supervisory structure, they reduce the overall computational time greatly, which is shown by numerical studies. Finally, a number of FMS examples from the literature are presented to illustrate the proposed methods.