基于改进遗传算法的多项目资源均衡配置研究-段世霞.pdf

《基于改进遗传算法的多项目资源均衡配置研究-段世霞.pdf》由会员分享，可在线阅读，更多相关《基于改进遗传算法的多项目资源均衡配置研究-段世霞.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 96 工业技术经济Journal of Industrial Technologyical Economics第 10 期（总第 288 期）2017 年 10 月No.10（General, No.288）Oct.2017引 言“十三五”期间，我国的经济发展进入新常态，与此同时，建筑行业呈现出持续稳步发展的新趋势，具有大型、复杂、跨地域新形态的工程项目越来越多，其中不乏有多个项目并行施工的情况存在，这给建筑行业带来了新的挑战。多个项目并行施工与企业资源有限之间的矛盾突出且日益加剧，成为制约建筑企业在激烈的市场竞争环境中生存下来的瓶颈。因此，如何提高企业建设资源在多个项目中的利用率和配置效率

2、，是项目管理的一大难题。怎样去解决资源利用率和配置效率低下的问题，成为许多国内外学者的研究焦点，他们将资源配置问题分为两类：（1）“工期固定， 资源均衡” ； （2） “资源约束， 工期最小” 。起初，资源配置问题只是针对单项目而言，随着社会经济的发展，企业承揽的项目不再单一化，随之单项目资源配置问题逐渐演变成多项目环境下的资源配置问题。1 文献综述在单项目资源配置方面，仲勇等研究了大型工程项目多类型资源地有效配置问题，基于挣值法和系统动力学理论，在分析资源可用性和工作可操作性之间因果关系的基础上，构建了系统动力学模型1；邓肖夫等泛化了工程项目物质资源范围，除基本的人、材、机资源之外加入环境和

3、信息资源，应用模糊综合评判原理，构建资源配置合理性的评价指标体系，形成评判标准，为资源配置评价提供了一个新方法2；乞建勋建立了多资源均衡的熵目标函数来反映资源配置的均衡程度，论证了粒子群算法比传统遗传算法更加有效，从而大大降低工程造价3；Weng-Tat Chan等在解决“工期一定，资源均衡”的问题上，用遗传算法和启发式算法分别对研究案例进行求解，验证了遗传算法的优越性4；J.Son 研究了建设工程项目中具有混合工艺的资源分配问题，将启发式算法与模拟退火方法相融合，来解决资源配置平衡问题5；Easa 针对中小型项目的单资源均衡优化建立了一种整数线性规划模型，模型的目标函数是资源需求量与资源平均

4、水平之间的绝对值最小化或者资源需求量与理想的非平均资源水平之间绝对值最小化，并结合关键路径法来调度资源，这个模型还可以延伸至多资源均衡问题的研究6；Tarek Hegazy 在文中提出资源分配是项目管理的一大挑战，启发式算法已经满足不了收稿日期：2017-04-14作者简介：段世霞，博士，郑州大学管理工程学院教授。研究方向：工程项目管理。张金茹，郑州大学管理工程学院硕士研究生。研究方向：工程项目管理。基于改进遗传算法的多项目资源均衡配置研究段世霞 张金茹(郑州大学管理工程学院，郑州 450001)摘 要 如何解决建筑企业在多个项目中资源利用率和配置效率低下的问题，是施工方项目管理的一大难题。本

5、文根据多项目工程施工特点，建立了多项目并行施工时的资源均衡优化模型。为了提高遗传算法对多项目资源配置问题求解的性能，本文对遗传算法进行了改进，并以某公司 3 个并行施工的工程项目为例，根据工程施工初始网络计划的资源需求，运用改进遗传算法（IGA）和遗传算法（GA）计算多项目的资源配置方差。结果表明，改进遗传算法可使资源配置达到更好的优化状态，并能得到各个项目非关键线路上工序的最佳开工时间，为建筑施工企业提供了具有实践价值的技术手段。关键词 多项目 资源 均衡 改进遗传算法 模拟退火 资源配置DOI：10.3969/j.issn.1004-910X.2017.10.012中图分类号 F224.3

