随机服务时间下的家庭护理人员调度问题研究

Home care crew scheduling problems under service time uncertainty

研究了家庭护理中的医疗服务人员调度问题,考虑了随机的客户服务时间和最迟开始服务时间约束.建立了带补偿的随机规划模型,得到了客户期望迟到惩罚成本的近似计算表达式,并分析了期望惩罚成本的性质.根据问题的特点,基于列生成算法思想建立问题的集分割最优化主问题模型和生成新列的最短路子问题模型,并设计标签算法对子问题加以求解.将列生成算法嵌入到分枝定界过程中形成分枝定价算法得到问题整数可行解.通过数值实验,验证了所提出客户期望迟到惩罚成本近似表达式和分枝定价算法的有效性.

This paper addressed the home care crew scheduling problem,which included stochastic service times and the deadlines of starting service at customers.A stochastic programming model with recourse was proposed to describe the problem.The approximate formula for the expected penalty for late arrivals at customers was obtained,and its properties were analyzed.In order to solve the model,the problem was modeled as a classical set partitioning problem（SPP） and an elementary shortest path problem with resource constraints（ESPPRC） which was for the generation of paths.The SPP and ESPPRC were solved by the column generation algorithm and the label algorithm,respectively.The column generation procedure was embedded within a branch and bound method,which was called the branch and price algorithm,to get integer solutions.The effectiveness of the approximate formula for the expected penalty for late arrivals and the branch and price approach were validated by the numerical experiment.