Control Systems and Computers

https://doi.org/10.15407/csc.2019.05.038

Control Systems and Computers, 2019, Issue 5 (283), pp. 38-47.

UDK 658.5

Tadeush Witkowski, Faculty of Production Engineering, Warsaw University of Technology, Plac Politechniki, 1, 00-661, Warsaw, Poland,Warsaw, Poland

The DABC and TLBO Algorithms for Solve Job Shop Scheduling Problem

This paper shows use Discrete Artificial Bee Colony and Teaching-Learning-Based Optimization algorithms for solving the job shop scheduling problem in order to minimize makespan (C_max value). The Job Shop Scheduling Problem is one of the most difficult problems as it is classified as an NP-hard one. Stochastic search techniques, such as evolutionary algorithms, are used to find a good solution. Our objective is to estimate efficiency of Discrete Artificial Bee Colony and Teaching-Learning-Based Optimization algorithms on many tests of job shop scheduling problem.

 Download full text! (In English).

Keywords: Discrete Artificial Bee Colony Algorithm; Teaching-Learning-Based Optimization; job shop scheduling problem;  makespan

1. Mesghouni, K., Hammadi, S., Borne, P., 2004. “Evolutionary Algorithms for Job Shop Scheduling”. J. Appl. Math. Comput. Sci., Vol. 14, No. 1, pp. 91-103.
2. Blazewicz, J., et al., 2007. Handbook on Scheduling; From Theory to Application, Springer, Berlin, Heidelberg, New York, 280 p.
3. Karaboga, D., Basturk, B., 2007. “Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems”, Springer-Verlag Berlin Heidelberg. IFSA 2007, LNAI 4529, pp. 789-798.
   https://doi.org/10.1007/978-3-540-72950-1_77
4. Li, J., Pan, Q., Gao, K., 2011. “Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems”, Int. J. Advance Manufacturing Technology, 55, pp. 1159-1169.
   https://doi.org/10.1007/s00170-010-3140-2
5. Li, J. Pan, Q. Xie, S. Wang, S., 2011. “A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems”, Int. J. of Computers, Communications & Control, Vol. VI, N 2 (June), pp. 286-296.
   https://doi.org/10.15837/ijccc.2011.2.2177
6. Önder, E. , Özdemir, M., Yildirim, B.F., 2013. “Combinatorial Optimization Using Artificial Bee Colony Algorithm And Particle Swarm Optimization Supported Genetic Algorithm”, Kafkas University Journal of Economics and Administrative Sciences Faculty, Vol. 4, Issue 6, pp. 59-70.
7. Yurtkuran, A., Emel, E., 2016. “An Enhanced Artificial Bee Colony Algorithm with Solution Acceptance Rule and Probabilistic Metasearch”, Hindawi Publishing Corporation Computational Intelligence and Neuroscience Vol. 13 p.
   https://doi.org/10.1155/2016/8085953
8. Lei, D., 2010. “A genetic algorithm for flexible job shop scheduling problem with fuzzy processing time”, Int. J. Prod. Res., 48, pp. 2995-3013.
   https://doi.org/10.1080/00207540902814348
9. Li, X., Yin, M., 2012. “A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem”, ScientiaIranica, 19 (6), pp. 1921-1935.
   https://doi.org/10.1016/j.scient.2012.10.034
10. Greedy algorithm, in: Paul E. Black, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, US.
11. Rao, R.V., Savsani, V.J., Vakharia, D.P., 2011. “Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems”, Computer-Aided Design, Vol. 43, Issue 3, pp. p303-315.
    https://doi.org/10.1016/j.cad.2010.12.015
12. Witkowski, T., Krzyżanowski, P., Vasylishyna, S., 2016. “Comparison of DABC and TLBO Metaheuristics for Solve Job Shop Scheduling Problem”, 12 International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD 2016), 13-15 August, Changsha.
13. Rao, R.V., Kalyankar, V.D., 2013. “Parameter optimization of modern machining processes using teaching-learning-based optimization algorithm”, Engineering Applications of Artificial Intelligence, Vol. 26, Issue 1, pp. 524-531.
    https://doi.org/10.1016/j.engappai.2012.06.007
14. Pezzella, F., Morganti, G., Ciaschetti, G., 2008. “A genetic algorithm for the flexible job-shop scheduling problem”, Comput. Oper. Res., Vol.35, Issue 10, pp. 3202-3212.
    https://doi.org/10.1016/j.cor.2007.02.014
15. Xu, Y., Wang, L., Wang, S.Y., Liu, M., 2015. “An effective teaching-learning based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time”, Neurocomputing, Vol.148, pp. 260-268.
    https://doi.org/10.1016/j.neucom.2013.10.042
16. Zhang, G., Shao, K., Li, P.,Gao, L., 2009. “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem”, Computers & Industrial Engineering, Vol. 56(4), pp. 1309-1318.
    https://doi.org/10.1016/j.cie.2008.07.021
17. Kloud, T., Koblasa, F., 2011. “Solving job shop scheduling with the computer simulation”, The International Journal of Transport & Logistics, 3, pp. 7-17.
18. Witkowski, T., Strojny, G., Antczak, P., 2007. “The Application Of Neural Networks For Flexible Job Shop Problem”. Int. J. of Factory Automation, Robotics, and Soft Computing, Int. Society for Advanced Research, Palermo, Italy, Issue 2, pp. 116-121.
19. 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, Springer-Verlag Berlin, Vol. 6215, pp. 319-328.
    https://doi.org/10.1007/978-3-642-14922-1_40
20. Witkowski, T., Elzway, S., Antczak, A., Antczak, P., 2007. “Representation of Solutions and Genetic Operators for Flexible Job Shop Problem”, Communications in Computer and Information Science, Advanced Intelligent Computing Theories and Applications. Springer-Verlag, Berlin Heidelberg , Vol. 2, pp. 256-265.
    https://doi.org/10.1007/978-3-540-74282-1_29

Received 10.10.2019