摘要：针对带有爽约的预约调度问题，在假定未爽约病人都在相应预约段的起始点准时到达的情况下，构建了一个以预约人数为优化变量的整数规划模型．目标函数包括服务病人收益、病人等待费用及系统超时费用．通过松弛各时间段剩余人数概率的关联约束，提出了基于拉格朗日松弛的求解算法，其松弛问题通过动态规划求解，对偶问题通过经典的次梯度法求解．数值实验表明，针对小规模的预约段数，该算法都能找到最优解；当预约段数较大时，算法找到的最好解整体上优于文献中已有的算法，从而验证了算法的有效性．

关键词：预约调度 过度预约 爽约 拉格朗日松弛算法 动态规划 

单位：厦门大学自动化系; 厦门361005; 厦门大学计算机科学系; 厦门361005