A Comprehensive Survey of Flexible Manufacturing System Scheduling Using Petri Nets

Abstract:

A Flexible Manufacturing System (FMS) is an integrated, computer-controlled system of machines, automated handling systems, and storage systems that can be used to simultaneously manufacture a variety of jobs. FMSs can be characterized as asynchronous, concurrent, distributed and parallel systems in which multiple operations share multiple resources so that the performance criteria are optimized. Petri nets (PNs) have recently become a promising approach for modeling FMSs. PNs are formal graphical modeling tool that can be efficiently utilized as a process analysis and modeling tool, because it shows graphically and dynamically to simulate a process in an integrated manner. It is a mathematical modeling technique that is useful for modeling concurrent, asynchronous, distributed, parallel, nondeterministic, and stochastic systems. Unreasonably the dispatching resources/jobs to machine in FMS may result in a deadlock situation and the situation is studied thoroughly and avoided through PN techniques. From the design and analysis point of view, the uses of nets have many advantages in modeling, performance evaluation, qualitative analysis and code generation. Scheduling a manufacturing system is usually a Non-Polynomial hard problem. This means that only heuristic algorithms can be used to provide near-optimal schedule when it is merged with PN. The merging of PNs with knowledge based heuristic techniques seems to be very promising to deal with large complex discrete event dynamic systems. This paper presents a comprehensive survey of FMS that combines PNs with other methods.

• Periodical: Advanced Materials Research (Volumes 984-985)
• Pages: 111-117
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.984-985.111
• Online since: July 2014
• Authors: T.R. Chinnusamy*, T. Karthikeyan, M. Krishnan, A. Murugesan
• Keywords: Discrete Event Dynamic System, Flexible Manufacturing System, Heuristic Algorithm , Petri Net

References

[1] Desrochers.A. A, Jaar.R. Y, Applications of Petri nets in manufacturing systems, Institute of Electrical and Electronics Engineers Press, New York, NY. (1995).

[2] Byrkett.D. L, Ozden.M. H and Patton J.M., Integrating flexible manufacturing systems with traditional manufacturing, planning, and control, Journal of Production and Inventory Management, 29, 15-21, (1988).

[3] Maccarthy B.L. and Liu, J., A new classification scheme for flexible manufacturing systems, International Journal of Production Research, 31(2), 299-309, (1993).

DOI: 10.1080/00207549308956726

[4] Reyes. A, Yu. H, and Kelleher. S, Integrating Petri Nets and hybrid heuristic search for the scheduling of FMS, Computers in Industry, 47, 123 – 138, (2002).

DOI: 10.1016/s0166-3615(01)00124-5

[5] Gonca Tuncel. G, Mirac Bayhan, Applications of Petri nets in production scheduling: a review, International Journal of Advanced Manufacturing Technology 34, 762-773, (2007).

DOI: 10.1007/s00170-006-0640-1

[6] Kendra E. Moore, Surendra M. Gupta, Stochastic colored Petri net models of flexible manufacturing systems: material handling systems and machining, Computers and Industrial Engineering, vol. 29, No. 1-4, pp.333-337, (1995).

DOI: 10.1016/0360-8352(95)00094-h

[7] James T. Lin and Chia-Chu Lee, A Petri net-based integrated control and scheduling scheme for flexible manufacturing cells, Computer Integrated Manufacturing Systems vol. 10, No. 2, pp.109-122, (1997).

DOI: 10.1016/s0951-5240(97)00002-5

[8] Hong-Sen Yan, Ning-Sheng Wang, Jin-Ge Zhang, Xian-Yu Cui, Modelling, scheduling and simulation of flexible manufacturing systems using extended stochastic high-level evaluation Petri nets, Robotics and Computer-Integrated Manufacturing 14, 121-140, (1998).

DOI: 10.1016/s0736-5845(97)00019-7

[9] H. Yu, A. Reyes, S. Cang, S. Lloyd, Combined Petri net modelling and AI based heuristic hybrid search for flexible manufacturing systems—part 1. Petri net modeling and heuristic search, Computers and Industrial Engineering 44, 527-543, (2003).

DOI: 10.1016/s0360-8352(02)00212-7

[10] Han Zandong and Gibum Lee, Application of Petri nets for deadlock analysis and avoidance in flexible manufacturing systems, International Journal of Advanced Manufacturing Technology, 25, 735-742, (2005).

