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

Lagrangian relaxation based appointment scheduling model and algorithm

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

With the assumption that each appointment patient up in clinic arrives on time, this paper investigates the appointment scheduling problem with no-show. An integer programming model is estab- lished with the numbers of appointment patient and probability distribution of remaining patients at each slot as optimization variables. The objective function includes the benefits of serving patients, the patient waiting time costs, and system overtime expenses. By relaxing the coupled constraints about probability distribution of remaining patients at each slot, this paper proposes a Lagrangian relaxation method to solve the model with a dynamic programming algorithm solving the relaxation problem and a sub-gradient method solving the dual problem. Numerical experiments show that the algorithm can find the optimal solution for small scale problems, and that the best solution from the proposed algorithm is better than the one in the related literature for large scale problems.