Working Papers Home

2015 Working Papers
2014 Working Papers
2013 Working Papers
2012 Working Papers
2011 Working Papers
2010 Working Papers
2009 Working Papers
2008 Working Papers
2007 Working Papers
2006 Working Papers
2005 Working Papers
2004 Working Papers
2003 Working Papers
2002 Working Papers
2001 Working Papers
2000 Working Papers

Search All Papers

JEL Classification

Past Working Papers (Prior to 2000)

Office of Research
Home Page

Information on
Submitting a Paper

"Scheduling Commerical Videotapes in Broadcast Television"

Srinivas Bollapragada, Michael Bussieck, and Suman Mallik


First Author :

Srinivas Bollapragada
GE Global Research Center
1 Research Circle
Schenectady, NY 12309

Second Author :

Michael Bussieck
GAMS Development Corporation
1217 Potomac Street NW
Washington, DC 20007

Third Author :

Suman Mallik
Business Administration
University of Illinois at Urbana-Champaign
1206 S. Sixth Street, M/C 706
Champaign, IL 61820

Create Profile

Abstract :
This paper, motivated by the experiences of major US-based broadcast television network, presents algorithms and heuristics to schedule commercial videotapes. Major advertisers purchase several slots to air commercials during a given time period on a broadcast network. We study the problem of scheduling advertiser's commercials in the slots it purchased when the same commercial is to be aired multiple times. Under such a situation, the advertisers typically want the airings of a commercial to be as much evenly spaced as possible. Thus, our objective is to schedule a set of commercials on a set of available slots such that multiple airings of the same commercial are as much evenly spaced as possible. A natural formulation of this problem is a mixed integer program that can be solved using third party solvers. We also develop a branch-and-bound algorithm based on a problem specific bounding scheme. Both approaches fail to solve larger problem instances within a reasonable timeframe. We present an alternative mixed integer program that lends itself to efficient solution. For solving even larger problems, we present multiple heuristics. Various extensions of the basic model are discussed.
Keywords :
broadcast television, heuristics, Mixed integer programming, Scheduling
Manuscript Received : 2002
Manuscript Published : 2002
This abstract has been viewed 3052 times.
Click here to view the full text of this paper.