约束传播

约束传播是约束规划成功应用的关键技术之一。针对累积调度问题可提出一种结合工作间优先关系和工作最早开始/最晚完成时间约束的约束传播算法，保证算法的理论依据。

简介约束规划(Constraint programming， CP) 是人工智能领域的研究方法， 适合求解具有多种约束的组合优化问题.约束传播是CP 的关键技术之一， 其基本思想是通过循环分析变量、值域和约束， 检验并删除不可能出现在可行解中的变量赋值， 从而约减变量值域.CP 在调度问题研究领域已经获得了很多成功应用.1989 年Carlier 等在分枝定界算法中使用约束传播技术，首次成功解决了1963 年Muth 等提出后让众多学者孜孜不倦努力求解20 多年的车间调度问题。从此， 约束传播技术引起了调度问题研究领域学者的广泛关注， 针对调度问题的约束传播算法的时间复杂性也不断获得改进。1

研究进展调度问题研究领域的约束传播方法可以分为时间约束传播和资源约束传播两类。时间约束传播根据工作间优先关系约束计算各工作的[最早开始时间， 最晚完成时间] 区间，约束传播算法可以基于时间约束网络采用最短路径算法实现。资源约束传播通过分析竞争同一资源的工作对资源需求量和资源供应量的关系， 对工作[最早开始时间， 最晚完成时间] 区间进行约减。资源约束传播方法根据资源特性进一步分为两类: 一类是分离调度问题，DSP 中资源可用量和工作在执行期间对资源的需求量均为约束传播， 较好的DSP 约束传播方法有Edge-nding， Input-or-output， Not-rst/not-last。另一类是累积调度问题(Cumulative schedulingproblem， CuSP) (CuSP 中资源可用量和工作在执行期间对资源的需求量均大于等于约束传播， 较好的CuSP 约束传播方法有Edge-nding， Energetic-reasoning。

两类资源约束传播技术相比， DSP 约束传播技术比CuSP 约束传播技术受到更早的关注和研究， 成果相对较多、较成熟。CuSP 约束传播更加困难， 起步晚， 成果较少。目前，主流CuSP 约束传播算法在进行约束传播时， 首先将工作间的优先关系简化为工作的最早开始时间， 最晚完成时间区间约束， 而在约束传播过程中不再考虑工作间的优先关系，这样的处理方法在工作可行时间区间较大时， 往往得不到较好的约束传播效果。Laborie针对这一缺陷， 基于优先关系图提出了改进的约束传播算法。

约束传播实验设计为了测试本文约束传播算法的时间效率和约减效果， 利用标准问题库PSPLIB中J32、J62 两组问题对算法进行测试。两组问题根据项目的网络复杂性系数NC (Networkcomplexity)、资源因数系数RF (Resource factor)、资源强度系数RS (Resource strength) 的不同组合随机生成。其中NC 反映项目网络图中各工作间优先关系约束的松紧， RF 反映工作对资源需要的耦合程度， RF = 1 代表每项工作需要全部种类的资源， RS 反映资源的限制强度.两组问题分别包含32 项和62 项工作， 需要4 种可更新资源(K = 4)。对参数NC、RF和RS 的48 种不同组合， 每种组合随机生成10 个问题实例.因此， 每组包含480 个问题实例.2

本词条内容贡献者为:

李晓林 - 教授 - 西南大学