• PDF
• Cite
• Share
Article Contents  Article Contents

# Talent hold cost minimization in film production

• * Corresponding author: B. M. T. Lin
• This paper investigates the talent scheduling problem in film production, which is known as rehearsal scheduling in music and dance performances. The first lower bound on the minimization of talent hold cost is based upon the outside-in branching strategy. We introduce two approaches to add extra terms for tightening the lower bound. The first approach is to formulate a maximum weighted matching problem. The second approach is to retrieve structural information and solve a maximum weighted 3-grouping problem. We make two contributions: First, our results can fathom the matrix of a given partial schedule. Second, our second approach is free from the requirement to schedule some shooting days in advance for providing anchoring information as in the other approaches, i.e., a lower bound can be computed once the input instance is given. The lower bound can fit different branching strategies. Moreover, the second contribution provides a state-of-the-art research result for this problem. Computational experiments confirm that the new bounds are much tighter than the original one.

Mathematics Subject Classification: Primary: 590B35; Secondary: 80M50.

 Citation: • • Figure 1.  Day-out-of-days matrix

Figure 2.  Areas resolved by different lower bounds

Figure 3.  Partial schedule with days d2, d3, d6, d7 fixed

Figure 4.  Illustration of Lemma 3.1

Figure 5.  Illustration of Max-w-matching(Φ(P))

Figure 6.  Analysis of xi1, i2, i3 in Lemma 4.1

Figure 7.  Analysis of yi1, i2, i3 in Lemma 4.1

Table 1.  Development of xi1, i2, i3 in Lemma 4.1

 Arrangement Minimum hold cost x-1: $\beta_{\widetilde{i_1},{i_2},{i_3}}---\beta_{\widetilde{i_1},{i_2},{i_3}}$ $c_{i_2}|\beta_{{i_1},\widetilde{i_2},{i_3}}|+c_{i_3}|\beta_{{i_1},{i_2},\widetilde{i_3}}|$ x-2: $\beta_{{i_1},\widetilde{i_2},{i_3}}---\beta_{{i_1},\widetilde{i_2},{i_3}}$ $c_{i_1}|\beta_{\widetilde{i_1},{i_2},{i_3}}|+c_{i_3}|\beta_{{i_1},{i_2},\widetilde{i_3}}|$ x-3: $\beta_{{i_1},{i_2},\widetilde{i_3}}---\beta_{{i_1},{i_2},\widetilde{i_3}}$ $c_{i_1}|\beta_{\widetilde{i_1},{i_2},{i_3}}|+c_{i_2}|\beta_{{i_1},\widetilde{i_2},{i_3}}|$ x-4: $\beta_{\widetilde{i_1},{i_2},{i_3}}---\beta_{{i_1},\widetilde{i_2},{i_3}}$ $c_{i_3}|\beta_{{i_1},{i_2},\widetilde{i_3}}|$ x-5: $\beta_{\widetilde{i_1},{i_2},{i_3}}---\beta_{{i_1},{i_2},\widetilde{i_3}}$ $c_{i_2}|\beta_{{i_1},\widetilde{i_2},{i_3}}|$ x-6: $\beta_{{i_1},\widetilde{i_2},{i_3}}---\beta_{{i_1},{i_2},\widetilde{i_3}}$ $c_{i_1}|\beta_{\widetilde{i_1},{i_2},{i_3}}|$ $\displaystyle x_{i_1,i_2,i_3}=\min\Big\{c_{i_1}|\beta_{\widetilde{i_1},{i_2},{i_3}}|,c_{i_2}|\beta_{{i_1},\widetilde{i_2},{i_3}}|,c_{i_3}|\beta_{{i_1},{i_2},\widetilde{i_3}}|\Big\}$

