Scheduling TV commercials using genetic algorithms

In this paper, the problem of scheduling commercial messages during the peak of viewing time of a TV channel is formulated as a combinatorial auction-based mathematical programming model. Through this model, a profitable and efficient mechanism for allocating the advertising time to advertisers is developed by which the revenue of TV channels is maximised while the effectiveness of advertising is increased. We developed a steady-state genetic algorithm to find an optimal or a near optimal solution for the proposed problem. A computational experiment was conducted for evaluating the efficiency of the proposed algorithm. A set of test problems with different sizes were generated, using the pseudo-random generation mechanism, and solved by the proposed genetic algorithm. The optimal solutions of the linear programming relaxation of these test problems were also obtained and were used for evaluating the quality of solutions obtained by the developed algorithm. The results of this computational experiment revealed the robustness of the solutions and acceptably low computational time for obtaining these solutions. The computational results also demonstrated that the proposed genetic algorithm had an appropriate ability to preserve population diversity during the search and was capable of obtaining high-quality solutions for the proposed problem.