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

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.

• Sanjay Kumar Parjapati
• Ajai Jain

• Flexible Job Shop
• Genetic Algorithm
• Makespan
• Sequence Dependent Setup Times.

[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