DOI: 10.1007/s00170-003-1907-4

[11] Jongkun Lee, Ouajdi Korbaa, Modeling and scheduling of ratio-driven FMS using unfolding time Petri nets, Computers & Industrial Engineering 46, 639–653, (2004).

DOI: 10.1016/j.cie.2004.05.015

[12] Jongkun Lee, Ouajdi Korbaa, Scheduling analysis of FMS: An unfolding timed Petri nets approach, Mathematics and Computers in Simulation 70, 419–432, (2006).

DOI: 10.1016/j.matcom.2005.11.010

[13] Abdallah. B, ElMaraghy.H. A, ElMekkawy. T, Deadlock-free scheduling in flexible manufacturing systems, Int J Prod Res 40 (12): 2733–2756, (2002).

DOI: 10.1080/00207540210136496

[14] Moro.A. R, Yu. H, Kelleher. G, Hybrid heuristic search for the scheduling of flexible manufacturing systems using Petri nets,. IEEE Trans Robot Autom 18(2): 240–245, (2002).

DOI: 10.1109/tra.2002.999652

[15] Yu. H, Reyes. A, Cang S, Lloyd. S, Combined Petri nets modelling and AI-based heuristic hybrid search for flexible manufacturing systems-part II Heuristic hybrid search,. Computer and Industrial Engineering 44(4): 545–566, (2003).

DOI: 10.1016/s0360-8352(02)00213-9

[16] Elmekkawy T, Elmaraghy HA, Efficient search of Petri Nets for deadlock-free scheduling in FMSs using heuristic functions, International Journal of Computer Integrated Manufacturing 16(1): 14–24, (2003).

DOI: 10.1080/713804976

[17] Gonzalo Mejía and Carlos Montoya, A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems, DOI 10. 1007/s10479-007-0258-1, © Springer Science & Business Media, LLC, (2007).

DOI: 10.1007/s10479-007-0258-1

[18] Young Woo Kim et al., FMS scheduling based on timed Petri Net model and reactive graph search, Applied Mathematical Modelling 31, 955–970, (2007).

DOI: 10.1016/j.apm.2006.10.023

[19] Onaga. K, Silva. M, Watanabe. T, On periodic schedules for deterministically timed Petri net systems, The Proceedings of the Fourth International Workshop on Petri Nets and Performance Models (PNPM 91), Melbourne, Australia, IEEE Comp. Soc. Press, 2-5 December, p.200–215, (1991).

DOI: 10.1109/pnpm.1991.238799

[20] Proth.J. M, Sauer. N, Scheduling of piecewise constant product flows: a Petri net approach, European Journal Operation Research 106 (1): 45–56, (1998).

DOI: 10.1016/s0377-2217(98)00273-2

[21] Nicholas G. Odrey et al., An augmented Petri Net approach for error recovery in manufacturing systems control, Robotics and Computer-Integrated Manufacturing 21, 346–354, (2005).

DOI: 10.1016/j.rcim.2004.11.004

[22] Gang X, Wu Z, Deadlock-free scheduling strategy for automated production cell, IEEE Trans Syst Man Cybern Part C 34(1): 113–122, (2004).

DOI: 10.1109/tsmca.2003.820573

[23] Safiye Turgay, Agent-based FMS control, Robotics and Computer-Integrated Manufacturing, 29 February, (2008).

[24] Tiente Hsu et al., Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach, European Journal of Operational Research 191 464–484, (2008).

DOI: 10.1016/j.ejor.2007.02.055

[25] Reyes A, Yu H, et al., An Evolutionary Hybrid Schedular based in Petri net Structures for FMS Scheduling, IEEE, 0-7803-7087-2/01, (2001).

[26] Qiushuang Wang, Zhongdong Wang, Hybrid Heuristic Search Based on Petri Net for FMS Scheduling, Energy Procedia, 17 (2012) 506 – 512, (2012).

DOI: 10.1016/j.egypro.2012.02.128

[27] Lee. J, Korbaa. O, Modeling and scheduling of ratiodriven FMS using unfolding time Petri nets, Comput Ind Eng., 46(4): 639–653, (2004).

DOI: 10.1016/j.cie.2004.05.015