Talent hold cost minimization in film production

Tai Chiu Edwin Cheng; Bertrand Miao-Tsong Lin; Hsiao-Lan Huang

doi:10.3934/jimo.2016013

Article Contents

2017, Volume 13, Issue 1: 223-235. Doi: 10.3934/jimo.2016013

This issue Previous Article The finite-time ruin probability for an inhomogeneous renewal risk model Next Article Efficiency measures in fuzzy data envelopment analysis with common weights

Talent hold cost minimization in film production

1.
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
2.
Institute of Information Management, National Chiao Tung University, Hsinchu 300, Taiwan

* Corresponding author: B. M. T. Lin
* Corresponding author: B. M. T. Lin

Received: April 30, 2015

Revised: November 30, 2015

Published: August 2017

Abstract Full Text(HTML) Figure(7) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. Day-out-of-days matrix

Download: Full-size image PowerPoint slide

Figure 2. Areas resolved by different lower bounds

Download: Full-size image PowerPoint slide

Figure 3. Partial schedule with days d₂, d₃, d₆, d₇ fixed

Download: Full-size image PowerPoint slide

Figure 4. Illustration of Lemma 3.1

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 6. Analysis of x_{i₁, i₂, i₃} in Lemma 4.1

Download: Full-size image PowerPoint slide

Figure 7. Analysis of y_{i₁, i₂, i₃} in Lemma 4.1

Download: Full-size image PowerPoint slide

Table 1. Development of x_{i₁, i₂, i₃} 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\}$

| Show Table

DownLoad: CSV

Table 2. Analysis of y_{i₁, i₂, i₃} for actors a_i₁, a_i₂, and a_i₃

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\}$

| Show Table

DownLoad: CSV

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

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

| Show Table

DownLoad: CSV

Table 4. Lower bounds subject to sequential branching

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. M. Adelson, G. Laporte and J. M. Norman, A dynamic programming formulation with diverse applications, Operations Research Quarterly, 27 (1976), 119-121.
[2]	M. G. de la Banda, P. J. Stuckey and G. Chu, Solving talent scheduling with dynamic programming, INFORMS Journal on Computing, 23 (2011), 120-137. doi: 10.1287/ijoc.1090.0378.
[3]	T. C. E. Cheng, J. E. Diamond and B. M. T. Lin, Optimal scheduling in film production to minimize talent hold cost, Journal of Optimization Theory and Applications, 79 (1993), 479-492. doi: 10.1007/BF00940554.
[4]	M. Gendreau, A. Hertz and G. Laporte, A generalized insertion algorithm for the serilization problem, Mathematical and Computational Modeling, 19 (1994), 53-59.
[5]	R. M. Karp, Mapping the genome: Some combinatorial problems arising in molecular biology, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), (1993), 279-285. doi: 10.1145/167088.167170.
[6]	G. Laporte, The serialization problem and the travelling salesman problem, Journal of Computational and Applied Mathematics, 4 (1978), 259-268. doi: 10.1016/0771-050X(78)90024-4.
[7]	G. Laporte, Solving a family of permutation problems on 0-1 matrices, RAIRO (Operations Research), 21 (1987), 65-85.
[8]	G. Laporte and S. Taillefer, An efficient interchange procedure for the archaeological serisation problem, Journal of Archaeological Science, 14 (1987), 283-289.
[9]	B. M. T. Lin, A new branch-and-bound algorithm for the film production problem, Journal of Ming Chuan College, 10 (1999), 101-110.
[10]	A. L. Nordström and S. Tufekçi, A genetic algorithm for the talent scheduling problem, Computers and Operations Research, 21 (1994), 927-940.
[11]	R. S. Singleton, Film Scheduling: Or, How Long Will It Take to Shoot Your Movie? Lone Eagle, Los Angeles, U. S. A., 1997.
[12]	B. M. Smith, Constraint Programming in Practice: Scheduling a Rehearsal, Report APES-67-2003, University of Huddersfield, U. K., 2003.
[13]	S. Y. Wang, Y. T. Chuang and B. M. T. Lin, Talent scheduling with daily operating capacities, Journal of Production and Industrial Engineering, 33 (2016), 17-31.
[14]	M. Wyon, Preparing to perform periodization and dance, Journal of Dance Medicine and Science, 14 (2010), 67-72.