Efficient scheduling of a no-wait flexible job shop with periodic maintenance activities and processing constraints

Document Type : Research Paper

Authors

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

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

10.22070/jqepo.2023.16882.1246

Abstract

Flexible job-shop scheduling problem (F-JSP) is an expansion of the job shop scheduling problem (JSP) which allows an operation to be fulfilled by any machine among a set of accessible machines at each stage. This paper investigates a no-wait F-JSP (NW-F-JSP) with machines accessibility restrictions for maintenance activities and machines processing capability to minimize total weighted tardiness. The study is organized in two phases. Firstly, a novel nonlinear mathematical model is developed for the supposed problem, and then it is converted into a linear mathematical model using techniques found in the literature. Since the structure of the problem is NP-hard, an imperialist competitive algorithm is proposed in the second phase to solve large instances of the problem. In the proposed algorithm, an effective solution representation with an efficient and greedy decoding methodology is adopted to reduce the search space. Numerical experiments are used to appraise the performance of the developed algorithm. It is inferred that in small instances, solving the mathematical model by GAMS leads to the optimal solution. Still, with an increased instance size, this method loses its efficiency and the ICA approach performs better under these conditions. 

Keywords

References

Ahmadian, M. M., Salehipour, A., & Cheng, T. C. E. (2020). A meta-heuristic to solve the just-in-time job-shop scheduling problem. European Journal of Operational Research.
Ahmadizar, F., Mahdavi, K., & Arkat, J. (2019). Unrelated parallel machine scheduling with processing constraints and sequence dependent setup times. Advances in Industrial Engineering, 53(1), 495–507.
Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. 2007 IEEE Congress on Evolutionary Computation, 4661–4667. IEEE.
Benttaleb, M., Hnaien, F., & Yalaoui, F. (2018). Two-machine job shop problem under availability constraints on one machine: Makespan minimization. Computers & Industrial Engineering, 117, 138–151.
Boyer, V., Vallikavungal, J., Rodríguez, X. C., & Salazar-Aguilar, M. A. (2021). The generalized flexible job shop scheduling problem. Computers & Industrial Engineering, 160, 107542.
Brizuela, C. A., Zhao, Y., & Sannomiya, N. (2001). 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), 4, 2349–2354. IEEE.
Bürgy, R., & Bülbül, K. (2018). The job shop scheduling problem with convex costs. European Journal of Operational Research, 268(1), 82–100.
Caldeira, R. H., & Gnanavelbabu, A. (2019). Solving the flexible job shop scheduling problem using an improved Jaya algorithm. Computers & Industrial Engineering, 137, 106064.
Dai, M., Tang, D., Giret, A., & Salido, M. A. (2019). Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints. Robotics and Computer-Integrated Manufacturing, 59, 143–157.
Defersha, F. M., & Rooyani, D. (2020). 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, 147, 106605.
El Khoukhi, F., Boukachour, J., & Alaoui, A. E. H. (2017). The “Dual-Ants Colony”: A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance. Computers & Industrial Engineering, 106, 236–255.
Fan, H., & Su, R. (2022). Mathematical Modelling and Heuristic Approaches to Job-shop Scheduling Problem with Conveyor-based Continuous Flow Transporters. Computers & Operations Research, 148, 105998.
Fattahi, P., Messi Bidgoli, M., & Samouei, P. (2018). An improved Tabu search algorithm for job shop scheduling problem trough hybrid solution representations. Journal of Quality Engineering and Production Optimization, 3(1), 13–26.
Gao, Jie, Gen, M., & Sun, L. (2006). Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing, 17(4), 493–507.
Gao, Jinsheng, Zhu, X., Bai, K., & Zhang, R. (2021). New controllable processing time scheduling with subcontracting strategy for no-wait job shop problem. International Journal of Production Research, 1–21.
García-León, A. A., Dauzère-Pérès, S., & Mati, Y. (2019). An efficient Pareto approach for solving the multi-objective flexible job-shop scheduling problem with regular criteria. Computers & Operations Research, 108, 187–200.
Li, J., Deng, J., Li, C., Han, Y., Tian, J., Zhang, B., & Wang, C. (2020). An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowledge-Based Systems, 106032.
Li, X., Yang, X., Zhao, Y., Teng, Y., & Dong, Y. (2020). Metaheuristic for Solving Multi-Objective Job Shop Scheduling Problem in a Robotic Cell. IEEE Access, 8, 147015–147028.
Lu, C., Li, X., Gao, L., Liao, W., & Yi, J. (2017). An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times. Computers & Industrial Engineering, 104, 156–174.
Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8(2), 219–223.
Miyata, H. H., Nagano, M. S., & Gupta, J. N. D. (2019). Integrating preventive maintenance activities to the no-wait flow shop scheduling problem with dependent-sequence setup times and makespan minimization. Computers & Industrial Engineering, 135, 79–104.
Nohair, L., El Adraoui, A., & Namir, A. (2022). Solving Non-Delay Job-Shop Scheduling Problems by a new matrix heuristic. Procedia Computer Science, 198, 410–416.
Ozolins, A. (2020). A new exact algorithm for no-wait job shop problem to minimize makespan. Operational Research, 20(4), 2333–2363.
Samarghandi, H. (2019). Solving the no-wait job shop scheduling problem with due date constraints: A problem transformation approach. Computers & Industrial Engineering, 136, 635–662.
Samarghandi, H., & Firouzi Jahantigh, F. (2019). Comparing Mixed-Integer and Constraint Programming for the No-Wait Flow Shop Problem with Due Date Constraints. Journal of Quality Engineering and Production Optimization, 4(1), 17–24.
Shen, L., Dauzère-Pérès, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265(2), 503–516.
Tamssaouet, K., Dauzère-Pérès, S., & Yugma, C. (2018). Metaheuristics for the job-shop scheduling problem with machine availability constraints. Computers & Industrial Engineering, 125, 1–8.
Valenzuela-Alcaraz, V. M., Cosío-León, M. A., Romero-Ocaño, A. D., & Brizuela, C. A. (2022). A cooperative coevolutionary algorithm approach to the no-wait job shop scheduling problem. Expert Systems with Applications, 194, 116498.
Weng, W., Chen, J., Zheng, M., & Fujimura, S. (2022). Realtime scheduling heuristics for just-in-time production in large-scale flexible job shops. Journal of Manufacturing Systems, 63, 64–77.
Winklehner, P., & Hauder, V. A. (2022). Flexible job-shop scheduling with release dates, deadlines and sequence dependent setup times: a real-world case. Procedia Computer Science, 200, 1654–1663.
Wu, X., Shen, X., & Li, C. (2019). The flexible job-shop scheduling problem considering deterioration effect and energy consumption simultaneously. Computers & Industrial Engineering, 135, 1004–1024.
Yazdani, M., Aleti, A., Khalili, S. M., & Jolai, F. (2017). Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Computers & Industrial Engineering, 107, 12–24.
Ying, K.-C., & Lin, S.-W. (2020). Solving no-wait job-shop scheduling problems using a multi-start simulated annealing with bi-directional shift timetabling algorithm. Computers & Industrial Engineering, 146, 106615.
Zandieh, M., Khatami, A. R., & Rahmati, S. H. A. (2017). Flexible job shop scheduling under condition-based maintenance: Improved version of Imperialist competitive algorithm. Applied Soft Computing, 58, 449–464.
Zhang, G., Hu, Y., Sun, J., & Zhang, W. (2020). An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and Evolutionary Computation, 54, 100664.
Zhang, G., Sun, J., Lu, X., & Zhang, H. (2020). An improved memetic algorithm for the flexible job shop scheduling problem with transportation times. Measurement and Control, 0020294020948094.
Zhang, S. J., Gu, X. S., & Zhou, F. N. (2020). An improved discrete migrating birds optimization algorithm for the no-wait flow shop scheduling problem. IEEE Access.
Zhu, N., Zhao, F., Wang, L., Ding, R., & Xu, T. (2022). A discrete learning fruit fly algorithm based on knowledge for the distributed no-wait flow shop scheduling with due windows. Expert Systems with Applications, 198, 116921.
Zhu, Z., & Zhou, X. (2020a). An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints. Computers & Industrial Engineering, 140, 106280.
Zhu, Z., & Zhou, X. (2020b). Flexible job-shop scheduling problem with job precedence constraints and interval grey processing time. Computers & Industrial Engineering, 106781.
Journal of Quality Engineering and Production Optimization
Volume 8, Issue 1
May 2023
Pages 33-56

Files

Share

How to cite

Statistics