CAREER: Approximate Scheduling Algorithms via Mathematical Relaxations

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

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.