Online Algorithms for the Interval Scheduling Problem in the Cloud: Affinity Pair Threshold Based Approaches
Data
2022Language
en
Soggetto
Abstract
In the interval scheduling problem, jobs have known start and end times (referred to as job intervals) and must be assigned to processing nodes for their whole duration. Although the problem originally stems from the resource allocation demands of resident processes in operating systems, it found a renewed interest in the Cloud context, both in IaaS and SaaS, since reservations for virtual machines and services often have known activation intervals. A common objective of interval scheduling is to minimize busy time of machines which relates (among others) to minimizing the number of machines participating in the computation. As a consequence, bin packing techniques have been applied in the past. In this paper we tackle the online version of the problem, whereby future job arrivals are unknown. We propose novel algorithms that work as a pre-processing step to any bin packing scheme by offering recommendations that are enforced in all packing decisions. Job overlaps are used to characterize pairwise job affinity and subsequently provide threshold based job allocation recommendations. Thresholds are calculated using lower bound theoretical analysis upon two extreme workloads (sparse and dense). Experimental evaluation using real world workloads illustrates the merits of our approach against state-of-the-art algorithms. © 2016 IEEE.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Evaluating the cost of emissions in a pool-based electricity market
Andrianesis P., Biskas P., Liberopoulos G. (2021)This paper proposes a methodology that quantifies the impact of emissions cost on the electricity price, the generation scheduling outcome, and the overall emissions in a pool-based electricity market. It employs a mid-term ... -
Bin Packing Heuristics for the Multiple Workflow Scheduling Problem
Pappas N., Oikonomou P., Tziritas N., Kolomvatsos K., Loukopoulos T. (2021)In the multiple workflow scheduling problem a set of workflows has to be scheduled concurrently onto system's available resources. Workflows exhibit different characteristics e.g., topological structure, size and ... -
Control and optimization meet the smart power grid: Scheduling of power demands for optimal energy management
Koutsopoulos, I.; Tassiulas, L. (2012)The smart power grid harnesses information and communication technologies to enhance reliability and enforce sensible use of energy through effective management of demand load. We envision a scenario with real-time ...