Modeling and Simulation of Flow Shop Scheduling Problem through Petri Net Tools

Authors: Joselito Medina Marin, Norberto Hernández Romero, Juan Carlos Seck Tuoh Mora, Erick S. Martinez Gomez

Abstract:

The Flow Shop Scheduling Problem (FSSP) is a typical problem that is faced by production planning managers in Flexible Manufacturing Systems (FMS). This problem consists in finding the optimal scheduling to carry out a set of jobs, which are processed in a set of machines or shared resources. Moreover, all the jobs are processed in the same machine sequence. As in all the scheduling problems, the makespan can be obtained by drawing the Gantt chart according to the operations order, among other alternatives. On this way, an FMS presenting the FSSP can be modeled by Petri nets (PNs), which are a powerful tool that has been used to model and analyze discrete event systems. Then, the makespan can be obtained by simulating the PN through the token game animation and incidence matrix. In this work, we present an adaptive PN to obtain the makespan of FSSP by applying PN analytical tools.

Keywords: Flow-shop scheduling problem, makespan, Petri nets, state equation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124851

References:

[1] M.C. Zhou, and K. Venkatesh, Modeling, Simulation, and Control of Flexible Manufacturing Systems. New York: World Scientific, 1999.
[2] M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fourth Edition, New York: Springer, 2012.
[3] J.K. Lenstra, A.H.G. Kan, P. Brucker, “Complexity of machine scheduling problem,” Annals of Discrete Mathematics, vol. 1, pp. 343 – 362.
[4] A.H.G. Rinnooy Kan, Machine Scheduling Problems: Classification, Complexity and Computations, Nojhoff, The Hague, 1976.
[5] D.S. Palmer, “Sequencing jobs through a multistage process in the minimum total time: A quick method of obtaining a near-optimum,” Operational Research Quarterly, vol. 16, pp. 101-107, 1965.
[6] H.G. Campbell, R.A. Dudek, M.L. Smith, “A heuristic algorithm for the n job, m machine sequencing problem,” Management Science, vol. 16, no. 10, pp. B630-B637, 1970.
[7] D.G. Dannenbring, “An evaluation of flow shop sequencing heuristics,” Management Science, vol. 23, no. 11, pp. 1174-1182, 1977.
[8] M. Nawaz, E.E. Enscore Jr., I. Ham, “A heuristic algorithm for the m-machine, n-job flow shop sequencing problem,” OMEGA, vol. 11, no. 1, pp. 91-95, 1983.
[9] E. Taillard, “Some efficient heuristic methods for the flowshop sequencing problems,” European Journal of Operational Research, vol. 47, pp. 65-74, 1990.
[10] J. M. Framinan, R. Leisten, “An efficient constructive heuristic for flowtime minimisation in permutation flow shops,” OMEGA, vol. 31, pp. 311-317, 2003.
[11] J.M. Framinan, R. Leisten, R. Ruiz-Usano, “Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation,” European Journal of Operational Research, vol. 141, pp. 559-569, 2002.
[12] 1. Osman, C. Potts, “Simulated annealing for permutation flow shop scheduling,” OMEGA, vol. 17, no. 6, pp. 551-557, 1989.
[13] F. Ogbu, D. Smith, “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem,” Computers and Operations Research, vol. 17, no. 3, pp. 243-253, 1990.
[14] J. Grabowski, M. Wodecki, “A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion,” Computers and Operations Research, vol. 31, no. 11, pp. 1891-1909, 2004.
[15] E. Nowicki, C. Smutnicki, “A fast tabu search algorithm for the permutation flowshop problem”, European Journal of Operational Research, vol. 91, pp. 160-175, 1996.
[16] T. Aldowaisan, A. Allahverdi, “New heuristics for no-wait f1owshops to minimize makespan,” Computers and Operations Research, vol. 30, no. 8, pp. 1219-1231, 2003.
[17] T. Murata, H. Ishibuchi, H. Tallaka, “Genetic algorithms for f1owshop scheduling problems,” Computers and Industrial Engineering, vol. 30, no. 4, pp. 1601-1071, 1996.
[18] R. Ruiz, C. Maroto, J. Alcaraz, “Two new robust genetic algorithms for the flowshop scheduling problems,” OMEGA, vol. 34, pp. 461-476, 2006.
[19] C. Rajendran, H. Ziegler, “Ant-colony algorithms for permutation f1owshop scheduling to minimize makespan/total flowtime of jobs,” European Journal of Operational Research, vol. 155, no. 2, pp. 426-438, 2004.
[20] T. Stutzle, “An ant approach to the f1owshop problem,” In: Proceedings of the 6th European Congress on Intelligent Techniques and Soft Cmputing (EUFIT'98), Verlag Mainz, Aachen, Germany, pp. 1560-1564, 1998.
[21] T. Stutzle, “Applying iterated local search to the permutation f1owshop problem,” Technical Report, AIDA-98-04, Darmstad University of Technology, Computer Science Department, Intellctics Group, Darmstad, Germany, 1998.
[22] M.F. Tasgetiren, M. Sevkli, Y.C. Liang, and G. Gencyilmaz, “Particle swarm optimization algorithm for permutation flowshop sequencing problem,” In: Proceedings of the 4th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS2004), LNCS 3172, Brussels, Belgium, pp. 382-390, 2004.
[23] M.F. Tasgetiren, Y.C. Liang, M. Sevkli, G. Gencyilmaz, “Particle swarm optimization algorithm for makespan and total f1owtime minimization in the permutation f1owshop sequencing problem,” European Journal of Operational Research, 2006.
[24] T. Murata, “Petri Nets: Properties, Analysis and Applications,” Proceedings of the IEEE, vol. 77, no. 4, pp. 541 – 580, 1989.
[25] M.A. Gonzalez-Hernandez, “Metaheuristics solutions for Job-Shop Scheduling Problem with sequence-dependent setup times,” PhD Thesis. Universtiy of Oviedo, 2011.
[26] R. Qing-dao-er-ji, Wang, Y. “A new hybrid genetic algorithm for job shop scheduling problem.” Computers and Operations Research, vol. 39, pp. 2291-2299, 2012.
[27] Q.K. Pan, M.F. Tasgetiren, Y.C. Liang, “A Discrete Particle Swarm Optimization Algorithm for the Permutation Flowshop Sequencing Problem with Makespan Criterion,” Research and Development in Intelligent Systems XXIII, Springer London, pp. 19-31, 2007.
[28] Z. Zhao, G. Zhang, Z. Bing, “Scheduling Optimization for FMS Based on Petri Net Modeling and GA”, Proceedings of the IEEE International Conference on Automation and Logistics, pp. 422-427. August 2011, Chongqing, China.