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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1287/ijoc.1120.0514 | INFORMS Journal on Computing |
Keywords | Field | DocType |
grammar-based column generation,context-free grammar,large-scale instance,branch-and-price algorithm,large-scale problem instance,model restriction,multi-activity shift scheduling problem,personalized multi-activity shift scheduling,different class,dynamic programming,computational experiment,column generation method,context free grammars,column generation,branch and price | Rule-based machine translation,Dynamic programming,Mathematical optimization,Column generation,Context-free grammar,Fair-share scheduling,Scheduling (computing),Computer science,Branch and price,Theoretical computer science,Dynamic priority scheduling | Journal |
Volume | Issue | ISSN |
25 | 3 | 1091-9856 |
Citations | PageRank | References |
14 | 0.67 | 17 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marie-Claude Cô/té/ | 1 | 14 | 0.67 |
Bernard Gendron | 2 | 688 | 49.92 |
Louis-Martin Rousseau | 3 | 888 | 63.71 |