Talent scheduling

<h2 id="mathematical-formulation">Mathematical formulation</h2>
<p>Consider a film shoot composed of 
  
    
      
        n
      
    
    {\displaystyle n}
  
 shooting days and involving a total of 
  
    
      
        m
      
    
    {\displaystyle m}
  
 actors. Then we use the day out of days matrix (DODM) 
  
    
      
        
          T
          
            0
          
        
        ∈
        {
        0
        ,
        1
        
          }
          
            m
            ×
            n
          
        
      
    
    {\displaystyle T^{0}\in \{0,1\}_{m\times n}}
  
 to represent the requirements for the various shooting days. The matrix with the 
  
    
      
        (
        i
        ,
        j
        )
      
    
    {\displaystyle (i,j)}
  
 entry given by:
</p>

t
          
            m
            ×
            n
          
          
            0
          
        
        =
        
          
            {
            
              
                
                  1
                  ,
                
                
                  
                    
                      if actor i is required in scene j,
                    
                  
                
              
              
                
                  0
                  ,
                
                
                  
                    
                      otherwise.
                    
                  
                
              
            
            
          
        
      
    
    {\displaystyle t_{m\times n}^{0}={\begin{cases}1,&{\mbox{if actor i is required in scene j,}}\\0,&{\mbox{otherwise.}}\end{cases}}}

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

σ
        :
        {
        1
        ,
        2
        ,
        .
        .
        .
        ,
        n
        }
        →
        {
        1
        ,
        2
        ,
        .
        .
        .
        ,
        n
        }
      
    
    {\displaystyle \sigma :\{1,2,...,n\}\rightarrow \{1,2,...,n\}}

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

t
          
            i
            ,
            j
          
        
        (
        σ
        )
        =
        
          t
          
            i
            ,
            σ
            (
            j
            )
          
          
            0
          
        
      
    
    {\displaystyle t_{i,j}(\sigma )=t_{i,\sigma (j)}^{0}}
  
 <i>for</i> 
  
    
      
        i
        ∈
        {
        1
        ,
        2
        ,
        .
        .
        .
        ,
        n
        }
        ,
        j
        ∈
        {
        1
        ,
        2
        ,
        .
        .
        .
        ,
        n
        }
      
    
    {\displaystyle i\in \{1,2,...,n\},j\in \{1,2,...,n\}}

<p>Then we use 
  
    
      
        
          l
          
            i
          
        
        (
        σ
        )
      
    
    {\displaystyle l_{i}(\sigma )}
  
 and 
  
    
      
        
          e
          
            i
          
        
        (
        σ
        )
      
    
    {\displaystyle e_{i}(\sigma )}
  
 to represent denote respectively the earliest and latest days in the schedule 
  
    
      
        S
      
    
    {\displaystyle S}
  
 determined by a which require actor 
  
    
      
        i
      
    
    {\displaystyle i}
  
. So we can find actor 
  
    
      
        i
      
    
    {\displaystyle i}
  
 will be hired for 
  
    
      
        
          l
          
            i
          
        
        (
        σ
        )
        −
        
          e
          
            i
          
        
        (
        σ
        )
        +
        1
      
    
    {\displaystyle l_{i}(\sigma )-e_{i}(\sigma )+1}
  
 days. But in these days, only 
  
    
      
        
          r
          
            i
          
        
        =
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          t
          
            i
            j
          
          
            0
          
        
      
    
    {\displaystyle r_{i}=\sum _{j=1}^{n}t_{ij}^{0}}
  
 days are actually required, which means 
  
    
      
        
          h
          
            i
          
        
        (
        S
        )
      
    
    {\displaystyle h_{i}(S)}
  
 days are unnecessary, we have:
</p>

h
          
            i
          
        
        (
        S
        )
        =
        
          h
          
            i
          
        
        (
        σ
        )
        =
        
          l
          
            i
          
        
        (
        σ
        )
        −
        
          e
          
            i
          
        
        (
        σ
        )
        +
        1
        −
        
          r
          
            i
          
        
        =
        
          l
          
            i
          
        
        (
        σ
        )
        −
        
          e
          
            i
          
        
        (
        σ
        )
        +
        1
        −
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          t
          
            i
            ,
            j
          
          
            0
          
        
      
    
    {\displaystyle 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_{i,j}^{0}}

<p>The total cost of unnecessary days is:
</p>

K
        (
        σ
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            m
          
        
        
          c
          
            i
          
        
        
          h
          
            i
          
        
        (
        σ
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            m
          
        
        
          c
          
            i
          
        
        [
        
          l
          
            i
          
        
        (
        σ
        )
        −
        
          e
          
            i
          
        
        (
        σ
        )
        +
        1
        −
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          t
          
            i
            ,
            j
          
          
            0
          
        
        ]
      
    
    {\displaystyle K(\sigma )=\sum _{i=1}^{m}c_{i}h_{i}(\sigma )=\sum _{i=1}^{m}c_{i}[l_{i}(\sigma )-e_{i}(\sigma )+1-\sum _{j=1}^{n}t_{i,j}^{0}]}

<p>
  
    
      
        K
        (
        σ
        )
      
    
    {\displaystyle K(\sigma )}
  
 will be the objective function we should minimize.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h2 id="proof-of-strong-np-hardness">Proof of strong NP-hardness</h2>
<p>It can be proved that the talent scheduling problem is NP-hard by a reduction to the optimal linear arrangement(OLA) problem.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> 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 <a href="/facts/Pseudo-polynomial_time/7a35x5wN">pseudo-polynomial algorithm</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="integer-programming">Integer programming</h2>
<p>The <a href="/facts/Integer_programming/MDaaadoA">integer programming</a> model is given by:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<table><tbody><tr><td>Minimize</td><td colspan="2">                              ∑                      i            =            1                                m                                    c                      i                          (                  l                      i                          −                  e                      i                          +        1        )              {\displaystyle \sum _{i=1}^{m}c_{i}(l_{i}-e_{i}+1)}  </td></tr><tr><td>subject to</td><td>                              ∑                      j            =            1                                n                                    x                      j            ,            k                          =                  ∑                      k            =            1                                n                                    x                      j            ,            k                          =        1        ,              {\displaystyle \sum _{j=1}^{n}x_{j,k}=\sum _{k=1}^{n}x_{j,k}=1,}  </td><td></td><td>                    1        ≤        j        ,        k        ≤        n              {\displaystyle 1\leq j,k\leq n}  </td></tr><tr><td></td><td>                              t                      i            ,            j                                    e                      i                          ≤                  ∑                      k            =            1                                n                                    t                      i            ,            j                          k                  x                      j            ,            k                          ≤                  l                      i                          ,              {\displaystyle t_{i,j}e_{i}\leq \sum _{k=1}^{n}t_{i,j}kx_{j,k}\leq l_{i},}  </td><td></td><td>                    1        ≤        i        ≤        m        ,        1        ≤        j        ≤        n              {\displaystyle 1\leq i\leq m,1\leq j\leq n}  </td></tr><tr><td></td><td>                              l                      i                          ,                  e                      i                          ≥        1        ,              {\displaystyle l_{i},e_{i}\geq 1,}  </td><td></td><td>                    1        ≤        i        ≤        m              {\displaystyle 1\leq i\leq m}  </td></tr><tr><td></td><td>                              x                      j            ,            k                          ∈        {        0        ,        1        }        ,              {\displaystyle x_{j,k}\in \{0,1\},}  </td><td></td><td>                    1        ≤        j        ,        k        ≤        n              {\displaystyle 1\leq j,k\leq n}  </td></tr><tr><td></td><td>                              l                      i                          ,                  e                      i                          ∈                  Z                ,              {\displaystyle l_{i},e_{i}\in \mathbb {Z} ,}  </td><td></td><td>                    1        ≤        i        ≤        m              {\displaystyle 1\leq i\leq m}  </td></tr></tbody></table>
<p>In this model, 
  
    
      
        
          e
          
            i
          
        
      
    
    {\displaystyle e_{i}}
  
 means the earliest shooting day for talent 
  
    
      
        i
      
    
    {\displaystyle i}
  
, 
  
    
      
        
          l
          
            i
          
        
      
    
    {\displaystyle l_{i}}
  
 is the latest shooting day for talent 
  
    
      
        i
      
    
    {\displaystyle i}
  
, 
  
    
      
        
          x
          
            j
            ,
            k
          
        
      
    
    {\displaystyle x_{j,k}}
  
 is the scheduling for the project, i.e.
</p>

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

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Cheng, T. C. E.; Diamond, J. E.; Lin, B. M. T. (1 December 1993). "Optimal scheduling in film production to minimize talent hold cost". Journal of Optimization Theory and Applications. 79 (3): 479–492. doi:10.1007/BF00940554. S2CID 120319128. Retrieved 25 July 2022. <a href="https://link.springer.com/article/10.1007/BF00940554" target="_blank">https://link.springer.com/article/10.1007/BF00940554</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Cheng, T. C. E.; Diamond, J. E.; Lin, B. M. T. (1 December 1993). "Optimal scheduling in film production to minimize talent hold cost". Journal of Optimization Theory and Applications. 79 (3): 479–492. doi:10.1007/BF00940554. S2CID 120319128. Retrieved 25 July 2022. <a href="https://link.springer.com/article/10.1007/BF00940554" target="_blank">https://link.springer.com/article/10.1007/BF00940554</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1 February 1976). "Some simplified NP-complete graph problems". Theoretical Computer Science. 1 (3): 237–267. doi:10.1016/0304-3975(76)90059-1. ISSN 0304-3975. <a href="https://doi.org/10.1016%2F0304-3975%2876%2990059-1" target="_blank">https://doi.org/10.1016%2F0304-3975%2876%2990059-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066. <a href="0-7167-1045-5" target="_blank">0-7167-1045-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>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). <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Talent scheduling open-in-new

Talent scheduling