Talent scheduling is a combinatorial optimization problem in computer science and operations research.
Example
Consider a scenario where multiple films are to be produced, each film contains several scenes, each scene requires one or more actors, and only a single scene can be filmed per day. The salaries of the actors are calculated by the day. In this problem, actors must be employed on consecutive days; for example, an actor cannot be hired on the first and third days only, as the actor would have to be hired on the second day too. During the hiring period, the producers still need to pay the actors even if they are not involved in the filming assignment. The purpose of talent scheduling is to minimize the actors' total salary by adjusting the sequence of scenes.
Mathematical formulation
Consider a film shoot composed of n shooting days and involving a total of m actors. Then we use the day out of days matrix (DODM) T0∈{0,1}m×n to represent the requirements for the various shooting days. The matrix with the (i,j) entry given by:
tm×n0={1,if actor i is required in scene j,0,otherwise.
Then we define the pay vector ℜm, with the ith element given by ci which means rate of pay per day of the ith actor. Let v denote any permutation of the n columns of T0, we have:
σ:{1,2,...,n}→{1,2,...,n}
σn is the permutation set of the n shooting days. Then define T(σ) to be the matrix T0 with its columns permuted according to σ, we have:
ti,j(σ)=ti,σ(j)0 for i∈{1,2,...,n},j∈{1,2,...,n}
Then we use li(σ) and ei(σ) to represent denote respectively the earliest and latest days in the schedule S determined by a which require actor i. So we can find actor i will be hired for li(σ)−ei(σ)+1 days. But in these days, only ri=∑j=1ntij0 days are actually required, which means hi(S) days are unnecessary, we have:
hi(S)=hi(σ)=li(σ)−ei(σ)+1−ri=li(σ)−ei(σ)+1−∑j=1nti,j0
The total cost of unnecessary days is:
K(σ)=∑i=1mcihi(σ)=∑i=1mci[li(σ)−ei(σ)+1−∑j=1nti,j0]
K(σ) will be the objective function we should minimize.
Proof of strong NP-hardness
It can be proved that the talent scheduling problem is NP-hard by a reduction to the optimal linear arrangement (OLA) problem. Even if we restrict the problem by requiring that each actor is needed for just two days and all actors' salaries are 1, it's still polynomially reducible to the OLA problem. Thus, this problem is unlikely to have pseudo-polynomial algorithm.
Integer programming
The integer programming model is given by:
In this model, ei means the earliest shooting day for talent i, li is the latest shooting day for talent i, xj,k is the scheduling for the project, i.e.
xj,k={1if scene j is scheduled in day k of shooting 0otherwise
References
