Solving a multiple-qualifications physician scheduling problem with multiple types of tasks by dynamic programming and variable neighborhood search

This article investigates a novel physician scheduling problem. Different types of tasks can be performed by physicians with certain qualifications. Tasks have different properties depending on their types, lengths, and starting times. Physicians performing tasks can yield different values of benefit and cost according to their qualifications and the task property. The objective is to maximise the sum of profit (i.e., benefit minus cost). For solving the studied problem, three layer-progressive processes are proposed and corresponding solution strategies are developed for them respectively. A Variable Neighbourhood Search is applied in the first-layer process to assign a certain qualification of physicians to each task property. The problem is then decomposed into scheduling physicians of single qualification as the second-layer process. On this layer, a heuristic incorporating a Dynamic Programming algorithm is developed to generate a task property list for each qualification of physicians to guarantee the optimum of the solutions. The Dynamic Programming algorithm is applied on the third-layer process to get the task property list for a physician. In the computational experiments, the proposed approach is compared with three meta-heuristic algorithms and Gurobi. The results show that the proposed approach outperforms other compared algorithms.