UC Merced

This dissertation focuses on the design and analysis of approximation and online algorithms for scheduling problems arising in large datacenters and cloud computing environments.The recent advancement of science and engineering crucially relies on computing platforms processing large data sets, and modern datacenters provide such platforms.

We address four different scheduling settings motivated by modern computing environments; speed scaling setting, co-flow setting, batch scheduling setting, and unrelated machines setting.

Speed scaling setting: Modern processors typically allow dynamic speed-scaling offering an effective trade-off between high throughput and energy efficiency. In a classical model, a processor/machine runs at speed s when consuming power s^α where α>1 is a constant. We study the problem of completing all jobs before their deadlines non-preemptively with the minimum energy on parallel machines with dynamic speed-scaling capabilities. This problem is crucial in datacenters that are estimated to use energy as much as a city.

Co-flow setting: Coflow has recently been introduced to abstract communication patterns that are widely observed in the cloud and massively parallel computing frameworks. Coflow consists of several flows that each represent data communication from one machine to another. A coflow is completed when all of its flows are completed. We consider coflow for the objective of maximizing partial throughput. This objective seeks to measure the progress made for partially completed coflows before their deadlines.

Batch scheduling setting: This setting is used to model client-server systems like multiuser operating systems, web servers, etc. In this setting, there is a server that stores different pages of information and receives requests from clients over time for specific pages. The server can transmit at most one page at each time to satisfy a batch of requests for that page, up to a certain capacity. We study the maximum flow time minimization problem in this setting, which is a capacitated version of broadcast scheduling.

Unrelated machines setting: The unrelated machines setting is one of the most general and versatile scheduling models. It captures the heterogeneity of jobs and machines, which is widely observed in cloud computing environments and server clusters. We consider the classic scheduling problem of minimizing total weighted completion time on unrelated parallel machines. Machines are unrelated in the sense that each job can have different processing times on different machines.

We use the standard worst-case analysis to measure the quality of the algorithms we develop for the underlying scheduling problems. Approximation ratio and competitive ratio are two popular quantities that measure the worst-case performance of offline and online algorithms, respectively. An offline algorithm is said to be α-approximation if its objective is within a multiplicative factor α of the optimal scheduler's objective for any input instance. Roughly speaking, an algorithm with a small approximation ratio performs well compared to the optimal scheduler, even on a worst-case input. To evaluate the worst-case performance of an online algorithm, we compute the worst ratio between the objective value of the online algorithm and the optimal offline scheduler's objective for any input instance.