6、3 文献标识码 A万方数据工业技术经济Journal of Industrial Technologyical Economics第 10 期（总第 288 期）2017 年 10 月No.10（General, No.288）Oct.2017 97 资源优化的需求，而是通过寻找任务优先级，用运用遗传算法对资源网络计划进行二进制编码求解7。在多项目资源配置方面，有学者从“资源有限，工期最短”出发，研究了以最小化项目工期为目标，资源如何调度的问题，得到了有效的资源配置计划8,9；袁晨弘提出多项目管理资源配置手段不适合石化施工企业发展这一问题，从人们获取信息方式改变这一角度出发，探讨了石化企业多项

7、目资源配置的组织结构和信息平台搭建，从而为石化企业在激烈的市场竞争中提供决策依据，提升企业资源配置效率10；祁神军等认为资源配置的合理性应该有一个评判标准，否则无法评价资源配置是否合理，更无法控制不良配置情况的发生和一旦发生如何及时采取科学措施来解决多项目的资源配置不良问题，于是，祁神军等提出了RPM评估模型，从静态和动态方面评估建设企业集团多项目资源配置是否合理11。张永会等人分析了在解决多项目资源配置问题上几种传统方法的不足，提出用隔代映射微遗传算法模型分析了多项目资源均衡配置问题，认为用该算法可以避免早熟现象，在算法实例中，将多项目转化为单项目来研究，验证了该模型的可行性，从而降低了项目

8、成本，提高了资源利用率12；Xiuren 在多项目环境下研究了基于约束理论的人力资源配置问题，文章引入了“割集”理论，建立了人力资源约束配置模型，使用定量的分析方法解决了人力资源供需矛盾13；Shu Shun Liu 等人讨论了多项目调度问题的资源分配策略，文章建立了一个约束规划模型，此模型针对每个涉及资源分配组合的工序解决不同的优化目标，比如项目总成本和整个项目的持续时间最小化14；Steyn 指出了 TOC 理论最早被应用于项目进度管理，而文章研究的是 TOP 理论的另一个应用，即多项目并行时的资源共享管理，除了这两方面的应用，TOP 理论还可以用来研究项目成本管理和项目风险管理15；Le

9、ach 提出的 CCPM 推进了项目管理知识体系的改善，通过 CCPM 将项目计划上的不确定性聚集到缓冲区，此举能保证项目按资源需求计划和资金使用计划完成16；Wu，Sun在考虑员工学习效率的基础上研究了针对项目计划的人力资源分配问题，以外包成本最小化作为目标函数建立了混合非线性模型，运用遗传算法求解17。资源配置问题引起了国内外学者广泛研究，但是在多项目资源均衡配置方面研究尚少，张永 会等12虽然研究了多项目资源均衡配置问题，但是他建立的模型和改进遗传算法过于复杂，在实践中较难实施。在多项目环境下，本文研究的是上文所述的第一类问题， 即 “工期固定， 资源均衡” ，如果对多个项目所有工序进行

10、调整从而达到资源配置均衡的效果， 无疑是一项艰巨而复杂的任务，但是由于关键线路是项目成败的瓶颈，项目经理会优先考虑此线路上的资源配置问题，所以文章仅研究非关键线路上的资源均衡配置问题，并在前人研究的基础上提出一种符合工程实际的改进遗传算法来解决多项目资源均衡配置问题。2 问题假设和资源配置模型建立解决资源均衡配置问题，主要有解析法、启发式方法和遗传算法，解析法虽然可以阐明问题实质，但是只适用于单项目单资源的均衡配置，使用范围具有局限性；启发式方法包括削峰填谷法、优选法和差值法，这几种方法计算简单容易理解，但是它们有一个共同的缺点，即每一次计算之后可能会带来新的资源不均衡，需要进行重复计算获得最

11、满意解，而本文在建立精确模型的基础上采取了改进遗传算法，该方法具有良好的优化性和并行性，方便全局寻优。为了方便问题的研究，建立以下假设：假设 1：本文所研究的多项目资源配置问题共包含 m 个项目，各个项目之间相互独立，不存在任何紧前紧后的逻辑关系，各项目内部的各项任务之间存在紧前紧后的逻辑关系。假设 2：各个项目的各项任务一旦开始，不允许间断。假设 3：各个项目的性质相同，包括使用的人、材、机种类相同，比如每个项目的工种，材料类型和机械型号都是一致的。但是由于人、材、机的量级不一致，无法进行直接比较，文章以“资源消耗强度”为比较标准，用 表示。万方数据 98 工业技术经济Journal of

