2026-08-25T18:47:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27190 2026-08-25T13:18:17Z ddc:004 open_access

Online Demand Strip Packing Bruchhold, Sebastian Eberle, Franziska Moneftsis, Georgios Rau, Malin Vesterlund, Albert Online Demand Strip Packing competitive analysis scheduling packing In the Demand Strip Packing problem (DSP), we are given a finite set of tasks, each characterized by a specific duration and energy demand. These tasks need to be scheduled non-preemptively within a given time frame while minimizing the peak demand: the maximum amount of energy consumed by the tasks being executed at any point in time. We are the first to consider the online variant of the problem, where tasks are revealed to an algorithm one by one in a list. Upon arrival, each task must be assigned an irrevocable starting time before the next task in the list is revealed. As usual in online optimization, we evaluate the performance of online algorithms using competitive analysis. We give a strictly 4.263-competitive algorithm for Online DSP, which is stronger than the respective bound of 6.479 for the related problem Online Strip Packing. Additionally, we prove a lower bound of 1.812 on the competitive ratio of any online algorithm for DSP and, thus, clearly separate Online DSP from Online Minimum Peak Appointment Scheduling (MPAS), a special case of Online DSP, for which a strictly 5/3-competitive algorithm is known. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Bruchhold and Franziska Eberle and Georgios Moneftsis and Malin Rau and Albert Vesterlund 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.54 urn:nbn:de:0030-drops-271909 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.54 eng https://creativecommons.org/licenses/by/4.0/legalcode