The talent scheduling problem can be described as follows. A film producer needs to
schedule the scenes of his/her movie on a given location. Each scene has a duration (the days it takes to
shoot it) and requires some subset of the cast to be on location. The cast are paid for each day they are
required to be on location from the day the first scene they are in is shot, to the day the last scene they are in
is shot, even though some of those days they might not be required by the scene currently being shot (i.e.,
they will be on location waiting for the next scene they are in to be shot). Each cast member has a different
daily salary. The aim of the film producer is to order the scenes in such a way as to minimize the salary cost
of the shooting.
Talent scheduling examples
The format of the following examples is
Name of data file on the first line
Number of scenes
Number of actors
For each actor a line of 1s and 0s
1 indicating the scenes in which the actor appears,
followed by the cost of the actor.
A line of integers the duration of each scene
We give examples below:
Mob Story is the data from the
The remainder were developed by Barbara Smith.
Cheng, T. C. E., J. E. Diamond, B. M. T. Lin. 1993.
Optimal scheduling in film production to minimize talent hold
cost. Journal of Optimization Theory and Applications 79 479-482.
Smith, B.M. 2005. Caching search states in permutation problems. P. Van Beek, ed., Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming - CP 2005,, LNCS, vol. 3709. Springer,
Talent Scheduling Results
Maria Garcia de la Banda, Peter Stuckey and Geoffrey Chu.
We have built a dynamic programming solution
to talent scheduling with a number of optimizations.
Our results are shown in the following table.
We compare against Smiths results: although ours are run on a
2.5GHz Intel Core2 Quad
while hers are from a
1.7GHz Pentium M PC.
The number of cached states and number of subproblems are
equivalent measures from the two approaches.
Below we give the solutions, and all optimial solutions (where the first scene
is numbered before the last scene, to avoid symmetric solutions)
All benchmarks used in the paper:
| || || || Smith || Our results |
| Problem || Actors || Scenes || Time || Cached states || Time || Subproblems
| MobStory || 8 || 20 || 64.71s || 136,765 || 108ms || 6,605
| film105 || 8 || 18 || 16.07s || 40,511 || 20ms || 1,108
| film116 || 8 || 19 || 125.8s || 225,314 || 156ms || 13,576
| film119 || 8 || 18 || 70.80s || 144,226 || 84ms || 7,105
| film118 || 8 || 19 || 93.10s || 205,190 || 40ms || 1,980
| film114 || 8 || 19 || 127.0s || 267,526 || 84ms || 4,957
| film103 || 8 || 19 || 76.69s || 180,133 || 64ms || 4,103
| film117 || 8 || 19 || 76.86s || 174,100 || 96ms || 7,227
are included in the [ZIP]
- M. Garcia de la Banda, P.J. Stuckey, and G. Chu. Solving talent scheduling
with dynamic programming. INFORMS Journal of Computing, 23(1):120-137,