CAREER: Approximate Scheduling Algorithms via Mathematical Relaxations

在一组机器上调度一组可能相关的任务的问题出现在许多现代应用程序领域。然而，尽管进行了深入的研究，对许多基本调度问题的一般认识仍远不能令人满意。本研究将加强对数学松弛技术的理解，以解决在许多情况下出现的调度问题。项目的成功完成将为基本调度问题提供改进的近似算法。该项目将为研究生和本科生提供研究和教育机会，并促进不同院校之间的跨领域合作。该项目的主要目标是利用数学规划中的尖端技术来缩小对调度问题理解的差距。研究者打算探索的具体技术包括：(1)利用LP（线性规划）层次来近似相同机器上的优先约束调度问题；(2)探索时间索引LP松弛来解决具有加权和目标的调度问题；(3)使用背包覆盖不等式来捕获调度问题中自然产生的资源约束。该项目以三种数学规划技术为中心。(1) Levey和Rothvoss最近的突破性成果，基于自然时间索引LP松弛的sherli - adams层次提升，给出了一个（1 + epsilon）逼近算法，用于在恒定数量机器上调度优先级受限的单位大小作业的最大跨度最小化问题。研究者将继续这条研究路线，从不同的角度改进这些结果，并将其扩展到许多其他设置。如果工作有不同的大小呢？如何处理加权完成时间目标的问题？这些结果可以推广到更一般的机器模型吗？(2)考虑到时间概念在调度问题中的重要作用，时间索引LP松弛是调度问题的自然松弛。然而，对于许多问题，它们在推导改进算法方面的能力尚未得到充分利用。本研究将通过研究不相关机器上最小化加权完成时间的调度问题、有向无循环作业调度问题和协同流调度问题来促进对该技术的理解。(3)引入了背包覆盖不等式，增强了许多具有背包覆盖约束的问题的基本LP松弛性，并用于推导许多调度和其他类型问题的基于LP的算法。研究者的目标是进一步加深对相关调度问题的理解，包括开放车间调度的加权流时间最小化问题，具有一般成本函数的单机调度问题，以及容量批量问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The problem of scheduling a set of possibly dependent tasks over a collection of machines arises in many modern application domains. In spite of intensive study, however, the general understanding of many fundamental scheduling problems is still far from satisfactory. This research will enhance understanding of the mathematical relaxation techniques to solve scheduling problems that appear in many contexts. Successful completion of the project will yield improved approximation algorithms for fundamental scheduling problems. This project will provide research and educational opportunities to both graduate and undergraduate students, and foster cross-field collaborations between different institutions. The major goal of the project is to leverage cutting-edge techniques in mathematical programming to close the gaps in the understanding of scheduling problems. The specific techniques the investigator intends to explore include: (1) leveraging the LP (linear programming) hierarchy in approximating precedence-constrained scheduling problems on identical machines, (2) exploring time-indexed LP relaxations to solve scheduling problems with weighted-sum objectives, and (3) the use of knapsack covering inequalities in capturing resource constraints arising naturally in scheduling problems. The project is centered around three mathematical-programming techniques. (1) The recent breakthrough result of Levey and Rothvoss gave a (1 + epsilon)-approximation algorithm for the makespan minimization problem for scheduling precedence-constrained unit-size jobs on constant number of machines, based on the Sherali-Adams hierarchy lift of the natural time-indexed LP relaxation for the problem. The investigator will continue this line of research, by improving these results from various angles and extending them to many other settings. What if jobs have different sizes? How can the problem with the weighted completion-time objective be handled? Can the results be extended to more general machine models? (2) Time-indexed LP relaxations are natural ones for scheduling problems, given the important role the notion of time plays in the problems. However, for many problems, their power in deriving improved algorithms has not been fully exploited. This investigation will advance the understanding of the technique by studying the scheduling problem on unrelated machines to minimize weighted completion time, directed-acyclic job scheduling and coflow scheduling problems. (3) The knapsack covering inequalities have been introduced to strengthen the basic LP relaxation for the many problems with knapsack covering constraints, and have been used to derive LP-based algorithms for many scheduling and other types of problems. The investigator aims to further advance the understanding of the technique in tackling relevant scheduling problems including weighted flow time minimization for open-shop scheduling, the single-machine scheduling problem with general cost functions, and the capacitated lot-sizing problem.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.