Talent scheduling explained

Talent scheduling is an optimization problem in computer science and operations research, and it is also a problem in combinatorial optimization. Suppose we need to make films, and each film 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.^[1]

Mathematical formulation

Consider a film shoot composed of

shooting days and involving a total of

actors. Then we use the day out of days matrix (DODM)

T⁰\in\{0,1\}_m

to represent the requirements for the various shooting days. The matrix with the

(i,j)

entry given by:

	0
t
	m x n

=\begin{cases} 1,&ifactoriisrequiredinscenej,\\ 0,&otherwise. \end{cases}

Then we define the pay vector

ak{R}^m

, with the

th element given by

c_i

which means rate of pay per day of the

th actor. Let v denote any permutation of the n columns of

T⁰

, we have:

\sigma:\{1,2,...,n\} → \{1,2,...,n\}

\sigma_n

is the permutation set of the n shooting days. Then define

T(\sigma)

to be the matrix

T⁰

with its columns permuted according to

\sigma

, we have:

t_i,j

	0
(\sigma)=t
	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

determined by a which require actor

. So we can find actor

will be hired for

l_i(\sigma)-e_i(\sigma)+1

days. But in these days, only

r_i=\sum

	n

	j=1

	0
t
	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}

	n

	j=1

	0
t
	i,j

The total cost of unnecessary days is:

	m
K(\sigma)=\sum
	i=1

c_ih_{i(\sigma)=\sum}

	m

	i=1

c_i[l_i(\sigma)-e_{i(\sigma)+1-\sum}

	n

	j=1

	0
t
	i,j

]

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(OLA) problem.^[2] And in this problem, even we restrict 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.^[3]

Integer programming

The integer programming model is given by:^[4]

Minimize

	m
\sum
	i=1

c_i(l_i-e_i+1)

subject to

	n
\sum
	j=1

x_j,k=

	n
\sum
	k=1

x_j,k=1,

1\leqj,k\leqn

t_i,je_i\leq

	nt
\sum
	i,j

kx_j,k\leql_i,

1\leqi\leqm,1\leqj\leqn

l_i,e_i\geq1,

1\leqi\leqm

x_j,k\in\{0,1\},

1\leqj,k\leqn

l_i,e_i\inZ,

1\leqi\leqm

In this model,

e_i

means the earliest shooting day for talent

l_i

is the latest shooting day for talent

x_j,k

is the scheduling for the project, i.e.

x_j,k=\begin{cases}1&ifscenejisscheduledindaykofshooting\ 0&otherwise\end{cases}

Notes and References

Cheng . T. C. E. . Diamond . J. E. . Lin . B. M. T. . Optimal scheduling in film production to minimize talent hold cost . Journal of Optimization Theory and Applications . 25 July 2022 . 479–492 . en . 10.1007/BF00940554 . 1 December 1993. 79 . 3 . 120319128 .
Garey . M. R. . Johnson . D. S. . Stockmeyer . L. . Some simplified NP-complete graph problems . Theoretical Computer Science . 1 February 1976 . 1 . 3 . 237–267 . 10.1016/0304-3975(76)90059-1 . en . 0304-3975. free .
Book: Garey. M. R.. Michael R. Garey. Johnson. D. S.. David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979. 0-7167-1045-5. x+338. A Series of Books in the Mathematical Sciences. Victor Klee. Victor Klee. W. H. Freeman and Co.. San Francisco, Calif.. 519066.
CloseKochetov, 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).