Fakultät II - Mathematik und Naturwissenschaften

Institut für Mathematik, Secr. MA 5-2

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

Office: MA663

Email: f.(lastname)@tu-berlin.de

- O(1/\(\epsilon\)) Is the Answer in Online Weighted Throughput Maximization ( )

STACS 2024 – Proc. 41st International Symposium on Theoretical Aspects of Computer Science, pp. 32:1–32:15.

@inproceedings{Eberle2024,

author = {Franziska Eberle},

booktitle = {STACS 2024 – Proc. 41st International Symposium on Theoretical Aspects of Computer Science},

title = {O(1/{\(\epsilon\)}) Is the Answer in Online Weighted Throughput Maximization},

pages = {32:1--32:15},

year = {2024},

doi = {10.4230/LIPICS.STACS.2024.32},

}We study a fundamental online scheduling problem where jobs with processing times, weights, and deadlines arrive online over time at their release dates. The task is to preemptively schedule these jobs on a single or multiple (possibly unrelated) machines with the objective to maximize the weighted throughput, the total weight of jobs that complete before their deadline. To overcome known lower bounds for the competitive analysis, we assume that each job arrives with some slack $\varepsilon > 0$; that is, the time window for processing job $j$ on any machine $i$ on which it can be executed has length at least $(1+\varepsilon)$ times $j$'s processing time on machine $i$. Our contribution is a best possible online algorithm for weighted throughput maximization on unrelated machines: Our algorithm is $O\big(\frac1\varepsilon\big)$-competitive, which matches the lower bound for unweighted throughput maximization on a single machine. Even for a single machine, it was not known whether the problem with weighted jobs is "harder" than the problem with unweighted jobs. Thus, we answer this question and close weighted throughput maximization on a single machine with a best possible competitive ratio $\Theta\big(\frac1\varepsilon\big)$. While we focus on non-migratory schedules, on identical machines, our algorithm achieves the same (up to constants) performance guarantee when compared to an optimal migratory schedule.

- Speed-robust scheduling: sand, bricks, and rocks ( )

Mathematical Programming, 197(2):1009–1048, 2023.

@article{EberleHoeksmaMegow+2023,

author = {Franziska Eberle and Ruben Hoeksma and Nicole Megow and Lukas N{\"{o}}lke and Kevin Schewior and Bertrand Simon},

title = {Speed-robust scheduling: sand, bricks, and rocks},

journal = {Mathematical Programming},

volume = {197},

number = {2},

pages = {1009--1048},

year = {2023},

doi = {10.1007/S10107-022-01829-0},

}The speed-robust scheduling problem is a two-stage problem where, given $m$ machines, jobs must be grouped into at most $m$ bags while the processing speeds of the machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor $2-\frac1m$ for the most general setting and improve this to $1.8$ for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to $\frac e{e-1}\approx 1.58$. The particular machine environment in which all machines have either speed $0$ or $1$ was studied before by Stein and Zhong (ACM Trans.\ Alg.\ 2020). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $\frac{1+\sqrt{2}}2\approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $\frac43$ for equal-size jobs. - Online Throughput Maximization on Unrelated Machines: Commitment is No Burden ( )

ACM Transactions on Algorithms, 19(1):10:1–10:25, 2023.

@article{EberleMegowSchewior2023,

author = {Franziska Eberle and Nicole Megow and Kevin Schewior},

title = {Online Throughput Maximization on Unrelated Machines: Commitment is No Burden},

journal = {ACM Transactions on Algorithms},

volume = {19},

number = {1},

pages = {10:1--10:25},

year = {2023},

}We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a single or multiple possibly unrelated machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis on a single machine, we require that jobs contain some \em slack $\varepsilon>0$, which means that the feasible time window for scheduling a job is at least $1+\varepsilon$ times its processing time on each eligible machine. Our contribution is two-fold: (i) We give the first non-trivial online algorithms for throughput maximization on unrelated machines, and (ii), this is the main focus of our paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services, and disallows last-minute rejections of critical tasks. We present an algorithm for unrelated machines that is $\Theta\big(\frac{1}\varepsilon\big )$-competitive when the scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job's slack becomes less than a $\delta$-fraction of its size, we prove a competitive ratio of $\mathcal{O}\big(\frac{1}{\varepsilon - \delta}\big)$ for $0 < \delta < \varepsilon$. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm admits any bounded competitive ratio. While we mainly focus on scheduling without migration, our results also hold when comparing against a migratory optimal solution in case of identical machines. - Configuration Balancing for Stochastic Requests ( )

IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization, Springer, pp. 127–141.

@inproceedings{EberleGuptaMegow+2023,

author = {Franziska Eberle and Anupam Gupta and Nicole Megow and Benjamin Moseley and Rudy Zhou},

title = {Configuration Balancing for Stochastic Requests},

booktitle = {IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization},

series = {Lecture Notes in Computer Science},

volume = {13904},

pages = {127--141},

publisher = {Springer},

year = {2023},

doi = {10.1007/978-3-031-32726-1\_10},

}The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given $m$ resources and $n$ requests; each request has multiple possible \emphconfigurations, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize the \emphmakespan: the load of the most-loaded resource. In the stochastic setting, the amount by which a configuration increases the resource load is uncertain until the configuration is chosen, but we are given a probability distribution. We develop both offline and online algorithms for configuration balancing with stochastic requests. When the requests are known offline, we give a non-adaptive policy for configuration balancing with stochastic requests that $O(\frac{\log m}{\log \log m})$-approximates the optimal adaptive policy, which matches a known lower bound for the special case of load balancing on identical machines. When requests arrive online in a list, we give a non-adaptive policy that is $O(\log m)$ competitive. Again, this result is asymptotically tight due to information-theoretic lower bounds for special cases (e.g., for load balancing on unrelated machines). Finally, we show how to leverage adaptivity in the special case of load balancing on \emphrelated machines to obtain a constant-factor approximation offline and an $O(\log \log m)$-approximation online. A crucial technical ingredient in all of our results is a new structural characterization of the optimal adaptive policy that allows us to limit the correlations between its decisions.

- Speed-Robust Scheduling - Sand, Bricks, and Rocks ( )

IPCO 2021 – Proc. 22nd Conference on Integer Programming and Combinatorial Optimization, Springer, pp. 283–296.

@inproceedings{EberleHoeksmaMegow+2021,

author = {Franziska Eberle and Ruben Hoeksma and Nicole Megow and Lukas N{\"{o}}lke and Kevin Schewior and Bertrand Simon},

title = {Speed-Robust Scheduling - Sand, Bricks, and Rocks},

booktitle = {IPCO 2021 – Proc. 22nd Conference on Integer Programming and Combinatorial Optimization},

series = {Lecture Notes in Computer Science},

volume = {12707},

pages = {283--296},

publisher = {Springer},

year = {2021},

doi = {10.1007/978-3-030-73879-2\_20},

}The speed-robust scheduling problem is a two-stage problem where, given $m$ machines, jobs must be grouped into at most $m$ bags while the processing speeds of the machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor $2-\frac1m$ for the most general setting and improve this to $1.8$ for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to $\frac e{e-1}\approx 1.58$. The particular machine environment in which all machines have either speed $0$ or $1$ was studied before by Stein and Zhong (ACM Trans.\ Alg.\ 2020). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $\frac{1+\sqrt{2}}2\approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $\frac43$ for equal-size jobs.