Abstract
Scheduling jobs is a fundamental problem that arises in numerous forms and in various situations. In this talk, we introduce and study a general scheduling problem that we term the Packing Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates at which a scheduler can process jobs are subject to arbitrary packing constraints. We show that the PSP framework captures a variety of scheduling problems, including the classical problems of heterogeneous machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from multi-core computer architectures to data centers. More concretely, PSP models multidimensional resource and network bandwidth requirements arising in scheduling jobs on shared clusters. We design non-clairvoyant online algorithms for PSP and its special cases ? in this setting, the scheduler is unaware of the sizes of jobs and these jobs arrive in an adversarial fashion. For several special cases of PSP, we show constant competitive algorithms for minimizing the standard QoS metrics of total weighted completion time and total delay. Surprisingly, we achieve these results by applying the well-known Proportional Fairness algorithm from economics literature to allocate resources each time instant. Proportional Fairness has been extensively studied in the context of maximizing fairness in resource allocation; however, we present the first unifying analyses in the context of optimizing job latency in scheduling contexts. Our results yield the first constant competitive algorithms for the completion times and delay metrics for several classical non-clairvoyant scheduling problems. They showcase the advantage of viewing complex scheduling problems as sequential resource allocation problems, and applying ideas from economics to both perform these allocations and analyze them. Joint work with Sungjin Im (UC Merced) and Janardhan Kulkarni (Microsoft Research). Appeared in STOC 2014 and FOCS 2015.