Flexible Job Shop Scheduling Problem Considering Upper Bounds for the Amount of Interruptions Between Operations and Machines Maintenance Activities

Document Type : Original Article

Authors

1 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

2 Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

In modern production environments where perishable products are manufactured in a job shop system, machine reliability is of utmost importance, and delays during job processing are not acceptable. Therefore, it becomes crucial to consider machines maintenance activities and set upper bounds for interruptions between job operations. This paper tackels the Flexible Job Shop Scheduling Problem taking into account these factors. The study is conducted in two phases. Initially, a novel Mixed-Integer Linear Programming (MILP) model is elaborated for the problem and juxtaposed with the Benders decomposition method to assess computational efficiency. Nevertheless, owing to the elevated complexity of the problem, attaining an optimal solution for instances of realistic size poses an exceptionally challenging task using exact methods. Thus, in the second stage, a Discrete Grey Wolf Optimizer (D-GWO) as an alternative approach to solve the problem is proposed. The performance of the extended algorithms is evaluated through numerical tests. The findings indicate that for small instances, the Benders decomposition method outperforms other approaches. Nevertheless, as the instances grow in size, the efficiency of exact methods diminishes, and the Discrete Grey Wolf Optimizer (D-GWO) performs better under such conditions. Overall, this study highlights the importance of considering machines maintenance activities and interruptions in scheduling of job shop for the production of perishable products. The proposed model and Benders decomposition method in small instances, and the metaheuristic algorithm in large instances provide viable solutions.

Graphical Abstract

Flexible Job Shop Scheduling Problem Considering Upper Bounds for the Amount of Interruptions Between Operations and Machines Maintenance Activities

Keywords

Main Subjects

