Abstract
Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion” combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has received little attention. In this paper, we extend the Beam A* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that the Petri Net approach is also valid to minimize due date related criteria in flexible systems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baker, K. R. (1974). Introduction to sequencing and scheduling. New York: Wiley.
Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 22, 158–183.
Jeng, M. D., & Chen, S. C. (1998). A heuristic search approach using approximate solutions to Petri Net state equations for scheduling flexible manufacturing systems. The International Journal of Flexible Manufacturing Systems, 10, 139–162.
Lee, D. Y., & DiCesare, F. (1994). Scheduling flexible manufacturing systems using Petri Nets and heuristic search. IEEE Transactions on Robotics and Automation, 10(2), 123–131.
Mejía, G. (2003). Timed Petri Net modeling and optimization with heuristic search for flexible manufacturing workstations. In Proceedings of the 2003 IEEE emerging technologies and factory automation (ETFA), Lisbon, Portugal, September 16–19, 2003.
Mejía, G., & Odrey, N. (2005). An approach using Petri Nets and improved heuristic search for manufacturing system scheduling. Journal of Manufacturing Systems, 34(2), 79–92.
Moore, K. E., & Gupta, S. M. (1996). Petri Net models of flexible and automated manufacturing systems: A survey. International Journal of Production Research, 34(11), 3001–3035.
Murata, T. (1989). Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4), 541–580.
Ow, P. S., & Morton, T. E. (1988). Filtered beam search in scheduling. International Journal of Production Research, 26, 35–62.
Pinedo, M., & Chao, X. (1999). Operations scheduling with applications in manufacturing and services. New York: McGraw-Hill.
Reyes-Moro, A., Yu, H., Kelleher, G., & Lloyd, S. (2002). Integrating Petri Nets and hybrid heuristic search for the scheduling of FMS. Computers in Industry, 47, 123–138.
Russell, S., & Norvig, P. (1995). Artificial intelligence: A modern approach. Englewood Cliffs: Prentice-Hall.
Sabuncuoglu, I., & Bayiz, M. (1999). Job shop scheduling with Beam search. European Journal of Operational Research, 118(2), 390–412.
Sun, T., Cheng, W., & Fu, L. (1994). A Petri Net based approach to modeling and scheduling for an FMS and a case study. IEEE Transactions on Industrial Electronics, 41(6), 593–601.
Xiong, H. H., & Zhou, M. C. (1998). Scheduling of semi-conductor test facility via Petri Nets and hybrid heuristic search. IEEE Transactions on Semiconductor Manufacturing, 11(3), 384–393.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mejía, G., Montoya, C. A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems. Ann Oper Res 164, 63–78 (2008). https://doi.org/10.1007/s10479-007-0258-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0258-1