Modern Mathematical Programming Approaches to Obtain Deeper Insights into Machine Scheduling

本研究的目的是研究困难（即NP-hard）机器调度问题，使用数学规划方法。本研究将重点研究以下四类调度问题：(1)有优先约束的调度问题，(2)不完全信息的调度问题，(3)并行作业调度问题，以及(4)车间环境下的调度问题。数学规划理论将被用作一种工具，用于建立最优调度成本的下限，开发最优和接近最优调度结构的洞察力，并帮助设计高效（即多项式时间）算法，以产生保证合理接近最优的调度。在这个过程中，这些问题的新的数学规划公式将被开发出来。这项研究的结果将在一系列的书籍章节中传播，并在为计算机科学和运筹学博士生设计的新课程中传播。本研究的主要目的是从结构和算法两方面对上述四类调度问题有更好的理论认识。成功实现这些目标会带来一些预期的附带好处。本研究中提出的任何新的结构或算法思想，以及任何新的数学规划公式，都可能为相关但更复杂的实际调度问题提供更好的启发式方法。特别是，良好的下界对于切割平面、分支定界和分支切割等算法方案的性能至关重要。此外，在这项工作中开创的任何新的数学证明技术可能更普遍地有用，用于推进各种其他组合优化问题的理论。

The objective of this research is to study the difficult (i.e. NP-hard) machine scheduling problems, using mathematical programming approaches. This study will focus on the following four classes of scheduling problems: (1) scheduling with precedence constraints, (2) scheduling with incomplete information, (3) scheduling parallel jobs, and (4) scheduling in shop environments. The theory of mathematical programming will be used as a tool to establish lower bounds on the cost of optimal schedules, to develop insight on the structure of optimal and near-optimal schedules, and to aid in the design of efficient (i.e. polynomial-time) algorithms that produce schedules that are guaranteed to be reasonably close to optimal. In the process, novel mathematical programming formulations for these problems will be developed. The results of this research will be disseminated in a series of book chapters, and in a new course in scheduling designed for doctoral students in computer science and operations research.The primary goal of this research is to gain a better theoretical understanding of the four aforementioned classes of scheduling problems, both structurally and algorithmically. Success in achieving these goals has some anticipated side benefits. Any new structural or algorithmic ideas, as well as any new mathematical programming formulations developed in this research may lead to better heuristics for related, but more complex, practical scheduling problems. In particular, good lower bounds are critical to the performance of algorithmic schemes such as cutting plane, branch-and-bound, and branch-and-cut methods. In addition, any new mathematical proof techniques pioneered in this work may be useful more generally, for advancing the theory of various other combinatorial optimization problems.