Joint optimization of production and maintenance scheduling for unrelated parallel machine using hybrid discrete spider monkey optimization algorithm

Chen, Y.; Zhong, L.; Shena, C.; Mumt, J.; Chou, F.

Abstract: This paper considers an unrelated parallel machine scheduling problem with variable maintenance based on machine reliability to minimize the maximum completion time. To obtain the optimal solution of small-scale problems, we firstly establish a mixed integer programming model. To solve the medium and large-scale problems efficiently and effectively, we develop a hybrid discrete spider monkey optimization algorithm (HDSMO), which combines discrete spider monkey optimization (DSMO) with genetic algorithm (GA). A few additional features are embedded in the HDSMO: a three-phase constructive heuristic is proposed to generate better initial solution, and an individual updating method considering the inertia weight is used to balance the exploration and exploitation capabilities. Moreover, a problem-oriented neighborhood search method is designed to improve the search efficiency. Experiments are conducted on a set of randomly generated instances. The performance of the proposed HDSMO algorithm is investigated and compared with that of other existing algorithms. The detailed results show that the proposed HDSMO algorithm can obtain significantly better solutions than the DSMO and GA algorithms.

How to cite this paper

 Chen, Y., Zhong, L., Shena, C., Mumt, J & Chou, F. (2023). Joint optimization of production and maintenance scheduling for unrelated parallel machine using hybrid discrete spider monkey optimization algorithm.International Journal of Industrial Engineering Computations , 14(3), 539-554.

References

