IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v57y2009i5p1098-1105.html
   My bibliography  Save this article

Conflict Resolution in the Scheduling of Television Commercials

Author

Listed:
  • Daya Ram Gaur

    (Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta T1K 3M4, Canada)

  • Ramesh Krishnamurti

    (School of Computing Science, Simon Fraser University, Burnaby, British Columbia V5A 1S6, Canada)

  • Rajeev Kohli

    (Graduate School of Business, Columbia University, New York, New York 10027)

Abstract

We extend a previous model for scheduling commercial advertisements during breaks in television programming. The proposed extension allows differential weighting of conflicts between pairs of commercials. We formulate the problem as a capacitated generalization of the max k -cut problem in which the vertices of a graph correspond to commercial insertions and the edge weights to the conflicts between pairs of insertions. The objective is to partition the vertices into k capacitated sets to maximize the sum of conflict weights across partitions. We note that the problem is NP-hard. We extend a previous local-search procedure to allow for the differential weighting of edge weights. We show that for problems with equal insertion lengths and break durations, the worst-case bound on the performance of the proposed algorithm increases with the number of program breaks and the number of insertions per break, and that it is independent of the number of conflicts between pairs of insertions. Simulation results suggest that the algorithm performs well even if the problem size is small.

Suggested Citation

  • Daya Ram Gaur & Ramesh Krishnamurti & Rajeev Kohli, 2009. "Conflict Resolution in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 57(5), pages 1098-1105, October.
    • Handle: RePEc:inm:oropre:v:57:y:2009:i:5:p:1098-1105
    DOI: 10.1287/opre.1080.0635
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0635
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1080.0635?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Srinivas Bollapragada & Marc Garbiras, 2004. "Scheduling Commercials on Broadcast Television," Operations Research, INFORMS, vol. 52(3), pages 337-345, June.
    2. Srinivas K. Reddy & Jay E. Aronson & Antonie Stam, 1998. "SPOT: Scheduling Programs Optimally for Television," Management Science, INFORMS, vol. 44(1), pages 83-102, January.
    3. de Klerk, E. & Pasechnik, D.V. & Warners, J.P., 2004. "On approximate graph colouring and MAX-k-CUT algorithms based on the theta-function," Other publications TiSEM 7a6fbcee-93d0-4f7d-86be-b, Tilburg University, School of Economics and Management.
    4. Srinivas Bollapragada & Michael R. Bussieck & Suman Mallik, 2004. "Scheduling Commercial Videotapes in Broadcast Television," Operations Research, INFORMS, vol. 52(5), pages 679-689, October.
    5. Orlin, James & Punnen, Abraham & Schulz, Andreas, 2004. "Approximate Local Search in Combinatorial Optimization," Working papers 4325-03, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Daniel Kowalczyk & Roel Leus, 2017. "An exact algorithm for parallel machine scheduling with conflicts," Journal of Scheduling, Springer, vol. 20(4), pages 355-372, August.
    2. Giovanni Giallombardo & Giovanna Miglionico & Houyuan Jiang, 2015. "New Reformulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Working Papers 2015/03, Cambridge Judge Business School, University of Cambridge.
    3. Giovanni Giallombardo & Houyuan Jiang & Giovanna Miglionico, 2016. "New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 64(4), pages 838-848, August.
    4. José Antonio Carbajal & Peter Williams & Andreea Popescu & Wes Chaar, 2019. "Turner Blazes a Trail for Audience Targeting on Television with Operations Research and Advanced Analytics," Interfaces, INFORMS, vol. 49(1), pages 64-89, January.
    5. Shinjini Pandey & Goutam Dutta & Harit Joshi, 2017. "Survey on Revenue Management in Media and Broadcasting," Interfaces, INFORMS, vol. 47(3), pages 195-213, June.
    6. José Antonio Carbajal & Wes Chaar, 2017. "Turner Optimizes the Allocation of Audience Deficiency Units," Interfaces, INFORMS, vol. 47(6), pages 518-536, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Giovanni Giallombardo & Houyuan Jiang & Giovanna Miglionico, 2016. "New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 64(4), pages 838-848, August.
    2. José Antonio Carbajal & Wes Chaar, 2017. "Turner Optimizes the Allocation of Audience Deficiency Units," Interfaces, INFORMS, vol. 47(6), pages 518-536, December.
    3. José Antonio Carbajal & Peter Williams & Andreea Popescu & Wes Chaar, 2019. "Turner Blazes a Trail for Audience Targeting on Television with Operations Research and Advanced Analytics," Interfaces, INFORMS, vol. 49(1), pages 64-89, January.
    4. Shinjini Pandey & Goutam Dutta & Harit Joshi, 2017. "Survey on Revenue Management in Media and Broadcasting," Interfaces, INFORMS, vol. 47(3), pages 195-213, June.
    5. Srinivas Bollapragada & Marc Garbiras, 2004. "Scheduling Commercials on Broadcast Television," Operations Research, INFORMS, vol. 52(3), pages 337-345, June.
    6. Guohua Wan & Xiangtong Qi, 2010. "Scheduling with variable time slot costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(2), pages 159-171, March.
    7. Sylvia Hristakeva & Julie Holland Mortimer, 2023. "Price Dispersion and Legacy Discounts in the National Television Advertising Market," Marketing Science, INFORMS, vol. 42(6), pages 1162-1183, November.
    8. M J Brusco, 2008. "Scheduling advertising slots for television," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1363-1372, October.
    9. John Turner & Alan Scheller-Wolf & Sridhar Tayur, 2011. "OR PRACTICE---Scheduling of Dynamic In-Game Advertising," Operations Research, INFORMS, vol. 59(1), pages 1-16, February.
    10. Giovanni Giallombardo & Giovanna Miglionico & Houyuan Jiang, 2015. "New Reformulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Working Papers 2015/03, Cambridge Judge Business School, University of Cambridge.
    11. Dana G. Popescu & Pascale Crama, 2016. "Ad Revenue Optimization in Live Broadcasting," Management Science, INFORMS, vol. 62(4), pages 1145-1164, April.
    12. Shi, Yang & Zhao, Ying, 2019. "Modeling Advertisers' Willingness to Pay in TV Commercial Slot Auctions," Journal of Interactive Marketing, Elsevier, vol. 48(C), pages 120-133.
    13. Yiting Xing & Ling Li & Zhuming Bi & Marzena Wilamowska‐Korsak & Li Zhang, 2013. "Operations Research (OR) in Service Industries: A Comprehensive Review," Systems Research and Behavioral Science, Wiley Blackwell, vol. 30(3), pages 300-353, May.
    14. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    15. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    16. Albert Corominas & Alberto García-Villoria & Rafael Pastor, 2013. "Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 296-312, July.
    17. Cheng Lu & Zhibin Deng, 2021. "A branch-and-bound algorithm for solving max-k-cut problem," Journal of Global Optimization, Springer, vol. 81(2), pages 367-389, October.
    18. Gaurav Sabnis & Rajdeep Grewal, 2015. "Cable News Wars on the Internet: Competition and User-Generated Content," Information Systems Research, INFORMS, vol. 26(2), pages 301-319, June.
    19. Bollapragada, Srinivas & Bussieck, Michael & Mallik, Suman, 2002. "Scheduling Commercial Videotapes in Broadcast Television," Working Papers 02-0127, University of Illinois at Urbana-Champaign, College of Business.
    20. Cemalettin Öztürk & F. Zeynep Sargut & M. Arslan Örnek & Deniz Türsel Eliiyi, 2017. "Optimisation and heuristic approaches for assigning inbound containers to outbound carriers," Maritime Policy & Management, Taylor & Francis Journals, vol. 44(7), pages 825-836, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:57:y:2009:i:5:p:1098-1105. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.