12、Industrial Technologyical Economics第 10 期（总第 288 期）2017 年 10 月No.10（General, No.288）Oct.2017资源消耗强度是衡量资源使用量的指标，是指一定时间内单个项目的每一道工序上所耗费的各种资源的程度。在产出一定的情况下，资源消耗强度越低说明资源投入量越少， 资源利用效率越高。每道工序的资源消耗强度是经验丰富的资源管理员结合工程数据加以确定的。具体的确定方法是根据每个项目每道工序的资源使用计划再结合资金使用计划找出一个针对工序而言的基准使用金额，然后将每道工序的人材机使用量转化为资金使用量，令其与基准金额相比较，得出

13、来的比值就是资源消耗强度，采用四舍五入法将强度值取为整数， 的取值范围在 110 之间。本文利用资源消耗强度的波动情况来表示资源均衡配置效果的好坏。基于以上分析和假设，本文建立数学模型来解决资源均衡配置问题，通过调整非关键线路上实际开工时间来控制资源配置波动大小，波动越小，资源配置越均衡，所以引入“数学方差”的理念来表示资源配置均衡效果的好坏。在固定工期内，以各个项目每天资源消耗强度的方差 为目标函数，建立如下模型：（1）实际开工时间处于最早开始时间和最晚开始时间之间，并且紧前工序完成之后才能进入下一道工序，所以会产生以下约束：（ 2 ） （3）（4）其中， 表示第 k 个项目中作业 的松弛时

14、间； 表示第k个项目中作业的最晚开工时间； 表示第 k 个项目中作业的最早开工时间； 表示第 k 个项目中作业 的紧前作业集； 表示第k个项目中作业 的实际开工时间。平均每天的资源消耗总强度是：（5）其中， 表示第k个项目的总工期； T 表示m 个项目工期的最大值。各个项目每天的资源消耗总强度是： （6）其中， 表示第 t 个工作日各个项目的资源消耗总强度； 表示第t天作业 的资源消耗强度。如果第 t 天的作业实际开始时间在最早开始时间和最晚开始时间之间，则资源消耗强度是， 如果不满足时间约束， 资源消耗强度是0，即：（7）其中， 表示第k个项目中作业的单位时间的资源消耗强度； 表示第k个项目

15、中作业 的实际完工时间。3 模型的求解和算例分析3.1改进遗传算法通过对遗传算法的研究得知常规遗传算法如果不进行改进，会造成个体早熟和局部最优的现象，所以本文采取自适应交叉概率和变异概率以及拉伸适应度的方式对遗传算法改进。遗传算法在运用过程中，参数的选取会直接影响算法的性能和行为，所以对交叉概率和变异概率大小的选择是否合理尤为重要。新个体产生的速度取决于交叉概率，新个体产生的速度越快代表交叉概率越大，但此时遗传模式极有可能被破坏；搜索过程缓慢甚至停滞代表交叉概率过小。新的个体结构产生的难易程度取决于变异概率，新个体结构的生成受到阻碍说明变异概率过小；但如果变异概率过大，破坏遗传模式的风险同样会

16、大大增加。由此可见，实时调整交叉概率和变异概率十分必要。当个体适应度值大于群体平均适应度值时，该个体需对应于较小的交叉概率和变异概率才能使得遗传模式得以保护，通过实时调整交叉概率和变异概率能够令该个体顺利进人下一代；当个体适应度值低于群体平均适应度值时，该个体对应于相对较高的交叉概率和变异概率，通过实时调整交叉概率和变异概率令该个体被淘汰掉。经过两种情况的调整，从而获得优秀的个体结构。交叉概率和变异概率经过改进，可用计算公式来表达：万方数据工业技术经济Journal of Industrial Technologyical Economics第 10 期（总第 288 期）2017 年 10

