Modern Mathematical Programming Approaches to Obtain Deeper Insights into Machine Scheduling

本研究的目的是研究困难的（即NP难）机器调度问题，使用数学规划方法。本研究将集中于以下四类排序问题：（1）具有优先限制的排序问题，（2）具有不完全信息的排序问题，（3）并行作业的排序问题，以及（4）车间环境中的排序问题。数学规划的理论将被用来作为一种工具，以建立最佳时间表的成本下限，发展最佳和接近最佳时间表的结构的洞察力，并帮助设计有效的（即多项式时间）算法，产生的时间表，保证合理地接近最佳。在这个过程中，将开发新的数学规划公式，这些问题。 这项研究的结果将在一系列的书的章节，并在一个新的课程，在调度设计的博士生在计算机科学和操作research.The研究的主要目标是获得一个更好的理论理解上述四类调度问题，无论是结构和算法。成功实现这些目标有一些预期的附带好处。任何新的结构或算法的想法，以及在这项研究中开发的任何新的数学规划公式可能会导致相关的，但更复杂的，实际的调度问题更好的算法。特别是，良好的下限是至关重要的算法方案，如切割平面，分支定界，分支和切割方法的性能。此外，在这项工作中开创的任何新的数学证明技术可能更普遍地有用，用于推进各种其他组合优化问题的理论。

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.