Answers are grounded in this paper and cite their sources.
In the MAXSPACE problem, given a set of ads A , one wants to place a subset A ′ ⊆ A into K slots B 1 , …, 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.
No takes yet. Share an insight, caveat, or question.
Silva et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: