Development of a Genetic Algorithm for Advertising Time Allocation Problems

Document Type : Research Paper


1 PO.Box: 53816-14497, Tehran, Iran

2 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran


Commercial advertising is the main source of income for TV channels and allocation of advertising time slots for maximizing broadcasting revenues is the major problem faced by TV channel planners. In this paper, the problem of scheduling advertisements on prime-time of a TV channel is considered. The problem is formulated as a multi-unit combinatorial auction based mathematical model. This is an efficient mechanism for allocating the advertising time to advertisers in which the revenue of TV channel is maximized. However, still this problem is categorized as a NP-Complete problem. Therefore, a steady-state genetic algorithm is developed for finding a good or probably near-optimal solution, and is evaluated through a set of test problems for its robustness. Computational results reveal that the proposed algorithm is capable of obtaining high-quality solutions for the randomly generated real-sized test problems.


Main Subjects

[1] Benoist T., Bourreau E., Rottembourg B. (2007), The TV-break packing problem; European Journal of Operational Research 176; 1371-1386.
[2] Bichler M., Davenport A., Hohner G., Kalagnanam J., In Cramton P., Shoham Y., Steinberg R. (2006), Combinatorial Auctions, Chapter 22; Industrial Procurement Auctions, MIT Press.
[3] Bollapragada S., Cheng H., Philips M., Garbiras M., Scholes M., Gibbs T., Humhreville M. (2002), NBCs optimization systems increase revenues and productivity; Interfaces 32(1); 47-60.
[4] Bollapragada S., Garbiras M. (2004), Scheduling commercials on broadcast television; Operations Research 52(3); 337-345.
[5] Bollapragada S., Bussieck M., Mallik S. (2004), Scheduling commercial videotapes in broadcast television; Operations Research 52(5); 679-689.
[6] Brown A.R. (1969), Selling television time: An optimization problem; Computer Journal 12; 201-206.
[7] Brusco M.J. (2008), Scheduling advertising slots for television; Journal of the Operational Research Society 59(10); 1373-1382.
[8] Cramton P., Shoham Y., Steinberg R. (2005), Combinatorial Auctions, MIT Press.
[9] Holland J. (1975), Adaptation in Natural and Artificial Systems; University of Michigan Press.
[10] Jones J.J. (2000), Incompletely Specified Combinatorial Auction: An Alternative Allocation Mechanism for Business to Business Negotiations; PhD Dissertation, University of Florida, FL.
[11] Kimms A., Muller-Bungart M. (2007), Revenue management for broadcasting commercials; International Journal of Revenue Management 1; 28-44.
[12] Leyard J.O., Olson M., Porter D., Swanson J.A., Torma D.P. (2002), The first use of combined-value auction for transportation services; Interfaces 32(5); 4-12.
[13] Mao J., Shi J., Wanitwattanakosol J., Watanabe Sh. (2011), An ACO-based algorithm for optimizing the revenue of TV advertisement using credit information; International Journal of Revenue Management 5(2); 109-120.
[14] Mihiotis A., Tsakiris I. (2004), A mathematical programming study of advertising allocation problem; Applied Mathematics and Computation 148; 373-379.
[15] Pereira P.A., Fontes F.A.C.C., Fontes D.B.M.M. (2007), A decision support system for planning promotion time slots; Operations Research Proceedings; 147-152.
[16] Rassenti S., Smith V., Bulfin R. (1982), A combinatorial auction mechanism for airport time slot allocation; Bell Journal of Economics 13(2); 402-417.
[17] Sandholm T., Suri S., Gilpin A., Levine D. (2002), Winner determination in combinatorial auction generalizations; Proceeding of Autonomous Agents and Multi-Agent Systems Conference; 69-76.
[18] Wuang M.S., Yang C.L., Huang R.H., Chuang S.P. (2010), Scheduling of television commercials; IEEE International Conference on Industrial Engineering and Engineering Management (IEEM); Macao, 803-807.
[19] Zhang X. (2006), Mathematical models for the television advertising allocation problem; International Journal of Operational Research 1(3); 302-322.