In the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on different TV channels to maximize revenue and minimize penalties. This type of TV commercial scheduling problem is similar to the machine scheduling problem, and both have availability constraints. However, the literature on TV commercial scheduling has not considered this perspective. Motivated by this, we consider the problem of scheduling commercials with specific service-level requirements on TV channels while minimizing the maximum lateness. The lateness of a commercial is defined to be its completion time minus its due date, and the maximum lateness is the maximum value of lateness among all commercials. We propose an exact branch and bound algorithm based on the LFJ (least flexible job first)/EDD (earliest due date first) rules and network flow methods, which were developed to solve the machine scheduling problem with availability constraints. Computational analysis shows that the bounding scheme proposed is highly effective, and a very low percentage of nodes is generated by the branch and bound algorithm. The algorithm can obtain an optimal solution for the problem.
Citation: Lu-Wen Liao. A branch and bound algorithm for optimal television commercial scheduling[J]. Mathematical Biosciences and Engineering, 2022, 19(5): 4933-4945. doi: 10.3934/mbe.2022231
In the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on different TV channels to maximize revenue and minimize penalties. This type of TV commercial scheduling problem is similar to the machine scheduling problem, and both have availability constraints. However, the literature on TV commercial scheduling has not considered this perspective. Motivated by this, we consider the problem of scheduling commercials with specific service-level requirements on TV channels while minimizing the maximum lateness. The lateness of a commercial is defined to be its completion time minus its due date, and the maximum lateness is the maximum value of lateness among all commercials. We propose an exact branch and bound algorithm based on the LFJ (least flexible job first)/EDD (earliest due date first) rules and network flow methods, which were developed to solve the machine scheduling problem with availability constraints. Computational analysis shows that the bounding scheme proposed is highly effective, and a very low percentage of nodes is generated by the branch and bound algorithm. The algorithm can obtain an optimal solution for the problem.
| [1] | O. Sinha, P. Dharmarha, P. Kumar, Application of goal programming to optimize the schedule and frequency of product advertisement in Telemedia, in Recent Advances in Mechanical Engineering, Springer, Singapore, (2021), 875-884. https://doi.org/10.1007/978-981-15-9678-0_73 |
| [2] |
M. Singh, M. Pant, A. Kaul, P. C. Jha, Advertisement scheduling models in television media: a review, Soft Comput. Theor. Appl., 584 (2018), 505-514. https://doi.org/10.1007/978-981-10-5699-4_47 doi: 10.1007/978-981-10-5699-4_47
|
| [3] | Statista, Broadcast television advertising revenue of NBCUniversal from 2012 to 2020, 2021. Available from: https://www.statista.com/statistics/811648/nbcuniversal-broadcast-tv-ad-revenue. |
| [4] | Statista, TV advertising revenue in the United States from 2019 to 2025, 2021. Available from: https://www.statista.com/statistics/259974/tv-advertising-revenue-in-the-us/. |
| [5] |
F. G. Tari, R. Alaei, Scheduling TV commercials using genetic algorithms, Int. J. Prod. Res., 51 (2013), 4921-4929. https://doi.org/10.1080/00207543.2013.778431 doi: 10.1080/00207543.2013.778431
|
| [6] |
K. Czerniachowska, Scheduling TV advertisements via genetic algorithm, Eur. J. Ind. Eng., 13 (2019), 81-116. https://doi.org/10.1504/EJIE.2019.097926 doi: 10.1504/EJIE.2019.097926
|
| [7] |
A. García-Villoria, S. Salhi, Scheduling commercial advertisements for television, Int. J. Prod. Res., 53 (2015), 1198-1215. https://doi.org/10.1080/00207543.2014.951095 doi: 10.1080/00207543.2014.951095
|
| [8] |
D. B. Fontes, P. A. Pereira, A. C. C. Fontes, A decision support system for TV self-promotion scheduling, Int. J. Adv. Trends Comput. Sci. Eng., 8 (2019), 134-140. https://doi.org/10.30534/ijatcse/2019/06822019 doi: 10.30534/ijatcse/2019/06822019
|
| [9] |
F. Díaz-Núñez, N. Halman, Ó. C. Vásquez, The TV advertisements scheduling problem, Optim. Lett., 13 (2019), 81-94. https://doi.org/10.1007/s11590-018-1251-0 doi: 10.1007/s11590-018-1251-0
|
| [10] | A. R Brown, Selling television time: An optimisation problem, Comput. J., 12 (1969), 201-207. https://doi.org/10.1093/comjnl/12.3.201 |
| [11] |
K. Hägele, C. Ó Dúnlaing, S. Riis, The complexity of scheduling TV commercials, Electron. Notes Theor. Comput. Sci., 40 (2001), 162-185. https://doi.org/10.1016/S1571-0661(05)80043-X doi: 10.1016/S1571-0661(05)80043-X
|
| [12] | S. Bollapragada, H. Cheng, M. Phillips, M. Garbiras, M. Scholes, T. Gibbs, et al., NBC's optimization systems increase revenues and productivity, Interfaces, 32 (2002), 47-60. https://doi.org/10.1287/inte.32.1.47.19 |
| [13] |
S. Bollapragada, M. R. Bussieck, S. Mallik, Scheduling commercial videotapes in broadcast television, Oper. Res, 52 (2004), 679-689. https://doi.org/10.1287/opre.1040.0119 doi: 10.1287/opre.1040.0119
|
| [14] |
M. J. Brusco, Scheduling advertising slots for television, J. Oper. Soc, 59 (2008), 1363-1372. https://doi.org/10.1057/palgrave.jors.2602481 doi: 10.1057/palgrave.jors.2602481
|
| [15] |
S. Bollapragada, M. Garbiras, Scheduling commercials on broadcast television, Oper. Res, 52 (2004), 337-345. https://doi.org/10.1287/opre.1030.0083 doi: 10.1287/opre.1030.0083
|
| [16] |
D. R. Gaur, R. Krishnamurti, R. Kohli, Conflict resolution in the scheduling of television commercials, Oper. Res, 57 (2009), 1098-1105. https://doi.org/10.1287/opre.1080.0635 doi: 10.1287/opre.1080.0635
|
| [17] |
F. Guerriero, G. Miglionico, F. Olivito, Managing TV commercials inventory in the Italian advertising market, Int. J. Prod. Res, 54 (2016), 5499-5521. https://doi.org/10.1080/00207543.2016.1162919 doi: 10.1080/00207543.2016.1162919
|
| [18] |
Y. Ma, C. Chu, C. Zuo, A survey of scheduling with deterministic machine availability constraints, Comput. Ind. Eng, 58 (2009), 199-211. https://doi.org/10.1016/j.cie.2009.04.014 doi: 10.1016/j.cie.2009.04.014
|
| [19] |
G. Schmidt, Scheduling with limited machine availability, Eur. J. Oper. Res, 121 (2000), 1-15. https://doi.org/10.1016/S0377-2217(98)00367-1 doi: 10.1016/S0377-2217(98)00367-1
|
| [20] |
L. W. Liao, Scheduling jobs with service level requirements on parallel machines under availability and eligibility constraints, JIOS, 30 (2009), 1157-1176. https://doi.org/10.1080/02522667.2009.10699933 doi: 10.1080/02522667.2009.10699933
|
| [21] |
G. J. Sheen, L. W. Liao, Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints, Comput. Oper. Res., 34 (2007), 2266-2278. https://doi.org/10.1016/j.cor.2005.09.002 doi: 10.1016/j.cor.2005.09.002
|
Lu-Wen Liao. A branch and bound algorithm for optimal television commercial scheduling[J]. Mathematical Biosciences and Engineering, 2022, 19(5): 4933-4945. doi: 10.3934/mbe.2022231
DownLoad: