臺灣博碩士論文加值系統

Flexible manufacturing systems (FMSs) have provided the necessary flexibility to enable manufacturers to cope with increased demand diversity so that they can improve the reliability, flexibility, and capability of the production system. A problem emerging from FMS implementation is that of system deadlock. The occurrence of deadlock may even paralyze the entire system. First, in this study, deadlock detection and resolution schemes are developed. Second, the deadlock
resolving strategy is proposed. Third, an integer programming model is developed to schedule the parts’induction processes so that the total flow time is minimized. Based on the testing problems, the proposed approach outperforms the others including random, batch, and deadlock-freed approaches.

Flexible manufacturing systems (FMSs) have provided the necessary flexibility to enable manufacturers to cope with increased demand diversity so that they can improve the reliability, flexibility, and capability of the production system. A problem emerging from FMS implementation is that of system deadlock. The occurrence of deadlock may even paralyze the entire system. First, in this study, deadlock detection and resolution schemes are developed. Second, the deadlock
resolving strategy is proposed. Third, an integer programming model is developed to schedule the parts’induction processes so that the total flow time is minimized. Based on the testing problems, the proposed approach outperforms the others including random, batch, and deadlock-freed approaches.

Contents i
List of Figures ii
List of Tables ii
Abstract iii
1 Introduction 1
1.1 The motivation . . . . . . . . . . . . . . . . . . . . . 1
1.2 The objective . . . . . . . . . . . . . . . . . . . . . . 1
1.3 The scope . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 The research procedures . . . . . . . . . . . . . . . . . 2
1.5 The article structure . . . . . . . . . . . . . . . . . . 2
2 Literature Review 3
2.1 Detection/recovery strategies: . . . . . . . . . . . . . 3
2.1.1 Using Petri nets tools: . . . . . . . . . . . . . . . . 3
2.1.2 Using graph-theoretic tools:. . . . . . . . . . . . . . 4
2.1.3 Others: . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Prevention method: . . . . . . . . . . . . . . . . . . . 4
2.3 Avoidance schemes: . . . . . . . . . . . . . . . . . . . 4
3 Deadlock Detection and Resolution 6
3.1 Problem description . . . . . . . . . . . . . . . . . . . 6
3.1.1 Given . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.2 Goal . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Defnition . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.2 Routing matrix (RM) . . . . . . . . . . . . . . . . . . 8
3.2.3 Successor graph (SG). . . . . . . . . . . . . . . . . . 9
3.2.4 Adjacency matrix (A) . . . . . . . . . . . . . . . . . 9
3.2.5 Deadlock . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Methodology. . . . . . . . . . . . . . . . . . . . . . . 10
3.3.1 Algorithm. . . . . . . . . . . . . . . . . . . . . . . 10
3.3.2 Strategy . . . . . . . . . . . . . . . . . . . . . . . 11
4 Part Induction Scheduling 15
4.1 Problem description . . . . . . . . . . . . . . . . . . 15
4.1.1 Notations. . . . . . . . . . . . . . . . . . . . . . . 15
4.1.2 Problem formulation P1 . . . . . . . . . . . . . . . . 16
4.1.3 Illustrative example:. . . . . . . . . . . . . . . . . 17
4.2 Performance comparisons. . . . . . . . . . . . . . . . . 24
4.2.1 Notations. . . . . . . . . . . . . . . . . . . . . . . 24
4.2.2 Simulation data. . . . . . . . . . . . . . . . . . . . 25
4.2.3 Simulation results . . . . . . . . . . . . . . . . . . 27
5 Conclusions and Recommendations 30
5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Recommendations for future research. . . . . . . . . . . 30
References 31

[1] T.C. Chang, R. A. Wysk, and H. P. Wang, Computer-Aid turing. Englewood Cli¤s, NJ: Prentice-Hall, 1991.
[2] Okogbaa, O. G., and Huang J., 1992, "A simulation study of deadlock avoidance in FMS". Proceedings of the 1st Industrial Engineering Research Conference, pp. 197-201
[3] L. Ferrarini and M. Maroni, "Deadlock Avoidance Control for Manufacturing Systems with Multiple Capacity Resources", Int J Adv Manuf Technol(1998) 14:729-736
[4] Chu, F. and Xie, X., "Deadlock Analysis of Petri Nets Using Siphons and Mathematical Programming", IEEE Transcation on Robotics and Automation, Vol. 13, No. 6, pp. 793-804 (December 1997)
[5] Hyuenbo Cho, T.K. Kumaran, and Richard A. Wysk, "Graph-
Theoretic Deadlock Detection and Resolution for Flexible Manufacturing Systems", IEEE Transaction on Robotics and Automation. Vol. 11, No. 3, June 1995
[6] D.-S. Yim, J.-S. Kim and H.-S.Woo, "Avoidance of deadlocks in flexible manufacturing systems using a capacity-designated directed graph". Int. J. Prod. Res., 1997, Vol. 35, No. 9, 2459-2475
[7] Mark Lawley, Spiridon Reveliotis, and Placid Ferreira, "De-
sign Guidelines for Deadlock-Handling Strategies in Flexible Manufacturing Systems", The International Journal of Flexible Manufacturing Systems, 9 (1997): 5-30
[8] Mark Lawley, Spiridon Reveliotis, and Placid Ferreira, "The
Application and Evaluation of Banker’s Algorithm for Deadlick-Free Bu¤er Space Allocation in Flexible Manufacturing Systems", The International Journal of Flexible Manufacturing Systems, 10(1998): 73-100
[9] Spyros A. Reveliotis, "Accommodating FMS Operational Contingencies Through Routing Flexiblilty", IEEE Transactions on Robotics and Automation, Vol. 15,NO. 1, February 1999
[10] Widodo Sulistyono and Mark A. Lawley, "Deadlock Avoidance for Manufacturing Systems With Partically Ordered Process Plans", IEEE Transactions on Robotics and Automation, Vol. 17, No. 6, December 2001
[11] Maria Pia Fanti, Guide Maione, and Biagio Burchiano, "Design of Supervisors to Avoid Deadlock in Flexible Assembly Systems", The International of Flexible Manufacturing Systems, 14, 157-175, 2002
[12] Jo Wyns, Hendrik Ven Brussel, and Paul Valckenaers, "Design pattern for deadlock handling in holonic manufacturing systems", Production Planning & Control, 1999, VOL. 10, NO. 7, 616-626
[13] Luca Ferrarini,Luigi Piroddi, and Stefano Allegri, "A comparative performance analysis of deadlock avoidance control algorithms for FMS", Journal of Inteligent Manufacturing (1999) 10, 569-585
[14] M. Lawley and J. Mittenthal, "Order release and deadlock avoidance interactions in counter-‡ow system optimization", Int. J. Prod. Res., 1999, Vol. 37, No. 13, 3043-3062
[15] T. Minoura and C. Ding, "Adeadlock prevention method for a sequence controller for manufacturing control", International Journal of Robotics and Automation, 6(3), p. 149. 1991
[16] Nagi Z. Gebraeel and Mark A. Lawley, "Deadlock Detection, Prevention, and Avoidance for Automated Tool Sharing Systems", IEEE Transcation on Robotics and Automation, Vol. 17, No. 3, June 2001
[17] Sanjay E. Ramaswamy and Sanjay B. Joshi, "Deadlock-free schedules for automated manufacturing workstations", IEEE Transactions on Robotics and Automation, Vol. 12, No. 3, June 1996