Lagrangian relaxation-based scheduling algorithm for operating theatres

ZHOU Binghai, YIN Meng, ZHONG Zhenyi

Systems Engineering - Theory & Practice ›› 2016, Vol. 36 ›› Issue (1) : 224-233.

PDF(635 KB)
中国科学院数学与系统科学研究院期刊网
PDF(635 KB)
Systems Engineering - Theory & Practice ›› 2016, Vol. 36 ›› Issue (1) : 224-233. DOI: 10.12011/1000-6788(2016)01-0224-10

Lagrangian relaxation-based scheduling algorithm for operating theatres

  • ZHOU Binghai, YIN Meng, ZHONG Zhenyi
Author information +
History +

Abstract

To improve the efficiency of operating theatre effectively, reduce the hospital's costs and improve the satisfaction of patients, an operating theatre scheduling method was presented based on a Lagrangian relaxation (LR) algorithm. Firstly, a problem domain was described. Mathematical programming models were also set up with objective functions of minimizing related costs of the operating theatre and maximizing the satisfaction of patients. On the basis of the descriptions mentioned above, a solving policy of generating feasible scheduling solutions was established. Combining with the specific constraints of operating theatre, the LR-based algorithm was put forward to solve scheduling problems, and the sub-problems were solved via a branch and bound algorithm. Finally, computational experiments were performed on different scale of problems. The performance of the proposed algorithm was evaluated and compared with that of other approaches. Results demonstrated that the proposed method can obtain better near-optimal solutions in acceptable computation time.

Key words

operating theatre scheduling / multi-objective optimization / Lagrangian relaxation algorithm / branch and bound

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
ZHOU Binghai , YIN Meng , ZHONG Zhenyi. Lagrangian relaxation-based scheduling algorithm for operating theatres. Systems Engineering - Theory & Practice, 2016, 36(1): 224-233 https://doi.org/10.12011/1000-6788(2016)01-0224-10

References

[1] Su M C, Lai S C, Wang P C, et al. A SOMO-based approach to the operating room scheduling problem[J]. Expert Systems with Applications, 2011, 38(12): 15447-15454.
[2] 邓富民, 梁学栋, 刘爱军, 等. 多资源约束下改进NSGA-II算法的手术调度[J]. 系统工程理论与实践, 2012, 32(6): 1337-1345.Deng F M, Liang X D, Liu A J, et al. Surgical operation scheduling with multi-resource constrained based on the improved NSGA-II algorithm[J]. Systems Engineering-Theory & Practice, 2012, 32(6): 1337-1345.
[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.
[4] Devi S P, Rao K S, Sangeetha S S. Prediction of surgery times and scheduling of operation theaters in ophthalmology department[J]. Journal of Medical Systems, 2012, 36(1): 415-430.
[5] Lamiri M, Augusto V, Xie X L. Patients scheduling in a hospital operating theatre[C]//IEEE International Conference on Automation Science and Engineering. IEEE, 2008: 627-632.
[6] Huang G X, Xiang W, Li C, et al. Surgical scheduling based on hybrid flow-shop scheduling[C]//3rd International Conference on Engineering Design and Optimization. Trans Tech Publications Ltd, 2012: 1004-1007.
[7] Augusto V, Xie X L, Perdomo V. Operating theatre scheduling using Lagrangian relaxation[J]. European Journal of Industrial Engineering, 2008, 2(2): 172-189.
[8] 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.
[9] 轩华, 唐立新. 实时无等待 HFS调度的一种拉格朗日松弛算法[J]. 控制与决策, 2006, 21(4): 376-380.Xuan H, Tang L X. Lagrangian relaxation algorithm for real-time hybrid flow-shop scheduling with no-wait in process[J]. Control and Decision, 2006, 21(4): 376-380.
[10] 朱宝琳, 于海斌, 黄小原, 等. 基于拉格朗日松弛的供应链合作生产计划模型研究[J]. 控制与决策, 2009, 24(12): 1791-1794, 1800.Zhu B L, Yu H B, Huang X Y, et al. Cooperation production planning model for supply chain based on Lagrangian relaxation technology[J]. Control and Decision, 2009, 24(12): 1791-1794, 1800.
[11] Xuan H, Tang L X. Scheduling a hybrid flowshop with batch production at the last stage[J]. Computers & Operations Research, 2007, 34(9): 2718-2733.
[12] Eastman W L, Even S, Isaacs I M. Bounds for the optimal scheduling of n jobs on m processors[J]. Management Science, 1964, 17(3): 268-279.
[13] Tang L X, Xuan H, Liu J Y. A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time[J]. Computers & Operations Research, 2006, 33(11): 3344-3359.
[14] Wang S, Liu M. A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem[J]. Computers & Operations Research, 2013, 40(4): 1064-1075.
[15] Tang L, Wang X. An improved particle swarm optimization algorithm for the hybrid flowshop scheduling to minimize total weighted completion time in process industry[J]. IEEE Transactions on Control Systems Technology, 2010, 18(6): 1303-1314.

Funding

National Natural Science Foundation of China (71471135, 61273035)
PDF(635 KB)

352

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