×
Ahmad, Farooq; Khan, Sher Afzal

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

Comput. Math. Appl. 64, No. 1, 1-10 (2012).
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

Keywords:

Petri net; periodic scheduling; asynchronous synthesis; net-modules
PDF BibTeX XML Cite
\textit{F. Ahmad} and \textit{S. A. Khan}, Comput. Math. Appl. 64, No. 1, 1--10 (2012; Zbl 1252.90021)
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, (Proceedings of the 11th Joint Conference on Information Sciences, JCIS-2008 Proceedings (2008), Atlantis Press)
[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, (Intelligent Control and Intelligent Automation (1998), World Scientific: World Scientific Singapore)
[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
[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, (Lecture Notes in Artificial Intelligence, vol. 2691 (2003), Springer-Verlag), 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)
[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)
[28] Lee, D. Y.; DiCesare, F., FMS scheduling using Petri nets and heuristic search, IEEE Transactions on Robotics and Automation, 10, 123-132 (1994)
[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)
[35] Reisig, W., (Petri Nets: An Introduction. Petri Nets: An Introduction, EATCS Monographs on Theoretical Computer Science, vol. 4 (1985), Springer-Verlag: Springer-Verlag Berlin, Heidelberg) · Zbl 0555.68033
[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.