Avalos-Rosales, O., Angel-Bello, F., Álvarez, A., & Cardona-Valdés, Y. (2018). Including preventive maintenance activities in an unrelated parallel machine environment with dependent setup times. Computers & Industrial Engineering, 123,364-377. https://doi.org/10.1016/j.cie.2018.07.006.
Azizoglu, M., & Kirca, O. (1999). Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Transactions, 31,153-159. https://doi.org/10.1023/A:1007516602473.
Bansal, J. C., Sharma, H., Jadon, S. S., & Clerc, M. (2014). Spider Monkey Optimization algorithm for numerical optimization. Memetic Computing, 6,31-47. https://doi.org/10.1007/s12293-013-0128-0.
Beldar, P., Moghtader, M., Giret, A., & Ansaripoor, A.H. (2022). Non-identical parallel machines batch processing problem with release dates, due dates and variable maintenance activity to minimize total tardiness. Computers & Industrial Engineering, 168,108135. https://doi.org/10.1016/j.cie.2022.108135.
Chen, Y., Huang, P., Huang, C., Huang, S., & Chou, F.-D. (2021). Makespan minimization for scheduling on two identical parallel machines with flexible maintenance and nonresumable jobs. Journal of Industrial and Production Engineering, 38(4),271-284. https://doi.org/10.1080/21681015.2021.1883131.
Cheng, T.C.E., Hsu, C.-J, & Yang, D.-L. (2011). Unrelated parallel-machine scheduling with deteriorating maintenance activities. Computers & Industrial Engineering, 60(4),602-605. https://doi.org/10.1016/j.cie.2010.12.017.
Cheng, T. C. E., & Sin, C.C.S. (1990). A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, 47(3), 271-292. https://doi.org/10.1016/0377-2217(90)90215-W.
Cheruku, R., Edla, D. R., & Kuppili, V. (2017). SM-RuleMiner: Spider monkey based rule miner using novel fitness function for diabetes classification. Computers in biology and medicine, 81, 79-92. https://doi.org/10.1016/j.compbiomed.2016.12.009.
Dang, Q.-V., van Diessen, T., Martagan, T., & Adan, I. (2021). A matheuristic for parallel machine scheduling with tool replacements. European Journal of Operational Research, 291(2), 640-660. https://doi.org/10.1016/j.ejor.2020.09.050.
Fanjul-Peyro, L., Ruiz, R., & Perea, F. (2019). Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times. Computers & Operations Research, 101,173-182. https://doi.org/10.1016/j.cor.2018.07.007.
Gara-Ali, A., Finke, G., & Espinouse, M.-L. (2016). Parallel-machine scheduling with maintenance: Praising the assignment problem. European Journal of Operational Research, 252(1),90-97. https://doi.org/10.1016/j.ejor.2015.12.047.
Gupta, K., Deep, K., & Bansal, J. C. (2017). Spider monkey optimization algorithm for constrained optimization problems. Soft Computing, 21,6933-6962. https://doi.org/10.1007/s00500-016-2419-0.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A.H.G.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Operations Research, 5,287-326. https://doi.org/10.1016/S0167-5060(08)70356-X.
Hsu, C.-J., Ji, M., Guo, J.-Y., &Yang, D.-L. (2013). Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities. Information Sciences, 253,163-169.https://doi.org/10.1016/j.ins.2013.08.053.
Kim, Y. -H., & Kim, R. -S. (2020). Insertion of new idle time for unrelated parallel machine scheduling with job splitting and machine breakdowns. Computers & Industrial Engineering, 147,106630. https://doi.org/10.1016/j.cie.2020.106630.
Lei, D., & He, S. (2022). An adaptive artificial bee colony for unrelated parallel machine scheduling with additional resource and maintenance. Expert Systems with Applications, 205,117577. https://doi.org/10.1016/j.eswa.2022.117577.
Lei, D., & Liu, M. (2020). An artificial bee colony with division for distributed unrelated parallel machine scheduling with preventive maintenance. Computers & Industrial Engineering,141,106320. https://doi.org/10.1016/j.cie.2020.106320.
Lei, D., & Yang, H. (2022). Scheduling unrelated parallel machines with preventive maintenance and setup time: Multi-sub-colony artificial bee colony. Applied Soft Computing,125, 109154. https://doi.org/10.1016/j.asoc.2022.109154.
Lei, D., & Yi, T. (2021). A novel shuffled frog-leaping algorithm for unrelated parallel machine scheduling with deteriorating maintenance and setup time. Symmetry, 13(9) ,1574. https://doi.org/10.3390/sym13091574.
Lei, D., Yuan, Y., & Cai, J. (2021). An improved artificial bee colony for multi-objective distributed unrelated parallel machine scheduling. International Journal of Production Research, 59(17),5259-5271. https://doi.org/10.1080/00207543.2020.1775911.
Lei, D., Yuan, Y., Cai, J., & Bai, D. (2020). An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling. International Journal of Production Research, 58(2),597-614.https://doi.org/10.1080/00207543.2019.1598596.
Lin, Y. K., Pfund, M. E., & Fowler, J. W. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Computers & Operations Research,38(6),901-916.https://doi.org/10.1016/j.cor.2010.08.018.
Lin, S. W., Ying, K. C. (2015). A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems. International Journal of Production Research, 53(4),1065-1076.https://doi.org/10.1080/00207543.2014.942011.
Lin, S. W., Ying, K. C., Wu, W. J., & Chiang, Y.I. (2016). Multi-objective unrelated parallel machine scheduling: a Tabu-enhanced iterated Pareto greedy algorithm. International Journal of Production Research, 54(4),1110-1121. https://doi.org/10.1080/00207543.2015.1047981.
Lu, S., Liu, X., Pei, J., T. Thai, M., & M. Pardalos, P. (2018). A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Applied Soft Computing, 66,168-182. https://doi.org/10.1016/j.asoc.2018.02.018.
Mumtaz, J., Guan, Z., Yue, L., Zhang, L., & He, C. (2020). Hybrid spider monkey optimisation algorithm for multi-level planning and scheduling problems of assembly lines. International Journal of Production Research, 58(20),6252-6267. https://doi.org/10.1080/00207543.2019.1675917.
Nickabadi, A., Ebadzadeh, M. M., & Safabakhsh, R. (2011). A novel particle swarm optimization algorithm with adaptive inertia weight. Applied soft computing, 11(4), 3658-3670. https://doi.org/10.1016/j.asoc.2011.01.037.
Pang, J, Tsai, Y. -C., & Chou, F.-D. (2021). Feature-extraction-based iterated algorithm to solve the unrelated parallel machine problem with periodic maintenance activities. IEEE Access, 9, 139089-139108. https://doi.org/10.1109/ACCESS.2021.3118986.
Pfund, M., Fowler, J. W., & Gupta, J. N. D. (2004). A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems. Journal of the Chinese Institute of Industrial Engineers, 21(3), 230-241. https://doi.org/10.1080/10170660409509404.
Rocha, P. L., Ravetti, M. G., Mateus, G. R., & Pardalos, P. M. (2008). Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Computers & Operations Research, 35(4),1250-1264. https://doi.org/10.1016/j.cor.2006.07.015.
Rodriguez, F. J., Lozano, M., Blum, C., & García-Martínez C. (2013). An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & Operations Research,40(7),1829-1841. https://doi.org/10.1016/j.cor.2013.01.018.
Sharma, A., Sharma, A., Panigrahi, B.K., Kiran, D., & Kumar, R. (2016). Ageist spider monkey optimization algorithm. Swarm and Evolutionary Computation, 28,58-77. https://doi.org/10.1016/j.swevo.2016.01.002.
Sharma, A., Sharma, H., Bhargava, A., Sharma, N., & Bansal, J. C. (2017). Optimal placement and sizing of capacitor using Lima limaçon inspired spider monkey optimization algorithm. Memetic Computing, 9,311-331. https://doi.org/10.1007/s12293-016-0208-z.
Tavana, M., Zarook, Y., & Santos-Arteaga, F. J. (2015). An integrated three-stage maintenance scheduling model for unrelated parallel machines with aging effect and multi-maintenance activities. Computers & Industrial Engineering, 83,226-236. https://doi.org/10.1016/j.cie.2015.02.012.
Wang, H., & Alidaee, B. (2019). Effective heuristic for large-scale unrelated parallel machines scheduling problems. Omega, 83,261-274. https://doi.org/10.1016/j.omega.2018.07.005.
Wang, X., Li, Z., Chen, Q., & Mao, N. (2020) Meta-heuristics for unrelated parallel machines scheduling with random rework to minimize expected total weighted tardiness. Computers & Industrial Engineering, 145,106505. https://doi.org/10.1016/j.cie.2020.106505.
Wang, M., & Pan, G. (2019). A novel imperialist competitive algorithm with multi-elite individuals guidance for multi-object unrelated parallel machine scheduling problem. IEEE Access, 7,121223-121235. https://doi.org/10.1109/ACCESS.2019.2937747.
Xia, X., Liao, W., Zhang, Y., & Peng, X. (2021). A discrete spider monkey optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing, 111,107676. https://doi.org/10.1016/j.asoc.2021.107676.
Yang, D.-L., Cheng, T. C. E., Yang, S.-J., & Hsu, C.-J. (2012). Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities. Computers and Operations Research, 39(7),1458-1464.https://doi.org/10.1016/j.cor.2011.08.017.
Yue, L., Guan, Z., Zhang, L., Ullah, S., & Cui, Y. (2019). Multi objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm. Computers & Industrial Engineering, 128,659-680. https://doi.org/10.1016/j.cie.2018.12.065.
Zhang, X., & Chen, L. (2022). A general variable neighborhood search algorithm for a parallel-machine scheduling problem considering machine health conditions and preventive maintenance. Computers & Operations Research, 143,105738. https://doi.org/10.1016/j.cor.2022.105738.
Zhang, X., Liu, S. C., Lin, W. C., & Wu, C.C. (2020). Parallel-machine scheduling with linear deteriorating jobs and preventive maintenance activities under a potential machine disruption. Computers & Industrial Engineering, 145,106482. https://doi.org/10.1016/j.cie.2020.106482.