Scheduling advertising slots for television

Abstract

The ISCI (Industry Standard Commercial Identification) rotator problem requires the assignment of a set of commercial videotapes to slots such that multiple airings of each tape in the set are as equally spaced as possible with respect to an L₁ loss function. The contributions of this research paper are threefold. First, an enhanced branch-and-bound algorithm is presented and shown to produce optimal solutions for each of several problems that were not computationally feasible for a previously developed branch-and-bound implementation. Second, a fast simulated annealing heuristic is developed for larger problems. This heuristic has established new benchmark (best-known) solutions for 16 large ISCI rotator problems from a recently published test suite. Third, we consider alternative loss function metrics, and have found that a branch-and-bound algorithm for the L_∞ algorithm is especially scalable.

Keywords:

• scheduling
• optimization
• heuristics