Discrete Breeding Swarm for Cost Minimization of Parallel Job Shop Scheduling Problem

Authors: Tarek Aboueldah, Hanan Farag

Abstract:

Parallel Job Shop Scheduling Problem (JSSP) is a multi-objective and multi constrains NP-optimization problem. Traditional Artificial Intelligence techniques have been widely used; however, they could be trapped into the local minimum without reaching the optimum solution. Thus, we propose a hybrid Artificial Intelligence (AI) model with Discrete Breeding Swarm (DBS) added to traditional AI to avoid this trapping. This model is applied in the cost minimization of the Car Sequencing and Operator Allocation (CSOA) problem. The practical experiment shows that our model outperforms other techniques in cost minimization.

Keywords: Parallel Job Shop Scheduling Problem, Artificial Intelligence, Discrete Breeding Swarm, Car Sequencing and Operator Allocation, cost minimization.

References:

[1] Khaled Mesghouni, Slim Hammadi "Evolutionary algorithms for job-shop scheduling" International Journal of Applied Mathematics and Computer Science, Vol. 14, no.1. pp. 91-103 January 2004.
[2] Etiler, O., Toklu, B., Atak, M., Wilson, J. “A genetic algorithm for flow shop scheduling problems.” J.of the Ope. Res. Soc., vol. 55, pp. 830–835, 2004
[3] R. Kolisch and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: an update”, European Journal of Operational Research, vol. 174, no. 1, pp. 23–37, 2006.
[4] J. H. Holland, "Adaptation in Natural and Artificial Systems, " The University of Michigan Press.Ann Arbor. 1975.
[5] A. Lihu, and S. Holban," Top five most promising algorithms in scheduling" 5th International Symposium on Applied Computational Intelligence. IEEE, Timisoara, Romania, pp. 397 – 404. 2009
[6] Zhang Liping, Gao Liang, LiXinyu "A hybrid genetic algorithm and tabu search for multi-objective dynamic job shop scheduling problem" International Journal of Production Research, Vol. 51, pp. 3516-3531, 2013.
[7] Imen Driss, Kinza Mouss, Assia Laggoun "A new genetic algorithm for flexible job-shop scheduling problems."Congrès international de génieindustriel –CIGI2015 Québec, Canada 26-28.Octobre,2015.
[8] X. Wang, L. Gao, C. Zhang, and X. Shao, “A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem,” International Journal of Advanced Manufacturing Technology, vol. 51, no. 5–8, pp. 757–767, 2010.
[9] J. Kennedy, R.C. Eberhart Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, pp.1942-1948, 1995.
[10] Cheng “A hybrid particle swarm optimization for job shop scheduling problem”. Computers & Industrial Engineering. Vol. 51, Issue 4.pp791–808.2006.
[11] S. Karthikeyan, P. Asokan, S. Nickolas, Tom Page: A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems. Int. J. Bio Inspired Computation. Vol.7, Issue6, pp. 386-401, 2015.
[12] G. Moslehi and M. Mahnam, “A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search,” International Journal of Production Economics, vol. 129, no. 1, pp. 14–22, 2011.
[13] Kirkpatrick, S., C.D. Gelatt Jr. and M.P. Vecchi, "Optimization by simulated annealing." Science, 220: pp. 671-680.1983.
[14] Rui Zhang "A Simulated Annealing-Based Heuristic Algorithm for Job Shop Scheduling to Minimize Lateness" International Journal of Advanced Robotic.Vol.10, Issue 4.April 2013.
[15] R.S Nakandhrakumar and M Balachandar "Implementation of Simulated Annealing Technique for Optimizing Job Shop Scheduling Problem" International Journal of Advanced Mechanical Engineering. ISSN 2250-3234 Volume 4, Number 2. pp. 169-174, 2014,
[16] Alper Türkyılmaz, Özlem Şenvar, İrem Ünal & Serol Bulkan "A research survey: heuristic approaches for solving multi objective flexible job shop problems" Journal of Intelligent Manufacturing Vol. 31, pp.1949–1983, 2020.
[17] M. Settles, T. Soule, Breeding swarms: a GA/PSO hybrid, in: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO, Washington, DC, USA, 2005.
[18] S. Venkatesh, W. Fabens, "A heuristic-Based car-shop scheduling application." International Conference on tools in AI, IEEE, Arlington, VA, pp128 – 135, 1992.
[19] N. Shivasankaran, P. Senthil Kumar, G. Nallakumarasamy, K. Venkatesh Raja "Repair Shop Job Scheduling with Parallel Operators ad Multiple Constraints Using Simulated Annealing.” International Journal of Computational Intelligence Systems. Vol. 6, Issue 2, 2013.
[20] A.C. Nearchou, “The effect of various operators on the genetic search for large scheduling problems” International Journal of Production Economics, vol. 88(2), pp. 191-203, 2004.
[21] B. Kim and S. Kim, “Application of genetic algorithms for scheduling batch-discrete production system”, Production Planning & Control, 13(2), 155- 165, 2002.