preprint
Cost-efficient Scheduling on Machines from the Cloud
Alexander
Mäcker
author 13536
Manuel
Malatyali
author
Friedhelm
Meyer auf der Heide
author 15523
Sören
Riechers
author
63
department
We consider a scheduling problem where machines need to be rented from the
cloud in order to process jobs. There are two types of machines available which
can be rented for machine-type dependent prices and for arbitrary durations.
However, a machine-type dependent setup time is required before a machine is
available for processing. Jobs arrive online over time, have machine-type
dependent sizes and have individual deadlines. The objective is to rent
machines and schedule jobs so as to meet all deadlines while minimizing the
rental cost.
Since we observe the slack of jobs to have a fundamental influence on the
competitiveness, we study the model when instances are parameterized by their
(minimum) slack. An instance is called to have a slack of $\beta$ if, for all
jobs, the difference between the job's release time and the latest point in
time at which it needs to be started is at least $\beta$. While for $\beta < s$
no finite competitiveness is possible, our main result is an
$O(\frac{c}{\varepsilon} + \frac{1}{\varepsilon^3})$-competitive online
algorithm for $\beta = (1+\varepsilon)s$ with $\frac{1}{s} \leq \varepsilon
\leq 1$, where $s$ and $c$ denotes the largest setup time and the cost ratio of
the machine-types, respectively. It is complemented by a lower bound of
$\Omega(\frac{c}{\varepsilon})$.
2016
eng
arXiv:1609.01184
1609.01184
Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling on Machines from the Cloud. <i>arXiv:160901184</i>. 2016.
A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient Scheduling on Machines from the Cloud,” <i>arXiv:1609.01184</i>. 2016.
@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient Scheduling on Machines from the Cloud}, journal={arXiv:1609.01184}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016} }
A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, ArXiv:1609.01184 (2016).
Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2016). Cost-efficient Scheduling on Machines from the Cloud. <i>ArXiv:1609.01184</i>.
Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” <i>ArXiv:1609.01184</i>, 2016.
Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.” <i>ArXiv:1609.01184</i>, 2016.
163962020-04-03T09:24:28Z2022-01-06T06:52:50Z