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

Lan S. Fan W. Yang S. Mladenović N. Pardalos P.M.
2022 Taylor and Francis Ltd.

Journal of the Operational Research Society
2022 #73 Issue 9 2043 - 2058 pp.

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.

dynamic programming , multiple qualifications , multiple types of tasks , Physician scheduling problem , Variable Neighbourhood Search

Text of the article Перейти на текст статьи

School of Management, Hefei University of Technology, Hefei, China
Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education, Hefei, China
Khalifa University, Abu Dhabi, United Arab Emirates
Institute of Information and Computational Technologies, Alma Ata, Kazakhstan
University of Florida, Gainesville, FL, United States

School of Management
Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education
Khalifa University
Institute of Information and Computational Technologies
University of Florida

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026