International Journal of Applied Science and Engineering
Published by Chaoyang University of Technology

Tzong-Ming Cheng*

Department of Industrial Engineering and Management, Chaoyang University of Technology, Wufeng, Taichung country 413, Taiwan, R.O.C.

Download Citation: |
Download PDF


The time for electronically connecting business and manufacturing has come. Advancements in e-commerce have requested that business decisions on web be the direct driving info to the corresponding manufacturing activities without human interventions. Since orders from the web may arrive in random sequence and with a range of specifications, flexible manufacturing systems (FMS) may be the proper automata for the basis of e-manufacturing. An FMS is designed to handle orders having moderate variations in both part style and quantity. The computerized nature of the FMS makes it readily adaptive to the web-based information system. However, processes run by the FMS may not be fully automatic because of potential resource conflict, i.e. a floating characteristic relationship between system facility and production orders. Since coordination between system facility and unpredictable orders is difficult, this paper will present an off-line simulation approach to reveal the embedded relationship and then avoid the conflicts on-line. The method employs three dispatching rules individually to direct the process flows inside a flexible manufacturing cell (FMC), and acquires potential deadlock patterns of part processing sequence from an off-line simulation. Then an on-line matching/reordering process is used to keep the incoming orders dissimilar to the deadlock patterns. Two major advantages have been achieved by the proposed method: it provides an effective routing mechanism for deadlock-free production on randomly arrived orders, and it improves the feasibility of any planned schedules by removing the potential of resource deadlock. This research uses timed Petri nets to simulate the flexible manufacturing cell. Three dispatching rules, which generate pull tendency at cell exit, are employed and compared to demonstrate the routing mechanism.

Keywords: deadlock avoidance; e-Manufacturing; flexible manufacturing systems.

Share this article with your colleagues



[1]  Basnet, C. and Mize, J. H. 1994. Scheduling and control of flexible Manufacturing system: a critical review. International Journal of Computer Integrated Manufacturing, 7, 6: 340-355.

[2] Belarmino, A. D., Sebastian, L., Jesus, R., and Fernado, G.. 2001. Machine cell formation in generalized group technology. Computers and Industrial Engineering, 41: 227-240.

[3] Chang, K. F. and Gong, D. C. 1999. Introduction to the basic theory of petri met. Journal of the Chinese Institute of Industrial Engineers, 16, 1: 63-83.

[4] Huang, H. H. 2001. Matrix Controller Design and deadlock analysis of automated manufacturing systems. Part 1. Designing the matrix-based controller. The International Journal of Advanced Manufacturing Technology, 18: 434-447.

[5] Jeong, K. C. and Kim, Y. D. 1998. A real-time scheduling mechanism for a flexible manufacturing system: using simulation and dispatching rules. International Journal of Production Research, 36, 9: 2609-2626.

[6] Jonghun, P. and Spyros, A. R. 2001. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Transactions on Automatic Control, 46, 10:1572-1583.

[7] Lee, D. Y. and DiCesare, F. 1994. Scheduling flexible manufacturing systems using Petri nets and heuristic seaech. IEEE Transactions on Robotics and Automation, 10, 2: 123-132.

[8] Maria, P. F., Bruno, M., and Biagio, T. 2000. Comparing digraph and Petri net approaches to deadlock avoidance in FMS. IEEE Transactions on Systems, Man, and Cybernetics, 30, 5:783-798.

[9] Maria, P. F., Guido, M., and Biagio, T. 2002. Design of supervisors to avoid deadlock in flexible assembly systems. The International Journal of Flexible Manufacturing Systems, 14: 153-171.

[10] Mark, L. and Spyros, R. 2001. Deadlock avoidance for sequential resource allocation systems: hard and easy cases. The International Journal of Flexible Manufacturing Systems, 13: 385-404.

[11] Matta, A., Tolio, T., Karaesmen, F., and Dallery, Y. 2001. An integrated approach for the configuration of automated manufacturing systems. Robotics and Computer Integrated Manufacturing, 17: 19-26.

[12] Mu, D. J. 1997. A Petri net synthesis theory for modeling flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, 27, 2:169-183.

[13] Peterson, J. L. 1981. “Petri Net Theory and the Modeling of Systems”. Prentice Hall Inc.

[14] Reyes, A., Yu, H., Kelleher, G., and Lloyed, S. 2002. Integrating Petri Nets and hybrid heuristic search for the scheduling of FMS. Computers in Industry, 47: 123-138.

[15] Tianlong, G.. and Parisa, A. B. 2002. A survey of Petri net applications in batch processes. Computers in Industry, 47: 99-111.

[16] Uzam, M. 2002. An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. The International Journal of Advanced Manufacturing Technology, 19: 192-208.

[17] Widodo, S. and Mark, A. L. 2001. Deadlock avoidance for manufacturing systems with partially ordered process plans. IEEE Transactions on Robotics and Automation, 17, 6:819-832.

[18] Xiong, H. H., Zhou, M. C., and Caudill, R. J. 1996. A hybrid heuristic search algorithm for scheduling flexible manufacturing systems. Proceedings of the 13th IEEE International Conference on Robotics and Automation, 2793-2797.

[19] Yim, S. J. and Lee, D. Y. 1996. Multiple objective scheduling for flexible manufacturing systems using Petri nets and heuristic search. IEEE: 2984-2989.

[20] Yu, H., Reyes, A., Cang, S., Yu, H., and Lloyed, S. 2003. Combined Petri net modeling and AI-based heuristic hybrid search for flexible manufacturing systems-part II. Heuristic hybrid search. Computers and Industrial Engineering, 44: 545-566.

[21] Zhou, M. C., Chiu, H. S., and Xiong, H. H. 1995. Petri net scheduling of FMS using branch and bound method. IEEE: 211-216.


Accepted: 2004-04-16
Available Online: 2004-07-03

Cite this article:

Cheng, T.-M. 2004. On-line deadlock avoidance for complex routing flexible manufacturing cells, International Journal of Applied Science and Engineering, 2, 163–176.