Logo PTI Logo FedCSIS

Communication Papers of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 37

Mushroom Picking Framework with Cache Memories for Solving Job Shop Scheduling Problem

,

DOI: http://dx.doi.org/10.15439/2023F9294

Citation: Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 37, pages 157–164 ()

Full text

Abstract. Applying population-based metaheuristics is a known method of solving difficult optimization problems. In this paper the search for the best solution is conducted by decentralized, self-organized agents, working in parallel threads, in the so called mushroom-picking method. The search is enhanced by remembering in which part of the recently improved solution the last successful change took place and intensifying the search in this part. A computational experiment shows that introducing the component for remembering the most recent changes may improve the results obtained by the model in the case of JSSP problems.

References

  1. F. Glover and M. Samorani, “Intensification, diversification and learning in metaheuristic optimization,” Journal of Heuristics, vol. 25, 03 2019. http://dx.doi.org/10.1007/s10732-019-09409-w
  2. J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA, USA: MIT Press, 1992. ISBN 0-262-11170-5
  3. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989.
  4. D. B. Fogel, “On the relationship between the duration of an encounter and the evaluation of cooperation in the iterated prisoner’s dilemma,” Evol. Comput., vol. 3, no. 3, pp. 349–363, 1995. http://dx.doi.org/10.1162/evco.1995.3.3.349. [Online]. Available: https://doi.org/10.1162/evco.1995.3.3.349
  5. Z. Michalewicz, “Genetic algorithms + data structures = evolution programs,” in Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/978-3-662-03315-9
  6. M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society, vol. 26 1, pp. 29–41, 1996. http://dx.doi.org/10.1109/3477.484436
  7. R. Poli, J. Kennedy, and T. M. Blackwell, “Particle swarm optimization,” Swarm Intelligence, vol. 1, pp. 33–57, 1995. http://dx.doi.org/10.1109/icnn.1995.488968
  8. T. Sato and M. Hagiwara, “Bee system: finding solution by a concentrated search,” 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, vol. 4, pp. 3954–3959 vol.4, 1997.
  9. H. Ma, S. Shen, M. Yu, Z. Yang, M. Fei, and H. Zhou, “Multi-population techniques in nature inspired optimization algorithms: A comprehensive survey,” Swarm Evol. Comput., vol. 44, pp. 365–387, 2019. http://dx.doi.org/10.1016/j.swevo.2018.04.011
  10. P. Jedrzejowicz, “Current trends in the population-based optimization,” in Computational Collective Intelligence, N. T. Nguyen, R. Chbeir, E. Exposito, P. Aniorté, and B. Trawiński, Eds. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-28377-3_4343. ISBN 978-3-030-28377-3 pp. 523–534.
  11. H. R. Er and N. Erdogan, “Parallel genetic algorithm to solve traveling salesman problem on mapreduce framework using hadoop cluster,” JSCSE, 01 2014. http://dx.doi.org/10.7321/jscse.v3.n3.57
  12. E. Alanzi and H. Bennaceur, “Hadoop mapreduce for parallel genetic algorithm to solve traveling salesman problem,” International Journal of Advanced Computer Science and Applications, vol. 10, 01 2019. http://dx.doi.org/10.14569/IJACSA.2019.0100814
  13. Y. Karouani and Z. Elhoussaine, “Efficient spark-based framework for solving the traveling salesman problem using a distributed swarm intelligence method,” in 2018 International Conference on Intelligent Systems and Computer Vision (ISCV), 2018. http://dx.doi.org/10.1109/ISACV.2018.8354075 pp. 1–6.
  14. P. Jedrzejowicz and I. Wierzbowska, “Apache spark as a tool for parallel population-based optimization,” in Intelligent Decision Technologies 2019, I. Czarnowski, R. J. Howlett, and L. C. Jain, Eds. Singapore: Springer Singapore, 2020. ISBN 978-981-13-8311-3 pp. 181–190.
  15. E. Alba, G. Luque, and S. Nesmachnow, “Parallel metaheuristics: Recent advances and new trends,” International Transactions in Operational Research, vol. 20, pp. 1–48, 08 2012. http://dx.doi.org/10.1111/j.1475-3995.2012.00862.x
  16. P. González, X. Pardo, R. Doallo, and J. Banga, “Implementing cloud-based parallel metaheuristics: an overview,” Journal of Computer Science and Technology, vol. 18, p. e26, 12 2018. http://dx.doi.org/10.24215/16666038.18.e26
  17. M. Essaid, L. Idoumghar, J. Lepagnot, and M. Brévilliers, “GPU parallelization strategies for metaheuristics: a survey,” International Journal of Parallel, Emergent and Distributed Systems, vol. 34, pp. 1–26, 01 2018. http://dx.doi.org/10.1080/17445760.2018.1428969
  18. H. Hu, W. Lei, X. Gao, and Y. Zhang, “Job-shop scheduling problem based on improved cuckoo search algorithm,” International Journal of Simulation Modelling, vol. 17, pp. 337–346, 06 2018. http://dx.doi.org/10.2507/IJSIMM17(2)CO8
  19. Z. Zhang, Z. Guan, J. Zhang, and X. Xie, “A novel job-shop scheduling strategy based on particle swarm optimization and neural network,” International Journal of Simulation Modelling, vol. 18, pp. 699–707, 12 2019. http://dx.doi.org/10.2507/IJSIMM18(4)CO18
  20. J. Zhu, Z. Shao, and C. Chen, “An improved whale optimization algorithm for job-shop scheduling based on quantum computing,” International Journal of Simulation Modelling, vol. 18, pp. 521–530, 09 2019. http://dx.doi.org/10.2507/IJSIMM18(3)CO13
  21. X. Chen, B. Zhang, and D. Gao, “Algorithm based on improved genetic algorithm for job shop scheduling problem,” in 2019 IEEE International Conference on Mechatronics and Automation (ICMA). IEEE Press, 2019. http://dx.doi.org/10.1109/ICMA.2019.8816334. ISBN 978-1-7281-1698-3 p. 951–956. [Online]. Available: https://doi.org/10.1109/ICMA.2019.8816334
  22. F. Wang, Y. Tian, and X. Wang, “A discrete wolf pack algorithm for job shop scheduling problem,” in 2019 5th International Conference on Control, Automation and Robotics (ICCAR), 2019. http://dx.doi.org/10.1109/IC-CAR.2019.8813444 pp. 581–585.
  23. A. Vital-Soto, A. Azab, and M. Baki, “Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility,” Journal of Manufacturing Systems, vol. 54, pp. 74–93, 01 2020. http://dx.doi.org/10.1016/j.jmsy.2019.11.010
  24. H. Piroozfard, K. Y. Wong, and A. D. Asl, “A hybrid harmony search algorithm for the job shop scheduling problems,” in 2015 8th International Conference on Advanced Software Engineering & Its Applications (ASEA), 2015. http://dx.doi.org/10.1109/ASEA.2015.23 pp. 48–52.
  25. R. Krishnaswamy and C. Rajendran, “A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan,” IOP Conference Series: Materials Science and Engineering, vol. 310, p. 012143, 02 2018. http://dx.doi.org/10.1088/1757-899X/310/1/012143
  26. H. Yu, Y. Gao, L. Wang, and J. Meng, “A hybrid particle swarm optimization algorithm enhanced with nonlinear inertial weight and gaussian mutation for job shop scheduling problems,” Mathematics, vol. 8, no. 8, p. 1355, Aug 2020. http://dx.doi.org/10.3390/math8081355. [Online]. Available: http://dx.doi.org/10.3390/math8081355
  27. C.-W. Tsai, H.-C. Chang, K.-C. Hu, and M.-C. Chiang, “Parallel coral reef algorithm for solving JSP on spark,” in 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2016. http://dx.doi.org/10.1109/SMC.2016.7844511 pp. 001 872–001 877.
  28. L. Sun, L. Lin, H. Li, and M. Gen, “Large scale flexible scheduling optimization by a distributed evolutionary algorithm,” Computers & Industrial Engineering, vol. 128, pp. 894–904, 2019. http://dx.doi.org/https://doi.org/10.1016/j.cie.2018.09.025. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S036083521830442X
  29. A. Dabah, A. Bendjoudi, A. AitZai, and N. Nouali-Taboudjemat, “Efficient parallel tabu search for the blocking job shop scheduling problem,” Soft Computing, vol. 23, p. 13283–13295, 12 2019. http://dx.doi.org/10.1007/s00500-019-03871-1
  30. P. Jedrzejowicz and I. Wierzbowska, “Parallelized swarm intelligence approach for solving TSP and JSSP problems,” Algorithms, vol. 13, no. 6, p. 142, Jun 2020. http://dx.doi.org/10.3390/a13060142. [Online]. Available: http://dx.doi.org/10.3390/a13060142
  31. P. Jedrzejowicz, E. Ratajczak-Ropel, and I. Wierzbowska, “A population-based framework for solving the job shop scheduling problem,” in Computational Collective Intelligence: 13th International Conference, ICCCI 2021, Rhodes, Greece, September 29 – October 1, 2021, Proceedings. Berlin, Heidelberg: Springer-Verlag, 2021. http://dx.doi.org/10.1007/978-3-030-88081-1_26. ISBN 978-3-030-88080-4 p. 347–359. [Online]. Available: https://doi.org/10.1007/978-3-030-88081-1_26
  32. S. Lawrence, “Resource constrained project scheduling - technical report,” Carnegie-Mellon University: Pittsburgh, PA, USA, Tech. Rep., 1984.
  33. M. A. Belmamoune, L. Ghomri, and Z. Yahouni, “Solving a job shop scheduling problem using Q-learning algorithm,” in Service Oriented, Holonic and Multi-Agent Manufacturing Systems for Industry of the Future, T. Borangiu, D. Trentesaux, and P. Leitão, Eds. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-24291-5_16. ISBN 978-3-031-24291-5 pp. 196–209.
  34. Y. Wei, Z. Othman, K. Mohd Daud, S. Yin, and Q. Luo, “Equilibrium optimizer and slime mould algorithm with variable neighborhood search for job shop scheduling problem,” Mathematics, vol. 10, p. 4063, 11 2022. http://dx.doi.org/10.3390/math10214063
  35. C.-S. Shieh, T.-T. Nguyen, W.-W. Lin, D.-C. Nguyen, and M.-F. Horng, “Modified coral reef optimization methods for job shop scheduling problems,” Applied Sciences, vol. 12, no. 19, p. 9867, Sep 2022. http://dx.doi.org/10.3390/app12199867. [Online]. Available: http://dx.doi.org/10.3390/app12199867