Abstract
A TV channel has a single advertisement break of duration h and a convex continuous function \(f{:}\;[0,h] \rightarrow \mathbb {R}^+\) representing the TV rating points within the advertisement break. Given n TV advertisements of different durations \(p_j\) that sum up to h, and willingness to pay coefficients \(w_j\), the objective is to schedule them on the TV break in order to maximize the total revenue of the TV channel \(\sum _j w_j \int _{c_j-p_j}^{c_j} f(t) dt,\) where \([c_j-p_j,c_j)\) is the broadcast time interval of TV advertisement j. We show that this problem is NP-hard and propose a fully polynomial time approximation scheme, using a special dominance property of an optimal schedule and the technique of K-approximation sets and functions introduced by Halman et al. (Math Oper Res 34:674–685, 2009).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bansal, N., Dürr, C., Thang, N.K., Vásquez, Ó.C.: The local–global conjecture for scheduling with non-linear cost. J. Sched. 20(3), 239–254 (2017)
Bansal, N., Pruhs, K.: The geometry of scheduling. SIAM J. Comput. 43(5), 1684–1698 (2014)
Benoist, T., Bourreau, E., Rottembourg, B.: The TV-break packing problem. Eur. J. Oper. Res. 176(3), 1371–1386 (2007)
Bollapragada, S., Bussieck, M.R., Mallik, S.: Scheduling commercial videotapes in broadcast television. Oper. Res. 52(5), 679–689 (2004)
Bollapragada, S., Cheng, H., Phillips, M., Garbiras, M., Scholes, M., Gibbs, T., Humphreville, M.: NBC’s optimization systems increase revenues and productivity. Interfaces 32(1), 47–60 (2002)
Bollapragada, S., Garbiras, M.: Scheduling commercials on broadcast television. Oper. Res. 52(3), 337–345 (2004)
Cheung, M., Shmoys, D.: A primal–dual approximation algorithm for min-sum single-machine scheduling problems. In: Proceedings of the 14th International Workshop APPROX and 15th International Workshop RANDOM, pp. 135–146 (2011)
Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L.: Universal sequencing on an unreliable machine. SIAM J. Comput. 41(3), 565–586 (2012)
García-Villoria, A., Salhi, S.: Scheduling commercial advertisements for television. Int. J. Prod. Res. (2014). https://doi.org/10.1080/00207543.2014.951095
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)
Ghassemi, F., Tari, Alaei, R.: Scheduling TV commercials using genetic algorithms. Int. J. Prod. Res. 51(16), 4921–4929 (2013)
Halman, N.: A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy. Theor. Comput. Sci. 645, 41–47 (2016)
Halman, N., Klabjan, D., Li, C.-L., Orlin, J., Simchi-Levi, D.: Fully polynomial time approximation schemes for stochastic dynamic programs. SIAM J. Discrete Math. 28, 1725–1796 (2014)
Halman, N., Klabjan, D., Mostagir, M., Orlin, J., Simchi-Levi, D.: A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Math. Oper. Res. 34, 674–685 (2009)
Halman, N., Nannicini, G., Orlin, J.: A computationally efficient FPTAS for convex stochastic dynamic programs. SIAM J. Optim. 25, 317–350 (2015)
Halman, N., Orlin, J.B., Simchi-Levi, D.: Approximating the nonlinear newsvendor and single-item stochastic lot-sizing problems when data is given by an oracle. Oper. Res. 60, 429–446 (2012)
Höhn, W., Jacobs, T.: On the performance of Smith’s rule in single-machine scheduling with nonlinear cost. ACM Trans. Algorithms 11(4), 25:1–25:30 (2015)
Höhn, W., Mestre, J., Wiese, A.: How unsplittable-flow-covering helps scheduling with job-dependent cost functions. In: International Colloquium on Automata, Languages, and Programming. Springer, pp. 625–636 (2014)
Mao, J., Shi, J., Wanitwattanakosol, J., Watanabe, S.: An ACO-based algorithm for optimising the revenue of TV advertisement using credit information. Int. J. Revenue Manag. 5(2), 109–120 (2011)
Megow, N., Verschae, J.: Dual techniques for scheduling on a machine with varying speed. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), pp. 745–756 (2013)
Mestre, J., Verschae, J.: A 4-approximation for scheduling on a single machine with general cost function. CoRR, arXiv:1403.0298 (2014)
Mihiotis, A., Tsakiris, I.: A mathematical programming study of advertising allocation problem. Appl. Math. Comput. 148(2), 373–379 (2004)
Pereira, J., Vásquez, O.C.: The single machine weighted mean squared deviation problem. Eur. J. Oper. Res. 261(2), 515–529 (2017)
Vásquez, Ó.C.: On the complexity of the single machine scheduling problem minimizing total weighted delay penalty. Oper. Res. Lett. 42(5), 343–347 (2014)
Vásquez, O.C.: For the airplane refueling problem local precedence implies global precedence. Optim. Lett. 9(4), 663–675 (2015)
Velusamy, S., Gopal, L., Bhatnagar, S., Varadarajan, S.: An efficient ad recommendation system for TV programs. Multimed. Syst. 14(2), 73–87 (2008)
Zhang, X.: Mathematical models for the television advertising allocation problem. Int. J. Oper. Res. 1(3), 302–322 (2006)
Acknowledgements
The authors are grateful for partial support from the following sources: FONDECYT Grant 11140566 (F. Díaz-Núñez and Ó. C. Vásquez), Universidad de Santiago, Proyecto DICYT 061817VP (Ó. C. Vásquez) and Israel Science Foundation Grant 399/17 (N. Halman).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Díaz-Núñez, F., Halman, N. & Vásquez, Ó.C. The TV advertisements scheduling problem. Optim Lett 13, 81–94 (2019). https://doi.org/10.1007/s11590-018-1251-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-018-1251-0