Arrangement | Minimum hold cost |
x-1: | |
x-2: | |
x-3: | |
x-4: | |
x-5: | |
x-6: | |
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.
Citation: |
Table 1. Development of xi1, i2, i3 in Lemma 4.1
Arrangement | Minimum hold cost |
x-1: | |
x-2: | |
x-3: | |
x-4: | |
x-5: | |
x-6: | |
Table 2. Analysis of yi1, i2, i3 for actors ai1, ai2, and ai3
Arrangement | Lower bound of costs |
y-1: | |
y-2: | |
y-3: | |
y-4: | |
y-5: | |
y-6: | |
y-7: | |
y-8: | |
y-9: | |
y-10: | |
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 |
[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.
![]() |