CAREER: New Algorithmic Foundations for Online Scheduling

随着大量低成本计算资源变得越来越可用，利用它们的力量在现代科学和工程中至关重要。一个特别的问题涉及到调度：什么是为任务分配资源(例如计算周期)以确保良好性能的最有效方法？当事先对任务知之甚少或一无所知时，调度问题尤其严重，包括任务可能何时到达以及它们可能需要多少计算时间；在这种情况下，需要动态分配资源。在过去的二十年里，解决这些所谓的在线调度问题的方法已经出现了令人兴奋的进步，但该领域仍然在努力解决现代计算集群中发现的日益具有挑战性的调度环境。该项目旨在开发新的方法，借助于广泛使用的优化技术来系统地设计和分析在线调度算法，从而潜在地解决在线调度中的一些关键的开放问题。研究结果可能会提供另一种方法，在广泛的背景下教育学生如何安排日程，这将对计算机科学课程产生重大影响。该项目还将通过研讨会、编写教程和开发新的课程材料来指导学生和传播研究成果。在更技术性的层面上，这个项目打算调查在线调度技术对各种问题的有效性。该项目的第一个目标是开发新的梯度下降方法来设计和分析在线调度。第二个目标是使用装箱来研究基本的接纳控制问题，并在允许抢占的情况下开发新的算法工具。要研究的第三个研究问题涉及针对低维调度环境的细粒度调度算法的开发。令人惊讶的是，尽管最近取得了一些进展，但许多现有的算法甚至无法在低维情况下与最简单的贪婪算法相匹配，这在实践中很常见。第四个研究目标是在工作负载接近系统极限时改进在线算法的行为，这与基本分析模型的基本问题有关。最后一个目标是探索具有相互依赖关系的作业调度的新模型，通过利用大规模调度环境来绕过传统模型中常见的难以处理的结果。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.