Physician Scheduling Problem through Logic-Based Benders Decomposition
The Physician Scheduling Problem (PSP) addresses the assignment of shifts over a medium to long term planning horizon, a problem that is inherently complex and becomes even more challenging when fairness criteria among professionals are incorporated. Traditionally, it has been modeled using MILP formulations that integrate such criteria into the objective function, or tackled through matheuristic and metaheuristic approaches, since exact methods often struggle to deliver high-quality solutions within reasonable computational times. In this work, we propose an alternative methodology based on Logic-Based Benders Decomposition (LBBD), still underexplored in this domain. The master problem provides a global perspective by ensuring daily coverage, while the subproblem handles detailed shifts assignments. This approach is compared with a monolithic multicommodity flow model, showing advantages in computational time and solution quality under a one-hour runtime.
Keywords: Optimization Physician Scheduling Fairness Logic-Based Benders Decomposition