17、月No.10（General, No.288）Oct.2017 99 （8）（9）式中， 和 分别表示交叉概率和变异概率，和 分别表示最大的交叉概率和最大的变异概率， 和 分别表示最小的交叉概率和最小的变异概率。当个体适应度值 与最大的适应度值越来越接近，交叉概率和变异概率就变得越来越小，直到个体适应度值 与最大的适应度值相等时，交叉概率和变异概率达到最小，分别等于 和 ，此时，个体适应度值达到最大，同时 和 不为零。所以，该改进策略能使群体中优秀个体的交叉率和变异率得到实时调整，从而保护遗传模式。为了保留每一代优秀个体并且个体结构不被破坏，直接使用精英选择操作，将优秀个体完整地复制到下一代。

18、 运行初期，种群个体差异处于较大的状态，用轮盘赌的方式选择出来的后代个数与个体本身的适应度值大小的关系成正相关，由此选择出来的优秀个体结构容易在种群内部造成早熟现象；到运行后期，当优秀的个体再次通过交叉和变异产生后代时，个体优势不再突出，造成整个种群停止进化。为了解决这个问题，需要拉伸适应度值，于是引入模拟退火思想来对适应度值进行拉伸，具体拉伸方式是：（10）其中， 是第 个个体的适应度， P 是种群个数， 是遗传代数， T0是初始温度。由式 （10） 可以看出， 遗传算法前期 T 值较高，适应度值比较接近，最优个体无法显示出其优势，但是到遗传算法后期，随着温度的降低，个体适应度值的差距显著，

19、优秀个体凸显出来并顺利被选择至下一代。3.2 求解步骤经过对问题模型的建立和遗传算法的改进之后，需要对多项目资源配置模型进行求解。求解步骤如下：（1）编码。一般情况下，需要对目标函数中的变量进行编码，但是对于多项目资源配置问题不再适用，因为关键线路上自由时差和总时差是 0，即关键线路上的任务没有能运用的机动时间，所以关键线路上的任务开始时间固定，于是对于该问题只需针对非关键线路上的实际开工时间 进行实数编码，共有 8 条非关键线路，所以编码串长度是 8 位，这样不仅对关键线路上的任务没有任何影响同时可以缩短问题的寻优搜索时间。（2）产生初始种群。在范围内随机产生 P 条染色体，即 P 个初始个

20、体。（3）适应度函数设计。本文中目标函数值越小，表明施工进度计划安排越好，资源配置越均衡，但是适应度函数的设计需要满足最大化的条件，所以可以采用目标函数的倒数来作为适应度函数，以此评价个体对环境的适应性。（4）遗传操作。遗传操作包括选择、交叉和变异。在选择过程中常常会因概率事件使得优秀个体无法被选择出来继续加入到算法的运行当中，这样的随机误差可以被克服，只需在采取轮盘赌选择的基础上引入最优个体保存策略，即可将最优染色体成功保留至下一代。交叉方式是单点交叉，在基因总个数范围内产生一个随机数，这个随机数就是染色体交叉部位的基因起始位置。变异方式是一致变异。为防止局部最优，利用改进后的变异概率公式和

21、交叉概率公式对变异概率和交叉概率进行自适应调节。（5）对约束条件的处理。本文采用修复策略来判断非关键线路上的工序是否满足约束，如果不满足则强制改变 的大小使等号成立。（6） 终止操作。 为了防止算法无休止地运行，需主动控制算法终止条件，将算法的终止条件设定为产生最大世代数和最小方差。 3.3 工程算例分析本文依托工程实例来验证改进遗传算法的有效性和一般性。经过对某公司承接项目的了万方数据 100 工业技术经济Journal of Industrial Technologyical Economics第 10 期（总第 288 期）2017 年 10 月No.10（General, No.288

22、）Oct.2017解，选取了3个并行施工的项目，初始网络计划图如图 13。具体项目参数如表 1，表 1 中加* 号的作业为非关键线路上的作业。图1 项目1初始网络计划图表1 项目参数表项目 工序工序的资源消耗强度 最早开工时间 最晚开工时间 松弛时间 作业工期 紧前作业集1 A 90004无1 B 344 2A1 C*6 6 8 2 B1 D 44402A1 E 866 3BD1 F*5 9 10 1 1CE1 G 26603D1 H 199 2GE2 A 40003无2 B 533722 C 25503A2 D 188 1C2 E 3550 A2 F*2 6 7 1 2 E2 G 45533

