基于拉格朗日松弛的预约调度模型与算法

发布时间：2018-01-30 01:25

本文关键词： 预约调度过度预约爽约拉格朗日松弛算法动态规划　出处：《系统工程理论与实践》2016年06期 　论文类型：期刊论文

【摘要】：针对带有爽约的预约调度问题,在假定未爽约病人都在相应预约段的起始点准时到达的情况下,构建了一个以预约人数为优化变量的整数规划模型.目标函数包括服务病人收益、病人等待费用及系统超时费用.通过松弛各时间段剩余人数概率的关联约束,提出了基于拉格朗日松弛的求解算法,其松弛问题通过动态规划求解,对偶问题通过经典的次梯度法求解.数值实验表明,针对小规模的预约段数,该算法都能找到最优解;当预约段数较大时,算法找到的最好解整体上优于文献中已有的算法,从而验证了算法的有效性.
[Abstract]:In order to solve the problem of reservation scheduling with breaking down, it is assumed that the patients who have not reneged will arrive on time at the starting point of the corresponding reservation segment. An integer programming model with reservation number as the optimization variable is constructed. The objective function includes the benefits of service patients, patient waiting costs and system timeout costs. By loosening the correlation constraints of the probability of the remaining number of people in each time period, the paper constructs an integer programming model with reservation number as the optimization variable. A solution algorithm based on Lagrangian relaxation is proposed. The relaxation problem is solved by dynamic programming and the dual problem is solved by the classical subgradient method. Numerical experiments show that the number of reserved segments is small. The algorithm can find the optimal solution. When the number of reserved segments is large, the best solution found by the algorithm is better than that of the existing algorithms in the literature, which verifies the validity of the algorithm.
【作者单位】：厦门大学自动化系;厦门大学计算机科学系;
【基金】：国家自然科学基金(11201391,61303004)~~
【分类号】：TP301.6
【正文快照】： i引言近年来,随着医疗信息化的发展以及人们医疗需求的增加,国家对卫生事业投入的比重逐步加大,医疗运作管理研究得到快速发展.预约调度问题作为医疗运作管理中一个重要环节,吸引了众多学者的研究卜A从1952年Baikal的第一篇关于预约调度规则的文献起,预约调度经过60多年的发

【相似文献】