A Hybrid Algorithm for Flow Shop Scheduling Problem with Unavailable Time Periods and Additional Resources

Abstract

In the scheduling literature, the studies that consider unavailable periods (UPs) have generally ignored the resources. However, when the resources to be used in unavailable periods are limited and these resources are needed for more than one machine at the same time, the problem of when the resource should be allocated to which machine arises. This decision is important as it can greatly affect the effectiveness of the machine schedule. For this reason, it is necessary to consider not only the UPs, but also the resources used by the UPs. In this study, flow shop scheduling problem with unavailable periods, flexible in a time window, and additional resources is discussed. In the considered problem, since additional resources are required during the unavailable periods and they can serve just one machine at a time, they cannot overlap. A MIP model and a hybrid algorithm that genetic algorithm and modified subgradient algorithm works together, have been developed for the considered problem. The performance of the hybrid algorithm is compared with pure genetic algorithm and Cplex solver of GAMS by using randomly generated test problems. Test results showed that while hybrid algorithm has solution quality advantage, genetic algorithm has solution time advantage. In addition, with the developed hybrid algorithm, GAMS results were improved up to 88%.

Keywords

• Flow shop scheduling
• Unavailable periods
• Additional resources
• Hybrid algorithm

References

1. [1] Geurtsen, M., Didden, J.B.H.C., Adan, J., Atan, Z., Adan, I., “Production, maintenance and resource scheduling: A review”, European Journal of Operational Research, (2022) (In press).
2. [2] Lee, C., Chen, Z., “Scheduling jobs and maintenance activities on parallel machines”, Naval Research Logistics, 47: 145–165, (2000).
3. [3] Yoo, J., Lee, I., “Parallel machine scheduling with maintenance activities”, Computers & Industrial Engineering, 101: 361–371, (2016).
4. [4] Belkaid, F., Dahane, M., Sair, Z., Khatab, A., “Efficient approach for joint maintenance planning and production scheduling under consumable resources constraints”, 44th International conference on computers& industrial engineering, (2014).
5. [5] Wong, C.S., Chan, F.T.S., Chung, S.H., “A genetic algorithm approach for production scheduling with mould maintenance consideration”, International Journal of Production Research, 50(20): 5683–5697, (2012).
6. [6] Wong, C., Chan, F.T., Chung, S., “Decision-making on multi-mould maintenance in production scheduling”, International Journal of Production Research, 52(19): 5640–5655, (2014).
7. [7] Wang, S., Liu, M., “Multi-objective optimization of parallel machine scheduling integrated with multi-resources preventive maintenance planning”, Journal of Manufacturing Systems, 37(1): 182–192, (2015).
8. [8] Fu, X., Chan, F.T., Niu, B., Chung, N.S., Qu, T., “A three-level particle swarm optimization with variable neighbourhood search algorithm for the production scheduling problem with mould maintenance”, Swarm and Evolutionary Computation, 50: 100572, (2019).

9. [9] Liu, C.L., Wang, J.J., “Unrelated parallel-machine scheduling with controllable processing times and impact of deteriorating maintenance activities under consideration”, Asia-Pacific Journal of Operational Research, 33(1): 1–16, (2016).
10. [10] Rebai, M., Kacem, I., Adjallah, K.H., “Scheduling jobs and maintenance activities on parallel machines”, Operational Research, 13(3): 363–383, (2013).
11. [11] Tavana, M., Zarook, Y., Santos-Arteaga, F.J., “An integrated three-stage maintenance scheduling model for unrelated parallel machines with aging effect and multi-maintenance activities”, Computers and Industrial Engineering, 83: 226–236, (2015).
12. [12] Li, M.B., Xiong, H., Lei, D.M., “An artificial bee colony with adaptive competition for the unrelated parallel machine scheduling problem with additional resources and maintenance”, Symmetry, 14(7): 1380, (2022).
13. [13] Aramon Bajestani, M., Beck, J.C., “A two-stage coupled algorithm for an integrated maintenance planning and flowshop scheduling problem with deteriorating machines”, Journal of Scheduling, 18(5): 471–486, (2015).
14. [14] Boufellouh, R., Belkaid, F., “Bi-objective optimization algorithms for joint production and maintenance scheduling under a global resource constraint: Application to the permutation flow shop problem”, Computers & Operations Research, 122: 104943, (2020).
15. [15] Wang, S., Yu, J., “An effective heuristic for flexible job-shop scheduling problem with maintenance activities”, Computers & Industrial Engineering, 59(3): 436–447, (2010).
16. [16] Fu, X., Chan, F.T., Niu, B., Chung, S.H., Bi, Y., “Minimization of makespan through jointly scheduling strategy in production system with mould maintenance consideration”, International Conference on Intelligent Computing, 577–586, Springer, (2017).
17. [17] Gasimov, R.N., “Augmented Lagrangian duality and nondifferentiable optimization methods in nonconvex programming”, Journal of Global Optimization, 24(2): 187-203, (2002).
18. [18] Kasimbeyli, R., Ustun, O., Rubinov, A.M., “The modified subgradient algorithm based on feasible values”, Optimization, 58(5): 535-560, (2009).
19. [19] Gasimov, R.N., Ustun, O., “Solving the quadratic assignment problem using F-MSG algorithm”, Journal of Industrial and Management Optimization, 3(2): 173-191, (2007).
20. [20] Sipahioglu, A, Saraç, T, “The performance of the modified subgradient algorithm on solving the 0-1 quadratic knapsack problem”, Informatica, 20(2): 1-12, (2009).
21. [21] Ozcelik, F., Saraç, T., “A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings”, International Journal of Production Research, 50(15): 4025-4037, (2012).
22. [22] Ulutas, B., Saraç, T., “Determining the parameters of MSG algorithm for multi period layout problem”, Journal of Manufacturing Technology Management, 7: 922–936, (2012).
23. [23] Saraç, T., Sipahioglu, A., “Generalized quadratic multiple knapsack problem and two solution approaches”, Computers & Operations Research, 43: 78-89, (2014).
24. [24] Takan, M.A., Kasımbeyli, R., “A hybrid subgradient method for solving the capacitated vehicle routing problem”, Journal of Nonlinear and Convex Analysis, 21(2): 413-423, (2020).
25. [25] Bulbul, K.G., Kasimbeyli, R., “Augmented Lagrangian based hybrid subgradient method for solving aircraft maintenance routing problem”, Computers & Operations Research, 132: 105294, (2021).
26. [26] Singh, H., Oberoi, J.S., Singh, D., “Multi-objective permutation and non-permutation flow shop scheduling problems with no-wait: a systematic literature review”, Rairo-Operations Research, 55(1): 27-50, (2021).
27. [27] Komaki, G.M., Sheikh, S., Malakooti, B., “Flow shop scheduling problems with assembly operations: a review and new trends”, International Journal of Production Research, 57(10): 2926-2955, (2019).
28. [28] Yenisey, M.M., Yagmahan, B., “Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends”, OMEGA-International Journal of Management Science, 45: 119-135, (2014).
29. [29] Ozcelik, F., Islier, A.A., “Generalisation of unidirectional loop layout problem and solution by a genetic algorithm”, International Journal of Production Research, 49(3): 747-764, (2011).