Search Advanced

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 5: 4933-4945. doi: 10.3934/mbe.2022231
Previous Article Next Article
Research article Special Issues

A branch and bound algorithm for optimal television commercial scheduling

  • Department of Intelligent Production Engineering, National Taichung University of Science and Technology, Taichung 40401, Taiwan

  • Academic Editor: Danilo Pelusi
  • Received: 18 November 2021 Revised: 22 February 2022 Accepted: 25 February 2022 Published: 15 March 2022

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Mathematical Biosciences and Engineering
3.9

Metrics

Article views(1672) PDF downloads(82) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(2)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog