Optimization of Flexible Job Shop Scheduling Problem with Sequence Dependent Setup Times Using Genetic Algorithm Approach

Authors: Sanjay Kumar Parjapati, Ajai Jain

Abstract:

This paper presents optimization of makespan for ‘n’ jobs and ‘m’ machines flexible job shop scheduling problem with sequence dependent setup time using genetic algorithm (GA) approach. A restart scheme has also been applied to prevent the premature convergence. Two case studies are taken into consideration. Results are obtained by considering crossover probability (pc = 0.85) and mutation probability (pm = 0.15). Five simulation runs for each case study are taken and minimum value among them is taken as optimal makespan. Results indicate that optimal makespan can be achieved with more than one sequence of jobs in a production order.

Keywords: Flexible Job Shop, Genetic Algorithm, Makespan, Sequence Dependent Setup Times.

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

References:

[1] Al-Hinai, N. and ELMekkawy, T.Y.; (2011) “Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm”, International Journal of Production Economics, Vol. 132, pp 279-291.
[2] Allahverdi, A., Ng, C.T., Cheng, T.C.E. and Kovalyov Y. M. (2008), A survey of scheduling problems with setup times or costs, European journal of Operational Research, Vol. 187, pp 985-1032.
[3] Asadzadeh, L. and Zamanifar, K.; (2010) “An Agent Based Parallel Approach for the Job Shop Scheduling Problem with Genetic Algorithm”. Mathematical and Computer Modelling, Vol. 52, pp 1957- 1965.
[4] Bagheri, A. and Zandieh, M. (2011) “Bi-criteria flexible job shop scheduling with sequence-dependent setup times-Variable neighborhood search approach” Journal of Manufacturing Systems, Vol. 30, pp 8-15.
[5] Chen, J.C., Wu, C.C., Chen, C.W. and Chen, K.H. (2012) “Flexible Job Shop Scheduling with Parallel Machines using Genetic Algorithm and Grouping Genetic Algorithm”. Expert System with Applications, Vol. 39, pp 10016-10021.
[6] Deb, K. (2003), Optimization for Engineering Design, Algorithm and Examples, Prentice Hall, New Delhi, India.
[7] Dhingra, A. (2010), “Multi objective flow shop scheduling using metaheuristics”, unpublished Ph.D. dissertation, N.I.T. Kurukshetra.
[8] Luh P.B., Gou, L., Zhang, Y., Nagahora, T., Tsuji, M., Yoneda, K., Hasegawa, T., Kyoya, Y., and Kano, T. (1998), “Job shop scheduling with group dependent setup, finite buffers and long time horizon”, Journal of Annals of Operation Research, Vol. 76, pp233-259
[9] Mitchell, M. (2002), An introduction to genetic algorithm, Prentice Hall, New Delhi, India.
[10] Moghaddas, R. and Houshmand, M. “Job Shop Scheduling Problem with Sequence Dependent Setup Times”. Multi Conference of Engineers and Computer Scientists, March 19-21, 2008, Hong Kong.
[11] Moon, I., Lee, S. and Bae, H. (2008) “Genetic Algorithms for Job Shop Scheduling Problems with Alternate Routings”. International Journal of Production Research, Vol. 46, pp 2695-2705.
[12] Motaghedi, A., Sabri-laghaie, K. and Heydari, M. (2010) “Solving Flexible Job Shop Scheduling with Multi Objective Approach”. International Journal of Industrial Engineering & Production Research, Vol. 21, pp 197-209.
[13] Mousakhani, M. (2013), “Sequence Dependent Setup Times Flexible Job Shop Scheduling Problem to Minimize Total Tardiness”. International Journal of Production Research available online: http://dx.doi.org/10.1080/00207543.2012.746480
[14] Naderi, B., Ghomi S.M.T.F. and Aminnayeri, M. (2010) “A high performing metaheuristic for job shop scheduling with sequence dependent setup times”, Applied Soft Computing 10 (2010) pp 703-710
[15] Parjapati, S.K. (2013), “Flexible job shop scheduling optimization with sequence dependent set up times using genetic algorithm approach”, unpublished M.Tech. dissertation, N.I.T., Kurukshetra.
[16] Pinedo, M. (2001), Scheduling: Theory, Algorithm, and Systems, Prentice Hall, New York.
[17] Ruiz, R. and Maroto, C. (2006), “A genetic algorithm for hybrid flow shops with sequence dependent setup times and machine eligibility”, European Journal of Operational Research, Vol. 169, pp 781-800.
[18] Roshanaei, V., Esfehani, M.M.S. and Zandieh, M. (2010) “ Integrating non-preemptive open shop scheduling with sequence-dependent setup times using advanced metaheuristics”, Expert Systems with Applications, Vol. 37, pp 259-266
[19] Tang, J., Zhang, G., Lin, B. and Zhang B. (2011) “A Hybrid Algorithm for Flexible Job-Shop Scheduling Problem”. Advanced in Control Engineering and Information Science, Vol. 15, pp 3678-3683.
[20] Wang, L., Wang, S. and Liu, M. (2013) “A Pareto Based Estimation of Distribution Algorithm for the Multi Objective Flexible Job Shop Scheduling Problem”. International Journal of Production Research, available online: http://dx.doi.org/10.1080/00207543.2012.752588
[21] Wang, Y.M., Li, H.Y. and Wang, J. (2009), “Genetic Algorithm with New Encoding Scheme for Job Shop Scheduling”. International Journal of Advanced Manufacturing Technology. Vol. 44, pp 977-984.
[22] Xing, Y.J., Wang, Z. Q., Sun, J. and Meng, J.J. (2006), “A Multi Objective Fuzzy Genetic Algorithm for Job Shop Scheduling Problems”, Journal of Achievements in Material and Engineering, Vol. 17, Issue 1- 2, pp 297-300.
[23] Xu, L., Shuang, W. and Ming, H. (2009), “Application on Job Shop Scheduling with Genetic Algorithm based on Mixed Strategy”. IEEE International Conference on Chinese Control and Decision 2009, pp 2007-2009 Guilin.
[24] Zhang G., Shao X., Li P. and Gao L. (2009) “An effective hybrid particle swarm optimization algorithm for multi-objective flexible jobshop scheduling problem”, Computer and industrial engineering, Vol. 56, pp 1309-1318.
[25] Ziaee, M. (2014) “ An Efficient Heuristic Algorithm for Flexible Job Shop Scheduling with maintenance Constrain” Applied Mathematics and Sciences, Vol. 1, No. 1, May 2014