FEFranziska Eberle
Franziska Eberle
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Franziska Eberle has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Nicole Megow
University of Bremen, Bremen, Germany
9 shared publications - Kevin Schewior
Department of Mathematics and Computer Science University of Cologne Germany
5 shared publications - Bertrand Simon
IN2P3 Computing Center CNRS Villeurbanne France
2 shared publications Kevin Schewior
Universität zu Köln
2 shared publications- Lin Chen
Zhejiang University
2 shared publications - Lukas Nölke
Faculty of Mathematics and Computer Science, University of Bremen, Bremen, Germany
2 shared publications
Latest Publications
- Open Access
- 31 January 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (1) , 1-25
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
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 slack ɛ > 0, which means that the feasible time window for scheduling a job is at least 1+ɛ 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 (\frac{1}{\varepsilon })\) -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 δ-fraction of its size, we prove a competitive ratio of \(\mathcal {O}(\frac{1}{\varepsilon - \delta })\) for 0 < δ < ɛ. 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.- 31 January 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (1) , 1-25
Open AccessOnline Throughput Maximization on Unrelated Machines: Commitment is No Burden
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 slack ɛ > 0, which means that the feasible time window for scheduling a job is at least 1+ɛ 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 (\frac{1}{\varepsilon })\) -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 δ-fraction of its size, we prove a competitive ratio of \(\mathcal {O}(\frac{1}{\varepsilon - \delta })\) for 0 < δ < ɛ. 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. - 30 August 2022
- Published by Springer Nature
- p. 9-14
Scheduling and Packing Under Uncertainty
- 2 July 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1009-1048
Speed-robust scheduling: sand, bricks, and rocks
- 2 July 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1009-1048
Speed-robust scheduling: sand, bricks, and rocks
- Open Access
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
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 given $m$ 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-1/m$ 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 $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 (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $(1+\sqrt{2})/2 \approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $4/3$ for equal-size jobs.Open AccessSpeed-Robust Scheduling -- Sand, Bricks, and Rocks
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 given $m$ 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-1/m$ 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 $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 (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $(1+\sqrt{2})/2 \approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $4/3$ for equal-size jobs. - Open Access
- 1 April 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (3) , 322-328
Online load balancing with general reassignment cost
- 1 April 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (3) , 322-328
Open AccessOnline load balancing with general reassignment cost
- Open Access
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
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 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.Open AccessOnline Throughput Maximization on Unrelated Machines: Commitment is No Burden
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 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. - Open Access
- 3 February 2020
- Published by Springer Nature in Mathematical Programming
- Vol. 183 (1-2) , 215-247
A general framework for handling commitment in online throughput maximization
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least $$1+\varepsilon $$ times its processing time, for some $$\varepsilon >0$$ . We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of $$\mathcal {O}(1/\varepsilon )$$ is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the 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}(\varepsilon /((\varepsilon -\delta )\delta ^2))$$ , for $$0<\delta <\varepsilon $$ . When a provider must commit upon starting a job, our bound is $$\mathcal {O}(1/\varepsilon ^2)$$ . Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.- 3 February 2020
- Published by Springer Nature in Mathematical Programming
- Vol. 183 (1-2) , 215-247
Open AccessA general framework for handling commitment in online throughput maximization
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least $$1+\varepsilon $$ times its processing time, for some $$\varepsilon >0$$ . We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of $$\mathcal {O}(1/\varepsilon )$$ is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the 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}(\varepsilon /((\varepsilon -\delta )\delta ^2))$$ , for $$0<\delta <\varepsilon $$ . When a provider must commit upon starting a job, our bound is $$\mathcal {O}(1/\varepsilon ^2)$$ . Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms. - 1 May 2019
- Published by Elsevier in Operations Research Letters
- Vol. 47 (3) , 213-218
On index policies for stochastic minsum scheduling
- 1 May 2019
- Published by Elsevier in Operations Research Letters
- Vol. 47 (3) , 213-218
On index policies for stochastic minsum scheduling