Scheduling using constraint programming

调度是将任务分配到时隙和资源的过程。资源不应该遇到超负荷的时间段，任务通常会受到最后期限的限制。许多额外的限制使这个问题变得难以解决。解算器是一种计算机程序，它将问题参数作为输入，探索问题的解空间，并产生解。 这一研究计划旨在设计更有效的求解器，能够在更短的时间内产生解。实现这一长期目标将对该行业产生许多不同的影响。在时间关键的环境中安排运营的行业将从这项研究中受益匪浅，因为他们将在较短的时间内获得更好的计划。 我们看到了三种有希望实现这一目标的方法。首先，我们希望改进目前在调度程序中使用的关键算法。一些算法的复杂性已经被认为是次优的，通过使用简单而有效的数据结构可以大大改进它们。 其次，我们希望探索更强的松弛和新的全球约束，这些都可以用在求解器中。松弛及其相关的全局约束限制了搜索的范围，并让求解器专注于最有希望的候选解决方案。 最后，我们提出了一种新的调度问题建模方法，可以减少计算时间。有了新的隐式模型，解算者将忽略解决方案的多个细节，而更专注于解决问题的困难部分。隐式模型导致了专门算法可以高效完成的部分解。

Scheduling is the process of allocating tasks to a time slot and a resource. Resources should not encounter overloaded periods and tasks are often subject to deadlines. Many additional constraints make the problem intractable. Solvers are computer programs that take the problem parameters as input, explore the solution space of the problem, and produce a solution. This research program aims at designing more efficient solvers that are able to produce solutions in a shorter period of time. Reaching this long-term goal will impact the industry in many different ways. Industries that schedule their operations in a time critical environment will greatly beneficiate from this research since they will obtain better schedules in a shorter period of time. We see three ways that are promising for reaching this goal. First, we want to improve key algorithms that are currently used in schedulers. Some algorithms, whose complexity has been identified as suboptimal, can be greatly improved by using simple and efficient data structures. Second, we want to explore stronger relaxations and new global constraints that can be used in a solver. Relaxations, and their associated global constraints, limit the scope of the search and let the solver focus on the most promising candidate solutions. Finally, we propose a new way of modeling scheduling problems that will improve the computation time. With new implicit models, solvers will ignore multiple details of a solution and rather focus on solving the hard part of a problem. An implicit model leads to a partial solution that specialized algorithms can efficiently complete.