Optimizing the physician scheduling problem in a large hospital ward

In recent years, large public hospitals have undergone a strong growth in healthcare services demand, not offset by resources increase. In this context, one of the most critical issues is the optimization of human resources. In this paper, we study the problem of finding the optimal assignment of tasks to physicians over a predefined time horizon in a large general surgery ward. Each task has to be executed by one or more physicians and assigned to one or more time slots in different days. Each physician has a minimum number of hours to work per week. The hours exceeding such a value constitute overtime. The problem minimizes the total time spent by all the physicians (and thus the global overtime) in the hospital to complete the execution of the assigned tasks, while complying with practical and legislative constraints. We propose two mathematical formulations for the problem and exploit both of them to develop repair heuristics of an Adaptive Large Neighborhood Search. A simple matheuristic is used to identify an initial feasible solution within a reasonable amount of time. To test algorithms, we have generated several classes of instances directly inspired by the studied real case. The performance of our solution approach (when setting a time limit of 15 min) has been compared to the results obtained by Gurobi 6.5.1 (with 1 h time limit) when solving both formulations. We show that our algorithm is extremely effective by frequently getting better solutions than Gurobi in a quarter of its computational time.