This lesson addresses a problem known as the talent scheduling problem, which involves deciding on the best order in which to shoot different film scenes in order to minimize actor waiting costs.

In this problem, there are m actors required to shoot n scenes. Each scene s has a filming duration d(s) and each actor a has a cost per unit duration (pay rate) of c(a). Not all actors are required for all scenes, and a predicate r(a,s) determines if actor a is required in scene s.

The scenes are shot in a certain order, and once an actor arrives on set, he will remain there until his last scene has been shot. All actors are paid for their time on set, including any time waiting for scenes to be shot which do not involve them. The objective of the search is to decide on the best filming order of scenes such that the total actor waiting cost is minimized.

For example, see the following 3 actor, 5 scene problem:

This problem has five scenes of filming durations 3, 1, 4, 2 and 2, and three actors who are paid 5, 7 and 2 units of currency per time unit. The central section of the table indicates which actors are required for each scene, a 1 meaning that the actor is required for the corresponding scene, and a 0 meaning that he is not.

If the scenes were filmed in the numerical order given, then actor 1 would have to wait during scene 2 at a cost of 5 units, actor 2 would have to wait during scene 4 at a cost of 14 units, and actor 3 would not wait, incurring no additional cost. The total cost of this filming schedule would be 5+14=19.

Optimal solutions for this problem have a cost of 4. Such a solution is given below:

Here, only actor 3 waits for 2 time units during the filming of scene 5.