(An) Optimization algorithm for the advertisement scheduling problem on broadcast television

Abstract

We consider the advertisement scheduling problem on broadcast television in a given period. Major advertisers want to air several kinds of commercials and purchase broadcast time slots for them without considering actual scheduling. When same commercials are aired multiple times, they usually need to be aired as regularly as possible. This problem is called Industry Standard Commercial Identification (ISCI) rotator problem. The objective of ISCI rotator problem is to assign commercials to be aired as regularly as possible. We propose an integer programming formulation of the problem. Contrary to the previous model, the new model has many columns hence we solved it by branch-and-price (B&P) approach and computational results are reported. We tested our algorithm on 40 instances that have various slot size.