{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:07Z","timestamp":1740144487945,"version":"3.37.3"},"reference-count":49,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"vor","delay-in-days":38,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2017\/21297-2"],"award-info":[{"award-number":["2017\/21297-2"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2020\/13162-2"],"award-info":[{"award-number":["2020\/13162-2"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2016\/23552-7"],"award-info":[{"award-number":["2016\/23552-7"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2015\/11937-9"],"award-info":[{"award-number":["2015\/11937-9"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["425806\/2018-9"],"award-info":[{"award-number":["425806\/2018-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["308689\/2017-8"],"award-info":[{"award-number":["308689\/2017-8"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["425340\/2016-3"],"award-info":[{"award-number":["425340\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,5,14]]},"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>In the MAXSPACE problem, given a set of ads <jats:italic>A<\/jats:italic>, one wants to place a subset <jats:italic>A<\/jats:italic>\u2032 \u2286 <jats:italic>A<\/jats:italic> into <jats:italic>K<\/jats:italic> slots <jats:italic>B<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026, <jats:italic>B<jats:sub>K<\/jats:sub><\/jats:italic> of size <jats:italic>L<\/jats:italic>. Each ad <jats:italic>A<jats:sub>i<\/jats:sub><\/jats:italic> \u2208 <jats:italic>A<\/jats:italic> has <jats:italic>size<\/jats:italic> <jats:italic>s<jats:sub>i<\/jats:sub><\/jats:italic> and <jats:italic>frequency<\/jats:italic> <jats:italic>w<jats:sub>i<\/jats:sub><\/jats:italic>. A schedule is feasible if the total size of ads in any slot is at most <jats:italic>L<\/jats:italic>, and each ad <jats:italic>A<jats:sub>i<\/jats:sub><\/jats:italic> \u2208 <jats:italic>A<\/jats:italic>\u2032 appears in exactly <jats:italic>w<jats:sub>i<\/jats:sub><\/jats:italic> 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 <jats:italic>A<jats:sub>i<\/jats:sub><\/jats:italic> has a release date <jats:italic>r<jats:sub>i<\/jats:sub><\/jats:italic> \u2265 1, a deadline <jats:italic>d<jats:sub>i<\/jats:sub><\/jats:italic> \u2265 <jats:italic>r<jats:sub>i<\/jats:sub><\/jats:italic>, a profit <jats:italic>v<jats:sub>i<\/jats:sub><\/jats:italic> that may not be related with <jats:italic>s<jats:sub>i<\/jats:sub><\/jats:italic> and lower and upper bounds <jats:italic>w<jats:sup>min<\/jats:sup><jats:sub>i<\/jats:sub><\/jats:italic> and <jats:italic>w<jats:sup>max<\/jats:sup><jats:sub>i<\/jats:sub><\/jats:italic> for frequency. In this problem, an ad may only appear in a slot <jats:italic>B<jats:sub>j<\/jats:sub><\/jats:italic> with <jats:italic>r<jats:sub>i<\/jats:sub><\/jats:italic> \u2264 <jats:italic>j<\/jats:italic> \u2264 <jats:italic>d<jats:sub>i<\/jats:sub><\/jats:italic>, 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 <jats:italic>et al<\/jats:italic>. [<jats:italic>Eur. J. Oper. Res<\/jats:italic>. 173 (2006) 1067\u20131089]. 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.<\/jats:p>","DOI":"10.1051\/ro\/2024114","type":"journal-article","created":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T18:54:47Z","timestamp":1715799287000},"page":"3203-3231","source":"Crossref","is-referenced-by-count":0,"title":["Local-search based heuristics for advertisement scheduling"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0691-4554","authenticated-orcid":false,"given":"Mauro Roberto","family":"Costa da Silva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0472-4810","authenticated-orcid":false,"given":"Rafael Crivellari Saliba","family":"Schouery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,8,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1002\/jos.74","volume":"5","author":"Adler","year":"2002","journal-title":"J. Sched."},{"key":"R2","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1287\/opre.23.6.1099","volume":"23","author":"Ahrens","year":"1975","journal-title":"Oper. Res."},{"key":"R3","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1109\/TSMCA.2005.855918","volume":"36","author":"Amiri","year":"2006","journal-title":"Proc. IEEE Trans. Syst. Man Cybern.-Part A: Syst. Hum."},{"key":"R4","unstructured":"Barr R.S. and Ross G.T., A linked list data structure for a binary knapsack algorithm. Technical report, Texas Univ at Austin Center for Cybernetic Studies (1975)."},{"key":"R5","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1016\/j.cor.2011.01.006","volume":"38","author":"Boskamp","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"R6","first-page":"33","volume":"37","author":"Briggs","year":"1997","journal-title":"J. Adv. Res."},{"key":"R7","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"Chekuri","year":"2005","journal-title":"SIAM J. Comput."},{"key":"R8","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1016\/j.entcs.2019.08.061","volume":"346","author":"Da Silva","year":"2019","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"R9","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1023\/A:1024060710627","volume":"6","author":"Dawande","year":"2003","journal-title":"Proc. J. Sched."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Dean B.C. and Goemans M.X., Improved approximation algorithms for minimum-space advertisement scheduling, in Proceedings of International Colloquium on Automata, Languages, and Programming (2003) 1138\u20131152.","DOI":"10.1007\/3-540-45061-0_87"},{"key":"R11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","volume":"255","author":"Delorme","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"R12","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s11590-017-1192-z","volume":"12","author":"Delorme","year":"2018","journal-title":"Optim. Lett."},{"key":"R13","first-page":"1","volume":"7","author":"Dem\u0161ar","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"R14","doi-asserted-by":"crossref","first-page":"39","DOI":"10.15388\/ioi.2015.04","volume":"9","author":"Dima","year":"2015","journal-title":"Olymp. Inform."},{"key":"R15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"Dolan","year":"2002","journal-title":"Math. Program."},{"key":"R16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF00226291","volume":"2","author":"Falkenauer","year":"1996","journal-title":"J. Heuristics"},{"key":"R17","first-page":"327","volume":"24","author":"Fenwick","year":"1994","journal-title":"Softw.: Pract. Exper."},{"key":"R18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"Feo","year":"1995","journal-title":"J. Global Optim."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Freund A. and Naor J.S., Approximating the advertisement placement problem, in Proceedings of International Conference on Integer Programming and Combinatorial Optimization (2002) 415\u2013424.","DOI":"10.1007\/3-540-47867-1_29"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Gendreau M. and Potvin J.-Y., Handbook of Metaheuristics, vol. 2. Springer (2010).","DOI":"10.1007\/978-1-4419-1665-5"},{"key":"R21","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"Glover","year":"1986","journal-title":"Comput. Oper. Res."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Graham R.L., Lawler E.L., Lenstra J.K. and Kan A.R., Optimization and approximation in deterministic sequencing and scheduling: a survey, in Annals of Discrete Mathematics. Elsevier (1979) 287\u2013326.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R23","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1287\/mnsc.16.5.327","volume":"16","author":"Greenberg","year":"1970","journal-title":"Manage. Sci."},{"key":"R24","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1287\/ijoc.2015.0670","volume":"28","author":"Gschwind","year":"2016","journal-title":"INFORMS J. Comput."},{"key":"R25","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"Hochbaum","year":"1987","journal-title":"J. ACM"},{"key":"R26","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"Horowitz","year":"1974","journal-title":"J. ACM (JACM)"},{"key":"R27","unstructured":"IAB, Internet advertising revenue report: full year 2022 (2022). https:\/\/www.iab.com\/wp-content\/uploads\/2023\/04\/IAB_PwC_Internet_Ad\\vertising_Revenue_Report_2022.pdf. [Online; Accessed on: 2023-05-03]."},{"key":"R28","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"Ibarra","year":"1975","journal-title":"J. ACM (JACM)"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Kellerer H., A polynomial time approximation scheme for the multiple knapsack problem, in Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. Springer (1999) 51\u201362.","DOI":"10.1007\/978-3-540-48413-4_6"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Kellerer H., Pferschy U. and Pisinger D., Introduction to np-completeness of knapsack problems, in Knapsack Problems. Springer (2004) 483\u2013493.","DOI":"10.1007\/978-3-540-24777-7_16"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Khuri S., B\u00a8ack T. and Heitk\u00f6tter J., The zero\/one multiple knapsack problem and genetic algorithms, in Proceedings of the 1994 ACM Symposium on Applied Computing. ACM (1994) 188\u2013193.","DOI":"10.1145\/326619.326694"},{"key":"R32","doi-asserted-by":"crossref","first-page":"106226","DOI":"10.1016\/j.cie.2019.106226","volume":"140","author":"Kim","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"R33","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1287\/mnsc.13.9.723","volume":"13","author":"Kolesar","year":"1967","journal-title":"Manage. Sci."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Kumar S., Optimization Issues in Web and Mobile Advertising: Past and Future Trends. Springer (2015).","DOI":"10.1007\/978-3-319-18645-0"},{"key":"R35","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1016\/j.ejor.2005.07.005","volume":"173","author":"Kumar","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"R36","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"Lawler","year":"1979","journal-title":"Math. Oper. Res."},{"key":"R37","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez M., C\u00e1ceres L.P., Dubois-Lacoste J., St\u00fctzle T. and Birattari M., The irace package: User guide. IRIDIA, Universit\u00e9 Libre de Bruxelles, Belgium, Tech. Rep. TR\/IRIDIA\/2016-004 (2016)."},{"key":"R38","unstructured":"Mangold B., Learning Google AdWords and Google Analytics. Loves Data (2018)."},{"key":"R39","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0377-2217(77)90024-8","volume":"1","author":"Martello","year":"1977","journal-title":"Eur. J. Oper. Res."},{"key":"R40","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"Mladenovi\u0107","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"R41","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1287\/mnsc.23.1.27","volume":"23","author":"Nauss","year":"1976","journal-title":"Manage. Sci."},{"key":"R42","unstructured":"Schoenfield J.E., Fast, exact solution of open bin packing problems without linear programming. Draft, US Army Space and Missile Defense Command, Huntsville, Alabama, USA (2002)."},{"key":"R43","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1016\/S0305-0548(96)00082-2","volume":"24","author":"Scholl","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"R44","first-page":"377","volume":"4","author":"Schwerin","year":"1997","journal-title":"Int. Trans. Oper. Res."},{"key":"R45","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF02243880","volume":"25","author":"Toth","year":"1980","journal-title":"Computing"},{"key":"R46","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"Ullman","year":"1975","journal-title":"J. Comput. Syst. Sci."},{"key":"R47","doi-asserted-by":"crossref","unstructured":"Vazirani V.V., Approximation Algorithms. Springer Berlin Heidelberg (2003). ISBN 9783642084690, 9783662045657.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"R48","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF01539705","volume":"18","author":"W\u00a8ascher","year":"1996","journal-title":"Oper.-Res.-Spektrum"},{"key":"R49","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1145\/322063.322073","volume":"25","author":"Zoltners","year":"1978","journal-title":"J. ACM (JACM)"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024114\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T12:03:34Z","timestamp":1723205014000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":49,"journal-issue":{"issue":"4"},"alternative-id":["ro230776"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024114","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,7]]}}}