Talent Scheduling

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 paper

The remainder were developed by Barbara Smith.

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.
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
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: are included in the [ZIP]