Xiaohu WU - PhD Student
Date: - Location: Eurecom
Algorithms for Scheduling Deadline-Sensitive Malleable Tasks We consider fundamental problems in cloud computing of scheduling n parallel batch jobs on C identical machines. Each task is specified by a value, a workload, a deadline and a parallelism bound. In this paper, two common and closely related objectives for scheduling with deadlines are to be addressed: machine minimization (i.e., minimizing the number of machines needed to schedule a set of tasks) and social welfare maximization (i.e., maximizing the sum of values of tasks completed by their deadlines). The social welfare maximization problem has recently been considered by Jain et al. in ACM SPAA12 and Jain et al. proposed a greedy algorithm with an approximation ratio of (C-k)/C*(s-1)/s, where k and s are parameters specific to the set of tasks. Our core result is a new theory to give the first optimal scheduling algorithm so that $C$ machines can be optimally utilized by a set of batch tasks with deadlines. The proposed theory enables the derivation of three algorithmic results in obvious or non-obvious ways: (1) an exact algorithm for machine minimization problem, (2) the first dynamic programming algorithm for social welfare maximization in the case where the set of possible task deadlines is finite, and (3) an improved greedy algorithm for social welfare maximization that achieves an approximation ratio of (s-1)/s. Finally, we prove that (s-1)/s is the best approximation ratio that a general greedy algorithm can achieve
