带广义紧前约束的资源受限项目计划问题求解

1、带广义紧前约束的资源受限工程方案问题求解论文导读：为图中的环状结构。带广义紧前约束资源受限工程方案问题因其自身的存在的普遍性，以及其简化问题存在的普遍性而受到研究者的关注，本文综合介绍了RCPSP-GPR问题的约束条件、数学模型、网络拓扑和时间约束条件、问题求解的相关定义、定理、预处理过程、问题求解算法，提出了该问题的蚁群优化算法,并提供了实验结果。关键词：广义紧前约束,资源受限,环状结构,蚁群禁忌优化算法1 引言工程进度方案的安排受到的约束往往难以用简单的工序之间的紧前逻辑约束关系来表达。如强制时限的问题，某工序必须于某天开工，某几个工序必须同时完工等等，该类工序之间的逻辑约束称为广义紧前约

2、束。同时工程可获得的资源是有限的，带广义紧前约束的资源受限工程方案问题简称RCPSP-GPR问题的目标即在遵守工序间的广义紧前约束和资源约束的前提下，求得工程工期最小的方案。带广义紧前约束的资源受限工程方案问题是许多组合优化问题的推广问题，许多组合优化问题如下料问题、人员指派问题、机器调度问题、开放车间调度问题等等都是其特例，研究该问题具有较高的理论意义和实践意义 【1】 。2 带广义紧前约束的资源受限工程方案问题建模 2.1 定义一个工程由 +2个工序组成，0， 为两个虚工序，分别表示工程的开工和完工， 为工程第 种资源的可供给量，假定在整个工程方案进行期间为常数， 为工序 进行过程中所需的

3、第 种可更新资源的需要量， 为工序 的工期， / 为工序 的开工/完工时间，那么 表示工程的一个方案。 / 为工序 的最早开工/完工时间， / 为工序 的最迟开工/完工时间。 为工序i和j之间的最小/最大开工时间间隔，又记为 ， 为以有向图表示的活开工序网络，该活开工序网络表示一个工程， 为网络图的弧权重，又记为 。 为时刻t正在进行的工序集合， 为时刻t所需的资源 的量， 为工序i的直接前驱集合， 为工序i的直接后继集合。为有向图的距离矩阵， 表示节点i与节点j之间的最长路径距离， 为完工/未完工工序集合。 为图中的环状结构。 / 为满足 / 排序条件的工序j的直接前驱的集合。 湖北省建设厅

4、建设科技工程资助, 工程编号: K200566 罗时朋: 1978，女，湖北公安人，博士，讲师，研究方向：工程管理，武汉理工大学土木工程与建筑学院 2.2广义紧前约束广义紧前关系又称为最大最小时间间隔、时间窗等，该关系能统一地表示为工序间开工-开工关系满足 ( 为最小开工延迟时间， 为最大开工延迟时间)，即两个工序的开工时间间隔为 之间的一个值。广义的紧前关系可以表达一些无法用普通的紧前关系来表达的工程方案约束 【2】 ，如：任意两个工序之间完工-开工、开工-开工、开工-完工、完工-完工的最大最小时间间隔约束关系，几个工序必须在同一时间开工或完工，几个工序必须接二连三地连续完成，中间不能有延误

5、，某个工序的开工或完工日期必须在某些固定的日期，某个工序的截止完工日期，某个工序所需要的资源量随时间变化，将该工序分解为资源需求量为常量的几个工序，这些工序的开工完工是连续的，中间没有间断等。与单代号网络图类似，构造一个有向图：结点0，1，.，n+1分别对应工程工序0，1，.，n+1。带广义紧前约束的工程网络图用带权的箭线表示工序与工序之间的最大最小时间间隔。对工序i和j之间时间间隔 ，在有向图上引入弧权重为 ，工序i和j之间的最大延迟时间 ，在有向图上引入反向弧权重为- 。由此，工程工程活开工序网络图可以表示为一个带权有向图，一般带有环状结构。结点集V = 0,1, ,n+1，弧集合E，权重

