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

Home care crew scheduling problems under service time uncertainty

作　　者：袁彪[1] 刘冉[1] 江志斌[1] 耿娜[1] 

机构地区：[1]上海交通大学工业工程与管理系,上海200240

出　　处：《系统工程理论与实践》2015年第12期3083-3091,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71302013);高等学校博士学科点专项科研基金(20130073120047);上海市浦江人才计划项目(13PJC075);上海市自然科学基金(13ZR1456400)

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

关 键 词：家庭护理 随机服务时间 半时间窗约束 分枝定价 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] U116.2[自动化与计算机技术—计算机科学与技术]