Grammar‐Based Column Generation for Personalized Multi‐Activity Shift Scheduling

We present a branch‐and‐price algorithm to solve personalized multi‐activity shift scheduling problems. The subproblems in the column generation method are formulated using grammars and solved with dynamic programming. The expressiveness of context‐free grammars is exploited to easily model restrictions over shifts, allowing the branch‐and‐price algorithm to solve large‐scale problem instances. We present computational experiments on two types of multi‐activity shift scheduling problems and compare our approach with existing methods in the literature. These experiments show that our approach can efficiently solve large‐scale instances and is flexible enough to model different classes of problems.