Algorithms for Scheduling Malleable Cloud Tasks
Preprint
Abstract
Due to the ubiquity of batch data processing in cloud computing, the related problem of scheduling malleable batch tasks and its extensions have received significant attention recently. In this paper, we consider a fundamental model where a set of n tasks is to be processed on C identical machines and each task is specified by a value, a workload, a deadline and a parallelism bound. Within the parallelism bound, the number of machines assigned to a task can vary over time without affecting its workload. For this model, we obtain two core results: a sufficient and necessary condition such that a set of tasks can be finished by their deadlines on C machines, and an algorithm to produce such a schedule. These core results provide a conceptual tool and an optimal scheduling algorithm that enable proposing new algorithmic analysis and design and improving existing algorithms under various objectives.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Efficient Approximation Algorithms for the Bounded Flexible Scheduling Problem in CloudsIEEE Transactions on Parallel and Distributed Systems, 2017
- Toward Scalable Systems for Big Data Analytics: A Technology TutorialIEEE Access, 2014
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobsAnnals of Operations Research, 1990
- A Functional Equation and its Application to Resource Allocation and Sequencing ProblemsManagement Science, 1969