Strong and efficient filtering algorithms for scheduling constraints

针对调度约束的强大且高效的过滤算法

• 批准号: RGPIN-2016-05953
• 负责人: Quimper, ClaudeGuy
• 金额: $ 2.26万
• 依托单位: Université Laval
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=684083
• 关键词: Strong; efficient; filtering; algorithms; scheduling

Scheduling is the process of determining in what order a collection of operations, tasks, or activities should be executed so that the resources required for their executions are not overloaded. The tasks are generally subject to a variety of constraints and the problem comes with an optimization criteria. Scheduling problems are generally NP-Hard and require special techniques to be efficiently solved. Constraint Programming (CP) is a technique issued from artificial intelligence that proved itself very efficient to solve scheduling problems.******Despite recent advances, industrial problems remain hard to solve. Due to long computation times, solvers are halted before the optimal solution is found and therefore return sub-optimal schedules that can cause delays in airports or idle times on an assembly line. These inconveniences would be avoided if faster solvers were developed.******The success of constraint programming for solving scheduling problems comes from its filtering algorithms that reason over the scheduling constraints to prune the search space. These algorithms apply several filtering rules based on a relaxation of the scheduling problem. If the relaxed version of the scheduling problem forbids a task to start at a given time, the solver can safely discard these solutions and spend time exploring another part of the search space. By improving the relaxation used by the filtering rules, it is possible to filter larger portions of the search space and therefore to speed up the solving process.******The long-term objective of this program is to increase the speed of constraint-based schedulers to find large and complex optimal schedules in a reasonable time. This is achieved by fulfilling 3 sub-objectives.***1) Designing filtering algorithms based on stronger relaxations that achieve more filtering than existing ones;***2) Designing filtering algorithms based on relaxations that are aware of the objective criterion;***3) Designing faster filtering algorithms.******We propose a research program that will fully train 2 new Ph.D. students, 3 new master students, and allow one actual Ph.D. student to complete his thesis. Moreover, this program offers 3 internships for undergrad students.******One master and one doctoral student will develop stronger relaxations that will offer a better pruning of the search space. One new Ph.D. and one finishing Ph.D. student will work on filtering rules that are adapted to the objective criterion. Finally, two master students will work on faster algorithms that enforce existing filtering rules.**

调度是确定应以什么顺序执行操作、任务或活动集合的过程，以便执行时所需的资源不会过载。这些任务通常受到各种约束，并且问题带有优化标准。调度问题通常是NP-Hard问题，需要特殊的技术才能有效解决。约束规划 (CP) 是一种源自人工智能的技术，事实证明它可以非常有效地解决调度问题。******尽管最近取得了进展，但工业问题仍然难以解决。由于计算时间较长，求解器在找到最佳解决方案之前就会停止，因此返回次优计划，这可能会导致机场延误或装配线空闲时间。如果开发出更快的求解器，这些不便就可以避免。******约束规划解决调度问题的成功来自于它的过滤算法，该算法对调度约束进行推理以修剪搜索空间。这些算法基于调度问题的松弛应用多种过滤规则。如果调度问题的宽松版本禁止任务在给定时间启动，则求解器可以安全地放弃这些解决方案，并花时间探索搜索空间的另一部分。通过改进过滤规则使用的松弛，可以过滤搜索空间的较大部分，从而加快求解过程。******该程序的长期目标是提高基于约束的调度程序的速度，以在合理的时间内找到大型且复杂的最佳调度。这是通过实现 3 个子目标来实现的。***1) 设计基于更强松弛的过滤算法，实现比现有算法更多的过滤；***2) 设计基于了解客观标准的松弛的过滤算法；***3) 设计更快的过滤算法。******我们提出了一个研究计划，将全面培训 2 名新的博士生。学生，3名新硕士生，并允许1名实际博士生。学生完成他的论文。此外，该项目还为本科生提供 3 个实习机会。****** 一名硕士生和一名博士生将开发出更强的松弛，从而更好地修剪搜索空间。一位新博士。和一名正在完成博士学位的人。学生将研究适合客观标准的过滤规则。最后，两名硕士生将研究执行现有过滤规则的更快算法。**