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.