Solving the planning and scheduling problem simultaneously in a hospital with a bi-layer discrete particle swarm optimization

Xiuli Wu; Xianli Shen; Linjuan Zhang; Xiuli Wu; Xianli Shen; Linjuan Zhang

doi:10.3934/mbe.2019039

Mathematical Biosciences and Engineering

2019, Volume 16, Issue 2: 831-861. doi: 10.3934/mbe.2019039

Previous Article Next Article

Research article

Solving the planning and scheduling problem simultaneously in a hospital with a bi-layer discrete particle swarm optimization

1.
Department of logistics engineering, School of Mechanical Engineering, University of Science and Technology Beijing, Beijing, China
2.
Department of Anesthesiology, the First Affiliated Hospital of Xi'an Jiaotong University, Xi’an, China

Received: 18 October 2018 Accepted: 10 December 2018 Published: 28 January 2019

The operating room is one of the most capital-intensive resources for a hospital. To achieve further improvements and to restrict cost increases, hospitals may need to operate more efficiently with the resources they already possess. The paper considers the joint problem of planning and scheduling patients in operating rooms on an operational level (weekly basis) with two objectives: maximizing the overall patients' satisfaction and minimizing the cost of overtime in operating rooms as well as the daily cost of operating rooms and recovery beds, which is NP-hard. The decision problem is solved using a bi-layer discrete particle swarm optimization, introducing a repair mechanism for infeasible solutions, specific operators like crossover, insertion and exchange. Moreover, a gap finding scheduling heuristic is designed to solve the surgical case sequencing problem. We first compare the performance of the proposed solution method to that of Fei et al. for three instances separately, using data of a Chinese hospital. Next, the efficient Pareto solutions for the joint problem are presented. The results show that the bi-layer discrete particle swarm optimization can solve the operating room scheduling efficiently and effectively.
Citation: Xiuli Wu, Xianli Shen, Linjuan Zhang. Solving the planning and scheduling problem simultaneously in a hospital with a bi-layer discrete particle swarm optimization[J]. Mathematical Biosciences and Engineering, 2019, 16(2): 831-861. doi: 10.3934/mbe.2019039

Related Papers:

Abstract

The operating room is one of the most capital-intensive resources for a hospital. To achieve further improvements and to restrict cost increases, hospitals may need to operate more efficiently with the resources they already possess. The paper considers the joint problem of planning and scheduling patients in operating rooms on an operational level (weekly basis) with two objectives: maximizing the overall patients' satisfaction and minimizing the cost of overtime in operating rooms as well as the daily cost of operating rooms and recovery beds, which is NP-hard. The decision problem is solved using a bi-layer discrete particle swarm optimization, introducing a repair mechanism for infeasible solutions, specific operators like crossover, insertion and exchange. Moreover, a gap finding scheduling heuristic is designed to solve the surgical case sequencing problem. We first compare the performance of the proposed solution method to that of Fei et al. for three instances separately, using data of a Chinese hospital. Next, the efficient Pareto solutions for the joint problem are presented. The results show that the bi-layer discrete particle swarm optimization can solve the operating room scheduling efficiently and effectively.

References

