The Optimal Craft of Movie Shooting Schedule

In a movie, there are often numerous scenes, each resembling puzzle pieces, meticulously arranged by the director. These scenes unfold, not always in sequential order, forming the cohesive narrative of the film.

Production teams utilize various strategies to optimize shooting schedules while minimizing costs. This may involve scheduling scenes with overlapping locations or similar set designs to maximize efficiency. Additionally, negotiating contracts with cast and crew, employing scheduling software for optimization, and carefully managing resources all contribute to achieving the dual goals of speed and cost-effectiveness in filmmaking.

This episode focuses on the application of constraint programming in scheduling movie shoots.

• For instance, let’s consider a scenario with 19 scenes and 11 actors/actresses.
• Each individual is assigned specific scenes and corresponding compensation based on their involvement.

Data

1  Patt    26481 2 5  7 10 11 13 15 17  .
2  Casta   25043 4 7  9 10 13 16 19  .  .
3  Scolaro 30310 3 6  9 10 14 16 17 18  .
4  Murphy   4085 2 8 12 13 15  .  .  .  .
5  Brown    7562 2 3 12 17  .  .  .  .  .
6  Hacket   9381 1 2 12 13 18  .  .  .  .
7  Anderson 8770 5 6 14  .  .  .  .  .  .
8  McDougal 5788 3 5  6  9 10 12 15 16 18
9  Mercer   7423 3 4  5  8  9 16  .  .  .
10 Spring   3303 5 6  .  .  .  .  .  .  .
11 Thompson 9593 6 9 12 15 18  .  .  .  .        

The data is read as follows:

Patt's salary is $26481/day and he is about to take part in scenes [2 5 7 10 11 13 15 17]

Assumptions

• An artist will receive the daily rate no matter how many scense he/she is involved in
• Max number of scenes per day is 5

First, I’ll outline the mathematical formulation of the problem, followed by implementing the solution using the ORTools optimization package.

Problem formulation

Case 1) Cost minimization, no additional constraint

1. Objective function is defined as the total payments to the artists.
2. Each scene should be assigned to one day
3. The toal scenes assigned to each day should not exceed 5
4. If an artist is not assigned to day d then all scens with this person involved will be cancelled
5. U_sd, AC_ad show if scene s/actor a is scheduled on day d (binary variables)

Python Code

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}
for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)
for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)
for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 
expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
  print("OPTIMAL")
elif status == cp_model.FEASIBLE:
  print("FEASIBLE")
elif status == cp_model.INFEASIBLE:
  print("INFEASIBLE")
  print("FEASIBLE")
elif status == cp_model.UNKNOWN:
  print("UNKNOWN")        

Result:

The total costs would be OF = $334144.0,

On the day 1: Thompson, Spring, McDougal, Anderson, Hacket and Scolaro are supposed be present to take the scenes [1, 6,14 and 18].

Case 2) Cost minimization, Symmetry Breaking

Case 1 exhibits symmetry, indicating that exchanging any pair of days would yield the same objective function. This symmetry arises due to the absence of precedence constraints within the problem.

We can easily break this symmetry by adding the following constraint:

Constraint 5 imposes a requirement for the solver to organize the assignment of scenes to each day in ascending order.

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}
for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)
for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)
  if d+1 in days:
    expressions_scen = [s*U[s,d] for s in scenes ]
    expressions_scen2 = [s*U[s,d+1] for s in scenes ]
    model.Add( sum(expressions_scen) <= sum(expressions_scen2))
  
for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
  print("OPTIMAL")
elif status == cp_model.FEASIBLE:
  print("FEASIBLE")
elif status == cp_model.INFEASIBLE:
  print("INFEASIBLE")
  print("FEASIBLE")
elif status == cp_model.UNKNOWN:
  print("UNKNOWN")        

OF = $334144.0 (no suprise this is the same as case 1, but solver does not have to check all possible solutions to return the optimal solution)

The total sum of scenes'numbers is ascending. [39, 42, 54, 55]. This is going to be helpful in larger instances.

Case 3) Cost minimization, Actors Who Refuse To Work With Each Other , Hacket and Spring

In light of recent rumors, it appears that Hacket and Spring refuse to collaborate. Therefore, the director must design the schedule in such a manner that ensures these two individuals are not scheduled to work on the same day.

We can easily avoid the conflict between these two stars by adding the following constraint:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}
for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)
for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)
  model.Add(AC['Hacket',d]+AC['Spring',d] <= 1)

