Scheduling commercial videotapes in broadcast television

This paper, motivated by the experiences of a major U.S.-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 evenly spaced as possible. Thus, our objective is to schedule a set of commercials in a set of available slots such that multiple airings of the same commercial are as 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 time frame. We present an alternative mixed-integer program that lends itself to an efficient solution. For solving even larger problems, we present multiple heuristics.