Particle Swarm Optimization and Tabu Search Hybrid Algorithm for Flexible Job Shop Scheduling Problem – Analysis of Test Results

Toshev, Asen

doi:10.2478/cait-2019-0034

Abstract

The paper presents a hybrid metaheuristic algorithm, including a Particle Swarm Optimization (PSO) procedure and elements of Tabu Search (TS) metaheuristic. The novel algorithm is designed to solve Flexible Job Shop Scheduling Problems (FJSSP). Twelve benchmark test examples from different reference sources are experimentaly tested to demonstrate the performance of the algorithm. The obtained mean error for the deviation from optimality is 0.044%. The obtained test results are compared to the results in the reference sources and to the results by a genetic algorithm. The comparison illustrates the good performance of the proposed algorithm. Investigations on the base of test examples with a larger dimension will be carried out with the aim of further improvement of the algorithm and the quality of the test results.

References

1. Adams, J., E. Balas, D. Zawack. The Shifting Bottleneck Procedurefor Job Shop Scheduling. – Management Science, Vol. 34, 1988, No 3, pp. 391-401.10.1287/mnsc.34.3.391
Search in Google Scholar Back to article
2. Aiex, R. M., S. Binato, M. G. C. Resende. Parallel GRASPwith Path-Relinkingfor Job Shop Scheduling. – Parallel Computing, Vol. 29, 2003, pp. 393-430.10.1016/S0167-8191(03)00014-0
Search in Google Scholar Back to article
3. Balas, E., A. Vazacopoulos. Guided Local Searchwith Shifting Bottleneckfor Job Shop Scheduling. – Management Science, Vol. 44, 1998, No 2, pp. 262-275.10.1287/mnsc.44.2.262
Search in Google Scholar Back to article
4. Bierwirth, C., D. C. Mattfeld. Production Schedulingand Reschedulingwith Genetic Algorithms. – Evolutionary Computation, Vol. 7, 1999, No 1, pp. 1-17.10.1162/evco.1999.7.1.1
Search in Google Scholar Back to article
5. Bosejko, W., M. Uchronski, M. Wodecki. Flexible Job Shop Scheduling Problem – Parallel Tabu Search Algorithmfor Multi-GPU. – Arhivesof Control Sciences, Vol. 22, 2012, No 4, pp. 389-397.10.2478/v10170-011-0030-2
Search in Google Scholar Back to article
6. Brinkkötter, W., P. Brucker. Solving Open Benchmark Problemsforthe Job Shop Problem. – J. Scheduling, Vol. 4. 2001, pp. 53-64.10.1002/1099-1425(200101/02)4:1<;53::AID-JOS59>3.0.CO;2-Y
Search in Google Scholar Back to article
7. Brucker, P. The Job-Shop Problem: Oldand New Challenges. – In: Proc. of 3rd Multidisciplinary International Scheduling Conference, Paris, 28-31 August, 2007. http://www.mistaconference.org/2007/papers/The%20Job%20Shop%20Problem%20Old%20and%20New%20Challenges.pdf
Search in Google Scholar Back to article
8. Brucker, P., R. Schlie. Job Shopwith Multi-Purpose Machine. – Computing, Vol. 45, 1990, pp. 369-375.10.1007/BF02238804
Search in Google Scholar Back to article
9. Fattahi, P., M. Saidi Mehrabad, F. Jolai. Mathematical Modelingand Heuristic Approachesto Flexible Job Shop Scheduling Problems. – Journalof Intelligent Manufacturing, Vol. 18, 2007, pp. 331-342.10.1007/s10845-007-0026-8
Search in Google Scholar Back to article
10. Garey, M., D. Johnson, R. Sethi. The Complexityof Flowshopand Jobshop Scheduling. – Mathematicsof Operations Research, Vol. 1, 1976, No 2, pp. 117-129.10.1287/moor.1.2.117
Search in Google Scholar Back to article
11. Ge, H., W. Du, F. Qian. A Hybrid Algorithm Basedon Particle Swarm Optimizationand Simulated Annealingfor Job Shop Scheduling. 2007. http://www.paper.edu.cn10.1109/ICNC.2007.44
Search in Google Scholar Back to article
12. Geiger, M. J. Research Report. RR-12-01-01, January 2012, ISSN: 2192-0826, Helmut Schmidt University, Hamburg, Germany. https://d-nb.info/1023241773/34
Search in Google Scholar Back to article
13. Glover, F. Tabu Search – Part 1. – ORSA Journalon Computing, Vol. 1, 1989, No 3, pp. 190-206.10.1287/ijoc.1.3.190
Search in Google Scholar Back to article
14. Glover, F. Tabu Search – Part 2. – ORSA Journalon Computing, Vol. 2, 1990, No 1, pp. 4-32.10.1287/ijoc.2.1.4
Search in Google Scholar Back to article
15. Glover, F., M. Laguna, R. Marti. Principlesof Tabu Search, 2003. https://www.uv.es/~rmarti/paper/docs/ts1.pdf
Search in Google Scholar Back to article
16. Guliashki, V., L. Kirilov. A Reference Point Genetic Algorithmfor Multi-Criteria Job Shop Scheduling Problems. – In: Proc. of International Conferenceon Information Technologies (InfoTech 2015), 29-th Issue, R. Romanski, Ed. 17-18 September 2015, Varna, St. St. Constantineand Elena Resort, Bulgaria, pp. 10-18. ISSN: 1314-1023.
Search in Google Scholar Back to article
17. Huang, Z. A Modified Shifting Bottleneck Procedurefor Job Shop Scheduling, 2005. http://www.paper.edu.cn
Search in Google Scholar Back to article
18. Gautam, J. V., H. B. Prajapati, V. K. Dabhi, S. Chaudhary. – Empirical Studyof Job Scheduling Algorithmsin Hadoop MapReduce. – Cyberneticsand Information Technologies, Vol. 17, 2017, No 1, Sofia. ISSN: 1311-9702.10.1515/cait-2017-0012
Search in Google Scholar Back to article
19. Kacem, I., S. Hammadi, P. Borne. Pareto-Optimality Approachfor Flexible Job-Shop Scheduling Problems: Hybridizationof Evolutionary Algorithmsand Fuzzy Logic. – Mathematicsand Computersin Simulation, Vol. 60, 2002, No 3-5, pp. 245-276.10.1016/S0378-4754(02)00019-8
Search in Google Scholar Back to article
20. Kennedy, J., R. C. Eberhart. A Diskrete Binary Versionofthe Particle Swarm Algorithm. – In: Proc. of Conference Systems Man Cybernetics, NJ, Piscataway, 1997, pp. 4104-4108.10.1109/ICSMC.1997.637339
Search in Google Scholar Back to article
21. Lawler, E., J. Lenstra, A. Rinnooy Kan, D. Shmoys. Sequencingand Scheduling: Algorithmsand Complexity. – In: A. H. G. Rinnooy Kan, S. C. Graves, P. H. Zipkin, Eds. Logisticsof Productionand Inventory, Vol. 4, Elsevier, 1993, Chapter 9, pp. 445-522.10.1016/S0927-0507(05)80189-6
Search in Google Scholar Back to article
22. Lenstra, J. K., A. R. Kan, P. Brucker. Complexityof Machine Scheduling Problems. – Annalsof Discrete Mathematics, Vol. 1, 1977, pp. 343-362.10.1016/S0167-5060(08)70743-X
Search in Google Scholar Back to article
23. Li, J., Q. Pan, S. Xie, J. Liang. A Hybrid Pareto-Based Tabu Searchfor Multi-Objective Flexible Job Shop Scheduling Problemwith E/T Penalty. – Advancesin Swarm Intelligence, Lecture Notesin Computer Science, Vol. 6145, 2010, pp. 620-627.10.1007/978-3-642-13495-1_76
Search in Google Scholar Back to article
24. Low, C., Y. Yip, T.-H. Wu. Modellingand Heuristicsof FMS Schedulingwith Multiple Objectives. – Computers & Operations Research, Vol. 33, 2006, pp. 674-694.10.1016/j.cor.2004.07.013
Search in Google Scholar Back to article
25. Olteanu, M., N. Paraschiv, P. Koprinkova-Hristova. Genetic Algorithmsvs. Knowledge-Based Controlof PHB Production. – Cyberneticsand Information Technologies, Vol. 19, 2019, No 2. ISSN: 1311-9702.10.2478/cait-2019-0018
Search in Google Scholar Back to article
26. Mastrollili, M., L. M. Gambardela. Effective Neighborhood Functionsforthe Flexible Job Shop Scheduling Problem.
Search in Google Scholar Back to article
27. Mattfeld, D. Evolutionary Searchandthe Job Shop: Investigationon Genetic Algorithmsfor Production Scheduling. – Physica, Springer, Heidelberg, Germany, 1996.
Search in Google Scholar Back to article
28. Mesghouni, K., S. Hammadi, P. Borne. Evolutionary Algorithmsfor Job-Shop Scheduling. – Int. J. Appl. Math. Comput. Sci., Vol. 14, 2004, No 1, pp. 91-103.
Search in Google Scholar Back to article
29. Nakandhkumar, R. S., atal. Optimizationof Job Shop Scheduling Problem Using Tabu Search Optimization Technique. – International Journalof Innovative Researchin Science, Engineeringand Technology, Vol. 3, March 2014, Special Issue 3.
Search in Google Scholar Back to article
30. Nawaz Ripon, K. S., C.-H. Tsang, S. Kwong. An Evolutionary Approachfor Solvingthe Multi-Objective Jop-ShopScheduling Problem. – Studiesin Computational Intelligence (SCI), Vol. 49, 2007, Berlin, Heidelberg, Springer-Verlag, pp. 165-195.10.1007/978-3-540-48584-1_7
Search in Google Scholar Back to article
31. Pesaru, V. Genetic Algorithm-Jobshop Scheduling. 2017. https://de.mathworks.com/matlabcentral/fileexchange/62567-genetic-algorithm-jobshop-scheduling
Search in Google Scholar Back to article
32. Rahimi-Vahed, R., S. M. Mirghorbani. A Multi-Objective Particle Swarmfora Flow Shop Scheduling Problem. – Journalof Combinatorial Optimization, Vol. 13, 2007, No 1, pp. 79-102.10.1007/s10878-006-9015-7
Search in Google Scholar Back to article
33. Romasevych, Y., V. Loveikin. A Novel Multi-Epoch Particle Swarm Optimization Technique. – Cyberneticsand Information Technologies, Vol. 18, 2018, No 3.10.2478/cait-2018-0039
Search in Google Scholar Back to article
34. Bordbar, S., P. Shamsinejad. A New Opinion Mining Methodbasedon Fuzzy Classifierand Particle Swarm Optimization (PSO) Algorithm. – Cyberneticsand Information Technologies, Vol. 18, 2018, No 2.10.2478/cait-2018-0026
Search in Google Scholar Back to article
35. Schmidt, K. Using Tabu Searchto Solve Job Shop Scheduling Problemwith Sequence Dependent Setup Times. 2001.
Search in Google Scholar Back to article
36. Sha, D. Y., H.-H. Lin. A Multi-Objective PSOfor Job-Shop Scheduling Problems. – Expert Systemswith Applications, Vol. 37, March 2010, Issue 2, pp. 1065-1070. http://dl.acm.org/citation.cfm?id=164584310.1016/j.eswa.2009.06.041
Search in Google Scholar Back to article
37. Shuib, A., S. S. A. Gran. Multi-Objectives Optimization Modelfor Flexible Job Shop Scheduling Problem (FJSSP) with Machines’ Workload Balancing. – In: AIP Conference Proceedings, 1974, 020106 (2018). https://doi.org/10.1063/1.504163710.1063/1.5041637
Open DOI Search in Google Scholar Back to article
38. Tang, J., G. Zhang, B. Lin, B. Zhang. A Hybrid Algorithmfor Flexible Job-Shop Scheduling Problem. – Procedia Engineering, Vol. 15, 2011, pp. 3678-3683.10.1016/j.proeng.2011.08.689
Search in Google Scholar Back to article
39. Udaiyakumar, K. C., M. Chandrasekaran. Applicationof Firefly Algorithmin Job Shop Scheduling Problemfor Minimizationof Makespan. – Procedia Engineering, Vol. 97, 2004, pp. 1798-1807.10.1016/j.proeng.2014.12.333
Search in Google Scholar Back to article
40. Vaessens, R. J. M., E. H. L. Aarts, J. K. Lenstra. Job Shop Schedulingby Local Search. – INFORMS J. Computing, Vol. 8, 1996, pp. 302-317.10.1287/ijoc.8.3.302
Search in Google Scholar Back to article
41. Xia, W. J., Z. M. Wu. An Effective Hybrid Optimization Approachfor Multi-Objective Flexible Job-Shop Scheduling Problems. – Computersand Industrial Engineering, Vol. 48, 2005, No 2, pp. 409-425.10.1016/j.cie.2005.01.018
Search in Google Scholar Back to article
42. Zhang, G. H., X. Y. Shao, P. G. Li, L. Gao. An Effective Hybrid Particle Swarm Optimization Algorithmfor Multi-Objective Flexible Job-Shop Scheduling Problem. – Comtputersand Industrial Engineering, Vol. 56, 2009, No 4, pp. 1309-1318.10.1016/j.cie.2008.07.021
Search in Google Scholar Back to article
43. Zhang, G., atal. An Effective Particle Swarm Optimizationfor Flexible Job Shop Scheduling Problem. – The Open Automationand Control Systems Journal, Vol. 6, 2014, pp. 1604-1611.10.2174/1874444301406011604
Search in Google Scholar Back to article
44. Zhang, J., G. Ding, Y. Zou, S. Qin, J. Fu. Reviewof Job Shop Scheduling Researchand Its New Perspectivesunder Industry 4.0. – Journalof Intelligent Manufacturing, Vol. 30, 2019, Issue 4, No 19, 1809-1830.10.1007/s10845-017-1350-2
Search in Google Scholar Back to article

Particle Swarm Optimization and Tabu Search Hybrid Algorithm for Flexible Job Shop Scheduling Problem – Analysis of Test Results

Abstract

Paradigm

My account