6、 ， 。2.3带广义紧前约束的资源受限工程方案问题的数学模型MinimizeS.t. 1 2 3 当一个方案满足第一个约束条件时，该方案为资源上可行方案。免费论文。广义紧前约束为第二个约束，满足该约束条件的点为时间上可行方案，如果一个方案既为资源上可行方案，又为时间上可行方案，那么该调度为一个可行的方案。问题的目标是寻找 最短的可行方案。3带广义紧前约束的资源受限工程方案问题分析3.1 相关定义有向图中依次相互连通的不同的节点 组成有向图中的一条有向路径，如果该路径起始节点与终止节点为同一节点，那么该路径构成了一个有向环 【3】 。 从节点0到网络图中的任意一个节点i至少存在一条非负长度的路径

7、，从网络图中的任一节点i到n1节点至少存在一条长度不小于pi的路径。免费论文。否那么，网络图中应对应添加弧或弧，对应权重为0或pi。图中各条路径的长度为其各组成弧的权重的和，构成环的各条弧的权重和为环的长度。 如果网络图中有一条节点i到工序j的路径，那么称工序j为工序i的广义后继，工序i为工序j的广义前驱， 和 分别为工序i的广义前驱集合和广义后继集合。如果存在某个工序节点 ，而且集合 的基数大于1，那么称子网络 为环状结构。即环状结构为由不止一个节点组成的强连接结构 【2】 。3.2时间约束分析当不考虑工程的资源约束时，由该方案问题的时间约束可以求出工程各工序的最早开工时间，由各工序满足时间

8、约束条件的最早开工时间组成的向量为工程的最早开工时间可行方案。ESS的求解方法可以由图的最长路径算法如Floyd-Warshall算法求出，算法如下 【2】 ：1取矩阵 ，其中 4 5 2由公式 6 计算距离矩阵 ，那么矩阵D中的元素 表示网络有向图中的工序i与工序j之间的最长路径距离。3取矩阵的第一列向量即为ESS。4假设矩阵中有某个 为正，那么说明图中有长度为正的环存在，该网络没有可行解。3.3 网络拓扑分析如果存在工序节点 ， 当且仅当满足(1) 7或(2) and 8时，称 满足 的排序条件 【3】 。免费论文。 对网络节点 ，定义： 9 为工序节点i所属的强连接局部 【3】 。如果存

9、在工序节点 ， 当且仅当满足 (1) 10或(2) ，并且存在某两节点 有 11或(3) 存在某节点 ，有 并且 ，即传递性 12称工序 满足 的排序条件。 关系的含义是将环状结构看成一个紧缩的节点参与整个网络所有节点的 排序。定义 集合为满足 排序条件的工序i的直接前驱的集合，即节点集合 13 定义 集合为满足 排序条件的工序i的前驱的集合，即节点集合 14 如果某个工序链 满足(1) 如果工序链中的两个工序满足 ，那么这两个工序在工序链中的位置满足 (即 )(2) 对每个环状结构，环状结构中的所有工序在工序链 中连续排列，即如果 ，有 ，那么必有 ,那么称工序链 为紧前-环状结构-相容工序

10、链 【4】 。4带广义紧前约束的资源受限工程方案问题求解4.1 问题求解相关定理网络中所有的环都必须是非正长度的，否那么，该网络方案是一个没有可行解的网络，是无效的 【3】 。确定带广义紧前约束的资源约束工程方案问题是否有可行解是NP-C问题 【4】 。确定该工程方案问题中的环状结构是否存在可行解是NP-Ce问题 【3】 。当且仅当RCPSP-GPR问题的每个环状结构都有可行解时，问题才存在可行解 【5】 。4.2 问题预处理对某个方案 ，如果有 ，那么称F为一个禁止集，此时产生了资源冲突。在网络中存在两个工序 ， ，而且 或 ，那么其可行方案必有 【4】 。问题的预处理步骤有：1利用定理5处

