{"title":"Modeling and Simulation of Flow Shop Scheduling Problem through Petri Net Tools","authors":"Joselito Medina Marin, Norberto Hern\u00e1ndez Romero, Juan Carlos Seck Tuoh Mora, Erick S. Martinez Gomez","volume":113,"journal":"International Journal of Computer and Information Engineering","pagesStart":936,"pagesEnd":941,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10004669","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.<\/p>\r\n","references":"[1]\tM.C. Zhou, and K. Venkatesh, Modeling, Simulation, and Control of Flexible Manufacturing Systems. New York: World Scientific, 1999.\r\n[2]\tM.L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fourth Edition, New York: Springer, 2012.\r\n[3]\tJ.K. Lenstra, A.H.G. Kan, P. Brucker, \u201cComplexity of machine scheduling problem,\u201d Annals of Discrete Mathematics, vol. 1, pp. 343 \u2013 362.\r\n[4]\tA.H.G. Rinnooy Kan, Machine Scheduling Problems: Classification, Complexity and Computations, Nojhoff, The Hague, 1976.\r\n[5]\tD.S. Palmer, \u201cSequencing jobs through a multistage process in the minimum total time: A quick method of obtaining a near-optimum,\u201d Operational Research Quarterly, vol. 16, pp. 101-107, 1965.\r\n[6]\tH.G. Campbell, R.A. Dudek, M.L. Smith, \u201cA heuristic algorithm for the n job, m machine sequencing problem,\u201d Management Science, vol. 16, no. 10, pp. B630-B637, 1970.\r\n[7]\tD.G. Dannenbring, \u201cAn evaluation of flow shop sequencing heuristics,\u201d Management Science, vol. 23, no. 11, pp. 1174-1182, 1977.\r\n[8]\tM. Nawaz, E.E. Enscore Jr., I. Ham, \u201cA heuristic algorithm for the m-machine, n-job flow shop sequencing problem,\u201d OMEGA, vol. 11, no. 1, pp. 91-95, 1983.\r\n[9]\tE. Taillard, \u201cSome efficient heuristic methods for the flowshop sequencing problems,\u201d European Journal of Operational Research, vol. 47, pp. 65-74, 1990.\r\n[10]\tJ. M. Framinan, R. Leisten, \u201cAn efficient constructive heuristic for flowtime minimisation in permutation flow shops,\u201d OMEGA, vol. 31, pp. 311-317, 2003.\r\n[11]\tJ.M. Framinan, R. Leisten, R. Ruiz-Usano, \u201cEfficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation,\u201d European Journal of Operational Research, vol. 141, pp. 559-569, 2002.\r\n[12]\t1. Osman, C. Potts, \u201cSimulated annealing for permutation flow shop scheduling,\u201d OMEGA, vol. 17, no. 6, pp. 551-557, 1989.\r\n[13]\tF. Ogbu, D. Smith, \u201cThe application of the simulated annealing algorithm to the solution of the n\/m\/Cmax flowshop problem,\u201d Computers and Operations Research, vol. 17, no. 3, pp. 243-253, 1990.\r\n[14]\tJ. Grabowski, M. Wodecki, \u201cA very fast tabu search algorithm for the permutation flowshop problem with makespan criterion,\u201d Computers and Operations Research, vol. 31, no. 11, pp. 1891-1909, 2004.\r\n[15]\tE. Nowicki, C. Smutnicki, \u201cA fast tabu search algorithm for the permutation flowshop problem\u201d, European Journal of Operational Research, vol. 91, pp. 160-175, 1996.\r\n[16]\tT. Aldowaisan, A. Allahverdi, \u201cNew heuristics for no-wait f1owshops to minimize makespan,\u201d Computers and Operations Research, vol. 30, no. 8, pp. 1219-1231, 2003.\r\n[17]\tT. Murata, H. Ishibuchi, H. Tallaka, \u201cGenetic algorithms for f1owshop scheduling problems,\u201d Computers and Industrial Engineering, vol. 30, no. 4, pp. 1601-1071, 1996.\r\n[18]\tR. Ruiz, C. Maroto, J. Alcaraz, \u201cTwo new robust genetic algorithms for the flowshop scheduling problems,\u201d OMEGA, vol. 34, pp. 461-476, 2006.\r\n[19]\tC. Rajendran, H. Ziegler, \u201cAnt-colony algorithms for permutation f1owshop scheduling to minimize makespan\/total flowtime of jobs,\u201d European Journal of Operational Research, vol. 155, no. 2, pp. 426-438, 2004.\r\n[20]\tT. Stutzle, \u201cAn ant approach to the f1owshop problem,\u201d In: Proceedings of the 6th European Congress on Intelligent Techniques and Soft Cmputing (EUFIT'98), Verlag Mainz, Aachen, Germany, pp. 1560-1564, 1998.\r\n[21]\tT. Stutzle, \u201cApplying iterated local search to the permutation f1owshop problem,\u201d Technical Report, AIDA-98-04, Darmstad University of Technology, Computer Science Department, Intellctics Group, Darmstad, Germany, 1998.\r\n[22]\tM.F. Tasgetiren, M. Sevkli, Y.C. Liang, and G. Gencyilmaz, \u201cParticle swarm optimization algorithm for permutation flowshop sequencing problem,\u201d In: Proceedings of the 4th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS2004), LNCS 3172, Brussels, Belgium, pp. 382-390, 2004.\r\n[23]\tM.F. Tasgetiren, Y.C. Liang, M. Sevkli, G. Gencyilmaz, \u201cParticle swarm optimization algorithm for makespan and total f1owtime minimization in the permutation f1owshop sequencing problem,\u201d European Journal of Operational Research, 2006.\r\n[24]\tT. Murata, \u201cPetri Nets: Properties, Analysis and Applications,\u201d Proceedings of the IEEE, vol. 77, no. 4, pp. 541 \u2013 580, 1989.\r\n[25]\tM.A. Gonzalez-Hernandez, \u201cMetaheuristics solutions for Job-Shop Scheduling Problem with sequence-dependent setup times,\u201d PhD Thesis. Universtiy of Oviedo, 2011.\r\n[26]\tR. Qing-dao-er-ji, Wang, Y. \u201cA new hybrid genetic algorithm for job shop scheduling problem.\u201d Computers and Operations Research, vol. 39, pp. 2291-2299, 2012.\r\n[27]\tQ.K. Pan, M.F. Tasgetiren, Y.C. Liang, \u201cA Discrete Particle Swarm Optimization Algorithm for the Permutation Flowshop Sequencing Problem with Makespan Criterion,\u201d Research and Development in Intelligent Systems XXIII, Springer London, pp. 19-31, 2007.\r\n[28]\tZ. Zhao, G. Zhang, Z. Bing, \u201cScheduling Optimization for FMS Based on Petri Net Modeling and GA\u201d, Proceedings of the IEEE International Conference on Automation and Logistics, pp. 422-427. August 2011, Chongqing, China.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 113, 2016"}