Exact algorithms for a personnel scheduling problem in intra-hospital patient transfer with hierarchical objectives
研究一家医疗物流公司为医院内部转运患者的人员排班问题，提出三种精确算法，其中分解方法能快速求解所有实际案例，并分析了员工数量、班次时长等参数对最优解的影响。
Abstract We study a personnel scheduling problem faced by a healthcare and pharmaceutical logistics company, whose goal is to schedule a set of identical employees to transport patients within different healthcare facilities of a hospital. In addition to minimizing the total number of working hours in the schedule, we also aim to maximize shift homogeneity, where two shifts are considered homogeneous if they start and end at the same time, possibly on different days. We introduce three solution methods: two based on integer linear programming (ILP) and one using a decomposition approach in which shifts are determined in the master problem and assigned to employees in the subproblem. We show that the decomposition approach can solve all real-world instances provided by the company in a short amount of time, unlike the ILP models. We also provide managerial insights regarding the effect on the optimal solution of modifying certain instance parameters, such as varying the number of employees, allowing for shorter shifts, and imposing a mandatory lunch break in each shift. Finally, we investigate instance features that make our scheduling problem more difficult to solve for the proposed approaches.