[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems

  • Original Article
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

In a flexible manufacturing system (FMS) with multiple products, deadlocks can arise due to limited shared resources, such as machines, robots, buffers, fixtures etc. The development of efficient deadlock prevention policies, which can optimise the use of system resources, while preventing deadlocks from occurring, has long been an important issue to be addressed. In [1], an optimal deadlock prevention policy was proposed, based on the use of reachability graph (RG) analysis of the Petri net model (PNM) of a given FMS and the synthesis of a set of new net elements, namely places with initial marking and related arcs, to be added to the PNM, using the theory of regions. The policy proposed in [1] is optimal in the sense that it allows the maximal use of resources in the system according to the production requirements. For very big PNMs, the reachability graph of the PNMs becomes very large and the necessary computations to obtain an optimal deadlock prevention policy become more difficult. In this paper, we propose the use of the Petri net reduction approach to simplify very big PNMs so as to make necessary calculations easily in order to obtain an optimal deadlock prevention policy for FMSs. An example is provided for illustration.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1a–f
Fig. 2
Fig. 3
Fig. 4a–c
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9a–c
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

References

  1. Uzam M (2002) 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 19:192–208

    Google Scholar 

  2. Visvanadham N, Nahari Y, Johnson TL (1990) Deadlock prevention and deadlock avoidance in flexible manufacturing systems using petri net models. IEEE Trans Robot Automat 6(6):713–723

    Article  Google Scholar 

  3. Banaszak ZA, Krogh BH (1990) Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans Robot Automat 6(6):724–734

    Article  Google Scholar 

  4. Tat LY,Gwo-Ji S (1993) Resolving deadlocks in flexible manufacturing cells. J Manuf Syst 12(4):291–307

    Google Scholar 

  5. Wysk RA, Neng-Shu Y, Sanjay J (1994) Resolution of deadlocks in flexible manufacturing systems: avoidance and recovery approaches. J Manuf Syst 13(2)128–136

    Google Scholar 

  6. Hsieh FS, Chang SC (1994) Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. IEEE Trans Robot Automat 10(2):196–209

    Article  Google Scholar 

  7. Ezpeleta J, Colom JM, Martinez J (1995) A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans Robot Automat 11(2):173–184

    Article  Google Scholar 

  8. Cho H, Kumaran TK, Wysk RA (1995) Graph-theoretic deadlock detection and resolution for flexible manufacturing systems. IEEE Trans Robot Automat 11(3):413–421

    Article  Google Scholar 

  9. Xing K, Hu B, Chen H (1995) Deadlock avoidance policy for flexible manufacturing systems. In: Zhou MC (ed) Petri nets in flexible and agile automation, Kluwer, Boston pp 239–263

  10. Xing K, Hu B, Chen H (1996) Deadlock avoidance policy for petri-net modelling of flexible manufacturing systems with shared resources. IEEE Trans Automat Control 41(2):289–295

    Google Scholar 

  11. Fanti MP, Maione B, Mascolo S, Turchiano B (1997) Event-based feedback control for deadlock avoidance in flexible production systems. IEEE Trans Robot Automat 13(3):347–363

    Article  Google Scholar 

  12. Lawley M, Reveliotis S, Ferreira P (1997) Design guidelines for deadlock handling strategies in flexible manufacturing systems. Int J Flex Manuf Syst 9(7):5–29

    Article  Google Scholar 

  13. Yim D, Kim J, Woo H (1997) Avoidance of deadlocks in flexible manufacturing systems using a capacity designated directed graph. Int J Prod Res 35(9):2459–2475

    Article  Google Scholar 

  14. Tricas F, Garcia-Valles F, Colom JM, Ezpelata J (1998) A structural approach to the problem of deadlock prevention in processes with resources. In: Proc of WODES’98, Italy, pp 273–278, 26–28 August 1998

  15. Lawley M, Reveliotis S, Ferreira P (1998) A correct and scalable deadlock avoidance policy for flexible manufacturing systems. IEEE Trans Robot Automat 14:796–809

    Article  Google Scholar 

  16. Abdallah IB, ElMaraghy HA (1998) Deadlock prevention and avoidance in FMS: a petri net based approach. Int J Adv Manuf Techol 14:704–715

    Google Scholar 

  17. Ferrarini L, Maroni M (1998) Deadlock avoidance control for manufacturing systems with multiple capacity resources. Int J Adv Manuf Technol 14:729–736

    Google Scholar 

  18. Lawley M (1999) Deadlock avoidance for production systems with flexible routing. IEEE Trans Robot Automat 15(3):497–509

    Article  Google Scholar 

  19. Tricas F, Garcia-Valles F, Colom JM, Ezpelata J (1998) A structural approach to the problem of deadlock prevention in processes with resources. In: Proc of the 4th WODES’98, pp 273–278, Cagliari, Italy 26–28 August 1998

  20. Ramaswamy SE, Joshi SB (1996) Deadlock-free schedules for automated manufacturing workstations. IEEE Trans Robot Automat 12(3):391–400

    Article  Google Scholar 

  21. Li Y, Wonham WM (1988) Deadlock issues in supervisory control of discrete event systems. In: Proc of the 1st WODES’88, pp 57–63, Princeton

  22. Badouel E, Darondeau P (1998) Theory of Regions. Reisig W, Rozenberg G (eds) Lecture notes in computer science (Lectures on Petri Nets I: Basic Models, Advances in Petri Nets), vol 1491. Springer, Berlin Heidelberg New York, pp 529–586

  23. Murata T (1989) Petri nets: properties, analysis and application. In: Proceedings of IEEE 44:541–579

  24. Peterson JL (1981) Petri net theory and the modelling of systems. Prentice-Hall, Englewood Cliffs, NJ

  25. Lee KH, Favrel J (1985) Hierarchical reduction method for analysis and decomposition of Petri nets. IEEE Trans Syst Man Cybern 15:272–280

    Google Scholar 

  26. Silva M (1985) Las Redes de Petri en la Automatica y la Informatica. Editorial AC, Madrid

  27. Zhou MC, Jeng MD (1998) Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems: a petri net approach. IEEE Trans Semicon Manuf 11(3):333–357

    Article  Google Scholar 

  28. PN-tools (1987–1996) A Petri net analysis tool, ver. 1.0, Pedagogical University of Rzesów, Poland

  29. Notomi M, Murata T (1994) Hierarchical reachability graph of bounded petri nets for concurrent-software analysis. IEEE Trans Soft Eng 20(5):325–336

    Article  Google Scholar 

  30. McMillan KL (1995) A technique for state space search based on unfolding. Form Method Syst Des 6(1):45–65

    Google Scholar 

  31. Esparza J, Römer S, Vogler W (1996) An improvement of McMillan’s unfolding algorithm. In: Tools and Algorithms for the Construction and Analysis of Systems. Passau, Germany, March 1996. Lecture notes in computer science, vol. 1055, Springer, Berlin Heidelberg New York, pp 87–106

  32. Heiner M (1997) Verification and Optimization of Control Programs by Petri Nets without State Explosion. In: Proceedings of the 2nd International Workshop on Manufacturing and Petri Nets, a workshop within the 28th International Conference on Application and Theory of Petri Nets, Toulouse, France, 23 June 1997

  33. Taubin A, Kondratvey A, Kishinevsky M (1998) Deadlock prevention using petri nets and their unfoldings. Int J Adv Manuf Technol 14:750–759

    Google Scholar 

Download references

Acknowledgments

This work was supported by the French National Research Institute INRIA under the MARS project. The author would like to thank the anonymous referees for their comments, which helped the author to improve the presentation of this paper.

Author information

Authors and Affiliations

  1. Mühendislik-Mimarlik Fakültesi, Elektrik-Elektronik Mühendisliği Bölümü, Niğde Üniversitesi, Kampüs , 51100, Niğde, Turkey

    Murat Uzam

Authors
  1. Murat Uzam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Murat Uzam.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Uzam, M. The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems. Int J Adv Manuf Technol 23, 204–219 (2004). https://doi.org/10.1007/s00170-002-1526-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-002-1526-5

Keywords

Search

Navigation