Table 2.  Analysis of yi1, i2, i3 for actors ai1, ai2, and ai3

 Arrangement Lower bound of costs y-1: $\beta_{{i_1},{i_2},{i_3}}---\beta_{{i_1},{i_2},{i_3}}$ $c_{i_1}(|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|+|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|)+ c_{i_2}(|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|+|\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|)$ $c_{i_3}(|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|+|\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|)$ y-2: $\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}---\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}$ $c_{i_3}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}\cup \beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|$ y-3: $\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}---\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}$ $c_{i_2}|\beta_{\widetilde{i_1},\widetilde{i_2}{i_3}}\cup \beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|$ y-4: $\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}---\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}$ $c_{i_1}|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}\cup \beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|$ y-5: $\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}---\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}$ $\min\{c_{i_2},c_{i_3}\}|\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|$, if $|\beta_{{i_1},{i_2},{i_3}}|>0$; 0, otherwise. y-6: $\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}---\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}$ $\min\{c_{i_1},c_{i_3}\}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|$, if $|\beta_{{i_1},{i_2},{i_3}}|>0$; 0, otherwise. y-7: $\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}---\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}$ $\min\{c_{i_1},c_{i_2}\}|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|$, if $|\beta_{{i_1},{i_2},{i_3}}|>0$; 0, otherwise. y-8: $\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}---\beta_{{i_1},{i_2}{i_3}}$ $\min\{c_{i_1}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|, c_{i_2}|\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|\}+c_{i_3}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}\cup \beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|$ y-9: $\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}---\beta_{{i_1},{i_2},{i_3}}$ $\min\{c_{i_1}|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|, c_{i_3}|\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|\}+c_{i_2}|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}\cup \beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|$ y-10: $\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}---\beta_{{i_1},{i_2},{i_3}}$ $\min\{c_{i_3}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|, c_{i_2}|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|\}+ c_{i_1}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}\cup \beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|$ $\displaystyle y_{i_1,i_2,i_3}=\min\Big\{\min\{c_{i_2},c_{i_3}\}|\beta_{{i_1},\widetilde{i_2},\widetilde{i_3}}|, \min\{c_{i_1},c_{i_3}\}|\beta_{\widetilde{i_1},{i_2},\widetilde{i_3}}|, \min\{c_{i_1},c_{i_2}\}|\beta_{\widetilde{i_1},\widetilde{i_2},{i_3}}|\Big\}$

Table 3.  Lower bounds subject to outside-in branching scheme

 Density lower bound k = 1 k = 3 k = 5 k = 10 value ratio value ratio value ratio value ratio 0.1 LB1 11,413 1.00 106,365 1.00 241,830 1.00 515,424 1.00 LB2 22,297 1.95 129,686 1.22 265,002 1.10 530,076 1.03 LB3 50,023 4.38 143,619 1.35 272,854 1.13 531,030 1.03 0.2 LB1 43,299 1.00 282,387 1.00 462,986 1.00 723,402 1.00 LB2 81,428 1.88 324,608 1.15 496,798 1.07 727,837 1.01 LB3 112,749 2.60 333,710 1.18 498,486 1.08 727,837 1.01 0.3 LB1 102,531 1.00 393,930 1.00 564,109 1.00 693,117 1.00 LB2 160,744 1.57 439,086 1.11 585,516 1.04 693,716 1.00 LB3 188,908 1.84 442,229 1.12 585,516 1.04 693,716 1.00

Table 4.  Lower bounds subject to sequential branching

 Density lower bound k = 1 k = 3 k = 5 k = 10 value ratio value ratio value ratio value ratio 0.1 LB1 0 N/A 7,764 1.00 22,918 1.00 87,358 1.00 LB2 6,541 N/A 26,995 3.48 51,991 2.27 127,306 1.46 LB3 37,745 N/A 49,103 6.32 67,435 2.94 132,759 1.52 0.2 LB1 0 N/A 11,737 1.00 35,605 1.00 11,7147 1.00 LB2 24,446 N/A 74,227 6.32 113,462 3.19 206,271 1.76 LB3 71,501 N/A 96,454 8.22 125,353 3.52 212,210 1.81 0.3 LB1 0 N/A 14,769 1.00 39,563 1.00 113,626 1.00 LB2 44,348 N/A 119,872 8.12 275,254 6.96 236,553 2.08 LB3 95,967 N/A 135,891 9.20 281,540 7.12 236,553 2.08
• Figures(7)

Tables(4)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint