×

Module-based architecture for a periodic job-shop scheduling problem. (English) Zbl 1252.90021

Summary: We address the Petri net (PN) based design and modeling approach for a periodic job-shop scheduling problem. Asynchronous synthesis for net-modules of the jobs is suggested in this paper for optimal allocation of shared resources to different operations. To make sure the completion of all the jobs in a single iteration of a production cycle and the correct calculation of a makespan, the synchronization problem among jobs is tackled by introducing the special synchronizing transition in the model. A timed-place PN is adopted for the purpose of finding the feasible schedule in terms of the firing sequence of the transitions of the PN model by using the heuristic search method. Further, the characterization of the PN model is performed and it is shown that the PN model for a periodic job-shop scheduling problem is equivalent to a class of PN known as parallel process net with resources (PPNRs). The modeling approach is demonstrated with a practical example and a makespan is calculated for the example.

MSC:

90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Hurz, B.; Zhou, M.C., Modeling and control of discrete-event dynamic systems: with Petri nets and other tools, (2007), Springer-Verlag London Limited
[2] Rudek, A.; Rudek, R., A note on optimization in deteriorating systems using scheduling problems with the ageing effect and resource allocation models, Computers & mathematics with applications, 62, 1870-1878, (2011) · Zbl 1231.90211
[3] Tuncel, G.; Bayhan, G.M., Applications of Petri nets in production scheduling: a review, International journal of advanced manufacturing technology, 34, 762-773, (2007)
[4] Ahmad, F.; Huang, H.; Wang, X., Analysis of the Petri net model of parallel manufacturing processes with shared resources, Information sciences, 181, 5249-5266, (2011)
[5] Jiao, L.; Huang, H.; Cheung, T.Y., Handling resource sharing problem using property-preserving place fusions of Petri nets, Journal of circuits, systems and computers, 17, 365-387, (2008)
[6] Li, Z.W.; Zhou, M.C., On siphon computation for deadlock control in a class of Petri nets, IEEE transactions on systems, man, and cybernetics part A:systems and humans, 38, 667-679, (2008)
[7] Li, J.; Huang, H.; Ahmad, F., Deadlock avoidance of a kind of JSP with multi-resources sharing, ()
[8] Li, Z.W.; Wei, N., Deadlock control of flexible manufacturing systems via invariant-controlled elementary siphons of Petri nets, International journal of advanced manufacturing technology, 33, 24-35, (2007)
[9] Sun, T.H.; Cheng, C.W.; Fu, L.C., Petri net based approach to modeling and scheduling for an FMS and a case study, IEEE transactions on industrial electronics, 41, 593-601, (1994)
[10] Zuberek, W.M.; Kubiak, W., Timed Petri net in modeling and analysis of simple schedules for manufacturing cells, Computers & mathematics with applications, 37, 191-206, (1999) · Zbl 0931.90022
[11] Zhou, M.C.; Venkatesh, K., Modeling, simulation, and control of flexible manufacturing systems: a Petri net approach, ()
[12] Zhang, W.; Freiheit, T.; Yang, H., Dynamic scheduling in flexible assembly system based on timed Petri nets model, Robotics and computer-integrated manufacturing, 21, 550-558, (2005)
[13] Christian, A.; Francois, R., A Petri net model and a general method for on and off-line multi-resource shop floor scheduling with setup times, International journal of production economics, 74, 63-74, (2001)
[14] Bayhan, G.M.; Tuncel, G., Modelling, behavioral analysis and performance evaluation of an automative assembly plant using Petri nets, International journal of industrial engineering, 9, 238-247, (2002)
[15] Guirao, J.L.G.; Pelayo, F.L.; Valverde, J.C., Modeling the dynamics of concurrent computing systems, Computers & mathematics with applications, 61, 1402-1406, (2011) · Zbl 1217.68150
[16] M.C. Zhou, H.S. Chiu, H.H. Xiong, PN Scheduling of FMS using branch and bound method, in: International Conference on Industrial Electronics, Control, and Instrumentation, 21st IEEE IECON, 1995, pp. 211-216.
[17] Venkatesh, K.; Zhou, M.C., Object-oriented design of FMS control software based on object modeling techniques diagrams and Petri nets, Journal of manufacturing systems, 17, 118-136, (1998)
[18] Zurawski, R.; Zhou, M.C., Petri nets and industrial applications: a tutorial, IEEE transactions on industrial electronics, 41, 567-582, (1994)
[19] Huang, H., Component-based design for job-shop scheduling systems, International journal of advanced manufacturing technology, 45, 958-967, (2009)
[20] Proth, J.M.; Xie, X., Petri nets: A tool for design and management of manufacturing systems, (1997), John Wiley & Sons, Inc.
[21] Hamerrlian, N., Refinement of open protocols for modeling and analysis of complex interactions in multi-agent systems, (), 423-434
[22] Zhou, M.C.; DiCesare, F., Parallel and sequential mutual exclusions for Petri net modeling for manufacturing systems with shared resources, IEEE transactions on robotics and automation, 7, 515-527, (1991)
[23] Kis, T.; Kiritsis, D.; Xirouchakis, P.; Neuendorf, K.P., Petri net model for integrated process and job shop production planning, Journal of intelligent manufacturing, 11, 191-207, (2000)
[24] Ezpeleta, J.; Colom, M.J.; Martinez, J., A Petri net based deadlock prevention policy for flexible manufacturing systems, IEEE transactions on robotics and automation, 11, 173-184, (1995)
[25] H. Huang, L. Jiao, T.Y. Cheung, Property-preserving composition of augmented marked graphs that share common resources, in: Proceeding of IEEE International Conference on Robotics and Automation, vol. 1, 2003, pp. 1446-1451.
[26] Abdallah, I.B.; E1Maraghy, H.A., Deadlock detection and avoidance in FMS: a PN approach, International journal of advanced manufacturing technology, 14, 704-715, (1998)
[27] D.Y. Lee, F. DiCesare, Petri nets and heuristic search for periodic scheduling, in: Proc. IEEE Int Systems, Man and Cybernetics Conf, IEEE SMC’92, 1992, pp. 998-1003.
[28] Lee, D.Y.; DiCesare, F., FMS scheduling using Petri nets and heuristic search, IEEE transactions on robotics and automation, 10, 123-132, (1994)
[29] H. Tohme, M. Nakamura, E. Hachiman, K. Onaga, Evolutionary Petri net approach to periodic job-shop-scheduling, in: Proc. IEEE Int Systems, Man, and Cybernetics Conf. IEEE SMC ’99, 1999, pp. 441-446.
[30] Bucci, G.; Fedeli, A.; Sassoli, L.; Vicario, E., Timed state space analysis of real-time preemptive systems, IEEE transactions on software engineering, 30, 97-111, (2004)
[31] Jiao, L.; Cheung, T.Y.; Lu, W., Handling synchronization problem in Petri net-based system design by property-preserving transition-reduction, The computer journal, 48, 692-701, (2005)
[32] Ahmad, F.; Huang, H.; Wang, X.-L., Petri net modeling and deadlock analysis of parallel manufacturing processes with shared resources, Journal of systems and software, 83, 675-688, (2010)
[33] M.D. Jeng, C.S. Lin, Petri nets for the formulation of aperiodic scheduling problems in FMSs, in: 6th International Conference on Emerging Technologies and Factory Automation Proceedings, ETFA’97, 1997, pp. 375-380.
[34] Y.L. He, G.N. Wang, Petri nets based deadlock-free scheduling for flexible manufacturing systems, in: 9th International Conference on Control, Automation, Robotics and Vision, ICARCV’06, 2006, pp. 1-5.
[35] Reisig, W., ()
[36] Murata, T., Petri nets: properties, analysis and application, Proceedings of IEEE, 77, 541-580, (1989)
[37] Jiao, L.; Huang, H.; Cheung, T.Y., Property-preserving composition by place merging, Journal of circuits, systems and computers, 14, 793-812, (2005)
[38] Jiao, L.; Huang, H.; Cheung, T.Y., Handling resource sharing problem using property-preserving place fusions of Petri nets’, Journal of circuits, systems and computers, 17, 365-387, (2008)
[39] Li, Z.W.; Zhou, M.C., Deadlock resolution in automated manufacturing systems: A novel Petri net approach, (2009), Springer-Verlag London Limited
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.