A variable neighborhood search algorithm for a PET/CT examination scheduling problem considering multi-stage process and deteriorating effect
Tóm tắt
In this paper, a Positron Emission Tomography/Computed Tomography (PET/CT) examination scheduling problem considering multi-stage processes is studied. Before the actual examination process, imaging agents (a drug with radioactivity) need to be injected into patients. The radioactivity of the imaging agents continuously decays, which results in the required dose by patients increasing with time, i.e., the later the injection time, the more imaging agents need to be prepared for the patients at the beginning. Considering the imaging agents are expensive and non-storable, the studied problem is to determine the start time of the examination service and injection time for the patients, to minimize the total dose of purchased imaging agents. An integer programming model and a set partitioning model are formulated for this problem. A variable neighborhood search heuristic is proposed, in which a scheduling rule based on some derived optimal properties is embedded as one of the search operators. Computational experiments show that the proposed algorithm can obtain near-optimal solutions in a short time, and moreover find much better results than the commonly used First Come First Service (FCFS) rule in most medical institutions, i.e., our approach’s results need much fewer required dose of the imaging agents, and hence can save a lot of costs for the medical institutions.
Tài liệu tham khảo
Aristophanous, M., Berbeco, R.I., Killoran, J.H., Yap, J.T., Sher, D.J., Allen, A.M., Larson, E., Chen, A.B.: Clinical utility of 4D FDG-PET/CT scans in radiation treatment planning. Int. J. Radiat. Oncol. Biol. Phys. 82(1), 99–105 (2012). https://doi.org/10.1016/j.ijrobp.2010.12.060
Arık, O.A.: Population-based Tabu search with evolutionary strategies for permutation flow shop scheduling problems under effects of position-dependent learning and linear deterioration. Soft. Comput. 25(2), 1501–1518 (2021). https://doi.org/10.1007/s00500-020-05234-7
Bansal, J.C.: Particle swarm optimization. In: Bansal, J.C., Singh, P.K., Pal, N.R. (eds.) Evolutionary and Swarm Intelligence Algorithms, pp. 11–23. Springer, Cham (2019)
Bilge, Ü., Kiraç, F., Kurtulan, M., Pekgün, P.: A tabu search algorithm for parallel machine total tardiness problem. Comput. Oper. Res. 31(3), 397–414 (2004). https://doi.org/10.1016/S0305-0548(02)00198-3
Cheng, T.C.E., Lee, W.C., Wu, C.C.: Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. Appl. Math. Model. 35(4), 1861–1867 (2011). https://doi.org/10.1016/j.apm.2010.10.015
Cui, W.W., Lu, Z., Pan, E.: Integrated production scheduling and maintenance policy for robustness in a single machine. Comput. Oper. Res. 47, 81–91 (2014). https://doi.org/10.1016/j.cor.2014.02.006
Engin, O., Güçlü, A.: A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems. Appl. Soft Comput. J. 72, 166–176 (2018). https://doi.org/10.1016/j.asoc.2018.08.002
Garey, M.R., Johnson, D.S., Sethi, R.: Complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2), 117–129 (1976). https://doi.org/10.1287/moor.1.2.117
Hansen, P., Mladenović, N., Moreno Pérez, J.A.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175(1), 367–407 (2010). https://doi.org/10.1007/s10479-009-0657-6
Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33(10), 3034–3045 (2006). https://doi.org/10.1016/j.cor.2005.02.033
Ji, M., Cheng, T.C.E.: Parallel-machine scheduling with simple linear deterioration to minimize total completion time. Eur. J. Oper. Res. 188(2), 342–347 (2008). https://doi.org/10.1016/j.ejor.2007.04.050
Johnson, S.M.: With setup times included. Naval Res. Logist. Q. 1, 61–68 (1954)
Koulamas, C.: Common due date assignment with generalized earliness/tardiness penalties. Comput. Ind. Eng. 109, 79–83 (2017). https://doi.org/10.1016/j.cie.2017.04.040
Li, S.S., Chen, R.X.: Scheduling with common due date assignment to minimize generalized weighted earliness–tardiness penalties. Optim. Lett. 14(7), 1681–1699 (2020). https://doi.org/10.1007/s11590-019-01462-5
Liu, S., Pei, J., Cheng, H., Liu, X., Pardalos, P.M.: Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes. Appl. Soft Comput. J. 84, 105701 (2019). https://doi.org/10.1016/j.asoc.2019.105701
Mazdeh, M.M., Zaerpour, F., Zareei, A., Hajinezhad, A.: Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs. Appl. Math. Model. 34(6), 1498–1510 (2010). https://doi.org/10.1016/j.apm.2009.08.023
Mirjalili, S.: Genetic algorithm. In: Mirjalili, S. (ed.) Evolutionary Algorithms and Neural Networks, pp. 43–55. Springer, Cham (2019a)
Mirjalili, S.: Ant colony optimisation. In: Mirjalili, S. (ed.) Evolutionary Algorithms and Neural Networks, pp. 33–42. Springer, Cham (2019)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997). https://doi.org/10.1016/S0305-0548(97)00031-2
Pei, J., Liu, X., Fan, W., Pardalos, P.M., Lu, S.: A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega (UK) 82, 55–69 (2019). https://doi.org/10.1016/j.omega.2017.12.003
Rosa, B.F., Souza, M.J.F., de Souza, S.R., de França Filho, M.F., Ales, Z., Michelon, P.Y.P.: Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties. Comput. Oper. Res. (2017). https://doi.org/10.1016/j.cor.2016.12.024
Rossit, D.A., Vásquez, Ó.C., Tohmé, F., Frutos, M., Safe, M.D.: A combinatorial analysis of the permutation and non-permutation flow shop scheduling problems. Eur. J. Oper. Res. 289(3), 841–854 (2021). https://doi.org/10.1016/j.ejor.2019.07.055
Ruiz, R., Pan, Q.K., Naderi, B.: Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega (UK) 83, 213–222 (2019). https://doi.org/10.1016/j.omega.2018.03.004
Ruiz, R., Vázquez-Rodríguez, J.A.: The hybrid flow shop scheduling problem. Eur. J. Oper. Res. 205(1), 1–18 (2010). https://doi.org/10.1016/j.ejor.2009.09.024
Sánchez-Herrera, S., Montoya-Torres, J.R., Solano-Charris, E.L.: Flow shop scheduling problem with position-dependent processing times. Comput. Oper. Res. 111, 325–345 (2019). https://doi.org/10.1016/j.cor.2019.06.015
Steward, B.W., Wild, C.P.: World cancer report 2014. Technical report, World Health Organization, International Agency for Research on Cancer (2014)
Tse, P.W., Atherton, D.P.: Prediction of machine deterioration using vibration based fault trends and recurrent neural networks. J. Vib. Acoust. (1999). https://doi.org/10.1115/1.2893988
Wang, J.B., Cheng, T.E.: Scheduling problems with the effects of deterioration and learning. Asia-Pac. J. Oper. Res. 24(02), 245–261 (2007). https://doi.org/10.1142/S021759590700122X
Wang, J.B.: Single-machine scheduling problems with the effects of learning and deterioration. Omega 35(4), 397–402 (2007). https://doi.org/10.1016/j.omega.2005.07.008
World Health Organization: GLOBOCAN 2018 (2018). http://globocan.iarc.fr/Default.aspx. Accessed 1 Oct 2020
Wu, X., Shen, X., Li, C.: The flexible job-shop scheduling problem considering deterioration effect and energy consumption simultaneously. Comput. Ind. Eng. 135, 1004–1024 (2019). https://doi.org/10.1016/j.cie.2019.06.048
Zhen, L., Liang, Z., Zhuge, D., Lee, L.H., Chew, E.P.: Daily berth planning in a tidal port with channel flow control. Transp. Res. Part B Methodol. 106, 193–217 (2017). https://doi.org/10.1016/j.trb.2017.10.008