Scheduling advertising slots for television

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 L1 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.