for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)        

OF = $343256.0, it is more than case 1 (just because two people don't want to visit eachother!). By looking at the visualized schedule we observe that Hacket and Spring are never present on the same day.

Case 4) Cost minimization, Scene 3 should be taken before 9

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}
for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)
for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)

model.Add( sum(d*U[3,d] for d in days) <= sum(d*U[9,d] for d in days) )
for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 
expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))        

OF = $336410.0 , the costs are more than case 1. Scene 3 is taken in day 2 while scene 9 is scheduled for day 3.

Case 5) Cost minimization, Max Scenes for each actor is 3

By looking at the case 1, it is observed that the number of scenes assigned to each actor per day varies from 0 (Murphy day 1) to 5 (Scolaro day 2). This is something that might create conflict between the actors ! Let's balance it by putting a cap on the max number of scenes for each actor/day.

The fornulation is updated as follows:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}
for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)
for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)

  for a in actors:
    scens_assigned_to_actor = [U[s,d] for s in scenes if a in scene_dic[s]]
    model.Add(sum(scens_assigned_to_actor) <= 3) # max scen per actor/actress is 3 

for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)        

OF = $367185.0 , the costs are more than case 1. However, each actor is not assigned more than 3 scenes per day.

Case 6) Cost minimization, Max actors per day is 7

The producer has informed the director of a constraint: the shooting location facilities can accommodate only a limited number of movie cast members each day. Consequently, the director must ensure that the number of actors per day does not exceed 7 individuals (look at case 5, day 4, there are 8 actors).

The model is edited as follows:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}

for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)

for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)
  expressions_actors = [AC[a,d] for a in actors ]
  model.Add(sum(expressions_actors) <= 7)

for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)        

OF = $348171.0

Case 7) Cost minimization, Max actors per day is 7 while Max shooting days per actor is 3

Look at the results of case 6. Murphy should be present at work for just 2 days but McDougal is there every day. Let's make sure no actor is scheduled more than 3 days for shooting the scenes.

Keeping in mind that the director must ensure that the number of actors per day does not exceed 7 individuals.

Here is the problem formulation:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}

for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)

for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)
  
  expressions_actors = [AC[a,d] for a in actors ]
  model.Add(sum(expressions_actors) <= 8)

for a in actors:
  expressions_actors = [AC[a,d] for d in days ]
  model.Add(sum(expressions_actors) <= 3)
  

for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 180
status = solver.Solve(model)        

OF = $336410.0, with this schedule no actor is present at work more than 3 days.

Case 8) Cost minimization, the ACTOR is absent !

• Spring is absent on the day 1,2
• Murphy had already signed a contract for another movie on day 3

We can easily force the AC_ad for the relavant actor-day = 0

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_zj3nl9r5")  for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_zj3nl9r5")  for a in actors for d in days}
for s in scenes:
  expressions = [U[s,d] for d in days ]
  model.AddExactlyOne(expressions)
for d in days:
  expressions = [U[s,d] for s in scenes ]
  model.Add(sum(expressions) <= 5)
  
  expressions_actors = [AC[a,d] for a in actors ]
  model.Add(sum(expressions_actors) <= 8)

for a in actors:
  expressions_actors = [AC[a,d] for d in days ]
  model.Add(sum(expressions_actors) <= 3)
  

for (s,d),v in U.items():
  for actor in scene_dic[s]:
    model.Add(v<=AC[actor,d] ) 


model.Add(AC['Spring',1]== 0 )
model.Add(AC['Spring',2]== 0 )
model.Add(AC['Murphy',3]== 0 )

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 180
status = solver.Solve(model)        

OF = $347114

In Summary:

Optimization tools are instrumental in several aspects of film production, including:

1. Efficiently scheduling scene shoots by arranging them in a manner that minimizes downtime and maximizes productivity.
2. Balancing the workload among the cast and crew, ensuring that resources are utilized effectively and no individual is overburdened.
3. Timing the shooting schedule based on factors such as the availability of actors and the precedence of scenes, optimizing the sequence of filming to meet deadlines and creative requirements.

Don't forget to subscribe to the github channel

You may also contact me !

PyomoChannel ??????

Some resources for learning the ORTools:

• Official ORTools website: https://developers.google.com/optimization
• Solved examples on github : https://github.com/OptimizationExpert/Pyomo