CAREER: New Algorithmic Foundations for Online Scheduling

As massive low-cost computing resources become increasingly available, harnessing their power is crucial in modern science and engineering. One particular issue involves scheduling: what is the most effective way to assign resources, say computing cycles, to tasks in order to ensure good performance? The scheduling problem is especially acute when little to nothing is known in advance about the tasks, including when they might arrive and how much compute time they may need; in such cases, dynamic allocation of resources is required. Over the past two decades, exciting advances in approaches for addressing these so-called on-line scheduling problems have emerged, but the field is still struggling to address the increasingly challenging scheduling environments found in modern computing clusters. This project aims to develop new methods to design and analyze online scheduling algorithms systematically with the aid of widely used optimization techniques, and as a result to potentially resolve some key open questions in online scheduling. The research findings will likely provide an alternative method of educating students on scheduling in a broad context, which will have a significant impact on the computer science curriculum. This project will also involve mentoring students and disseminating the research outcomes through workshops, writing tutorials, and developing new course materials.

At a more technical level, this project intends to investigate the effectiveness of online scheduling techniques for a variety of problems. The project's first objective is to develop new gradient-descent methods to design and analyze online-scheduling. The second objective is to use bin-packing to study fundamental admission-control problems, and to develop new algorithmic tools when pre-emption is allowed. The third research problem to be studied involves the development of fine-grained scheduling algorithms for low-dimensional scheduling environments. Surprisingly, despite recent advances, many existing algorithms are no match even for the simplest greedy algorithms in the low-dimensional case, which is common in practice. The fourth research goal is to refine the behavior of the online algorithms as the workload approaches the system limit, which is related to fundamental questions regarding the underlying analysis models. The last goal is to explore new models for scheduling jobs with inter-dependencies by taking advantage of large-scale scheduling environments to circumvent the intractability results that are commonly found in the traditional models.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Award Number: 2535599
Principal Investigator: Sungjin Im
Funds Obligated: $190,473
State: CA