Gunther Bidlingmaier

dblp:351/1079 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2025 Greedy Minimum-Energy Scheduling
abstract
Abstract We consider the problem of energy-efficient scheduling across multiple processors with a power-down mechanism. In this setting a set of n jobs with individual release times, deadlines, and processing volumes must be scheduled across m parallel processors while minimizing the consumed energy. When idle, each processor can be turned off to save energy, while turning it on requires a fixed amount of energy. For the special case of a single processor, the greedy Left-to-Right algorithm [1] guarantees an approximation factor of 2. We generalize this simple greedy policy to the case of $$m \ge 1$$ processors running in parallel and show that the energy costs are still bounded by $$2 {{\,\textrm{OPT}\,}}+ P$$ , where $${{\,\textrm{OPT}\,}}$$ is the energy consumed by an optimal solution and $$P < {{\,\textrm{OPT}\,}}$$ is the total processing volume. Our algorithm has a running time of $$\mathcal {O}(n f \log d)$$ , where d is the difference between the last deadline and the earliest release time, and f is the running time of a maximum flow calculation in a network of $$\mathcal {O}(n)$$ nodes.
Gunther Bidlingmaier
Theory Comput. Syst.1
2023 Greedy Minimum-Energy Scheduling
Gunther Bidlingmaier
WAOA1