  In the MAXSPACE problem, given a set of ads A, one wants to place a subset A'
of A into K slots B_1, ..., B_K of size L. Each ad A_i in 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 in 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, Local Search, and Tabu Search for MAXSPACE and
MAXSPACE-RDWV. We compare our proposed algorithms with Hybrid-GA proposed by
Kumar et al. (2006). We also create a version of Hybrid-GA for MAXSPACE-RDWV
and compare it with our meta-heuristics. Some meta-heuristics, such as 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 ours algorithms to run more iterations.
