Particle swarm optimization and discrete artificial bee colony algorithms for solving production scheduling problems
Tadeusz Witkowski
Abstrakt
This paper shows the use of Discrete Artificial Bee Colony (DABC) and Particle Swarm Optimization (PSO) algorithm for solving the job shop scheduling problem (JSSP) with the objective of minimizing makespan. The Job Shop Scheduling Problem is one of the most difficult problems, as it is classified as an NP-complete one. Stochastic search techniques such as swarm and evolutionary algorithms are used to find a good solution. Our objective is to evaluate the efficiency of DABC and PSO swarm algorithms on many tests of JSSP problems. DABC and PSO algorithms have been developed for solving real production scheduling problem too. The experiment results indicate that this problem can be effectively solved by PSO and DABC algorithms.
Słowa kluczowe:
Discrete Artificial Bee Colony, Particle Swarm Optimization, production scheduling problem, makespanBibliografia
Abu-Srhalm A., Al-Hasan M. 2015. Hybrid Algorithm using Genetic Algorithm and Cuckoo Search Algorithm for Job Shop Scheduling Problem. International Journal of Computer Science Issues, 12(2): 288-292.
Adams J., Balas E., Zawack D. 1988. The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3): 391–401.
Błażewicz J., Ecker K., Pesch E., Schmidt G., Węglarz J. 2007. Handbook on Scheduling; From Theory to Application. Springer, Berlin, Heidelberg, New York.
Fisher H., Thompson G. 1963. Probabilistic Learning combinations of local job shop scheduling rules. Englewood Cliffs, New York, Prentice-Hall.
Graczyk P. 2017. Particle swarm optimization for job shop scheduling (master thesis). Warsaw University of Technology, Warsaw.
Krause, J., Cordeiro, J., Parpinelli, R.S., Lopes H.S. 2013. A Survey of Swarm Algorithms Applied to Discrete Optimization Problems. In: Swarm Intelligence and Bio-Inspired Computation. Eds. X.-S. Yang, Z. Cui, R. Xiao, A.H. Gandomi, M. Karamanoglu. Elsevier Inc., p. 169-191
Karaboga D., Basturk B. 2007. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems. In: Lecture Notes in Artificial Intelligence. Eds. P. Melin, O. Castillo, L.T. Aguilar, W. Pedrycz. Springer-Verlag, Berlin, Heidelberg, p. 789–798.
Kloud T., Koblasa F. 2011. Solving job shop scheduling with the computer simulation. The International Journal of Transport & Logistics, 3: 7-17.
Lawrence S. 1984. Resource constrained project scheduling, An experimental investigation of heuristic scheduling techniques. Technical Report, GSIA, Carnegie Mellon University.
Mesghouni K., Hammadi S., Borne P. 2004. Evolutionary Algorithms for Job Shop Scheduling. International Journal of Applied Mathematics and Computer Science, 14(1): 91–103.
Rameshkumar K., Rajendran C. 2018. A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan. IOP Conference Series: Materials Science and Engineering, 310: 10.
Shua D.Y., Hsu Ch.Y. 2006. A hybrid particle swarm optimization for job shop scheduling problems. Computers & Industrial Engineering, 51: 791-808.
Song X., Yang C., Qiu-Hong M. 2008. Study on particle swarm algorithm for Job Shop Scheduling Problems. Systems Engineering and Electronics, 30(12): 2398-2401.
Storer R., Wu D., Vaccari R. 1992, New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling. Management Science, 38: 1495-1509.
Surekha P., Sumathi S. 2010. PSO and ACO based approach for solving combinatorial Fuzzy Job Shop Scheduling. International Journal of Computer Technology and Applications, 2(1): 112-120.
Witkowski T., Strojny G., Antczak P. 2007. The Application of Neural Networks for Flexible Job Shop Problem. International Journal of Factory Automation, Robotics and Soft Computing, 2: 116-121.
Witkowski T., Antczak A., Antczak P. 2010. Comparison of Optimality and Robustness between SA, TS and GRASP Metaheuristics in FJSP Problem. Lecture Notes in Computer Science, 6215: 319-328.
Witkowski T. 2016. Scheduling Algorithms for Flexible Job Shop Scheduling. Wydawnictwo Naukowe PWN, Warszawa.
Witkowski T., Krzyżanowski P., Vasylishyna S. 2016. Comparison of DABC and TLBO Metaheuristics for Solve Job Shop Scheduling Problem. 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery, Changsha, China (poster).
Adams J., Balas E., Zawack D. 1988. The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3): 391–401.
Błażewicz J., Ecker K., Pesch E., Schmidt G., Węglarz J. 2007. Handbook on Scheduling; From Theory to Application. Springer, Berlin, Heidelberg, New York.
Fisher H., Thompson G. 1963. Probabilistic Learning combinations of local job shop scheduling rules. Englewood Cliffs, New York, Prentice-Hall.
Graczyk P. 2017. Particle swarm optimization for job shop scheduling (master thesis). Warsaw University of Technology, Warsaw.
Krause, J., Cordeiro, J., Parpinelli, R.S., Lopes H.S. 2013. A Survey of Swarm Algorithms Applied to Discrete Optimization Problems. In: Swarm Intelligence and Bio-Inspired Computation. Eds. X.-S. Yang, Z. Cui, R. Xiao, A.H. Gandomi, M. Karamanoglu. Elsevier Inc., p. 169-191
Karaboga D., Basturk B. 2007. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems. In: Lecture Notes in Artificial Intelligence. Eds. P. Melin, O. Castillo, L.T. Aguilar, W. Pedrycz. Springer-Verlag, Berlin, Heidelberg, p. 789–798.
Kloud T., Koblasa F. 2011. Solving job shop scheduling with the computer simulation. The International Journal of Transport & Logistics, 3: 7-17.
Lawrence S. 1984. Resource constrained project scheduling, An experimental investigation of heuristic scheduling techniques. Technical Report, GSIA, Carnegie Mellon University.
Mesghouni K., Hammadi S., Borne P. 2004. Evolutionary Algorithms for Job Shop Scheduling. International Journal of Applied Mathematics and Computer Science, 14(1): 91–103.
Rameshkumar K., Rajendran C. 2018. A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan. IOP Conference Series: Materials Science and Engineering, 310: 10.
Shua D.Y., Hsu Ch.Y. 2006. A hybrid particle swarm optimization for job shop scheduling problems. Computers & Industrial Engineering, 51: 791-808.
Song X., Yang C., Qiu-Hong M. 2008. Study on particle swarm algorithm for Job Shop Scheduling Problems. Systems Engineering and Electronics, 30(12): 2398-2401.
Storer R., Wu D., Vaccari R. 1992, New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling. Management Science, 38: 1495-1509.
Surekha P., Sumathi S. 2010. PSO and ACO based approach for solving combinatorial Fuzzy Job Shop Scheduling. International Journal of Computer Technology and Applications, 2(1): 112-120.
Witkowski T., Strojny G., Antczak P. 2007. The Application of Neural Networks for Flexible Job Shop Problem. International Journal of Factory Automation, Robotics and Soft Computing, 2: 116-121.
Witkowski T., Antczak A., Antczak P. 2010. Comparison of Optimality and Robustness between SA, TS and GRASP Metaheuristics in FJSP Problem. Lecture Notes in Computer Science, 6215: 319-328.
Witkowski T. 2016. Scheduling Algorithms for Flexible Job Shop Scheduling. Wydawnictwo Naukowe PWN, Warszawa.
Witkowski T., Krzyżanowski P., Vasylishyna S. 2016. Comparison of DABC and TLBO Metaheuristics for Solve Job Shop Scheduling Problem. 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery, Changsha, China (poster).
Witkowski, T. (2019). Particle swarm optimization and discrete artificial bee colony algorithms for solving production scheduling problems. Technical Sciences, 22(1), 61–74. https://doi.org/10.31648/ts.4348
Tadeusz Witkowski
