TY - JOUR
T1 - Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems
AU - Chen, Yufeng
AU - Li, Zhiwu
AU - Zhou, Mengchu
N1 - Funding Information:
Manuscript received November 9, 2010; revised March 28, 2011; accepted April 30, 2011. Date of publication December 6, 2011; date of current version April 13, 2012. This work was supported in part by the Natural Science Foundation of China under Grant 60773001 and 61074035, the Fundamental Research Funds for the Central Universities under Grant JY10000904001 and K50510040012, the National Research Foundation for the Doctoral Program of Higher Education, the Ministry of Education, P. R. China, under Grant 20090203110009, and Alexander von Humboldt Foundation. This paper was recommended by Associate Editor A. Konar.
PY - 2012/5
Y1 - 2012/5
N2 - 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.
AB - 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.
KW - Deadlock prevention
KW - Petri net
KW - flexible manufacturing system (FMS)
KW - optimal liveness-enforcing supervisor
UR - http://www.scopus.com/inward/record.url?scp=84860191401&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860191401&partnerID=8YFLogxK
U2 - 10.1109/TSMCA.2011.2169956
DO - 10.1109/TSMCA.2011.2169956
M3 - Article
AN - SCOPUS:84860191401
SN - 1083-4427
VL - 42
SP - 615
EP - 629
JO - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
JF - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
IS - 3
M1 - 6095650
ER -