access icon free Control policy for a subclass of Petri nets without reachability analysis

© The Institution of Engineering and Technology
Received 07/06/2012, Accepted 20/03/2013, Revised 16/03/2013, Published

Traditional maximally permissive deadlock prevention control for flexible manufacturing systems requires costly reachability analysis. It has been a hot race to synthesise optimal controllers to be maximally permissive with fewest monitors. Previous work shows that among all n-dependent siphons, only one siphon (whose unmarked state follows some token distribution) needs to be controlled. This greatly simplifies the supervisor synthesis as well as minimises the number of monitors required while making the controlled net maximally permissive (i.e. all live states can be reached.). This study further proposes a maximally permissive control policy for a subclass of systems of simple sequential processes with resources (S3PR) based on the above theory of token distribution pattern of unmarked siphons.

Inspec keywords: flexible manufacturing systems; Petri nets; control system synthesis; optimal control

Other keywords: systems-of-simple sequential processes-with-resources; unmarked siphon token distribution pattern theory; flexible manufacturing systems; S3PR; optimal controller synthesis; Petri net subclass; supervisor synthesis; maximally permissive deadlock prevention control policy

Subjects: Control technology and theory (production); Optimal control; Manufacturing systems; Combinatorial mathematics; Combinatorial mathematics; Control applications in manufacturing processes; Control system analysis and synthesis methods

