OPTIMIZING THE PERMUTATION FLOWSHOP SCHEDULING PROBLEM (PFSP) USING THE SCATTER SEARCH METHOD

Abstract

Scheduling is the process of optimizing limited resources, depending on the objectives. Scheduling problems are one of the decision-making problems that play a critical role in production and service systems. Continuing production regularly and systematically is an important issue for production planners. Permutation flow shop scheduling, which is a sub-branch of production scheduling, is defined as “n” jobs being processed simultaneously on “m” machines. Permutation Flow Shop Scheduling Problems (PFSPs) are in the complex and difficult problem class. Many metaheuristic methods have been proposed to solve such problems. In this study, the Scatter Search method, which is one of the population-based evolutionary methods of metaheuristic methods, was used to solve the Permutation Flow Shop Scheduling Problem (PFSP). The scatter search method was analyzed with the algorithm prepared on JavaScript programming language. With the scatter search, the total completion time of the jobs was minimized and the effectiveness of the method was tested on the problem groups frequently used in the literature. The use of the JavaScript programming language in this study has contributed to the literature on testing large-scale problems. The distribution search algorithm has a positive effect on the PTSP with an average of 2% difference from the best-known solutions due to the minimization of work times.

Keywords

• Scheduling problem
• flow shop scheduling
• metaheuristic method
• scatter search
• JavaScript

References

1. 1. Abdel-Basset, M., Manogoran, G., El-Shahat, D. & Mirjalili, S. (2018). A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem. Future Generation Computer Systems, 85: 129-145.
2. 2. Abdelmaguid, T.F. (2020). Scatter search with path relinking for multiprocessor open shop scheduling. Computers & Industrial Engineering, 141, 1-19.
3. 3. Abdollahzadeh, B., Soleimanian Gharehchopogh, F., & Mirjalili, S. (2021). Artificial gorilla troops optimizer: a new nature‐inspired metaheuristic algorithm for global optimization problems. International Journal of Intelligent Systems, 36(10), 5887-5958.
4. 4. Alharkan, M.I. (2005). Algorithms for Sequencing and Scheduling, King Saud University, Riyadh.
5. 5. Amirghasemi, M. (2021). An Effective Decomposition-Based Stochastic Algorithm for Solving the Permutation Flow-Shop Scheduling Problem. Algorithms, 14, 112.
6. 6. Arshad, A., Gajpal, Y. & Elmekkawy, T.Y. (2021). Distributed permutation flowshop scheduling problem with total completion time objective. Opsearch, 58(2), 425-447.
7. 7. Baskar, A. & Xavior, M. A. (2021). New idle time-based tie-breaking rules in heuristics for the permutation flowshop scheduling problems. Computers & Operations Research, 133, 105348.
8. 8. Behnamian, J., Memar Dezfooli, S., & Asgari, H. (2021). A scatter search algorithm with a novel solution representation for flexible open shop scheduling: a multi-objective optimization. The Journal of Supercomputing, 77(11), 13115-13138.

