Speed-robust scheduling: sand, bricks, and rocks (Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, and Bertrand Simon)
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 (Franziska Eberle, Nicole Megow, and Kevin Schewior)
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 (Franziska Eberle, Anupam Gupta, Nicole Megow, Benjamin Moseley, and Rudy Zhou)
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.