23、A2 H 29902DFG3 A 500 3无3 B*6 0 4 4 23 C*3 3 6 3 3 A3 D 13304A3 E*4 3 6 3 3AB3 F 27702D3 G*1 6 9 3 4 C3 H*2 2 E图2 项目2初始网络计划图 图3 项目3初始网络计划图将上述数学模型、约束条件结合项目参数，得到具体的目标函数和约束条件：（11）万方数据工业技术经济Journal of Industrial Technologyical Economics第 10 期（总第 288 期）2017 年 10 月No.10（General, No.288）Oct.2017 101 （12）根据约

24、束条件形成的染色体结构，将实际开工时间的约束条件转化为： ， ， 。适应度函数为：（13）参数最终确定为，运用 式（10 ）确定适应度值， T0取1000；根据文献18建议的参数取值范围，种群大小取20200， 取0.51.0， 取0.000.05，所以种群规模 P 取 100，经过试算得到的交叉概率和变异概率也在其范围内，得到的值分别是=0.85， =0.65， =0.01， =0.001，运用的自适应概率计算公 式（8）和（9 ）来调整交叉概率和变异概率。运用 Matlab2014a 对遗传算法编程，首先采用常规遗传算法对模型求解，在迭代20次之后得到 TS(C1)=6， TS(F1)=9

25、， TS(F2)=6， TS(B3)=2，TS(C3)=4， TS(E3)=3， TS(G3)=7， TS(H3)=8，然后采用改进遗传算法对模型再次求解，迭代27次之后得到 TS(C1)=7， TS(F1)=9， TS(F2)=6， TS(B3)=1，TS(C3)=4， TS(E3)=4， TS(G3)=6， TS(H3)=7。目标函数值对比情况如表 2 所示。表2 两种算法结果比较表方案 资源均衡配置方差初始网络计划 47.89常规遗传算法优化 10.50改进遗传算法优化 3.20从表 2 可以看到，常规遗传算法得到的 值比初始网络计划的 值降低了 78%，说明多项目资源配置更均衡，改进遗

26、传算法得到的 值又比常规遗传算法得到的 值降低了 70%，说明常规的遗传算法已经无法满足在实际工程中的应用，改进遗传算法有更高的搜索精度和效率，能够得到一种更好的施工进度方案，使多项目资源配置均衡效果达到最令人满意的状态，而且通过调整非关键线路上工序的开工时间，并用改进遗传算法求解，资源均衡配置能收到显著效果，避免了全工序参与的复杂性，从而降低了操作难度。4 结束语纵观建筑市场的发展，单项目资源均衡配置已经满足不了建筑企业的需求，寻求多项目环境下的资源均衡配置体系是企业发展的必然趋势，在这种形势下，建筑企业只有形成自己的核心竞争力才能在激烈的市场竞争环境中生存下来。本文立足于多项目资源均衡配置

27、的探究，建立多项目资源均衡配置模型，将模拟退火思想引入遗传算法来拉伸适应度值并对交叉概率和变异概率进行自适应调节，在此基础上对模型求解，不仅可以找出非关键线路上的最佳开工时间而且保证了多项目并行施工情况下，资源得到均衡配置，从而可以在实际工程建设中，给工程施工的顺利进行提供保障，防止某些工序资源短缺或资源浪费的情况出现。通过工程实例证明，本文建立的多项目资源均衡配置数学模型在实际工程中操作简便，该模型给建筑施工企业提供了一种具有实践价值的技术手段，也可以为其他行业多项目并行资源配置管理提供一定的借鉴作用，而且运用改进遗传算法得到的结果与常规遗传算法相比，其搜索精度大大提高，计算结果更加贴近实际

