CAREER: Approximate Scheduling Algorithms via Mathematical Relaxations

在许多现代应用领域中，在一组机器上调度一组可能相关的任务的问题出现了。然而，尽管人们对排序问题进行了深入的研究，但对许多基本排序问题的认识还远远不能令人满意。 这项研究将提高理解的数学松弛技术来解决调度问题，出现在许多情况下。 该项目的成功完成将产生改进的近似算法的基本调度问题。该项目将为研究生和本科生提供研究和教育机会，并促进不同机构之间的跨领域合作。该项目的主要目标是利用数学编程中的尖端技术来缩小对调度问题的理解方面的差距。具体的技术，研究人员打算探索包括：（1）利用LP（线性规划）层次近似的优先级约束的调度问题在相同的机器上，（2）探索时间索引LP松弛解决调度问题的加权和目标，和（3）使用背包覆盖不等式捕捉资源约束自然产生的调度问题。 该项目主要围绕三种编程技术展开。(1)Levey和Rothvoss最近的突破性结果给出了一个（1 + 1）-近似算法，用于求解具有优先级约束的单位工件在固定机器数上的最小完工时间调度问题，该算法基于问题的自然时间指标LP松弛的Sherali-Adams层次提升.研究人员将继续这一研究路线，从各个角度改进这些结果，并将其扩展到许多其他环境。如果工作有不同的大小怎么办？如何处理加权完成时间目标的问题？这些结果是否可以推广到更一般的机器模型？(2)考虑到时间概念在调度问题中的重要作用，时间索引LP松弛是调度问题的自然松弛。然而，对于许多问题，他们的权力，在推导出改进的算法还没有得到充分利用。这项调查将通过研究不相关机器上的调度问题，以最大限度地减少加权完工时间，有向无环作业调度和coflow调度问题，促进对该技术的理解。(3)背包覆盖不等式已被引入，以加强基本的LP松弛的背包覆盖约束的许多问题，并已被用来推导LP为基础的算法，许多调度和其他类型的问题。调查员的目的是进一步推进技术的理解，在解决相关的调度问题，包括加权流时间最小化的开放式车间调度，单机调度问题与一般成本函数，并capacitated lot-sizing problem.This award reflects 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.