[1] Zhou Binghai, Yin Meng,. Novel operating theatre scheduling methodbased on estimation of distribution algorithm [J]. Journal of Southeast University (English Edition), 2016, 32 (1): 112-118. [doi:10.3969/j.issn.1003-7985.2016.01.019]
Copy
Novel operating theatre scheduling methodbased on estimation of distribution algorithm(
)
基于分布估计的新型手术室调度算法
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 32
- Issue:
- 2016 1
- Page:
- 112-118
- Research Field:
- Computer Science and Engineering
- Publishing date:
- 2016-03-20
Info
- Title:
- Novel operating theatre scheduling methodbased on estimation of distribution algorithm
- 基于分布估计的新型手术室调度算法
- Author(s):
- Zhou Binghai; Yin Meng
- School of Mechanical Engineering, Tongji University, Shanghai 201804, China
- PACS:
- TP391
- DOI:
- 10.3969/j.issn.1003-7985.2016.01.019
- Abstract:
- In order to improve the efficiency of operating rooms, reduce the costs for hospitals and improve the level of service qualities, a scheduling method was developed based on an estimation of distribution algorithm(EDA). First, a scheduling problem domain is described. Based on assignment constraints and resource capacity constraints, the mathematical programming models are set up with an objective function to minimize the system makespan. On the basis of the descriptions mentioned above, a solution policy of generating feasible scheduling solutions is established. Combined with the specific constraints of operating theatres, the EDA-based algorithm is put forward to solve scheduling problems. Finally, simulation experiments are designed to evaluate the scheduling method. The orthogonal table is chosen to determine the parameters in the proposed method. Then the genetic algorithm and the particle swarm optimization algorithm are chosen for comparison with the EDA-based algorithm, and the results indicate that the proposed method can decrease the makespan of the surgical system regardless of the size of operations. Moreover, the computation time of the EDA-based algorithm is only approximately 5 s when solving the large scale problems, which means that the proposed algorithm is suitable for carrying out an on-line scheduling optimization of the patients.
- 为了提高手术室的利用率、降低医院的成本、提高服务质量的水平, 提出了一种基于分布估计的调度算法(EDA).首先, 对问题域进行描述, 以最大完成时间最小为优化目标, 在考虑手术分配约束和资源能力约束的基础上, 建立数学规划模型;在此基础上, 建立可行调度解策略, 结合手术室特有的约束条件, 提出基于分布估计的手术室调度算法;最后, 设计仿真实验, 采用正交试验确定算法中的参数后, 与遗传算法和粒子群算法进行对比, 不同规模的实验结果表明该算法能够减少手术系统总完成时间, 且在大规模情况下运行时间仅为5 s, 说明该算法适应大规模实际情况下的手术室调度.
References:
[1] Aringhieri R, Landa P, Soriano P, et al. A two level metaheuristic for the operating room scheduling and assignment problem [J]. Computers & Operations Research, 2015, 54: 21-34. DOI:10.1016/j.cor.2014.08.014.
[2] Choi S, Wilhelm W E. An approach to optimize block surgical schedules [J]. European Journal of Operational Research, 2014, 235(1): 138-148. DOI:10.1016/j.ejor.2013.10.040.
[3] Vijayakumar B, Parikh P J, Scott R, et al. A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital [J]. European Journal of Operational Research, 2013, 224(3): 583-591. DOI:10.1016/j.ejor.2012.09.010.
[4] Zhao Z X, Li X P. Scheduling elective surgeries with sequence-dependent setup times to multiple operating rooms using constraint programming [J]. Operations Research for Health Care, 2014, 3(3): 160-167. DOI:10.1016/j.orhc.2014.05.003.
[5] Augusto V, Xie X L, Perdomo V. Operating theatre scheduling with patient recovery in both operating rooms and recovery beds [J]. Computers & Industrial Engineering, 2010, 58(2): 231-238. DOI:10.1016/j.cie.2009.04.019.
[6] Devi S P, Rao K S, Sangeetha S S. Prediction of surgery times and scheduling of operation theaters in optholmology department [J]. Journal of Medical Systems, 2012, 36(2): 415-430. DOI:10.1007/s10916-010-9486-z.
[7] Wang Y, Tang J F, Pan Z D, et al. Particle swarm optimization-based planning and scheduling for a laminar-flow operating room with downstream resources [J]. Soft Computing, 2015, 19(10): 2913-2926. DOI:10.1007/s00500-014-1453-z.
[8] Wang Y, Miao Y H, Zhu H, et al. A particle swarm optimization algorithm on the surgery scheduling problem with downstream process [C]//Proceedings of Chinese Control and Decision. Guiyang, China, 2013: 850-855.
[9] Xiang W, Yin J, Lim G. Modified ant colony algorithm for surgery scheduling under multi-resource constraints [J]. Advances in Information Sciences & Service Sciences, 2013, 5(9): 810-818.
[10] Souki M, Rebai A. Heuristics for the operating theatre planning and scheduling [J]. Journal of Decision Systems, 2010, 19(2): 225-252. DOI:10.3166/jds.19.225-252.
[11] Wang S, Wang L, Xu Y. An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with stochastic processing time [C]//2013 32nd Chinese Control Conference(CCC). Xi’an, China, 2013: 2456-2461.
[12] Wang S, Wang L, Liu M, et al. An estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem [C]//2013 IEEE Symposium on Computational Intelligence in Scheduling(SCIS). Singapore, 2013: 13814107-1-13814107-8.
[13] Hauschild M, Pelikan M. An introduction and survey of estimation of distribution algorithms [J]. Swarm and Evolutionary Computation, 2011, 1(3): 111-128. DOI:10.1016/j.swevo.2011.08.003.
[14] Mühlenbein H. The equation for response to selection and its use for prediction [J]. Evolutionary Computation, 1997, 5(3): 303-346.
[15] Latif M S, Zhou H, Amir M. A hybrid quantum estimation of distribution algorithm(Q-EDA)for flow-shop scheduling [C]//Ninth International Conference on Natural Computation(ICNC). Shenyang, China, 2013: 654-658.
[16] Latif M S, Hong Z, Ali A. An estimation of distribution algorithm(EDA)variant with QGA for flowshop scheduling problem [C]//Sixth International Conference on Digital Image Processing(ICDIP 2014). Athens, Greece, 2014: 915908. DOI:10.1117/12.2064054.
[17] Liu Z, Wang S. Hybrid particle swarm optimization for permutation flow shop scheduling [C]//The Sixth World Congress on Intelligent Control and Automation, WCICA 2006. Dalian, China, 2006: 3245-3249.
Memo
- Memo:
-
Biography: Zhou binghai(1965—), male, doctor, professor, bhzhou@tongji.edu.cn.
Foundation item: The National Natural Science Foundation of China(No.61273035, 71471135).
Citation: Zhou Binghai, Yin Meng. Novel operating theatre scheduling method based on estimation of distribution algorithm[J].Journal of Southeast University(English Edition), 2016, 32(1):112-118.DOI:10.3969/j.issn.1003-7985.2016.01.019.