Volume 3 Issue 1 pp. 53-62 January, 2013


Sufficient conditions for a flexible manufacturing system to be deadlocked


Paul E. Deering


In recent years, researchers have been interested in scheduling algorithms to avoid deadlock in Flexible Manufacturing Systems (FMS). FMS are discrete event systems characterized by the availability of resources to produce a set of products. Raw parts, which belong to various product types, enter the system at discrete times and are processed concurrently while sharing a limited number of resources. In such systems, a situation may occur in which parts become permanently block. This is called deadlock. This paper presents the sufficient conditions for deadlock to exist in a FMS; it models a FMS using digraphs to calculate slack, knot, order and space; it identifies three types of circuits that are fundamental in determining if a FMS is in deadlock.


DOI: 10.5267/j.ijiec.2011.08.016

Keywords: Deadlock, Deadlock avoidance algorithm, Flexible manufacturing system

References

Banaszak, Z., & Krogh, B. (1990). Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans. on Robotics and Auto., 6(6), 724–733.

Barkaoui, K. and I.B. Abdallah. (1995). A deadlock method for a class of FMS, Proceedings of the 1995 IEEE Int. Conf. On Systems, Man and Cybernetics, 4119–4124.

Cho, H., Kumaran, T. K., & Wysk, R. (1995). Graph-theoretic deadlock detection and resolution for flexible manufacturing systems. IEEE Trans. on Robotics and Auto., 11(3) 550–527.

Deering, E. P. (2000). Necessary and sufficient conditions for deadlock in manufacturing systems. PhD Dissertation, Ohio University.

Deering, E. P. (2008). A simple deadlock avoidance algorithm in flexible manufacturing systems. International Journal of Modern Engineering, 9(1) 19-26.

Ezpeleta, J., Colom, J., & Martinez, J. (1995). A petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. on Robotics and Automation, 11(2), 173–184.

Fanti, M.P., Maione, B., Mascolo, S., &Turchiano, B. (1995). control polices conciliating deadlock avoidance and flexibility in FMS resource allocation. IEEE Symposium on Emerging Technologies and Factory Automation, 1, 343–351.

Fanti, M., Maione, G., & Turchiano, B. (1996). Deadlock detection and recovery in flexible production systems with multiple capacity resources. Industrial Applications in Power Systems Computer Science and Telecommunications Proceedings of the Mediterranean Electrotechnical Conference, 1, 237–241.

Hsieh, F., & Chang, S. (1994). Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. IEEE Transaction on Robotics and Automation, 10(2), 196–209.

Judd, R. P., & Faiz, T. (1995). Deadlock detection and avoidance for a class of manufacturing systems. Proceedings of the 1995 American Control Conference, 3637–3641.

Judd, R. P., Deering, P., & Lipset, R. (1997). Deadlock detection in simulation of manufacturing systems. Proceedings of the 1997 Summer Computer Simulation Conference, 317–322.

Lipset, R., Deering, P., & Judd, R. P. (1997). Necessary and sufficient conditions for deadlock in manufacturing systems. Proceedings of the 1997 American Control Conference, 2,1022–1026.

Lipset, R., Deering, P., & Judd, R. P. (1998). A stack-based algorithm for deadlock avoidance in flexible manufacturing systems. Proceedings of the 1998 American Control Conference.

Viswanadham, N., Narahari, Y., & Johnson, T. (1990). Deadlock prevention and deadlock avoidance in flexible manufacturing systems using petri net models. IEEE Transaction on Robotics and Automation, 6(6), 713–723.

Wysk R., Yang, N., & Joshi, S. (1991). Detection of deadlocks in flexible manufacturing systems. IEEE Transactions Robotics and Automation, 7(6), 853–858.

Wenle, Z., Judd, R.P., & Deering, P. (2003). Evaluating order of circuits for deadlock avoidance in a flexible manufacturing system. Proceedings of the 2003 American Control Conference, 3679–3683.

Wenle, Z., Judd, R.P., & Deering, P. (2004). Necessary and sufficient conditions for deadlocks in flexible manufacturing systems based on a digraph model. Asian Journal of Controls, 6(2) 217–228.

Wenle, Z., & Judd, R. P. (2007). Evaluating order of circuits for deadlock avoidance in a flexible manufacturing system. Asian Journal of Controls, 9(2), 111–120.

Zhou, M., & DiCesare, F. (1992). Parallel and sequential mutual exclusion for petri net modeling of manufacturing systems with shared resources, IEEE Transaction on Robotics and Automation, 7(4), 550–527.

Zhou, M. (1996). Generalizing parallel and sequential mutual exclusions for petri net synthesis of manufacturing systems, IEEE Symposium on Emerging Technologies and Factory Automation, 1 49–55.