Advertisement
Published in:
2016 | OriginalPaper | Chapter
Cost-Efficient Scheduling on Machines from the Cloud
Authors : Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer auf der Heide, Sören Riechers
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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
-competitive online algorithm for \(\beta = (1+\varepsilon )s\) with
, 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
.
-competitive online algorithm for \(\beta = (1+\varepsilon )s\) with
, 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
.