Abstract

Job shop scheduling problem belongs to a class of NP-Hard problems. Hence, finding an optimal solution for this problem is a difficult task. In this study, a hybrid method consisting of Genetic Algorithm (GA) and Differential Evolution (DE) algorithm has been proposed for solving the Job Shop Scheduling problem (JSSP). These algorithms are evolutionary algorithms for solving optimization problems which refine the candidate solutions iteratively. The results of previous studies show that the application of genetic algorithm and differential evolution algorithm individually for this problem yield results close to the upper bounds. The proposed algorithm implemented in MATLAB R2013a uses minimization of makespan as the objective function. This algorithm has been tested on 50 instances of Taillard series (TA01-50) benchmark problem. The simulation results obtained by the proposed algorithm are better than those obtained by the IPSO-TSAB algorithm.

References

• Milosevic, M., Lukic, D., Durdev, M., Antic, A., and Borojevic, S., “An overview of Genetic Algorithms for Job Shop Scheduling problems”, Journal of Production Engineering, vol. 18, no. 2, pp. 11-15, 2015.
• Korytkowski, P., Rymaszewski, S., and Wisniewski, T., “Ant Colony Optimization for Job Shop Scheduling using multi-attribute dispatching rules”, International Journal of Advanced Manufacturing Technology, vol. 67, 2013.
• Nguyen, V. and Bao, H. P., “An Efficient Solution to the Mixed Shop Scheduling Problem Using a Modified Genetic Algorithm”, In: Procedia Computer Science, vol. 95, pp. 475-482, 2016.
• Yenisey, M. M. and Yagmahan, B., “Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends”, Omega, vol. 45, pp. 119-135, 2014.
• Huang, K. L. and Liao, C. J., “Ant colony optimization combined with taboo search for the job Shop scheduling problem”, Computers & operations research, vol. 35, no. 4, pp. 1030-1046, 2008.
• Dorndorf, U., Pesch, E. and Phan-Huy, T., “Solving the open shop scheduling problem”, Journal of Scheduling, vol. 4, no. 3, pp. 157-174, 2001.
• Zhang, R. and Wu, C., “A hybrid immune simulated annealing algorithm for the job shop scheduling problem”, Applied Soft Computing, vol. 10, no. 1, pp. 79-89, 2010.
• Li, J. Q., Pan, Q. K., Suganthan, P. N. and Chua, T. J., “A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem”, The International Journal of Advanced Manufacturing Technology, vol. 52, no. 5, pp. 683-697, 2011.
• Watanabe, M., Ida, K. and Gen, M., “A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem”, Computers & Industrial Engineering, vol. 48, no. 4, pp. 743-752, 2005.
• Lin, T. L., Horng, S. J., Kao, T. W., Chen, Y. H., Run, R. S., Chen, R. J., Lai, J. L. and Kuo, I. H., “An efficient job-shop scheduling algorithm based on particle swarm optimization”, Expert Systems with Applications, vol. 37, no. 3, pp. 2629-2636, 2010.
• Zhou, R., Nee, A. Y. C. and Lee, H. P., “Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems”, International Journal of Production Research, vol. 47, no. 11, pp. 2903-2920, 2009.
• Wu, C., Zhang, N., Jiang, J., Yang, J. and Liang, Y., “Improved bacterial foraging algorithms and their applications to job shop scheduling problems”, In: International Conference on Adaptive and Natural Computing Algorithms, Springer Berlin Heidelberg, 2007. pp. 562-569.
• Wisittipanich, W. and Kachitvichyanukul, V., “Differential evolution algorithm for job shop scheduling problem”, Industrial Engineering and Management Systems, vol. 10, no. 3, pp. 203-208, 2011.
• Gao, H., Kwong, S., Fan, B. and Wang, R., “A hybrid particle-swarm tabu search algorithm for solving job shop scheduling problems”, IEEE Transactions on Industrial Informatics, vol. 10, no. 4, pp. 2044-2054, 2014.
• Chang, H. C., Chen, Y. P., Liu, T. K. and Chou, J. H., “Solving the flexible job shop scheduling problem with makespan optimization by using a hybrid Taguchi-genetic algorithm”, IEEE, vol. 3, pp. 1740-1754, 2015.
• Goncalves, J. F., de Magalhaes Mendes, J. J. and Resende, M. G. C., “A hybrid genetic algorithm for the job shop scheduling problem”, European journal of operational research, vol. 167, no. 1, pp. 77-95, 2005.
• Wang, L. and Tang, D. B., “An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem”, Expert Systems with Applications, 2011.
• Qing-dao-er-ji, R. and Wang, Y., “A new hybrid genetic algorithm for job shop scheduling problem”, Computers & Operations Research, vol. 39, no. 10, pp. 2291-2299, 2012.
• Zhang, H., Yan, Q., Zhang, G. and Jiang, Z., “A Chaotic Differential Evolution Algorithm for Flexible Job Shop Scheduling”, In: Asian Simulation Conference, Springer, pp. 79-88, 2016.
• Ponsich, A. and Coello, C. A. C., “A hybrid differential evolution—tabu search algorithm for the solution of job-shop scheduling problems”, Applied Soft Computing, vol. 13, no. 1, pp. 462-474, 2013.
• Yuan, Y. and Xu, H., “Flexible job shop scheduling using hybrid differential evolution algorithms”, Computers & Industrial Engineering, vol. 65, no. 2, pp. 246-260, 2013.
• Vesterstrom, J. and Thomsen, R., “A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems”, Evolutionary Computation, CEC2004, IEEE, vol. 2, pp. 1980-1987, 2004.
• Kitayama, S., Arakawa, M. and Yamazaki, K., “Differential evolution as the global optimization technique and its application to structural optimization”, Applied Soft Computing, vol. 11, no. 4, pp. 3792-3803, 2011.
• Ying, W. and Bin, L., “Job-shop scheduling using genetic algorithm”, In: Systems, Man, and Cybernetics, IEEE International Conference, 1996. vol. 3, pp. 1994-1999.
• Taillard, E., “Benchmarks for basic scheduling problems”, European journal of operational research, vol. 64, no. 2, pp. 278-285, 1993.
• Chen, J. C., Wu, C. C., Chen, C. W. and Chen, K. H., “Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm”, Expert Systems with Applications, vol. 39, no. 11, pp. 10016-10021, 2012.
• Blazewicz, J., Domschke, W. and Pesch, E., “The job shop scheduling problem: Conventional and new solution techniques”, European journal of operational research, vol. 93, no. 1, pp. 1-33, 1996.
• Cheng, R., Gen, M. and Tsujimura, Y., “A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation”, Computers & industrial engineering, vol. 30, no. 4, pp. 983-997, 1996.
• Mesghouni, K., Hammadi, S. and Borne, P., “Evolutionary algorithms for job-shop scheduling”, International Journal of Applied Mathematics and Computer Science, vol. 14, no. 1, pp. 91-104, 2004.
• Ranjini, A. and Zoraida, B. S. E., “Analysis of selection schemes for solving job shop scheduling problem using genetic algorithm”, International Journal of Research in Engineering and Technology (IJRET), vol. 2, no. 11, pp. 2319-1163, 2013.
• Goldberg, D. E. and Deb, K., Foundations of Genetic Algorithms, vol. 1, CA: Morgan Kaufmann Publishers, 1991, A comparative analysis of selection schemes used in genetic algorithms, pp. 69-93.
• Aickelin, U. and Dowsland, K. A., “An indirect genetic algorithm for a nurse-scheduling problem”, Computers & Operations Research, vol. 31, no. 5, pp. 761-778, 2004.
• Yu, J. and Buyya, R., “Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms”, Scientific Programming, vol. 14, no. 3-4, pp. 217-230, 2006.
• De Falco, I., Della Cioppa, A. and Tarantino, E., “Mutation-based genetic algorithm: performance evaluation”, Applied Soft Computing, vol. 1, no. 4, pp. 285-299, 2002.
• Mohanty, B., Panda, S., and Hota, P. K., “Differential evolution algorithm based automatic generation control for interconnected power systems with non-linearity”, Alexandria Engineering Journal, vol. 53, no. 3, pp. 537-552, 2014.
• Storn, R., “On the usage of differential evolution for function optimization”, Fuzzy Information Processing Society, NAFIPS, 1996 Biennial Conference of the North American, IEEE. pp. 519-523.
• Zaharie, D., “A comparative analysis of crossover variants in differential evolution”, In Proceedings of International Multiconference on Computer Science and Information Technology (IMCSIT), 2007. pp. 171-181.
• Gao, A., and Zhao, C., “Parameter Controlling and Adjusting Strategy of Differential Evolution Algorithm”, Technical Journal of the Faculty of Engineering (TJFE), vol. 39, no. 5, pp. 351-357, 2016.