A column-generation-based approach for an integrated service planning and physician scheduling problem considering re-consultation

In this paper, an integrated service planning and physician scheduling problem in the outpatient department is investigated, considering the re-consultation of patients as well as multiple types of physicians and consultation services. The problem is to determine 1) the number of patients to be served for each type of consultation service in each shift of a planning horizon and, 2) the working schedule for all planned physicians during the horizon, to maximize the total net benefit of the department. An integer programming model is presented as the original model, which is further decomposed into a Master Problem (MP) and several Pricing Problems (PPs). An approach that incorporates the Column Generation (CG) heuristic and the Variable Neighborhood Search algorithm (VNS), i.e., CG-VNS, is developed to solve the problem. In the computational experiments, the proposed CG-VNS is compared with the original model in the small-scale instances. In the large-scale instances, the proposed CG-VNS is compared with CG-Gurobi, which applies the hybrid CG and the solver Gurobi to calculate the restricted MP and the PPs. The performances of the proposed CG-VNS and the CG-Gurobi approach are further tested in the experiments.