Greedy and Dynamic Programming Algorithms for Scheduling Deadline-Sensitive Parallel Tasks.
Patrick Loiseau, Xiaohu Wu · arXiv (Cornell University) · 2015
Due to the ubiquitous batch data processing in cloud computing, the fundamental model of scheduling malleable batch tasks and its extensions have received significant attention recently. In this model, a set of n tasks is to be scheduled 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 the machines allocated to a task can vary over time and its workload will not change accordingly. In this paper, the two core results of this paper are to quantitatively characterize a sufficient and necessary condition such that a set of malleable batch tasks with deadlines can be feasibly scheduled on C machines, and to propose a polynomial time algorithm to produce such a feasible schedule. The core results provide a conceptual tool and an optimal scheduling algorithm to enable proposing new analysis and design of algorithms or improving existing algorithms for extensive scheduling objectives.