Scheduling Commercial Videotapes in Broadcast Television

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.