基于阈值超启发算法的建设资源平衡优化_马晓彤.pdf

LOW CARBON WORLD 2022/12基于阈值超启发算法的建设资源平衡优化马晓彤，赵丹，蒋天娇（天水师范学院土木工程学院，甘肃 天水 741300）【摘要】提出了阈值超启发算法，以解决资源限制的项目调度或资源分配中资源均衡问题。首先，在元启发式过程域中通过设计阈值来设置启发式算法的优先级，通过优先级来判别选择进入的元启发式算法。其次，用软件运行解决方案域，计算资源分配值。最后，通过举例验证，证明所提出的方法提高了项目的自动均衡功能，有效地增强了资源分配能力。【关键词】进度安排；资源分配；资源均衡；超启发算法【中图分类号】TU722【文献标识码】A【文章编号】2095-2066（2022）12-0184-030引言关键路径法（critical path method,CPM）1一直广泛用作项目调度和控制的工具，以帮助项目经理确保项目完成进度和预算。在 CPM 基本模式中会假设活动所需要的资源是无限的，因而资源管理问题可被忽视。但项目经理经常遇到可用资源有限等复杂管理情况。有关资源管理的主要问题被归纳为资源受限项目调度问题2和资源均衡问题3。在资源约束调度或资源分配中，先假定工程项目中资源是有限的，通过找到可行的办法来解决无资源限制的 CPM 法计算项目完成时间的缺陷，目的是更有效地重新安排项目活动，进而最大限度地缩短项目工期。另一方面，资源均衡可以防止短期的所需资源闲置或缺乏，即其目的还有减少间接的总成本。虽然在资源均衡的典型模式下，可用资源是无限的，但考虑到有限资源情况下会导致最初的项目持续时间的延长，这就引出了工程建设项目中的多资源均衡的NPhard 问题4-6，其中，NP 是指非确定性多项式（nondeterministic polynomial）。早在1996 年，Chan 等7提出了一个使得资源波动和工期最小的遗传算法模型，决策者可在提高资源的可用性和缩短项目工期中做出权衡8-9。1问题的提出使用一个非循环的活动节点项目调度网络表示这个问题。该网络由 n 个活动（节点）和活动间的优先关系（弧）构成。用 di和 fi分别表示活动 i 的持续时间和完成时间。假定节点 1（n）是项目开始（完成）没有进入（或输出）的虚活动。资源分配和均衡问题如式（1）和式（2）所示。min Mx=fnt=1u2t；（1）min fn。（2）满足式（3）至式（6）。fifj-dj，所有优先关系（i，j）；（3）f1=0，d1=0，dn=0；（4）fnfpn；（5）iPtuitU；t=1，fn。（6）目标函数式（1）和式（2）为了找到一个最优的Mx和 fn，使得资源总量及项目工期最小化。式（3）确保各个活动节点的优先关系。式（4）表示项目从时间节点 0 开始。R 是分配给每个活动的单一资源，假定其使用在整个活动的进展中是保持恒定的。认定在项目过程中资源可用性 U 的执行是不变的。所有正在进行活动 Pt的资源使用情况的总和 uit在任何时间 t 不能超过 U式（6）。这是一个传统的资源调配和资源分配的双目标模型。式（1）至式（6）所描述的函数模型没有单一的最优解，而拥有一组非劣的解决方案，即没有使得资源总量 Mx和项目工期 fn在某一时刻达到最优的其他可行的解决方案。线性聚合方法可以借助一个权衡系数使得两个目标结合成一个单一的价值来进行优化，两个目标函数被组合成下面的函数，以便最大限度地加权总和来相对优化资源和进度，如式（7）所示。max z=MPx-MxMPx+（1-）fpn-fnfpn=1-MxMx+（1-）fnfpn=1-z。（7）式中：MPx和 fpn均衡状态下某一时刻极大项目资源用量和项目持续时间。综合论述184DOI:10.16844/10-1007/tk.2022.12.013LOW CARBON WORLD 2022/12由于 max（1-z）=min（z-1），聚合目标函数如式（8）所示。min z=MxMPx+（1-）fnfpn。（8）标量 01 反应决策者的偏好，当=0 时，项目经理完全忽略资源均衡；当=1 时，项目经理希望资源使用的波动最小化。2超启发算法多层次算法的核心思想10很早就被提出，“超启发式算法”的提出就是描述一个多层次的计算过程。上部的启发式层控制应用中的一些相关元启发式方法而非解决方案本身，下部的启发式算法反过来又依据探索解空间的特点11解决问题。为了克服传统启发式算法的一些缺点，例如，只依赖于试图解决问题本身的缺陷，超启发式算法作为一种解决 NPhard 问题的替代方法，可以被应用到解决各种问题11。不像启发式算法只是指导搜索空间的解决方案，超启发式算法在每个决策点从启发式空间中选择和运用一个元启发式算法12。虽然启发式算法在各种各样的应用领域取得了重大进展，包括项目调度问题，但这种方法强烈依赖于在一个给定的专业知识领域的专业问题。而超启发算法通常旨在减少在搜索过程中领域知识量，其研究方法是简单且易于实施的，并足以有效解决多个领域一系列问题实例13。超启发算法已被用于处理工业制造和环境问题中存在的调度问题，如车间作业调度问题14、流水车间调度问题15、资源调配16和资源受限项目调度问题17。3阈值超启发算法依据阈值超启发式算法的核心思想，超启发式算法通过使用确定性验收标准，试图摈弃一些接受增加目标函数值的局部最优解来解决方案。该算法的关键因素是设置一个适当的定义阈值序 r，r确定是否有新的解决方案可以被接受。初始阈值可设置高数值，随着搜索的过程渐渐变小，多次运算迭代后，阈值变得非常小，阈值超启发算法变为一个允许集约化的搜索的专业性启发式算法18。本文中提出阈值根据公式 r+1=r-b 计算，b是一个常数。阈值超启发算法的步骤如下。（1）初始化迭代总次数和阈值的顺序 r，r=1，2，rmax。（2）使用自动均衡化功能软件生成初始时间表Sc和计算资源量 Zc。（3）设置 Sbest=Sc，r=0，迭代计数器=1，并且当不满足迭代条件时停止迭代。（4）当迭代计数器计数迭代总次数时，设置 r=r+1。（5）选择一个低级别的启发式过程 l，其选择概率 p（l），将其应用到当前时间表的优先序列 Sc中，并计算新的时间表 Sn。（6）若 ZnZbest，则设置 Sbest=Sn，Zbest=Zn。（7）若 Zn-Zcr，则接受新的解决方案，设置 Zc=Zn，Sc=Sn。（8）设置迭代计数器=迭代计数器+1，停止。（9）更新所有的选择概率 p（l）；设置迭代计数器=1，结束而输出 Sbest。超启发算法从使用自动均衡功能的软件生成初步的时间表 Sc开始，选择一个元启发式算法的概率，并将其应用于一次的优先事项域。如果产生的结果优于 Sc或者如果没有更加优先目前的结果，将所得新的解决方案的 Sn将被接受。该算法具有较高的目标移动函数值解决方案，以避免被困在初始最低的水平，每个低级别启发式过程对应于一个周期内拥有固定数量的迭代次数，其选择概率 p（l）保持恒定不变，对于所有启发式过程第一次迭代都具有相等的选择概率值，一个基本的学习机制被引入选择之中进行趋向选择，每一个启发式过程依据以往其函数功能表现来选择概率 p（l）的方式表现，选择概率p（l）随迭代次数的增加而更新，迭代次数依据累计改善次数总和达到最终需求总数而停止，再将归一化的概率用于整个下一次循环迭代过程中。4元启发算法的启发式过程阈值超启发算法控制 11 个元启发式算法。基于简单的动作，如“交换”和“替换”，元启发式算法由符合超启发式算法框架要求以简单的方式引入。元启发式算法过程以操作计算为活动重点。本文使用 9个优先级，从 1 到 9 不等。依据选择优先级可以修改活动的标准，将启发式过程分成 4 组。A 组包含基于随机选择的启发式过程，B 组根据其总时差（TS）选择启发式活动，属于C 组和 D 组的启发式过程找到 和 两个时间点，分别是项目资源水平层面上的极大值 umax和极小值umin。选择活动的值由方程计算得到，如式（9）和式（10）所示。u-i=uiumax，对于 iP；（9）u=i=uiumin，对于 iP。（10）在 （）时间点内，所有活动的设置值被定义为P（P）。元启发式算法工作模式的描述如下。（1）A 组基于随机的元启发式算法。L1：随机选择两个活动，并交换这两个活动的优先级。综合论述185LOW CARBON WORLD 2022/12L2：选择一个随机活动，与一个新的随机活动更换其优先级。（2）B 组基于元启发式算法的总时差。L3：分配最低优先级值（1）给总时差最大的活动。L4：分配最高优先级值（9）给总时差最小的活动。L5：选择最大总时差的活动，替代一个优先级在（1，5）间隔内的随机活动；选择最小总时差的活动，替代一个优先级在（5，9）间隔内的随机活动；在这种关联关系情况下随机选取一个活动。（3）C 组元启发式算法的最大资源要求。L6：分配最低的优先级（1）给u-i值最大的活动。L7：分配最高的优先级（9）给u-i值最小的活动。L8：选择u-i值最大的活动并且替代一个优先级在（1，5）间隔内的随机活动；选择u-i最小的活动并且替代一个优先级在（5，9）间隔内的随机活动；在这种关联关系情况下随机选取一个活动。（4）D 组元启发式算法的最小资源要求。L9：分配最高的优先级（9）给 u=i值最大的活动。L10：分配最低的优先级（1）给 u=i值最小的活动。L11：选择 u=i值最大的活动并且替代一个优先级在（5，9）间隔内的随机活动；选择 u=i最小的活动并且替代一个优先级在（1，5）间隔内的随机活动；在这种关联关系情况下随机选取一个活动。基于启发式算法标准的基本原理。减少在项目工期内资源需求的峰值并且增加每日的消费需求，以求在资源分布图中形成小的波峰和波谷。5结语随后通过示例和实验随机生成的活动网络分析表明，遗传算法计算结果和阈值超启发算法相比，阈值超启发算法能够找到更好的解决方案，其算法更有效。本文中阈值超启发算法框架设计显示了其灵活性，突显了其独立地利用元启发式算法解决专业问题的优势，其能结合具体问题采用开放式的解空间探索，利用一定的阈值设定作为约束，更灵活高效地解决各种多目标、复杂性的问题，同时也有利于支持决策开发项目调度系统。参考文献1 任文晓，战德臣，徐晓飞.基于 CPM 的资源平衡问题研究J.微计算机信息，2009，25（9）：142-144.2 刘士新，宋健海.求解资源受限项目调度问题的约束规划/数学规划混合算法J.控制理论与应用，2011，28（8）：1113-1120.3 单汨源，邓莎，吴娟，等.一种求解项目调度中资源均衡问题的粒子群算法J.科学技术与工程，2007（22）：5805-5809.4 丁继勇，王卓甫.多资源均衡问题及其优化方法分析J.工程管理学报，2011，25（1）：51-55.5 刘士新.项目优化调度理论与方法M.北京：机械工业出版社，2007：42-46.6 方晨，王凌.资源约束项目调度研究综述J.控制与决策，2010，25（5）：641-650，656.7 CHAN W T,CHUA D,KANNAN G.Construction resourcescheduling with genetic algorithmsJ.Journal of constructionengineering and management,1996,122(2):125-132.8 褚春超，郑丕谔，李栋.网络计划资源均衡模型的改进及其应用J.天津大学学报，2006（2）：250-255.9 孙震.工期固定-资源均衡优化的新途径J.建筑管理现代化，2003（2）：10-12.10 FISHERH.Probab ilistic learning combinations of localjobshop scheduling rulesJ.Industrial scheduling，1963，9(5):225-251.11 BURKE E,KENDALL G,NEWALL J,et al.Hyperheuristi