References

    1. 1)
      • 7. Liu, G.J., Jiang, C.J., Wu, Z.H., Chen, L.J.: ‘A live subclass of Petri nets and their application in modeling flexible manufacturing systems’, Int. J. Adv. Manuf. Technol., 2009, 41, (1–2), pp. 66–74 (doi: 10.1007/s00170-008-1457-x).
    2. 2)
      • 30. Piroddi, L., Cordone, R., Fumagalli, I.: ‘Selective siphon control for deadlock prevention in Petri nets’, IEEE Trans. Syst. Man Cybern. A, 2008, 38, (6), pp. 1337–1348 (doi: 10.1109/TSMCA.2008.2003535).
    3. 3)
      • 34. Chen, Y.F., Li, Z.W., Zhou, M.C.: ‘Behavior optimal and structural simple liveness-enforcing supervisor for flexible manufacturing systems’, IEEE Trans. Syst. Man Cybern. A, 2012, 42, (3), pp. 615–629 (doi: 10.1109/TSMCA.2011.2169956).
    4. 4)
      • 13. Li, Z.W., Zhou, M.C.: ‘Clarifications on the definitions of elementary siphons in Petri nets’, IEEE Trans. Syst. Man Cybern. A, 2006, 36, (6), pp. 1227–1229 (doi: 10.1109/TSMCA.2006.878966).
    5. 5)
      • 16. Li, Z.W., Zhou, M.C.: ‘Control of elementary and dependent siphons in Petri nets and their application’, IEEE Trans. Syst. Man Cybern., A, 2008, 38, (1), pp. 133–148 (doi: 10.1109/TSMCA.2007.909548).
    6. 6)
      • 6. Wu, N.Q., Zhou, M.C., Li, Z.W.: ‘Resource-oriented Petri net for deadlock avoidance in flexible assembly systems’, IEEE Trans. Syst. Man Cybern. A, 2008, 38, (1), pp. 56–69 (doi: 10.1109/TSMCA.2007.909542).
    7. 7)
      • 31. Piroddi, L., Cordone, R., Fumagalli, I.: ‘Combined siphon and marking generation for deadlock prevention in Petri nets’, IEEE Trans. Syst. Man Cybern. A, 2009, 39, (3), pp. 650–661 (doi: 10.1109/TSMCA.2009.2013189).
    8. 8)
      • 14. Li, Z.W., Zhou, M.C.: ‘Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets’, IEEE Trans. Ind. Inf., 2006, 2, (4), pp. 313–325 (doi: 10.1109/TII.2006.885185).
    9. 9)
      • 27. Yamalidou, K., Moody, J., Lemmon, M., Antsaklis, P.: ‘Feedback control of Petri nets based on place invariants’, Automatica, 1996, 32, (1), pp. 15–28 (doi: 10.1016/0005-1098(95)00103-4).
    10. 10)
      • 42. Chao, D.Y.: ‘Conservative control policy for weakly dependent siphons in S3PR based on elementary siphons’, IET Control Theory Appl., 2010, 4, (7), pp. 1298–1302 (doi: 10.1049/iet-cta.2009.0118).
    11. 11)
      • 36. Nazeem, A., Reveliotis, S., Wang, Y., Lafortune, S.: ‘Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the linear case’, IEEE Trans. Autom. Control, 2011, 56, (8), pp. 1818–1833 (doi: 10.1109/TAC.2010.2095612).
    12. 12)
      • 3. Chao, D.Y.: ‘Improvement of suboptimal siphon- and FBM-based control model of a well-known S3PR’, IEEE Trans. Autom. Sci. Eng., 2011, 8, (2), pp. 404–411 (doi: 10.1109/TASE.2010.2088120).
    13. 13)
      • 12. Li, Z.W., Zhou, M.C.: ‘Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems’, IEEE Trans. Syst. Man Cybern. A, 2004, 34, (1), pp. 38–51 (doi: 10.1109/TSMCA.2003.820576).
    14. 14)
      • 43. Chao, D.Y.: ‘Technical Note - MIP iteration-reductions for deadlock prevention of flexible manufacturing systems’, Int. J. Adv. Manuf. Technol., 2009, 41, (3), pp. 343–346 (doi: 10.1007/s00170-008-1473-x).
    15. 15)
      • 38. Shih, Y.Y., Chao, D.Y.: ‘Sequence of control in S3PMR’, Comput. J., 2010, 53, (10), pp. 1691–1703 (doi: 10.1093/comjnl/bxp081).
    16. 16)
      • 41. Wang, S.G., Wang, C.Y., Zhou, M.C., Li, Z.W.: ‘A method to compute strict minimal siphons in a class of petri nets based on loop resource subsets’, IEEE Trans. Syst. Man Cybern. A., 2012, 42, (1), pp. 226–237 (doi: 10.1109/TSMCA.2011.2159590).
    17. 17)
      • 11. Ezpeleta, J., Colom, J.M., Martinez, J.: ‘A Petri net based deadlock prevention policy for flexible manufacturing systems’, IEEE Trans. Robot. Autom., 1995, 11, (2), pp. 173–184 (doi: 10.1109/70.370500).
    18. 18)
      • 29. Huang, Y.S., Pan, Y.L., Zhou, M.C.: ‘Computationally improved optimal deadlock control policy for flexible manufacturing systems’, IEEE Trans. Syst. Man Cybern. A, 2012, 42, (2), pp. 404–415 (doi: 10.1109/TSMCA.2011.2164241).
    19. 19)
      • 19. Ezpeleta, J., Couvreur, J.M., Silva, M.: ‘A new technique for finding a generating family of siphons, traps, and st-components: application to colored Petri nets’, in Rozenberg, G., (Ed.): ‘Advances in Petri nets’ (Springer-Verlag, New York, 1993), (LNCS, 674), pp. 126–147.
    20. 20)
      • 17. Li, Z.W., Zhou, M.C.: ‘Deadlock resolution in automated manufacturing systems: a novel Petri net approach’ (Springer-Verlag, London, 2009).
    21. 21)
      • 15. Li, Z.W., Zhou, M.C.: ‘On controllability of dependent siphons for deadlock prevention in generalized Petri nets’, IEEE Trans. Syst. Man Cybern. A, 2008, 38, (2), pp. 369–384 (doi: 10.1109/TSMCA.2007.914741).
    22. 22)
      • 10. Xing, K.Y., Zhou, M.C., Wang, F., Liu, H.X., Tian, F.: ‘Resource-transition circuits and siphons for deadlock control of automated manufacturing systems’, IEEE Trans. Syst. Man Cybern. A, 2011, 41, (1), pp. 74–84 (doi: 10.1109/TSMCA.2010.2048898).
    23. 23)
      • 4. Li, Z.W., Wu, N.Q., Zhou, M.C.: ‘Deadlock control of automated manufacturing systems based on Petri nets-A literature review’, IEEE Trans. Syst. Man Cybern. C, 2012, 42, (4), pp. 437–462 (doi: 10.1109/TSMCC.2011.2160626).
    24. 24)
      • 1. Zhou, M.C., Venkatesh, K.: ‘Modeling, simulation and control of flexible manufacturing systems: a Petri net approach’ (World Scientific, Singapore, 1999).
    25. 25)
      • 8. Liu, G.J., Jiang, C.J., Zhou, M.C.: ‘Two simple deadlock prevention policies for S3PR based on key-resource/operation-place pairs’, IEEE Trans. Autom. Sci. Eng., 2010, 7, (4), pp. 945–957 (doi: 10.1109/TASE.2010.2050059).
    26. 26)
      • 21. Xing, K.Y., Zhou, M.C., Liu, H., Tian, F.: ‘Optimal Petri-net based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems’, IEEE Trans. Syst. Man Cybern. A, 2009, 39, (1), pp. 188–199 (doi: 10.1109/TSMCA.2008.2007947).
    27. 27)
      • 32. Chen, Y.F., Li, Z.W.: ‘Design of a maximally permissive liveness-enforcing supervisor with compressed supervisory structure for flexible manufacturing systems’, Automatica, 2011, 47, (5), pp. 1028–1034 (doi: 10.1016/j.automatica.2011.01.070).
    28. 28)
      • 2. Fanti, M.P., Zhou, M.C.: ‘Deadlock control methods in automated manufacturing systems’, IEEE Trans. Syst. Man Cybern. A, 2004, 34, (1), pp. 5–22 (doi: 10.1109/TSMCA.2003.820590).
    29. 29)
      • 25. Uzam, M., Zhou, M.C.: ‘An improved iterative synthesis approach for liveness enforcing supervisors of flexible manufacturing systems’, Int. J. Prod. Res., 2006, 44, (10), pp. 1987–2030 (doi: 10.1080/00207540500431321).
    30. 30)
      • 37. Nazeem, A., Lafortune, S.: ‘Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the nonlinear case’, IEEE Trans. Autom. Control, 2012, 57, (7), pp. 1670–1684 (doi: 10.1109/TAC.2011.2179422).
    31. 31)
      • 18. Lautenbach, K.: ‘Linear algebraic calculation of deadlocks and traps’, in Voss, , Genrich, , Rozemberg, (Eds.), ‘Concurrency and nets’ (Springer-Verlag, Berlin, Germany, 1987), pp. 315–336.
    32. 32)
      • 9. Huang, Y.S., Pan, Y.L.: ‘An improved maximally permissive deadlock prevention policy based on the theory of regions and reduction approach’, IET Control Theory Appl., 2011, 5, (9), pp. 1069–1078 (doi: 10.1049/iet-cta.2010.0371).
    33. 33)
      • 22. Liu, G.J., Jiang, C.J., Zhou, M.C.: ‘Improved sufficient condition for the controllability of dependent siphons in system of simple sequential processes with resources’, IET Control Theory Appl., 2011, 5, (9), pp. 1059–1068 (doi: 10.1049/iet-cta.2010.0195).
    34. 34)
      • 40. Chao, D.Y., Liu, G.J.: ‘A simple suboptimal siphon-based control model of a well-known S3PR’, Asian J. Control, 2012, 14, (1), pp. 163–172 (doi: 10.1002/asjc.292).
    35. 35)
      • 24. Ghaffari, A., Rezg, N., Xie, X.L.: ‘Design of a live and maximally permissive Petri net controller using the theory of regions’, IEEE Trans. Robot. Autom., 2003, 19, (1), pp. 137–142 (doi: 10.1109/TRA.2002.807555).
    36. 36)
      • 35. Li, Z.W., Zhou, M.C., Jeng, M.D.: ‘A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions’, IEEE Trans. Autom. Sci. Eng., 2008, 5, (1), pp. 182–188 (doi: 10.1109/TASE.2006.884674).
    37. 37)
      • 20. Chao, D.Y.: ‘An incremental approach to extract minimal bad siphons’, J. Inf. Sci. Eng., 2007, 23, (1), pp. 203–214.
    38. 38)
      • 26. Uzam, M., Li, Z.W., Zhou, M.C.: ‘Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS’, Int. J. Adv. Manuf. Technol., 2007, 35, (1-2), pp. 150–168 (doi: 10.1007/s00170-006-0701-5).
    39. 39)
      • 33. Chen, Y.F., Li, Z.W., Khalgui, M., Moshabi, O.: ‘Design of maximally permissive liveness-enforcing petri net supervisor for flexible manufacturing systems’, IEEE Trans. Autom. Sci. Eng., 2011, 8, (2), pp. 374–393 (doi: 10.1109/TASE.2010.2060332).
    40. 40)
      • 23. Uzam, M.: ‘An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions’, Int. J. Adv. Manuf. Technol., 2002, 19, (3), pp. 192–208.
    41. 41)
      • 5. Wu, N.Q., Zhou, M.C.: ‘Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems based on a Petri net model’, IEEE Trans. Robot. Autom., 2001, 17, (5), pp. 658–669 (doi: 10.1109/70.964666).
    42. 42)
      • 39. Chao, D.Y.: ‘Computation of elementary siphons in Petri nets for deadlock control’, Comput. J., 2006, 49, (4), pp. 470–479 (doi: 10.1093/comjnl/bxl019).
    43. 43)
      • 28. Uzam, M.: ‘The use of Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems’, Int. J. Adv. Manuf. Technol., 2004, 23, (3-4), pp. 204–219 (doi: 10.1007/s00170-002-1526-5).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta.2012.0426
Loading

Related content

content/journals/10.1049/iet-cta.2012.0426
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading