Abstract
This paper introduces a new Petri Net based approach for resource allocation and scheduling. The goals are (i) minimize the number of required resources given a set of jobs, (ii) find both an assignment for all jobs in the span of a predefined shift and (iii) the sequence in which such jobs are executed. The studied problem was inspired from a complex real life manufacturing shop as described in this document. The modeling of the processes and jobs is carried out with Petri Nets due to their capability of representing dynamic, concurrent discrete-event dynamic systems. The resource assignment starts with an initial feasible solution (initial number of resources) and then follows with a re-optimization process aimed to further reduce the resource requirements. The algorithm is based on a modified Heuristic Search method previously presented. The algorithm was tested first on a number of instances from the literature and then on the aforementioned system (a car seat cover manufacturer). The proposed approach shows not only good results in terms of performance but also shows the potential of Petri Nets for modeling and optimizing real-life systems. An implementation phase at the first stages of the process is underway at the time of writing.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abdallah, I. B., Elmaraghy, H. A., & Elmekkawy, T. Y. (2002). Deadlock-free scheduling in flexible manufacturing systems using Petri-Nets. International Journal of Production Research, 40(12), 2733–2756.
Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34, 391–401.
Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2), 149–156.
Bachman, A., Cheng, T., & Janiak, A. (2002). Scheduling start time dependent jobs to minimize the total weighted completion time. Journal of the Operational Research Society, 53, 688–693.
Gutiérrez, E., & Mejía, G. (2009). Scheduling complex manufacturing systems using a genetic algorithm. In 20th international conference on production research, Shanghai, China, 2–6 August 2009. In CD-ROM.
Kim, Y., Tatsuya, T., & Tatsuo, N. (2007). FMS scheduling based on timed Petri Net model and reactive graph search. Applied Mathematical Modelling, 31(6), 955–970.
Lawrence, S. (1984). Resource constraint scheduling: an experimental investigation of heuristic scheduling techniques. GSIA, Carnegie Mellon University.
Lee, D., & DiCesare, F. (1994). Scheduling flexible manufacturing systems using Petri Nets and heuristic search. IEEE Transactions on Robotics and Automation, 10(2), 123–131.
Low, C., & Wu, T.H. (2001). Mathematical modeling and heuristic approaches to operation scheduling problems in an FMS environment. International Journal of Production Research, 39(4), 689–708.
Meisels, A. & Lusternik, N. (1997). Experiments on networks of employee timetabling problems. In LNCS : Vol. 1408. Pract. theo. autom. timetab. II, Toronto, Canada (pp. 130–141). Berlin: Springer.
Mejía, G. E., & Montoya, C. E. (2007). Resource assignment and scheduling using Petri Nets and heuristic search. In Proceedings of the ICPR 19 (International conference on production research), Valparaíso, Chile.
Mejía, G., & Montoya, C. (2008). A Petri Net algorithm for minimizing total tardiness in flexible manufacturing systems. Annals of Operations Research, 164, 63–78.
Mejía, G., & Montoya, C. (2009). Scheduling manufacturing systems with blocking: a Petri Net approach. International Journal of Production Research, 47(22), 6261–6277.
Mejía, G., & Odrey, N. (2005). An approach using Petri Nets and improved heuristic search for manufacturing system scheduling. Journal of Manufacturing Systems, 24(2), 79–92.
Murata, T. (1989). Petri Nets: properties, analysis and applications. Proceedings of the IEEE, 77(4), 541–580.
Nhu, B., Ho, J., Cing, T., & Edmund, M. (2007). An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research, 179(2), 316–333.
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.
Rodammer, F., & Whit, K. (1988). A recent survey of production scheduling. IEEE Transactions on Systems, Man, and Cybernetics, 18(6), 841–851.
Xiong, H., & Zhou, M. (1998). Scheduling of semi-conductor test facility via Petri Nets and hybrid heuristic search. IEEE Transactions on Semiconductor Manufacturing, 11(3), 384–393.
Yu, H., Reyes, A., Cang, K., & Lloyd, S. (2003). Combined Petri Net modelling and AI based heuristic hybrid search for flexible manufacturing systems—part 1, Petri Net modelling and heuristic search. Computers and Industrial Engineering, 44, 527–543.
Zhang, X., & Bard, J.F. (2006). A multi-period machine assignment problem. European Journal of Operational Research, 170(2), 398–415.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mejía, G., Montoya, C. Applications of resource assignment and scheduling with Petri Nets and heuristic search. Ann Oper Res 181, 795–812 (2010). https://doi.org/10.1007/s10479-010-0686-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-010-0686-1