Grammar-Based Column Generation for Personalized Multi-Activity Shift Scheduling
Marie-Claude Côté, Bernard Gendron, Louis-Martin Rousseau
INFORMS Journal on Computing · 2013 · Volume 25 · Issue 3
Abstract
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.
Keywords
shift scheduling, context-free grammars, column generation, branch-and-price
Enable JavaScript for citation tools and additional paper interactions.