Optimal Advertisement Scheduling in Breaks of Random Lengths

Broadcasters generate a large part of their revenue through advertising, especially in live sports. Scheduling advertisements can be challenging in live broadcasting, however, for sports such as Cricket that have breaks of ran-dom lengths and number during which the ads are shown. This uncertainty, coupled with the high price of spots for major competitions, means that improving ad scheduling can add significant value to the broadcaster. This problem shares similarities with the stochastic cutting stock problem and the dynamic stochastic knapsack problem, with applications in the wood, steel and paper industry and the transportation industry respectively. This dissertation adds to the existing literature on advertising scheduling by taking stochasticity in break sizes into consideration. We propose an opti-mal scheduling rule under simplifying assumptions and prove that our policy outperforms traditional scheduling methods. We also study the performance of several heuristics, and find that a flexible heuristic that does not depend on creating bundles performs the best