Talent scheduling

Talent Scheduling is an optimization problem in computer science and operations research. Suppose we need to make movies, and each movie contains several scenes. Each scene needs to be shot by one or more actors. And suppose you can only shoot one scene a day. The salaries of these actors are calculated by the day. In this problem, we can only hire each actor consecutively. For example, we can't hire an actor on the first and third days, but not the second day. 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) $T^{0}\in \{0,1\}_{m\times n}$ to represent the requirements for the various shooting days. The matrix with the $(i,j)$ entry given by:

$t_{m\times n}^{0}={\begin{cases}1,&{\mbox{if actor i is required in shooting day j,}}\\0,&{\mbox{otherwise.}}\end{cases}}$

Then we define the pay vector ${\mathfrak {R}}^{m}$, with the $i$th element given by $c_{i}$ which means rate of pay per day of the $i$th actor. Let v denote any permutation of the n columns of $T^{0}$, we have:

$\sigma :\{1,2,...,n\}\rightarrow \{1,2,...,n\}$

$\sigma _{n}$ is the permutation set of the n shooting days. Then define $T(\sigma )$ to be the matrix $T^{0}$ with its columns permuted according to $\sigma$, we have:

$t_{ij}(\sigma )=t_{i\sigma (j)}^{0}$ for $i\in \{1,2,...,n\},j\in \{1,2,...,n\}$

Then we use $l_{i}(\sigma )$ and $e_{i}(\sigma )$ 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 $l_{i}(\sigma )-e_{i}(\sigma )+1$ days. But in these days, only $r_{i}=\sum _{j=1}^{n}t_{ij}^{0}$ days are actually required, which means $h_{i}(S)$ days are unnecessary, we have:

$h_{i}(S)=h_{i}(\sigma )=l_{i}(\sigma )-e_{i}(\sigma )+1-r_{i}=l_{i}(\sigma )-e_{i}(\sigma )+1-\sum _{j=1}^{n}t_{ij}^{0}$

The total cost of unnecessary days is:

$K(\sigma )=\sum _{j=1}^{m}c_{i}h_{i}(\sigma )=\sum _{j=1}^{m}c_{i}[l_{i}(\sigma )-e_{i}(\sigma )+1-\sum _{j=1}^{n}t_{ij}^{0}]$

$K(\sigma )$ will be the objective function we should minimize.

Proof of Strong NP-hardness

In talent scheduling problem, we can prove that is NP-hard by a reduction from the optimal linear arrangement problem. And in this problem, even we restrict each actor is needed for just two days and pay vector is $(1,1,...,1)$, it's still polynomially reducible to the OLA problem. Thus, this problem is unlikely have pseudo-polynomial algorithm.