为紧前-环状结构-相容工序链 [4] 。
4带广义紧前约束的资源受限项目计划问题求解4.1 问题求解相关定理[定理1]网络中所有的环都必须是非正长度的，否则，该网络计划是一个没有可行解的网络，是无效的 [3] 。
[定理 2]确定带广义紧前约束的资源约束项目计划问题是否有可行解是NP-C问题 [4] 。
[推论 3]确定该项目计划问题中的环状结构是否存在可行解是NP-Ce问题 [3] 。
[定理 4]当且仅当RCPSP-GPR问题的每个环状结构都有可行解时，问题才存在可行解 [5] 。
4.2 问题预处理[定义 11]对某个计划  ，如果有  ，则称F为一个禁止集，此时产生了资源冲突。
[定理 5]在网络中存在两个工序  ，  ，而且  或  ，则其可行计划必有  [4] 。
问题的预处理步骤有：
（1）利用定理5处理2元禁止集中的资源冲突问题，在有向图中添加相应的带权弧；
（2）利用有向图的连通性算法和定义4确定网络中的环状结构；
（3）利用Floyd-Warshall算法求解网络的最早开工计划(不考虑资源约束)；
（4）对每个工序  确定其  集合(考虑环状结构计划时需要此步骤)。
4.3 利用改进蚁群优化方法对问题求解蚁群优化方法是解决复杂组合优化问题的一种多Agent方法。其总体思想是应用蚂蚁算法寻找一个好的工序链，形成该问题的紧前-环状结构-可行解，分析项目网络中的环状结构，在蚂蚁构造解的过程中，将环状结构中的元素连续地进行计划，在蚂蚁构造解时如果遇到不可行的状态，采用罚函数法计算计划的工期长度。同时采用与RCPSP-GPR问题结构相适应的禁忌邻域搜索算子对蚂蚁找到的解进行优化，同一代的蚂蚁采用不同的启发式信息引导其搜索，使得蚁群搜索的解更多样化，避免陷入早熟或停滞状态，采用直接评估与累积评估相结合的激素引导蚁群的搜索，更充分地利用蚂蚁的搜索经验，提高蚁群算法的性能。
为使蚂蚁生成的解为紧前-环状结构-相容解，蚂蚁根据其决策策略在如下公式定义的合法工序集合 中选择新的工序加入目前的不完整工序链中，合法工序集合 的定义为如下公式：
 （15）
由于资源约束的影响，当蚂蚁从合法工序集合 中选择工序 ，并确定其最早可行的开工时间满足 ，而且 在执行期间满足项目的资源约束，工序 的最早可行开工时间 计算公式为：
 （16）
如果出现工序 的最早可行开工时间 ，则该开工时间是不可行的，忽略生成解中的不可行开工时间 ，采用罚函数方法计算蚂蚁解的路径长度，计算公式为：
 （17）
 为目前蚁群寻找到的最优解的项目工期长度。
激素信息的大小决定蚂蚁的搜索经验与问题相关的启发式信息在概率决策中的相对重要性，算法在第一代蚂蚁中设定其激素信息值为0.9。
蚁群的启发式信息 由问题的启发式优先规则信息决定，蚁群选择三类启发式优先规则规则，分别是最迟开工时间(LST)，最大总后继工序数(MTS)，资源调度方法(RSM)。  （18）
 （19）
 （20）
 即满足 关系的工序集合中 工序的总数目，即有最多后继的工序优先。
 4/6 首页 上一页 2 3 4 5 6 下一页 尾页 |
