本研究主要係運用派屈網路理論(Petri nets, PN)來解決彈性製造系統（Flexible Manufacturing Systems, FMS）的死鎖問題。準確地說，開發了一種新穎的控制變遷(control transition)技術來解決彈性製造系統的死鎖問題。這個新提出的技術不僅可以識別派區網路模型（PNM）中的閒置位置的最大飽和標記，還可以進一步保留所有原始可達標記，無論它們是合法的還是非法的。換句話說，一旦識別出空閒位置飽和數量的令牌，就可以檢查系統的可達性圖的最大標記。兩個經典的具有資源的簡單順序過程系統(S3PR模型)示例用於說明所提出的技術。實驗結果表明，所提出的控制轉換技術算法，似乎是所有現有算法中最好的算法之一。

This paper focuses on solving deadlock problems of flexible manufacturing systems (FMS) based on Petri nets theory. Precisely, one novel control transition technology is developed to solve FMS' deadlock problem. This new proposed technology can not only identify the maximal saturated tokens of idle places in Petri nets model (PNM) but also further reserve all original reachable markings whatever they are legal or illegal ones. In other words, once the saturated number of tokens in idle places is identified, the maximal markings of system’ reachability graph can then be checked. Two classical S3PR (The Systems of Simple Sequential Processes with Resources) examples are used to illustrate the proposed technology. Experimental results indicate that the proposed algorithm of control transition technology seems the best one among all existing algorithms.

