Conflict resolution in the scheduling of television commercials

Conflict resolution in the scheduling of television commercials

0.00 Avg rating0 Votes
Article ID: iaor200971630
Country: United States
Volume: 57
Issue: 5
Start Page Number: 1098
End Page Number: 1105
Publication Date: Sep 2009
Journal: Operations Research
Authors: , ,
Keywords: timetabling, graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.