Cost-efficient Scheduling on Machines from the Cloud
Mäcker, Alexander
Malatyali, Manuel
Meyer auf der Heide, Friedhelm
Riechers, Sören
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
info:eu-repo/semantics/preprint
doc-type:preprint
text
https://ris.uni-paderborn.de/record/16396
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.
eng
info:eu-repo/semantics/altIdentifier/arxiv/1609.01184
info:eu-repo/semantics/closedAccess