[1]Ezpeleta J., Colom J. M., and Martinez J.: 'A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems', IEEE Transactions Robotics and Automation, 1995, 11, (2), pp. 173-184
[2]Liu G., Li Z. W., and Zhou C.: 'New Controllability Condition for Siphons in a Class of Generalised Petri Nets', IET Control Theory and Applications, 2010, 4, (5), pp. 854-864
[3]Huang Y. S., Jeng M. D., Jeng X. L., Xie X. L., and Chung T. H.: 'Deadlock Prevention Policy Based on Petri Nets and Siphons', International Journal of Production Research, 2001, 39, (3), pp. 283-305
[4]Huang Y. S., Jeng M. D., Xie X. L., and Chung T. H.: 'Siphon-Based Deadlock Prevention Policy for Flexible Manufacturing Systems', IEEE Transactions on Systems, Man and Cybernetics, Part A, Systems and Humans, 2006, 36, (6), pp. 2152-2160
[5]Li Z. W. and Zhou M. C.: 'Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems', IEEE Trans. Syst., Man, Cybern. A, Humans, 2004, 34, (1), pp. 38-51
[6]Li Z. W. and Zhou M. C.: 'Clarifications on the Definitions of Elementary Siphons in Petri Nets', IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2006, 36, (6), pp. 1227-1229
[7]Liu H., Xing K., Wu W., Zhou M. C., and HailinZou: 'Deadlock Prevention for Flexible Manufacturing Systems via Controllable Siphon Basis of Petri Nets', IEEE Transactions on Systems, Man and Cybernetics, 2015, 45, (3),pp. 519-529
[8]Uzam M.: 'An Optimal Deadlock Prevention Policy for Flexible Manufacturing Systems Using Petri Net Models with Resources and the Theory of Region', International Journal of Advanced Manufacturing Technology, 2002, 19, (3), pp. 192-208
[9]Uzam M. and Zhou M. C.: 'An Iterative Synthesis Approach to Petri Net-Based Deadlock Prevention Policy for Flexible Manufacturing Systems', IEEE Transactions on Systems, Man, Cybernetics, Part A, Systems and Humans, 2007, 37, (3), pp. 362-371
[10]Piroddi L. , Cordone R., and Fumagalli I.: 'Selective Siphon Control for Deadlock Prevention in Petri Nets', IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2008, 38, (6), pp. 1337-1348.
[11]Yen-Liang Pan,(2011), Deadlock Prevention Policy for Flexible
Manufacturing Systems Based on the Theory of Regions. Unpublished
Doctoral Dissertation,Chung Cheng Institute of Technoogy,National
Defense University School of Defense Sicence.
[12]Yen-Liang Pan, Yi-Sheng Huang, Mu-Der Jeng, and Sheng-Luen Chung, “Enhancement of an Efficient Control Policy for FMSs Using the Theory of Regions and Selective Siphons Method” The International Journal of Advanced Manufacturing Technology, vol. 66, pp. 1805-1815, Jun. 2013.
[13]Daniel Yuh Chao and Yen-Liang Pan, “Uniform Formulas for Compound Siphons, Complementary Siphons and Characteristic Vectors in Deadlock Prevention of Flexible Manufacturing Systems” Journal of Intelligent Manufacturing, vol. 13, no. 1, pp. 13-23, Jan. 2015.
[14]Murata T.: 'Petri nets: Properties, analysis and application', Pro. IEEE, 1989, 77, (4), pp541-580
[15]Li Z. W., Hanish H. M., and Zhou M. C.: 'Deadlock Prevention Based on Structure Reuse of Petri Net Supervisors for Flexible Manufacturing Systems', Systems, Man and Cybernetics, part A: System and Humans, IEEE Transactions, 2012,42, (1)
[16]Wang S. G., Wang C. G., Zhou M. C. ,and Li Z. W.: 'A Method to Compute Strict Minimal Siphons in S3PR Based on Loop Resource Subsets', IEEE Transactions on Systems Man and Cybernetics-Part A Systems and Humans, 2012,42, (1), pp. 226-237
[17]Liu H., Xing K., Wu W. M., Zhou M. C., and Zou H. L.: 'Deadlock Prevention for Flexible Manufacturing Systems via Controllable Siphon Basis of Petri nets', IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45, (3), pp. 519-529
[18]Li Z. W.and Zhou M. C.: 'On Siphon Compution for Deadlock Control in a Class of Petri Nets', IEEE Transactions on Systems, Man, and Cybernetics, part a: Systems and Humans, 2008, 38, (3), pp.667-679
[19]Marsan, M. A., Balbo G., Conte G., Donatelli S., and Franceschinis G.: 'Modeling with Generalized Stochastic Petri Nets', (John Wiley and Sons Press, 1995,1st edn.). pp. 111-112
[20]S. G. Wang, W. H. Wu, and J. Yang, “Deadlock prevention policy for a class of petri nets based on complementary places and elementary siphons,” Journal of Intelligent Manufacturing, 2015, 26, (2), pp. 321-330
[21]Wang F., Xing K. Y., Xu X. P. and Han L. B.: 'Research on Finding Elementary Siphon in Class of Petri Nets', Springer, Communications and Information Processing, 2012, 289, pp. 435-442
[22]Mowafak Hassan Abdul-Hussin, “Elementary Siphons of Petri Nets and Deadlock Control in FMS,” Journal of Computer and Communications, 2015, 3, (7), pp. 1-12
[23]Y. F. Chen, Z.W. Li, Kamel Barkaoui, and Murat Uzam, “New Petri Net Structure and Its Application to Optimal Supervisory Control: Interval Inhibitor Arcs,” IEEE Transactions on Systems, Man, Cybernetics: Systems, 2014, 44, (10), pp. 1384-1400
[24]Murata T., “State Equation, Controllability, and Maximal Matchings of
Petri Net,” IEEE Transactions on Automatic Control, 1977, 22, (3), pp. 412-416
[25]David R. and Alla H, “Discrete, Continuous and Hybrid PetriNets,” (Springer Verlag Berlin Heidelberg Press, 2005, 2nd end.), pp. 37-39
[26]Yi-Sheng Huang, Yen-Liang Pan, and Pin-June Su, “Transition-Based Deadlock Detection and Recovery Policy for FMSs Using Graph Technique,” ACM Trans. Embed. Comput. Syst. 2013, 12, (1), Article 11, pp. 1-13, (http://dx.doi.org/10.1145/2406336.2406347).
[27]M. Uzam and M.C. Zhou, “An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems,” Int. J. Prod. Res., 2006, 44, (10), pp. 1987-2030.
[28]D.Y. Chao, “Reaching more states for control of FMS,” Int. J. Prod. Res., 2009, 48, (4), pp. 1217–1339.
[29]Y. F. Chen and Z. W. Li, “Design of a maximally permissive liveness-enforcing supervisor with compressed supervisory structure for flexible manufacturing systems,” Automatica, 2011, 47, (5), pp. 1028–1034.
[30]Y.F. Chen, Z.W. Li, and M.C. Zhou, “Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems,” IEEE Trans. Syst., Man, Cybern. A, 2012, 42, (3), pp. 615–629.
[31]Hong L., Hou Y. F., Jing J. F. et al.: 'Deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors', Discrete. Dyn. Nat. Soc., 2015, http://dx.doi.org/10.1155/2015/579623.
[32]TINA (Time petri Net Analyzer) has been developed in the OLC then VerTICS, research groups of LAAS/CNRS. http://projects.laas.fr/tina//download.php
[33]Yi-Sheng Huang and Yen-Liang Pan, “An Improved Maximally Permissive Deadlock Prevention Policy Based on the Theory of Regions and Reduction Approach,” IET Control Theory and Applications, vol. 5, no. 9, pp. 1069-1078, Jun. 2011.
[34]Xiuyan Zhang and Murat Uzam, “Transition-based Deadlock Control Policy Using Reachability Graph for Flexible Manufacturing Systems,” Advances in Mechanical Engineering, vol. 8 no. 2 pp. 1-9, 2016.
[35]YuFeng Chen, ZhiWu Li, Abdulrahman Al-Ahmari, NaiQi Wu, and Qu Ting, “Deadlock Recovery for Flexible Manufacturing Systems Modeled with Petri nets,” Information Sciences, vol. 381, pp.290-303, 2017. doi:10.1016/j.ins.2016.11.011
[36]Yi-Sheng Huang, Yen-Liang Pan, and MC Zhou, “Computationally Improved Optimal Deadlock Control Policy for Flexible Manufacturing Systems” IEEE Transactions on Systems, Man, and Cybernetics Part A-Systems and Humans, vol. 42, no. 2, pp. 404-415, Mar. 2012.
[37]Yen-Liang Pan, Cheng-Fu Yang, and Mu-Der Jeng “Enhancement of Selective Siphon Control Method for Deadlock Prevention in FMSs,” Mathematical Problems in Engineering, Article ID 196514, 2015.
[38]Yen-Liang Pan, Yi-Sheng Huang, Yi-Shun Weng, Weimin Wu, and Mu-Der Jeng “Computationally Improved Optimal Control Methodology for Linear Programming Problems of Flexible Manufacturing Systems” Journal of Applied Mathematics, vol. 2013, pp. 1-11, 2013.
[39]Yen-Liang Pan, Ching-Yun, Tseng, Ter-Chan Row “Design of Improved Optimal or Suboptimal Deadlock Prevention for FMSs Based on Place Invariant and Reachability Graph Analysis Methods” Journal of Algorithms and Computational Technology, 11(3), pp. 261-270, 2017, DOI: 10.1177/1748301817710922.
[40]Ter-Chan Row and Yen-Liang Pan, “Maximally Permissive Deadlock Prevention Policies for Flexible Manufacturing Systems Using Control Transition,” Advances in Mechanical Engineering, vol. 10(7), pp. 1-10, July 2018.
[41]Yi-Sheng Huang and Yen-Liang Pan, “Enhancement of An Efficient Liveness-Enforcing Supervisor for Flexible Manufacture Systems,” The International Journal of Advanced Manufacturing Technology, vol. 48, pp. 725-737, 2010. (DOI: 10.1007/s00170-009-2299-x)
[42]K. Barkaoui and I. Ben Abdallah, “A deadlock prevention method for a class of FMS,” 1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century, Vol.5, pp. 4119-4124, 1995.
[43]YiFan Hou and Kamel Barkaoui, “Deadlock analysis and control based
on Petri nets: A siphon approach review,” Advances in Mechanical Engineering, Vol. 9(5), 1–30, 2017.
[44]GaiYun Liu and Kamel Barkaoui, “A survey of siphons in Petri nets,” Information Sciences, Vol. 363, pp. 198–220, 2016.
[45]Wang, A.R.,Li,Z.,Zhou,M,C., and Al-Ahmari,A.M.,2012,“Inerative Deadlock Control by Using Petri Nets,” IEEE Transations on Systems, Man and Cybernetics,Vol.42,N06.
[46]Peterson, J. L., Petri Net Theory and the Modeling of Systems, Prentice Hall, Englewood Cliffs, New Jersey, U.S.A., Apr. 1981.
[47]Murata, T., “Petri Nets: Properties, Analysis, and Applications,” Proc. IEEE, Vol. 77, No. 4, pp. 541-580, 1989.
[48]Li, Z. W., Wang, A., and Lin, H., “A Deadlock Prevention Approach for FMS Using Siphon and the Theory of Regions,” 2004 IEEE International Conference on System, Man, and Cybernnetics, Vol. 6, pp.5079-5084, Oct. 2004.
[49]Li, Z. W., Zhou, M. C., and Wu, N. Q., “A Survey and Comparison of Petri Net-Based Deadlock Prevention Policies for Flexible Manufacturing Systems,” IEEE Trans. Syst., Man, Cybern. C, Appl. Rev., Vol. 38, No. 2, pp. 173-188, 2008.
[50]Zhou, M. C. and Venkatesh, K., Modeling, Simulation and Control of Flexible Manufacturing Systems: a Petri Net Approach, World Scientific, Singapore, 1998.
[51]Yu-Jen Liu,2014,Design of Petri Net Siphon Control for Deadlock Prevention of Flexible Manufacturing Systems.Department of Industrial Engineering and Management.
[52]C.A.Petri, “Communication mitt Automation”PHD thesis instituted for instrumentally Mathematics,Boon.1962.