[1]	X. Chen, Z. P. Fan, Z. W. Li, X. L. Han, X. Zhang and H. C. Jia, A two-stage method for member selection of emergency medical service, J. Comb. Optim., 30 (2015), 871–891.
[2]	B. Wang, X. B. Han, X. X. Zhang, and S. H. Zhang, Predictive-reactive scheduling for single surgical suite subject to random emergency surgery, J. Comb. Optim., 30 (2015), 949–966.
[3]	M. E. Bruni, P. Beraldi, and D. Conforti, A stochastic programming approach for operating theatre scheduling under uncertainty, Ima. J. Manage. Math., 26 (2015), 99–119.
[4]	Z. X. Zhao and X. P. Li, Scheduling elective surgeries with sequence-dependent setup times to multiple operating rooms using constraint programming, Oper. Res. Health. Car., 3 (2014), 160–167.
[5]	S. Neyshabouri and B. P. Berg, Two-stage robust optimization approach to elective surgery and downstream capacity planning, Eur. J. Oper. Res., 260 (2016), 21–40.
[6]	D. Min and Y. Yih, An elective surgery scheduling problem considering patient priority, Comput. Oper. Res., 37 (2010), 1091–1099.
[7]	A. Jebali and A. Diabat, A Chance-constrained operating room planning with elective and emergency cases under downstream capacity constraints, Comput. Ind. Eng., 114 (2017), 329–344.
[8]	M. Lamiri, X. L. Xie, A. Dolgui and F. Grimaud, A stochastic model for operating room planning with elective and emergency demand for surgery, Eur. J. Oper. Res., 185 (2008), 1026–1037.
[9]	A. Abedini, H. H. Ye and W. Li, Operating room planning under surgery type and priority constraints, Procedia. Manuf., 5 (2016), 15–25.
[10]	N. Dellaert and J. Jeunet, A variable neighborhood search algorithm for the surgery tactical planning problem, Comput. Oper. Res., 84 (2017), 1–10.
[11]	Y. Yang, B. Shen, W. Gao, Y. Liu and L. W. Zhong, A surgical scheduling method considering surgeons' preferences, J. Comb. Optim., 30 (2015), 1016–1026.
[12]	T. M. Range, R. M. Lusby and J. Larsen, A column generation approach for solving the patient admission scheduling problem, Eur. J. Oper. Res., 235 (2014), 252–264.
[13]	W. Xiang, J. Yin and G. Lim, An ant colony optimization approach for solving an operating room surgery scheduling problem, Comput. Ind. Eng., 85 (2015), 335–345.
[14]	A. Riise, C. Mannino and E. K. Burke, Modelling and solving generalised operational surgery scheduling problems, Comput. Oper. Res., 66 (2016), 1–11.
[15]	D. Duma and R. Aringhieri, An online optimization approach for the real time management of operating rooms, Oper. Res. Health. Car., 7 (2015), 40–51.
[16]	F. Guerriero and R. Guido, Operational research in the management of the operating theatre: A survey, Health. Car. Manage. Sci., 14 (2011), 89–114.
[17]	E. Demeulemeester, J. Beliën, B. Cardoen and M. Samudra, Operating room planning and scheduling, Eur. J. Oper. Res., 201 (2010), 921–932.
[18]	R. M'. Hallah and A. H. Al-Roomi, The planning and scheduling of operating rooms: A simulation approach, Comput. Ind. Eng., 78 (2014), 235–248.
[19]	R. Aringhieri, P. Landa, P. Soriano, E. Tànfani and A. Testi, A two level metaheuristic for the operating room scheduling and assignment problem, Comput. Oper. Res., 54 (2015), 21–34.
[20]	R. Guido and D. Conforti, A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem, Comput. Oper. Res., 87 (2016), 270–282.
[21]	H. Y. Fei, N. Meskens and C. B. Chu, A planning and scheduling problem for an operating theatre using an open scheduling strategy, Comput. Ind. Eng., 58 (2010), 221–230.
[22]	J. M. Molina-Pariente, V. Fernandez-Viagas and J. M. Framinan, Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations, Comput. Ind. Eng., 82 (2015), 8–20.
[23]	P. Landa, R. Aringhieri, P. Soriano, E. Tànfani and A. Testi, A hybrid optimization algorithm for surgeries scheduling, Oper. Res. Health. Car., 8 (2016), 103–114.
[24]	A. J. Fong, M. Smith and A. Langerman, Efficiency improvement in the operating room, J. Surg. Res., 204 (2016), 371–383.
[25]	D. N. Pham and A. Klinkert, Surgical case scheduling as a generalized job shop scheduling problem, Eur. J. Oper. Res., 185 (2008), 1011–1025.
[26]	L. W. Zhong, S. C. Luo, L. D. Wu, L. Xu, J. H. Yang and G. C. Tang, A two-stage approach for surgery scheduling, J. Comb. Optim., 27 (2014), 545–556.
[27]	R. Burdett and E. Kozan,An integrated approach for scheduling health care activities in a hospital, Eur. J. Oper. Res., 264 (2017), 756–773.
[28]	A. Abedini, W. Li and H. H. Ye, An optimization model for operating room scheduling to reduce blocking across the perioperative process, Procedia. Manuf., 10 (2017), 60–70.
[29]	J. N. D. Gupta, Two-stage, hybrid flow shop scheduling problem, J. Oper. Res. Soc., 39 (1988), 359–364.
[30]	J. Q. Li, H. Y. Sang, Y. Y. Han, C. G. Wang and K. Z. Gao, Efficient multi-objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions, J. Cleaner. Prod., 181 (2018), 584–598.
[31]	J. Q. Li, Q. K. Pan and M. F. Tasgetiren, A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities, Appl. Math. Model., 38 (2014), 1111–1132.
[32]	H. C. Liu, L. Gao and Q. K. Pan, A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem, Exp. Syst. Appl., 38 (2011), 4348–4360.
[33]	J. Q. Li, Q. K. Pan and F. T. Wang, A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem, Appl. Soft. Comput. J., 24 (2014), 63–77.
[34]	X. Y. Li and L. Gao, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, Int. J. Prod. Econ., 174 (2016), 93–110.
[35]	S. Gao and C. G. Cao, Convergence analysis of particle swarm optimization algorithm, Sci. Technol. Eng., 4 (2008), 25–32.
[36]	M. A. Ghorbani, R. Kazempour, K. W. Chau and S. Shamshirband, Forecasting pan evaporation with an integrated Artificial Neural Network Quantum-behaved Particle Swarm Optimization model: A case study in Talesh, Northern Iran, Eng. Appl. Comput. Fluid. Mech., 12 (2018), 724–737.
[37]	J. Kennedy and R. C. Eberhart, Particle swarm optimization, Proc. IEEE. Int. Conf. Neural. Networks., 4 (1995), 1942–1948.
[38]	Q. K. Pan, W. H. Wang and J. Y. Zhu, Modified discrete particle swarm optimization algorithm for no-wait flow shop problem, Comput. Integr. Manuf. Syst., 13 (2007), 1127–1130.
[39]	X. L. Wu, S. D. Sun, J. J. Yu and H. F. Zhang, Research on multi-objective optimization for flexible job shop scheduling, Comput. Integr. Manuf. Syst., 12 (2006), 731–736.
[40]	M. J. Tessler, S. J. Kleiman and M. M. Huberman, A
[41]	M. Schuster, T. Standl, J. A. Wagner and J. Berger, Effect of different cost drivers on cost per anesthesia minute in different anesthesia subspecialties, Anesthesiology, 101 (2004), 1435–1443.
[42]	Y. Shi and R. C. Eberhart, Empirical study of particle swarm optimization, Proc. IEEE Congr. Evol. Comput., (1999), 1945–1950.
[43]	X. L. Wu and Y. J. Sun, A green scheduling algorithm for flexible job shop with energy-saving measures, J. Cleaner. Prod., 172 (2017), 3249–3264.

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)