Journal article
Solving talent scheduling with dynamic programming
MG De La Banda, PJ Stuckey, G Chu
Informs Journal on Computing | Published : 2011
Abstract
We give a dynamic programming solution to the problem of scheduling scenes to minimize the cost of the talent. Starting from a basic dynamic program, we show a number of ways to improve the dynamic programming solution by preprocessing and restricting the search. We show how by considering a bounded version of the problem, and determining lower and upper bounds, we can improve the search. We then show how ordering the scenes from both ends can drastically reduce the search space. The final dynamic programming solution is orders of magnitude faster than competing approaches and finds optimal solutions to larger problems than were considered previously. © 2011 INFORMS.
Grants
Funding Acknowledgements
The first two authors of this paper thank Manuel Hermenegildo at IMDEA Software, Universidad Polytecnica de Madrid, Spain, whom they were visiting while this work was undertaken. The authors thank Barbara Smith for many interesting discussions on the talent scheduling problem and for giving them her example data files. They also thank the reviewers for their careful reviewing, which improved the paper substantially. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council.