Combining Benders Decomposition and Column Generation for Physician Scheduling in Fever Clinics During Covid-19 Pandemic

This paper presents an approach to solving the physician scheduling problem in fever clinics by combining Benders decomposition and column generation. The Benders decomposition involves iterating between a master problem that computes the physician staffing requirements and a subproblem that allocates physicians’ schedules to meet these requirements. We suggest an approach based on column generation for an effective solution to the subproblem. In addition, several acceleration strategies are provided to enhance the solution’s efficiency. Based on data collected from fever clinics in Shanghai, the numerical study confirms that the proposed method can control patient queue length and physician working hours. It is also demonstrated that the method can effectively optimize physician scheduling under severe epidemics. The models and algorithms developed from this research can assist fever clinics in their operation and management during an epidemic.
Note to Practitioners
—Our study is motivated by our collaboration with a fever clinic in a large hospital in Shanghai, China. Since 2019, the Covid-19 virus has spread worldwide, burdening the healthcare system immensely. In China, fever clinics are on the front line in the fight against Covid-19, providing services to patients at high risk of infection. Because of several specific constraints, the physician scheduling process in such clinics is different and more complex. It is challenging for medical managers to provide physicians with high-quality schedules. In order to solve this problem, we proposed a series of methods. In particular, an approach combining Benders decomposition and column generation is designed to solve the problem exactly, and several acceleration strategies are proposed to solve the problem more effectively. Based on real-life hospital data, we demonstrate that the methods presented in this article may help hospital managers obtain more reasonable scheduling solutions, thereby improving patient service quality without increasing physician workload.