9. 9. Campbell, H. G., Dudek, R. A. & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management science, 16(10), B-630.
10. 10. Çiçekli, U.G. & Bozkurt S. (2016). Permütasyon akış tipi çizelgeleme probleminin dağınık arama ile optimizasyonu. Ege Akademik Bakış, 16, 31-40.
11. 11. Erol, V. (2006). Design and implementation of a population and neighborhood-based metaheuristic algorithm for vehicle routing problems, Master Thesis, Yıldız Technical University, İstanbul, Turkey.
12. 12. Fink, A. & Voß, S. (2003). Solving the Continuous Flow-Shop Scheduling Problem by Metaheuristics. European Journal of Operational Research, 151: 400-414.
13. 13. Graves, S.C. (1981). A Review of Production Scheduling. Operations Research, 29(4): 646-675.
14. 14. Kaya S. & Fığlalı N. (2018). Use of meta-heuristic methods to solve the multi-objective flexible job shop scheduling problems, Harran University Journal of Engineering, 3(3), 222-233.
15. 15. Kaya, S., Aydilek, İ.B., Tenekeci M.E. & Gümüşçü A. (2020). The effects of initial populations in the solution of flow shop scheduling problems by hybrid firefly and particle swarm optimization algorithms. Pamukkale University Journal of Engineering Sciences, 26(1), 140-149.
16. 16. Kurdi, M. (2021). Application of Social Spider Optimization for Permutation Flow Shop Scheduling Problem. Journal of Soft Computing and Artificial Intelligence, 2(2): 85-97.
17. 17. Külahlı, S., Engin, O., & Koç, İ. (2021). A New Hybrid Scatter Search Method for Solving the Flexible Job Shop Scheduling Problems. Celal Bayar University Journal of Science, 17(4).
18. 18. Marti, R., Laguna, M. & Glover, F. (2006). Principles of Scatter Search, European Journal of Operational Research, 169:359-372.
19. 19. Mashuri C., Mujianto A.H., Sucipto H., Arsam R. Y. & Permadi G.S. (2019). Production Time Optimization using Campbell Dudek Smith (CDS) Algorithm for Production Scheduling, E3S Web of Conferences 125, 23009.
20. 20. Mete, U. (2019). A variable neighborhood search approach for permutation flowshop. Scheduling. Master’s Thesis, Pamukkale University, Turkey.
21. 21. Moghaddam, R.T., Javadian, N., Khorrami, A. & Gholipour-Kanani Y. (2010). Design of a scatter search method for a novel multi-criteria group scheduling problem in a cellular manufacturing system, Expert Systems with Applications, 37 ,2661–2669.
22. 22. Nawaz, M., Enscore Jr, E. E. & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
23. 23. Nowicki E. & Smutnicki C., (2006). Some aspects of scatter search in the flow-shop problem, European Journal of Operational Research, 169, 654–666.
24. 24. Oktay, S. & Engin, O., (2006). Scatter search method for solving industrial problems: literature survey. Journal of Engineering and Natural Sciences, 3, 144-155.
25. 25. Osman, I.H. & Laporte, G. (1996). Metaheuristics: a bibliography. Annals of Operations Research, 63, 513- 623.
26. 26. Osman, I.H. & Kelly, J.P. (1996). Meta-heuristics: an overview. Meta-heuristics, 1-21.
27. 27. Palmer, D.S. (1965). Sequencing jobs through a multi-stage process in the minimum total time - a quick method of obtaining a near optimum. Journal of the Operational Research Society, 16(1), 101-107.
28. 28. Pan, Q.K., Gao, L., Wang, L., Liang, J. & Li, X.Y. (2019). Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Systems with Applications, 124, 309-324.
29. 29. Rahimi-Vahed, A.R., Javadi, B., Rabbani, M. & Moghaddam, R.T. (2008). A multi-objective scatter search for a bi-criteria nowait flow shop scheduling problem, Engineering Optimization, 331-346.
30. 30. Riahi V., Khorramizade M., Hakim Newton M.A. & Sattar A. (2017). Scatter search for mixed blocking flowshop scheduling, Expert Systems with Applications 79:20-32.
31. 31. Rimli M.A., Deris S., Mohamad M.S., Omatu S. & Corchado J.M. (2017). An enhanced scatter search with combined opposition-based learning parameter estimation in large-scale kinetic models of biochemical systems, Engineering Application of Artificial Intelligence 62, 164-180.
32. 32. Sadiq, A. & Muhamad, K. (2012). Improved scatter search for job shop scheduling problem. International Journal of Research and Reviews in Soft and Intelligent Computing, 2(1), 104-107.
33. 33. Sagarna, R. & Lozano, J. A. (2006). Scatter Search in Software Testing, Comparison and Collaboration with Estimation of Distribution Algorithms, European Journal of Operational Research, 169(2):392-412.
34. 34. Saravanan M. & Haq A.N. (2008). Evaluation of Scatter Search Approach for Scheduling Optimization of Flexible Manufacturing Systems, The International Journal of Advanced Manufacturing Technology, 38, 978–986.
35. 35. Stützle T. & Hoos H.H. (2000). MAX-MIN Ant System, Future Generation Computer Systems 16(8):889-914.
36. 36. Taillard E., (1993). Benchmarks for basic scheduling problems, European Journal of Operational Research, 64(2): 278-285.
37. 37. Yang Y., Li P., Wang S., Liu B. & Luo Y. (2017). Scatter Search for Distributed Assembly Flowshop Scheduling to Minimize Total Tardiness, IEEE, 861-868.