Strong and efficient filtering algorithms for scheduling constraints

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

基本信息

  • 批准号:
    RGPIN-2016-05953
  • 负责人:
  • 金额:
    $ 2.26万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2018
  • 资助国家:
    加拿大
  • 起止时间:
    2018-01-01 至 2019-12-31
  • 项目状态:
    已结题

项目摘要

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困难的,需要特殊的技术才能有效地解决。约束规划(CP)是由人工智能提出的一种技术,它被证明是解决调度问题的有效方法。******尽管最近取得了进步,但工业问题仍然难以解决。由于计算时间长,求解器在找到最优解之前就停止了,因此返回的是次优调度,这可能导致机场延误或装配线上的空闲时间。如果开发出更快的求解器,这些不便就可以避免。******约束规划解决调度问题的成功来自于它的过滤算法,该算法通过调度约束来精简搜索空间。这些算法应用了基于调度问题松弛的几个过滤规则。如果调度问题的宽松版本禁止任务在给定时间开始,求解器可以安全地放弃这些解决方案,并花时间探索搜索空间的另一部分。通过改进过滤规则使用的松弛性,可以过滤更大的搜索空间,从而加快求解过程。******该计划的长期目标是提高基于约束的调度程序的速度,以便在合理的时间内找到大型和复杂的最佳调度。这是通过完成3个子目标来实现的。***1)设计基于强松弛的过滤算法,实现比现有算法更多的过滤;***2)基于感知客观准则的松弛设计滤波算法;***3)设计更快的滤波算法。******我们提出一个研究计划,将充分培养2名新的博士研究生,3名新的硕士研究生,并允许一名真正的博士研究生完成他的论文。此外,该项目还为本科生提供3个实习机会。******一名硕士和一名博士生将开发更强的松弛,这将提供更好的搜索空间修剪。一名新博士和一名即将毕业的博士生将研究适应客观标准的过滤规则。最后,两位硕士生将研究执行现有过滤规则的更快算法

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Quimper, ClaudeGuy其他文献

Quimper, ClaudeGuy的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Quimper, ClaudeGuy', 18)}}的其他基金

Filtering Algorithms Based on Lagrangian Relaxation
基于拉格朗日松弛的滤波算法
  • 批准号:
    RGPIN-2022-05025
  • 财政年份:
    2022
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2021
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2020
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Amélioration des techniques de programmation par contraintes appliquées à l'ordonnancement de la production dans l'industrie agroalimentaire
农业食品工业生产中应用程序限制技术的改进
  • 批准号:
    519795-2017
  • 财政年份:
    2019
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Collaborative Research and Development Grants
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2019
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Amélioration des techniques de programmation par contraintes appliquées à l'ordonnancement de la production dans l'industrie agroalimentaire
农业食品工业生产中应用程序限制技术的改进
  • 批准号:
    519795-2017
  • 财政年份:
    2018
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Collaborative Research and Development Grants
Amélioration des techniques de programmation par contraintes appliquées à l'ordonnancement de la production dans l'industrie agroalimentaire
农业食品工业生产中应用程序限制技术的改进
  • 批准号:
    519795-2017
  • 财政年份:
    2017
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Collaborative Research and Development Grants
Planification des tournées de véhicules chez NSim Technologie
NSim Technologie 车辆锦标赛规划
  • 批准号:
    514090-2017
  • 财政年份:
    2017
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Engage Grants Program
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2017
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Génération automatique d'horaires des opérations de ménage et de mise en course d'une ligne de transformation agro-alimentaire
农业食品转型过程中的饲养和管理操作自动生成
  • 批准号:
    501072-2016
  • 财政年份:
    2016
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Engage Grants Program

相似国自然基金

固定参数可解算法在平面图问题的应用以及和整数线性规划的关系
  • 批准号:
    60973026
  • 批准年份:
    2009
  • 资助金额:
    32.0 万元
  • 项目类别:
    面上项目

相似海外基金

Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2021
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2020
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2019
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Faster, efficient artifact filtering from 3-dimensional focused ion beam datasets
从 3 维聚焦离子束数据集中更快、更高效地过滤伪影
  • 批准号:
    524945-2018
  • 财政年份:
    2018
  • 资助金额:
    $ 2.26万
  • 项目类别:
    University Undergraduate Student Research Awards
Spectral-spatial filtering for efficient multi-material decomposition in x-ray CT
用于 X 射线 CT 中高效多材料分解的谱空间滤波
  • 批准号:
    9751293
  • 财政年份:
    2018
  • 资助金额:
    $ 2.26万
  • 项目类别:
RUI: Efficient Adaptive Backward Stochastic Differential Equation Methods for Nonlinear Filtering Problems
RUI:解决非线性滤波问题的高效自适应后向随机微分方程方法
  • 批准号:
    1720222
  • 财政年份:
    2017
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Continuing Grant
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2017
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Strong and efficient filtering algorithms for scheduling constraints
针对调度约束的强大且高效的过滤算法
  • 批准号:
    RGPIN-2016-05953
  • 财政年份:
    2016
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Efficient particle filtering-based SLAM for mobile robots
用于移动机器人的基于粒子过滤的高效 SLAM
  • 批准号:
    401561-2010
  • 财政年份:
    2010
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Engage Grants Program
Efficient Algorithms for Multiple Object Filtering using Stochastic Geometry
使用随机几何进行多对象过滤的高效算法
  • 批准号:
    DP0989007
  • 财政年份:
    2009
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Projects
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了