Conflict resolution in the scheduling of television commercials
Coauthor(s): Daya Gaur, Ramesh Krishnamurti.
Adobe Acrobat PDF
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.
Source: Operations Research
Gaur, Daya, Ramesh Krishnamurti, and Rajeev Kohli. "Conflict resolution in the scheduling of television commercials." Operations Research 57, no. 5 (September 2009): 1098-1105.