Local-search based heuristics for advertisement scheduling

Institute of Computing, University of Campinas, Av. Albert Einstein, 1251, Campinas, 13083-852 Sãao Paulo, Brazil

^* Corresponding author: maurorcsc@gmail.com

Received: 8 November 2023
Accepted: 14 May 2024

Abstract

In the MAXSPACE problem, given a set of ads A, one wants to place a subset A′ ⊆ A into K slots B₁, …, B_K of size L. Each ad A_i ∈ A has size s_i and frequency w_i. A schedule is feasible if the total size of ads in any slot is at most L, and each ad A_i ∈ A′ appears in exactly w_i slots. The goal is to find a feasible schedule that maximizes the space occupied in all slots. We introduce MAXSPACE-RDWV, a MAXSPACE generalization with release dates, deadlines, variable frequency, and generalized profit. In MAXSPACE-RDWV each ad A_i has a release date r_i ≥ 1, a deadline d_i ≥ r_i, a profit v_i that may not be related with s_i and lower and upper bounds w^min_i and w^max_i for frequency. In this problem, an ad may only appear in a slot B_j with r_i ≤ j ≤ d_i, and the goal is to find a feasible schedule that maximizes the sum of values of scheduled ads. This paper presents some algorithms based on meta-heuristics GRASP, VNS, and Tabu Search for MAXSPACE and MAXSPACE-RDWV. We compare our proposed algorithms with Hybrid-GA proposed by Kumar et al. [Eur. J. Oper. Res. 173 (2006) 1067–1089]. We also created a version of Hybrid-GA for MAXSPACE-RDWV and compared it with our meta-heuristics. Some meta-heuristics like VNS and GRASP+VNS have better results than Hybrid-GA for both problems. In our heuristics, we apply a technique that alternates between maximizing and minimizing the fullness of slots to obtain better solutions. We also applied a data structure called BIT to the neighborhood computation in MAXSPACE-RDWV and showed that this enabled our algorithms to run more iterations.