References

  1. Mahdavi K, Mohammadi M, Ahmadizar F. Efficient scheduling of a no-wait flexible job shop with periodic maintenance activities and processing constraints. Journal of Quality Engineering and Production Optimization. 2023. https://doi.org/10.22070/JQEPO.2023.16882.1246
  2. Gao J, Gen M, Sun L. Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing. 2006;17:493-507. https://doi.org/10.1007/s10845-005-0021-x
  3. Özgüven C, Özbakır L, Yavuz Y. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling. 2010;34(6):1539-48. https://doi.org/10.1016/j.apm.2009.09.002
  4. Manne AS. On the job-shop scheduling problem. Operations research. 1960;8(2):219-23. https://doi.org/10.1287/opre.8.2.219
  5. Wagner HM. An integer linear‐programming model for machine scheduling. Naval research logistics quarterly. 1959;6(2):131-40. https://doi.org/10.1002/nav.3800060205
  6. El Khoukhi F, Boukachour J, Alaoui AEH. The “Dual-Ants Colony”: A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance. Computers & Industrial Engineering. 2017;106:236-55. https://doi.org/10.1016/j.cie.2016.10.019
  7. Yegane BY, Kamalabadia IN, Khanlarzadeb N. Critical path method for lot streaming problem in flexible job shop environment. International Journal of Engineering-Transactions B: Applications. 2017;30(2):261-9. https://doi.org/10.5829/idosi.ije.2017.30.02b.13
  8. Benttaleb M, Hnaien F, Yalaoui F. Two-machine job shop problem under availability constraints on one machine: Makespan minimization. Computers & Industrial Engineering. 2018;117:138-51. https://doi.org/10.1016/j.cie.2018.01.028
  9. Shen L, Dauzère-Pérès S, Neufeld JS. Solving the flexible job shop scheduling problem with sequence-dependent setup times. European journal of operational research. 2018;265(2):503-16. https://doi.org/10.1016/j.ejor.2017.08.021
  10. Tamssaouet K, Dauzère-Pérès S, Yugma C. Metaheuristics for the job-shop scheduling problem with machine availability constraints. Computers & Industrial Engineering. 2018;125:1-8. https://doi.org/10.1016/j.cie.2018.08.008
  11. Caldeira RH, Gnanavelbabu A. Solving the flexible job shop scheduling problem using an improved Jaya algorithm. Computers & Industrial Engineering. 2019;137:106064. https://doi.org/10.1016/j.cie.2019.106064
  12. Samarghandi H. Solving the no-wait job shop scheduling problem with due date constraints: A problem transformation approach. Computers & Industrial Engineering. 2019;136:635-62. https://doi.org/10.1016/j.cie.2019.07.054
  13. Zhang G, Hu Y, Sun J, Zhang W. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and evolutionary computation. 2020;54:100664. https://doi.org/10.1016/j.swevo.2020.100664
  14. Li J-q, Deng J-w, Li C-y, Han Y-y, Tian J, Zhang B, et al. An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowledge-Based Systems. 2020;200:106032. https://doi.org/10.1016/j.knosys.2020.106032
  15. Ying K-C, Lin S-W. Solving no-wait job-shop scheduling problems using a multi-start simulated annealing with bi-directional shift timetabling algorithm. Computers & Industrial Engineering. 2020;146:106615. https://doi.org/10.1016/j.cie.2020.106615
  16. Zhu Z, Zhou X. Flexible job-shop scheduling problem with job precedence constraints and interval grey processing time. Computers & Industrial Engineering. 2020;149:106781. https://doi.org/10.1016/j.cie.2020.106781
  17. Zhu Z, Zhou X. An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints. Computers & Industrial Engineering. 2020;140:106280. https://doi.org/10.1016/j.cie.2020.106280
  18. Zhang G, Sun J, Lu X, Zhang H. An improved memetic algorithm for the flexible job shop scheduling problem with transportation times. Measurement and Control. 2020;53(7-8):1518-28. https://doi.org/10.1177/0020294020948094
  19. Defersha FM, Rooyani D. An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time. Computers & Industrial Engineering. 2020;147:106605. https://doi.org/10.1016/j.cie.2020.106605
  20. Ozolins A. A new exact algorithm for no-wait job shop problem to minimize makespan. Operational Research. 2020;20(4):2333-63. https://doi.org/10.1007/s12351-018-0414-1
  21. Izadi L, Ahmadizar F, Arkat J. A hybrid genetic algorithm for integrated production and distribution scheduling problem with outsourcing allowed. International Journal of Engineering, Transactions B: Applications,. 2020;33(11):2285-98. https://doi.org/10.5829/IJE.2020.33.11B.19
  22. Gao J, Zhu X, Bai K, Zhang R. New controllable processing time scheduling with subcontracting strategy for no-wait job shop problem. International Journal of Production Research. 2022;60(7):2254-74. https://doi.org/10.1080/00207543.2021.1886368
  23. Boyer V, Vallikavungal J, Rodríguez XC, Salazar-Aguilar MA. The generalized flexible job shop scheduling problem. Computers & Industrial Engineering. 2021;160:107542. https://doi.org/10.1016/j.cie.2021.107542
  24. Torkashvand M, Ahmadizar F, Farughi H. Distributed production assembly scheduling with hybrid flowshop in assembly stage. International Journal of Engineering, Transactions B: Applications,. 2022;35(5):1037-55. https://doi.org/10.5829/IJE.2022.35.05B.19
  25. Valenzuela-Alcaraz VM, Cosio-Leon M, Romero-Ocaño AD, Brizuela CA. A cooperative coevolutionary algorithm approach to the no-wait job shop scheduling problem. Expert Systems with Applications. 2022;194:116498. https://doi.org/10.1016/j.eswa.2022.116498
  26. Fan H, Su R. Mathematical modelling and heuristic approaches to job-shop scheduling problem with conveyor-based continuous flow transporters. Computers & Operations Research. 2022;148:105998. https://doi.org/10.1016/j.cor.2022.105998
  27. Şahman MA, Korkmaz S. Discrete artificial algae algorithm for solving job-shop scheduling problems. Knowledge-Based Systems. 2022;256:109711. https://doi.org/10.1016/j.knosys.2022.109711
  28. Tutumlu B, Saraç T. A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting. Computers & Operations Research. 2023;155:106222. https://doi.org/10.1016/j.cor.2023.106222
  29. Gong G, Tang J, Huang D, Luo Q, Zhu K, Peng N. Energy-efficient flexible job shop scheduling problem considering discrete operation sequence flexibility. Swarm and Evolutionary Computation. 2024;84:101421. https://doi.org/10.1016/j.swevo.2023.101421
  30. Xie J, Li X, Gao L, Gui L. A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems. Journal of Manufacturing Systems. 2023;71:82-94. https://doi.org/10.1016/j.jmsy.2023.09.002
  31. Liu Z, Zha J, Yan J, Zhang Y, Zhao T, Cheng Q, et al. An improved genetic algorithm with an overlapping strategy for solving a combination of order batching and flexible job shop scheduling problem. Engineering Applications of Artificial Intelligence. 2024;127:107321. https://doi.org/10.1016/j.engappai.2023.107321
  32. Berterottière L, Dauzère-Pérès S, Yugma C. Flexible job-shop scheduling with transportation resources. European Journal of Operational Research. 2024;312(3):890-909. https://doi.org/10.1016/j.ejor.2023.07.036
  33. Brizuela CA, Zhao Y, Sannomiya N, editors. No-wait and blocking job-shops: Challenging problems for GA's. 2001 IEEE International Conference on Systems, Man and Cybernetics e-Systems and e-Man for Cybernetics in Cyberspace (Cat No 01CH37236); 2001: IEEE.
  34. Mirjalili S, Mirjalili SM, Lewis A. Grey wolf optimizer. Advances in engineering software. 2014;69:46-61. https://doi.org/10.1016/j.advengsoft.2013.12.007
  35. Shirvani H. A novel discrete grey wolf optimizer for scientific workflow scheduling in heterogeneous cloud computing platforms. Scientia Iranica. 2022;29(5):2375-93. https://doi.org/10.24200/SCI.2022.57262.5144
  36. Jiang T, Zhang C. Application of grey wolf optimization for solving combinatorial problems: Job shop and flexible job shop scheduling cases. Ieee Access. 2018;6:26231-40. https://doi.org/10.1109/ACCESS.2018.2833552
International Journal of Engineering
Volume 37, Issue 8
TRANSACTIONS B: Applications
August 2024
Pages 1600-1614

Files

Share

How to cite

Statistics