Scheduling commercial videotapes in broadcast television
成果类型：
Article
署名作者：
Bollapragada, S; Bussieck, MR; Mallik, S
署名单位：
General Electric; University of Illinois System; University of Illinois Urbana-Champaign
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0119
发表日期：
2004
页码：
679-689
关键词：
摘要：
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.