11、理2元禁止集中的资源冲突问题，在有向图中添加相应的带权弧；2利用有向图的连通性算法和定义4确定网络中的环状结构；3利用Floyd-Warshall算法求解网络的最早开工方案(不考虑资源约束)；4对每个工序 确定其 集合(考虑环状结构方案时需要此步骤)。4.3 利用改良蚁群优化方法对问题求解蚁群优化方法是解决复杂组合优化问题的一种多Agent方法。其总体思想是应用蚂蚁算法寻找一个好的工序链，形成该问题的紧前-环状结构-可行解，分析工程网络中的环状结构，在蚂蚁构造解的过程中，将环状结构中的元素连续地进行方案，在蚂蚁构造解时如果遇到不可行的状态，采用罚函数法计算方案的工期长度。同时采用与RCPSP-

12、GPR问题结构相适应的禁忌邻域搜索算子对蚂蚁找到的解进行优化，同一代的蚂蚁采用不同的启发式信息引导其搜索，使得蚁群搜索的解更多样化，防止陷入早熟或停滞状态，采用直接评估与累积评估相结合的激素引导蚁群的搜索，更充分地利用蚂蚁的搜索经验，提高蚁群算法的性能。为使蚂蚁生成的解为紧前-环状结构-相容解，蚂蚁根据其决策策略在如下公式定义的合法工序集合 中选择新的工序参加目前的不完整工序链中，合法工序集合 的定义为如下公式： 15 由于资源约束的影响，当蚂蚁从合法工序集合 中选择工序 ，并确定其最早可行的开工时间满足 ，而且 在执行期间满足工程的资源约束，工序 的最早可行开工时间 计算公式为： 16 如果

13、出现工序 的最早可行开工时间 ，那么该开工时间是不可行的，忽略生成解中的不可行开工时间 ，采用罚函数方法计算蚂蚁解的路径长度，计算公式为： 17 为目前蚁群寻找到的最优解的工程工期长度。 激素信息的大小决定蚂蚁的搜索经验与问题相关的启发式信息在概率决策中的相对重要性，算法在第一代蚂蚁中设定其激素信息值为0.9。蚁群的启发式信息 由问题的启发式优先规那么信息决定，蚁群选择三类启发式优先规那么规那么，分别是最迟开工时间(LST)，最大总后继工序数(MTS)，资源调度方法(RSM)。 18 19 20 即满足 关系的工序集合中 工序的总数目，即有最多后继的工序优先。 21 22 即在合法候选工序集中

14、先开工该工序引起其他合法工序开工延误时间最短的工序优先。蚂蚁使用的选择策略采用伪随机-比例选择策略，其计算公式如下： 23 是之间均匀分布的随机数，当 越大时，蚂蚁进行随机选择的概率就越小。当 时，蚂蚁根据如下公式在合法工序集合 各元素中计算出的转移概率进行选择。 24 在每代蚂蚁完成了搜索后，为了减少先前的激素信息对蚁群将来的搜索的影响，防止蚁群搜索的过早收敛，对蚁群系统的激素矩阵参加了一种蒸发机制，新一代蚂蚁的激素矩阵为： 25 其中 为激素蒸发的速度为了引导蚁群的搜索偏向质量高的解的区域，每代蚂蚁采用的全局最优解来更新蚁群的激素矩阵，激素更新公式如下： / 为全局最优解。26 4.4禁忌

15、搜索算子采用平移算子，回移算子，以及修补工序链方法对每代蚂蚁中的每一只蚂蚁生成的解进行禁忌搜索，用搜索到的优化解代替当前解，提高蚂蚁算法的效率。对蚂蚁搜索到的初始解的工序链 中的某个工序对 采用以下邻域操作算子得到工序链 ，解译工序链 对应的工程方案解。如果 ，采用平移算子，否那么采用回移算子，首先交换当前工序链 中工序 的位置，然后修补该工序链以形成新的紧前-环状结构-可行工序链。平移算子操作如图1所示： 图1 平移算子操作示意图平移算子将工序i移动到工序j之后，如果 ， 将被一起放置在 的最后一个元素之后，将所有满足 而且 的元素 置于 之后。回移算子操作如图2所示： 图2 回移算子操作示