28、，所达到的效果更为理想。参 考 文 献 1 仲勇，陈智高，周钟 . 大型建筑工程项目资源配置模型及策略研究基于系统动力学的建模和仿真 J .中国管理科学，2016，24（03）：125 132. 2 邓肖，陈顺良，张敏 . 工程施工项目资源配置合理性的模糊综合评价模型J. 中外建筑，2013，15（05）：130 131. 3 乞建勋，王强，贾海红 . 基于熵权和粒子群的资源均衡新方法研究J. 中国管理科学，2008，16（01）：90 95. 4 Weng-Tat Chan，David K.H. Chua，Govindan Kennan. Construction Resource Sche

29、duling with Genetic AlgorithmsJ.Journal of Construction Engineering and Management，1996，122（02）：125 132. 5 J.Son，M.J.Ski. Multi-heuristic Approach for Resource Leveling Problem in Construction Engineering Hybrid ApproachJ.万方数据 102 工业技术经济Journal of Industrial Technologyical Economics第 10 期（总第 288 期）2

30、017 年 10 月No.10（General, No.288）Oct.2017Journal of Construction Engineering and Management，1999，125（01）：23 31. 6 Easa. Resource Leveling in Construction by OptimizationJ.Journal of Construction Engineering and Management，2000，115（02）：302 316. 7 Tarek Hegazy. Optimization of Resource Allocation and L

31、eveling Using Genetic AlgorithmsJ. Journal of Construction Engineering and Management，2003（06）：167 175. 8 黄健仓 . 建设企业多项目管理中的资源调度问题研究J. 中国软科学，2016，15（01）：176 183. 9 白礼彪，刘锦涛，陈志 . 基于改进遗传算法的资源限制建设工程多项目调 度J. 计算机与现代 化，2016，32（08）：1 6. 10 袁晨弘 . 多项目管理下石化施工企业资源配置优化分析J.中国管理信息化，2015，18（11）：85 86. 11 祁神军，丁烈云，骆汉宾

32、 . 建设企业集团多项目关键资源配置有效性评估J. 西安建筑科技大学学报（自然科学版），2011，43（01）：119 124. 12 张永会，马力 . 多项目资源管理技术研 究J. 计算机工程与设计，2010，31（17）：3886 3890. 13 Xiuren. Multi-project Human Resource Constrained Allocation Based on Theory of ConstraintsJ.Science and Technology，2016，9（09）：383 394. 14 Shu Shun Liu，Wei Tong Chen. Constru

33、ction Multi-Project Scheduling Model Considering Different Resource Allocation BehaviorJ .Applied Mechanics and Materials， 2012， 174（02） ：815 819. 15 H.Steyn. Project Management Applications of the Theory of Constraints Beyond Critical Chain SchedulingJ.International Journal of Project Management，20

34、02，20（01）： 75 80. 16 Leach LP. Critical Chain Project Management Improves Project PerformanceJ.Project Management Journal，1999，30（02） ：39 51. 17 Wu W，Sun S. A Project Scheduling and Staff Assignment Model Considering Learning EffectJ.International Journal Advanced Manufacture Technology，2006，28（11）：

35、1190 1195. 18 席裕庚， 柴天佑， 恽为民. 遗传算法综述 J .控制理论与应用，1996，13（06）：697 708.Multi-Project Resource Leveling Allocation Research Based on Improved Genetic AlgorithmDuan Shixia Zhang Jinru( School of Management Engineering， Zhengzhou University， Zhengzhou 450001， China )Abstract It is a big problem in project

36、management about how to solve resource utilization effi ciency and allocative effi ciency in multiple projects. According to project engineering construction characteristics and considering the parallel construction of multi-project， this paper sets up resources equilibrium optimization model. In or

37、der to improve the performance of the genetic algorithm， this paper improves the genetic algorithms， and takes three parallel construction of the projects in a company as an example， according to the initial network plan of resource requirements construction of engineering construction， respectively

38、， this paper uses improved genetic algorithm（ IGA） and genetic algorithm (GA) to calculate the variance about allocation of resources. The results show that the improved genetic algorithm can get a better in optimizing the allocation of resources，at the same time， get the best starting time of project at non-critical lines by using improved genetic algorithm. It provides technology which has practical value for construction enterprises.Key words multiple-projects； resources； leveling； improved genetic algorithm； simulated annealing；resource allocation（责任编辑：史 琳）万方数据