Control Algorithm Using a Revised MIP Method to Deal with Livelocks in S4R of Petri Nets

doi:10.1007/s12204-018-2014-x

Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (2): 190-195.doi: 10.1007/s12204-018-2014-x

Previous Articles Next Articles

Control Algorithm Using a Revised MIP Method to Deal with Livelocks in S4R of Petri Nets

LI Shaoyong* (李绍勇), WU Zongli (吴宗礼), LI Hailin (李海林), WEI Xianhong (魏先宏), CAI Ying (蔡颖), HOU Caiqin (厚彩琴)

(School of Civil Engineering, Lanzhou University of Technology, Lanzhou 730050, China)
(School of Civil Engineering, Lanzhou University of Technology, Lanzhou 730050, China)

Online:2019-04-30 Published:2019-04-01
Contact: LI Shaoyong* (李绍勇) E-mail:lishaoyong99@163.com

Abstract

Abstract: Livelocks, like deadlocks, can result in serious results in running process of flexible manufacturing systems (FMSs). Current deadlock control policies (DCPs) based on mixed integer programming (MIP) cannot detect siphons that cause and cope with livelocks in Petri nets. This study proposes a revised mixed integer programming (RMIP) method to directly solve the new smart siphons (NSSs) associated with livelocks in a system of sequential systems with shared resources (S4R), a typical subclass of generalized Petri net models. Accordingly, the solved NSSs are max’-controlled by adding the corresponding control places (CPs). As a result, an original S4R system with livelocks can be converted into the live controlled Petri net system. The related theoretical analysis and an example are given to demonstrate the proposed RMIP and the corresponding control algorithm (CA).

Key words: flexible manufacturing system (FMS)| Petri nets| revised mixed integer programing (RMIP)| livelocks| live controlled Petri net system

摘要： Livelocks, like deadlocks, can result in serious results in running process of flexible manufacturing systems (FMSs). Current deadlock control policies (DCPs) based on mixed integer programming (MIP) cannot detect siphons that cause and cope with livelocks in Petri nets. This study proposes a revised mixed integer programming (RMIP) method to directly solve the new smart siphons (NSSs) associated with livelocks in a system of sequential systems with shared resources (S4R), a typical subclass of generalized Petri net models. Accordingly, the solved NSSs are max’-controlled by adding the corresponding control places (CPs). As a result, an original S4R system with livelocks can be converted into the live controlled Petri net system. The related theoretical analysis and an example are given to demonstrate the proposed RMIP and the corresponding control algorithm (CA).

关键词: flexible manufacturing system (FMS)| Petri nets| revised mixed integer programing (RMIP)| livelocks| live controlled Petri net system

CLC Number:

U 292.18

LI Shaoyong* (李绍勇), WU Zongli (吴宗礼), LI Hailin (李海林), WEI Xianhong (魏先宏), CAI Ying (蔡颖), HOU Caiqin (厚彩琴). Control Algorithm Using a Revised MIP Method to Deal with Livelocks in S4R of Petri Nets[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(2): 190-195.

References 11

[1]	LI Z W, ZHOUMC. Deadlock resolution in automatedmanufacturing systems: A novel Petri net approach[M]. Berlin: Springer-Verlag, 2009.
[2]	CHAO D Y. Max’-controlled siphons for liveness ofS3PGR2 [J]. IET Control Theory and Application,2007, 1(4): 933-936.
[3]	LIU G Y, LI Z W. General mixed integerprogramming-based liveness test for system of sequentialsystems with shared resources nets [J]. IET ControlTheory and Application, 2010, 4(12): 2867-2878.
[4]	LI S Y, LI Z W. Solving siphons with the minimalcardinality in Petri nets and its applications to deadlockcontrol [J]. International Journal of ProductionResearch, 2012, 50(22): 6203-6218.
[5]	LI S Y, AN A M, WANG Y, et al. Design ofliveness-enforcing supervisors with simpler structuresfor deadlock-free operations in flexible manufacturingsystems using necessary siphons [J]. Journal of IntelligentManufacturing, 2013, 24(6): 1157-1173.
[6]	LI Z W, ZHOU M C. On siphon computation for deadlockcontrol in a class of Petri nets [J]. IEEE Transactionon Systems, Man, and Cybernetics, 2008, 38(3):667-679.
[7]	ZHONG C F, LI Z W. A deadlock prevention approachfor flexible manufacturing systems without completesiphon enumeration of their Petri net models [J]. Engineeringwith Computers, 2009, 25(3): 269-278.
[8]	LI Z W, LIANG J W, LU Y, et al. A deadlock preventionmethod for FMS with multiple resource acquisitions[C]//8th International Conference on Control,Automation, Robotics and Vision. Kunming, China:IEEE, 2004: 2117-2122.
[9]	LI Z W, WANG A R, WEI N. Liveness-enforcing supervisorsfor flexible manufacturing systems with multipleresource acquisitions [C]//International Conferenceon Networking, Sensing and Control. Ft. Lauderdale,FL, USA: IEEE, 2006: 710-714.
[10]	ZHONG C F, LI Z W. Self-liveness of a class of Petrinet models for flexible manufacturing systems [J]. IETControl Theory and Applications, 2010, 4(3): 403-410.
[11]	LI S Y, LI Z W. Structure reduction of livenessenforcingPetri nets using mixed integer programming[J]. Asian Journal of Control, 2012, 14(2): 384-399

Control Algorithm Using a Revised MIP Method to Deal with Livelocks in S4R of Petri Nets

Control Algorithm Using a Revised MIP Method to Deal with Livelocks in S4R of Petri Nets

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References 11

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	LI Cheng,LI Shuang,FENG Yiping,RONG Gang. Scheduling Flexible Manufacturing System Based on Timed Petri Net and Heuristic Search [J]. Journal of Shanghai Jiaotong University, 2015, 49(05): 708-713.
[2]	LUO Ji-Liang, CHEN Xue-Kun, QI Peng-Fei, ZHAO Po. Sequential Controller Synthesis and Formal Models for Batch Chemical Processes [J]. Journal of Shanghai Jiaotong University, 2012, 46(12): 1896-1900.
[3]	DONG Zhen-Hua-a, b , DONG Xiao-Ju-a, b . Representing Bounded Petri Nets by Process Calculi [J]. Journal of Shanghai Jiaotong University, 2011, 45(07): 980-984.