Cloud computing has become the main paradigm for computing, storage and many other applications. The design of appropriate scheduling and pricing schemes for computing resource is therefore of great importance for cloud providers to increase the quality of service or maximize their revenue.
Due to the ubiquity of batch data processing in cloud computing, we consider a fundamental model in which a set of batch tasks is to be scheduled on multiple 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 allocated to a task can vary over time without affecting its workload. For this model, we obtain two core results: a quantitative characterization of a sufficient and necessary condition such that a set of malleable batch tasks with deadlines can be scheduled on the multiple machines, and a polynomial-time algorithm to produce such a feasible schedule. These core results provide a conceptual tool and an optimal scheduling algorithm that enable proposing new analyses and designs of algorithms and improving existing algorithms for extensive scheduling objectives.
We also provide new results for monotonic moldable tasks, for which the total workload increases when parallelizing a job.
On the other hand, given the main pricing models such as the one in Amazon EC2, we propose an extended online learning framework for tenants to decide on which type of instance to purchase and utilize between on-demand, spot, and long-term instances (e.g., reserved instances or instances that an organization itself possesses), in order to minimize their cost.