An improved strategy to solve shop deadlock problem based on the study on existing benchmark recovery strategies

Ranjan Bhattacharya1, Susmita Bandyopadhyay2
1Jadavpur University, Kolkata, India
2West Bengal University of Technology, Kolkata, India

Tóm tắt

In this paper, we study the effect of various benchmark deadlock recovery strategies, and we find that each of these recovery strategies either results into another kind of deadlock or results into very high handling cost and long handling time. We also propose a new improved strategy in order to solve the shop deadlock problem through the use of both automated guided vehicle and a central buffer. To the best knowledge of the authors, till date, no research study has been performed to propose any such strategy in this regard or to study the effect of several deadlock recovery strategies altogether. Simulation result shows that the proposed strategy performs better than the existing benchmark recovery strategies and provides much improved solution to the shop deadlock problem, resulting into considerable reduction in handling time and cost and better handling of jobs in central buffer compared to various benchmark deadlock recovery strategies available in the literature.

Tài liệu tham khảo

Viswanadham N, Narahari Y (1994) Performance modeling of automated manufacturing systems. Prentice-Hall of India Private Limited, New Delhi, p 117 Liu FH, Hung PC (2001) Real-time deadlock-free control strategy for single multi-load automated guided vehicle on a job shop manufacturing system. Int J Prod Res 39(7):1323–1342 Lochana MR, Wee HG, Ng WC, Teo CP (2003) Cyclic deadlock prediction and avoidance for zone-controlled AGV system. Int J Prod Econ 83:309–324 Wan KC, Tanchoco JMA, Koo PH (1997) Deadlock prevention in manufacturing systems with AGV systems: banker's algorithm approach. J Manuf Sci Eng 119:849–854 Jain A, Jain PK, Singh IP (2005) Deadlock analysis in FMS in the presence of flexible process plans—a simulation study. International Journal of Simul Model 4(2):53–66 Isloor SI, Marsland TA (1980) Deadlock problem: an overview. Computer 13(9):58–78 Coffman EG , Elphick MJ, Shoshani A (1971) System deadlocks. Computing Surveys 3(2), June Fanti Maria Pia, Zhou MengChu (2004) Deadlock control methods in automated manufacturing systems, IEEE transactions on systems, man, and cybernetics—Part A: Systems and Humans 34(1), January Zhang W, Judd RP (2007) Deadlock avoidance algorithm for flexible manufacturing systems by calculating effective free space of circuit. Int J Prod Res 46(13):3441–3457 Zhang W, Judd RP, Deering P (2004) Necessary and sufficient conditions for deadlocks in flexible manufacturing systems based on a digraph model. Asian J Cont 6:217–228 Zhang W, Judd RP, Paul P (2006) Evaluating order of circuits for deadlock avoidance algorithm for flexible manufacturing system. Int J Prod Res 44:5247–5259 Zhang W, Judd RP (2005) Deadlock avoidance algorithm for flexible manufacturing systems by calculating effective free space of circuits. in Proceedings of the 2005 American Control Conference, Portland, OR, 8-10 June, pp 3926-3931 Ke- Yi Xing, Bao-Sheng Hu, Hao-Xun Chen (1996) Deadlock avoidance policy for petri-net modeling of flexible manufacturing systems with shared resources. IEEE Transactions on Automatic Control 41(2) February Joaquin Ezpeleta, JosC Manuel Colom, Javier Martinez (1995) A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans Robot Autom, vol. II . no. 2. April Viswanadham N, Narahari Y, Timothy L. Johnson (1990) Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Trans Robot Autom 6(6) December Zhang W, Judd RP, Deering PE (2006) Evaluating order of circuits for deadlock avoidance in a flexible manufacturing system. Int J Prod Res 44(24):5247–5259 Cho H, Kumaran TK, Wysk R (1995) Graph-theoretic deadlock detection and resolution for flexible manufacturing systems. IEEE Trans Rob Auto 11:550–527 Lawley MA (1999) Deadlock avoidance for production systems with flexible routing. IEEE Trans Rob Auto 15:497–509 Wysk R, Yang N, Joshi S (1991) Detection of deadlocks in flexible manufacturing cells. IEEE Trans Rob Auto 7:853–859 Piroddi L, Cossalter M, Ferrarini L (2007) A resource decoupling approach for deadlock prevention in FMS. Int J Adv Manuf Technol 40:157–170. doi:10.1007/s00170-007-1319-y Wang Shengyong, Chew Song Foh, Lawley Mark A (2008) Using shared-resource capacity for robust control of failure-prone manufacturing systems, IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans 38(3), May Egbelu JP, Tanchoco JM (1984) Characterization of automatic guided vehicle dispatching rules. Int J Prod Res 22(3):359–374 Han M-H, McGinnis LF (1989) Control of material handling transporter in automated manufacturing. HE Transactions 21(2):184–190 Miyamoto T, Tsujimoto N, Kumagai S (2005) A Cooperative Algorithm for Autonomous Distributed Vehicle Systems with Finite Buffer Capacity, IEICE TRANS. FUNDAMENTALS, VOL.E88–A, NO.11 NOVEMBER 2005. Wu Naiqi, Zhou MengChu (2006) Resource-Oriented Petri Net for deadlock resolution in Automated Manufacturing Systems with Robots. 2006 IEEE International Conference on Systems, Man. and Cybernetics, October 8-11, Taipei, Taiwan, pp 74-79 Gupta JND, Luong LHS, Nguyen VH (1999) Part dispatching and machine loading in flexible manufacturing systems using central queues. Int J Prod Res 37(6):1427–1435 Roser Christoph, Nakano Masaru, Tanaka Minoru (2003) Buffer allocation model based on single simulation. Proceedings of the 2003 Winter Simulation Conference. In: S Chick, PJ Sanchez, D Ferrin, DJ Moorrice, (eds) Liu John J (1989) The periodic routing of a flexible manufacturing system with centralized in-process inventory flows. Int J Prod Res 27(6):943–951 Gupta T, Houshyar A (1990) Consideration of instage and central buffers in two-stage production system. Computers and Industrial Engineering 19(1-4):427–431 Muller Max (2003) Essentials of Inventory Management. AMACOM, a division of American Management Association. pp 49-65 Taghaboni, Fataneh (1989) Scheduling and control of manufacturing systems with critical material handling, Ph.D. thesis (Major Professor: J. M. A. Tanchoco), School of Industrial Engineering, Purdue University, West Lafayette, Indiana