16、意图回移算子将满足条件 而且 的第一个工序h移动到工序i之前，如果 ， 将被一起放置在 的第一个元素之前，因为工序h是工序链 中工序i之后第一个满足条件 的工序，所以对所有的 的工序l仍有 而且 ，得到的新工序链为紧前-环状结构-可行工序链。选取 为禁忌对象，禁忌表长度选择为4，邻域操作对每个蚂蚁寻找到的方案生成新方案数不超过20个。5算法实验结果算法选择的参数为：每代蚂蚁为5只， ，算法生成的总的方案数目为5000个(包括由蚂蚁形成的方案和由禁忌搜索方法搜索的方案)，算法参数，蒸发速率 ，每代蚂蚁中前两只使用LST规那么产生的启发式信息，第三只和第四只蚂蚁使用RSM规那么，最后一只蚂蚁使用M

17、TS规那么。rcpspmax.html 中工序数为50的90个测试工程进行计算的结果如下表1：表1 算法实验结果Tab.1 the result ofalgorithm 测试用例 实验结果 测试用例 实验结果 测试用例 实验结果 测试用例 实验结果 测试用例 实验结果 UBO50-01 inf UBO50-19 157 UBO50-37 265 UBO50-55 191 UBO50-73 169 UBO50-02 inf UBO50-20 144 UBO50-38 inf UBO50-56 162 UBO50-74 inf UBO50-03 216 UBO50-21 111 UBO50-39

18、inf UBO50-57 132 UBO50-75 226 UBO50-04 260 UBO50-22 124 UBO50-40 215 UBO50-58 184 UBO50-76 166 UBO50-05 inf UBO50-23 160 UBO50-41 151 UBO50-59 199 UBO50-77 260 UBO50-06 232 UBO50-24 272 UBO50-42 155 UBO50-60 129 UBO50-78 219 UBO50-07 inf UBO50-25 108 UBO50-43 104 UBO50-61 310 UBO50-79 inf UBO50-08 i

19、nf UBO50-26 129 UBO50-44 190 UBO50-62 240 UBO50-80 299 UBO50-09 222 UBO50-27 87 UBO50-45 191 UBO50-63 249 UBO50-81 274 UBO50-10 206 UBO50-28 181 UBO50-46 227 UBO50-64 357 UBO50-82 149 UBO50-11 145 UBO50-29 263 UBO50-47 192 UBO50-65 222 UBO50-83 139 UBO50-12 115 UBO50-30 287 UBO50-48 inf UBO50-66 inf

20、 UBO50-84 169 UBO50-13 130 UBO50-31 337 UBO50-49 167 UBO50-67 251 UBO50-85 191 UBO50-14 161 UBO50-32 inf UBO50-50 210 UBO50-68 292 UBO50-86 147 UBO50-15 109 UBO50-33 inf UBO50-51 124 UBO50-69 inf UBO50-87 269 UBO50-16 128 UBO50-34 239 UBO50-52 138 UBO50-70 inf UBO50-88 245 UBO50-17 120 UBO50-35 inf

21、UBO50-53 123 UBO50-71 165 UBO50-89 218 UBO50-18 163 UBO50-36 226 UBO50-54 91 UBO50-72 inf UBO50-90 246 应用改良蚁群优化算法计算每个工程的平均耗时为37秒,与测试结果文件benchmarks_ubo50.txt比照可知：文献【4】中多种算法共找到其中50个工程的最优解, 改良蚁群优化算法找到了40个问题的最优解斜体标注，而且有10个工程的计算工期优于结果文件中提供的计算最优工期UB值斜体标注，计算出的工期与下界LBW和LBD中较大值LB之间的平均偏差百分比LB为8.3%,优于文献 中提出的多种优化算法的结果。由于测试用例系数的随机性，可能存在无解的工程方案，inf表示该问题未求解到可行解。6 总结带广义紧前约束资源受限工程方案问题因其自身的存在的普遍性，以及其简化问题存在的普遍性而受到研究者的关注，本文综合介绍了RCPSP-GPR问题的约束条件、数学模型、网络拓扑和时间约束条件、问题求解的相关定义、定理、预处理过程、问题求解算法，提出了该问题的蚁群优化算法,并提供了实验结果。参考文献【1】 Peter Brucker. ComplexScheduling Problems. Technical Report, University Osnabruck,