Heuristic Algorithms for Simultaneously Accepting and Scheduling Advertisements on Broadcast Television

Abstract

This paper introduces a new optimization problem for a TV station to accept and schedule adver- tisements. The TV station has its advertising slots with audience ratings, and the advertisers purchase audience ratings. The objective of the TV station is to maximize the total revenue by simultaneously accepting some of the advertisements and \ufb01nding a feasible schedule for them. An integer programming model is formulated and three heuristic algorithms are proposed. The numerical experiments show that these heuristics are effective.