Talent scheduling

File:A example of talent scheduling.png

Talent scheduling represents a complex optimization challenge within the fields of computer science and operations research, specifically categorized under combinatorial optimization. Consider, for example, a case involving the production of multiple films, each comprising several scenes that necessitate the participation of one or more actors. Importantly, only one scene can be filmed per day, and the remuneration for the actors is calculated on a daily basis. A critical constraint in this problem is that actors must be engaged for consecutive days; for instance, an actor cannot be contracted for filming on the first and third days without also being hired on the intervening second day. Furthermore, during the entire hiring period, producers are obligated to compensate the actors, even on days when they are not actively participating in filming. The primary objective of talent scheduling is to minimize the total salary expenditure for the actors by optimizing the sequence in which scenes are filmed.{{cite journal |last1=Cheng |first1=T. C. E. |last2=Diamond |first2=J. E. |last3=Lin |first3=B. M. T. |title=Optimal scheduling in film production to minimize talent hold cost |url=https://link.springer.com/article/10.1007/BF00940554 |journal=Journal of Optimization Theory and Applications |access-date=25 July 2022 |pages=479–492 |language=en |doi=10.1007/BF00940554 |date=1 December 1993|volume=79 |issue=3 |s2cid=120319128 |url-access=subscription }}

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^0_{m \times n} = \begin{cases}
1, & \mbox{if actor i is required in scene 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_{i,j}(\sigma)=t^0_{i,\sigma(j)}$ 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^0_{ij}$ 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^0_{i,j}$

The total cost of unnecessary days is:

: $K(\sigma)=\sum_{i=1}^{m}c_ih_i(\sigma)=\sum_{i=1}^{m}c_i[l_i(\sigma)-e_i(\sigma)+1-\sum_{j=1}^{n} t^0_{i,j}]$

$K(\sigma)$ 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.{{cite journal |last1=Garey |first1=M. R. |last2=Johnson |first2=D. S. |last3=Stockmeyer |first3=L. |title=Some simplified NP-complete graph problems |journal=Theoretical Computer Science |date=1 February 1976 |volume=1 |issue=3 |pages=237–267 |doi=10.1016/0304-3975(76)90059-1 |language=en |issn=0304-3975|doi-access=free }} 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.{{cite book|last1=Garey|first1=M. R.|author-link1=Michael R. Garey|last2=Johnson|first2=D. S.|author-link2=David S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|year=1979|isbn=0-7167-1045-5|pages=[https://archive.org/details/computersintract0000gare/page/ x+338]|series=A Series of Books in the Mathematical Sciences|editor=Victor Klee|editor-link=Victor Klee|publisher=W. H. Freeman and Co.|location=San Francisco, Calif.|mr=519066}}

Integer programming

The integer programming model is given by:Close

Kochetov, Y. (2011). Iterative local search methods for the talent scheduling problem. In Proceedings of 1st international symposium and 10th Balkan conference on operational research, September 22, Thessaloniki, Greece (pp. 282–288).

cellspacing="10"

Minimize

| colspan="2" | $\sum_{i=1}^{m}c_i(l_i-e_i+1)$

subject to

| $\sum_{j=1}^n x_{j,k} = \sum_{k=1}^n x_{j,k}=1,$

| $1 \leq j,k \leq n$

t_{i,j}e_i \leq \sum_{k=1}^nt_{i,j}kx_{j,k} \leq l_i,

| $1 \leq i \leq m, 1 \leq j \leq n$

l_i,e_i \geq 1,

| $1 \leq i \leq m$

x_{j,k} \in \{0,1\},

| $1 \leq j,k \leq n$

l_i,e_i \in \mathbb{Z},

| $1 \leq i \leq m$

In this model, $e_i$ means the earliest shooting day for talent $i$ , $l_i$ is the latest shooting day for talent $i$ , $x_{j,k}$ is the scheduling for the project, i.e.

: $x_{j,k} = \begin{cases} 1 & \text{if scene } j \text{ is scheduled in day } k \text{ of shooting } \\ 0 & \text{otherwise} \end{cases}$

References

Category:Optimal scheduling

Category:NP-complete problems