多项目资源均衡问题及其模拟植物生长算法

多项目资源均衡问题及其模拟植物生长算法【摘要】本文针对多项目管理资源问题的特点，构建了多项目资源均衡问题的数学模型，并提出了一种改进的模拟植物生长算法。该算法对基本的模拟植物生长算法在生长点保留策略上做了改进，提高了算法的收敛速度并能寻找到最优解。实例仿真也证实了改进的算法能有效地解决多项目资源均衡问题。【关键词】多项目；资源均衡；模拟植物生长算法项目的进度计划决定了项目的资源需求计划，均衡施工有利于平缓资源需求量的强度，提高资源使用率，减少各种临时设施，降低施工管理费，从而削减资源使用成本，降低项目总造价。因此，企业在项目计划和控制过程中，需要合理安排项目各项工作的进度，保证完工日期的同时均衡工期范围内的资源需求。这也就是“工期固定资源均衡”的资源优化问题。随着经济的发展，越来越多的企业面临着多项目管理的环境，资源配置是多项目管理的核心，因为资源配置的合理性将直接影响到企业组织多项目运作的成本与效益。如何制定出合理的进度计划，优化各项目之间的资源配置是当代项目管理者成本控制工作的重要内容。仅仅对各项目进行资源均衡优化，只能均衡各项目内部的资源需求，并不能保证整个企业的资源需求处于最佳均衡状态，因此研究多项目资源均衡问题更具现实意义。资源均衡问题本质上是一个组合优化问题，其计算复杂度随着问题的规模呈指数增长，因此对于大型而又复杂的资源优化问题在理论上属于NP问题。目前，国内外学者提出了许多求解该问题的方法，大体可以归纳为以下两类：精确算法和启发式算法。精确算法由于难以有效解决大型而又复杂的问题，所以在实际工作中很少采用。启发式算法包括基于优先规则的启发式算法，以及元启发式算法即智能算法。基于优先规则的启发式算法过多地依赖问题本身以及人们对问题的认识和经验，所以通用性较差且容易陷入局部最优。智能算法是通过模拟生物的行为或自然界的现象来解决目标优化问题，主要包括遗传算法、粒子群算法和模拟退火算法等。智能算法具有适用性强，求解效率快，结果可靠的特点，因此越来越多学者致力于开发和改进智能算法用以解决此类资源优化问题，取得良好的成果。模拟植物生长算法具有原理简单，参数设置少优点，并且采用兼备随机性和方向性的搜索机制，在求解整数规划问题上具有很大的优越性。本文主要研究的是运用改进的模拟植物生长算法求解多项目资源均衡问题，并通过实例仿真验证其有效性。1.多项目资源优化数学模型的构建典型的多项目资源优化问题通常基于以下假设：（1）各项目的工作数目J以及各工作的资源消耗量确定不变；（2）各项目的工作之间的工艺关系确定；（3）各工作在执行过程中不间断。问题描述如下：某单位有M个并行的工程项目集合V=1，2，M，项目k（kV）的工作任务集体为Bk=k1，k2，kn；Sk为项目k的开工时间，Fk为项目k的完工时间，且每个项目的Sk和Fk固定不变；Ski是指工作ki的实际开始时间；LSki是指工作ki的最晚开始时间；dki表示工作ki的持续时间；Pki为是项目k中工作j的紧前工作集；Atk为项目k在（t-1，t）时段内正在执行的任务集合；Rj表示工作j资源消耗量；R（t）表示（t-1，t）时段内M个项目的资源消耗总量。资源均衡有多种评价指标，本文采用常用的资源方差作为目标函数，则该问题的数学模型为：目标函数：（1）其中：约束条件：（2）式（2）定义的是时序约束表示工作ki必须在其所有紧前工作完成后才能开始，并且不得晚于其最晚开始时间否则影响该子项目工期目标。2.模拟植物生长算法模拟植物生长算法是受大自然中植物生长的向光性机理的启发，将优化问题的可行域当作生长环境，全局最优点当作光源，整个搜寻优化解的过程视为一棵虚拟植物生长的生长过程，当整株虚拟植物完全成熟，整个优化过程也就结束，最终输出优化的结果。模拟植物生长算法由于对目标函数和约束条件的要求宽松，迭代次数少，效率高运行速度快等优点，广泛用于实际工程技术领域，求解复杂的整数规化问题。（1）植物的生长机理植物由根、主干、枝叶和生长点组成。生物学中的暗箱实验证实了植物生长具有向光生长的特性，究其根源，在于一种叫做生长素的物质，也称形态素。主干和枝的生长顺序和向光性正是由分布在枝干上的生长点的生长素浓度决定。当形态素浓度大于零时，主干和枝的生长点就开始生长且形态素浓度大的生长点优先获得生长机会。每一次生长动作结束后，形态素将根据新系统所在环境的改变而重新向各生长点分配。生长一般过程可以描述为：1）一个茎杆破土而土，分布其上的生长点发出新枝；2）大多数新枝又长出更新的枝，此行为反复进行；3）不同的枝彼此有相似性，整个植物有自相似结构。（2）植物生长的数学模拟文献6建立以L-系统为基础的植物生长演绎方式和以植物向光性理论为基础的概率生长模型。概率生长模型作为算法核心内容，其主要思想为：一株植物从根部所在的点S0开始生长出主干M，假定M上有k个比根部光照条件好的生长点SM1，SM2，.，SMk，那么各生长点的形态素浓度CM1，CM2，.，CMk计算公式如（3）所示：式中g（.）为背光函数，其值越小表示其光照条件越好，形态素浓度取值范围为（0，1），从公式可以看出，各点形态素浓度最终取决于生长点本身的光照条件。易知：即所有生长点的形态素浓度构成图1所示的空间。随机产生（0，1）之间的数，这个数落在某一区间，该区间对应的生长点即在下一时刻的生长，显然形态素浓度越大，区间长度越大，被选择的概率也就越大，这符合实际的植物生长规律。图1形态素浓度状态空间当选定某一主干生长点如CM1生长出枝m后，同样假定有q个比根部光照条件好的点，此时要对所有主干和枝干的所有未生长过的以及新的生长点形态素浓度重新计算，公式如（4）所示：同理可知，所有生长点的形态素浓度累加和为1，然后同样采用随机抽取的方式选择下一轮的生长点，此过程反复进行直至整株植物生长完成。3.基于改进模拟植物生长算法的资源均衡优化3.1决策变量选取与取值整形化项目资源优化调整的是非关键工作的开始时间，所以选取非关键工作的开始时间为决策变量。模拟植物生长算法是一种解决整数规化问题的全局优化算法，因此对于工程项目工作任务持续时间非整天的情况，在运用算法前需要对工作任务的持续时间数据整数化，处理方法为：把所有工作持续时间的最大公因子（GCD）作为时间单位7，然后按新时间单位重新计量各工作的持续数量，优化后需要把结果乘以新计量单位以还原成实际的时间。例如：工作A的持续时间为1.2天，工作B的持续时间为1.6天，则新的计量单位为0.4天，整形化后A，B的持续时间分别为3和4。3.2生长点集合的更新策略和步长的选取由于工程项目往往都包括多项工作任务，因此如果单纯采用基本的模拟植物生长算法进行迭代搜索，几轮过后生长点将极其庞大，收敛速度非常迟缓，难以适用于规模稍大的项目。因此，本文采用下述措施改进算法流程。选择更新周期N，每迭代N次进行一次生长点的裁剪，将生长点集合中不劣于最优解Fmin的点保存下来作为新的生长点集，同时将最优解Fmin定为下一搜索周期的评价基准值，即后续寻找的点，只有当它的目标函数大于或等于最优值Fmin时，才会被加入到新生长点集中。N的值正相关于收敛结果，负相关于收敛速度。基本的模拟生长算法在整个搜索过程中，始终以初始点的目标函数值作为后续点的评价基准值，而改进后的算法每完成一个周期的迭代后就更新下一周期搜索过程的基准值。生长点集合门槛的逐步提高极大地削减了生长空间的规模，加快算法的收敛速度，提高了算法的适用性。资源均衡优化是以工期固定为前提，所以非关键工作开始时间必定介于最早开始时间和最晚开始时间范围内。因此，我们可以设定生长基点XB各维度变量以该维度对应工作的最早和最晚开始时间为边界进行搜索，进而根据公式（5）设置步长。其中，+表示向各维度正方向搜索的最大步长；+表示向各维度负方向搜索的最大步长；ES表示各维度工作的最早开始时间；LS表示各维度工作的最晚开始时间。3.3形态素浓度计算公式的调整鉴于改进后的算法保留了目标函数值与评价基准值相等的点作为生长点，我们相应地对形态素浓度计算公式（6）作如下的调整，以保证为每一个生长点都分配了形态素。其中，为（0，1）之间的随机数。3.4调整后的算法步骤基于模拟植物生长算法的多项目资源均衡问题优化过程如图2所示：Step1：选择可行的初始点x0，生长基点XB=x0，设置步长step=；初始化最优变量值Xmin=x0和最优解Fmin=f（x0），参照目标函数值f0=f（x0）；生长点集Growset=x0，成长基点集Mature=。Step2：在基点的领域内沿坐标轴的正负方向搜索步长范围内的新生长点（目标函数值小于或等于f0的点）并将其加入到生长点集中，将该基点从生长点集移除到成长基点集中，同时不断更新最优变量Xmin和最优解Fmin。Step3：判断是否满足停止条件Growset=，如满足输出最优变量值和最优解，否则转第4步。Step4：如果迭代次数不为N的倍数，按公式（6）计算各点的形态素浓度，产生一个随机数，生成新的生长基点转第2步，否则转第5步。Step5：进行“剪枝”。在生长点集中保留不劣于当前搜索到的最优解Fmin的生长点，同时将其他生长点移除至成长基点集中，更新f0=Fmin按公式（6）计算各点的形态素浓度，产生一个随机数，生成新的生长基点转第2步。4.算例及分析本文的算例采用文献2中的实例，运用模拟植物生长算法比较合并前后的资源方差差异，另外通过对比遗传算法和粒子群算法，来验证模拟植物生长算法解决资源均衡优化问题的有效性。某单位有三项并行的工程项目，它们共享一个资源库。为了避免资源需求的高低起伏减少资源成本，我们需要合理安排各项工作的进度达到资源均衡。为了方便网络计划的调整，本文通过添加占用时间的虚工作来合并各项目的网络计划，合并后的双代号网络计划如图3所示，项目1的开始节点为2，开始时间为第0天，持续时间为14天，项目2的开始节点3，开始时间为第1天，持续时间为19天，项目3的开始节点为4，开始时间为第4天，持续时间为16天。节点1和节点7分别为合并后的网络计划的起点节点和终点节点。它们与各子项目的开始和完成节点之间的虚箭线1-2，1-3，1-4，23-27，26-27，25-27为辅助工作，各自的持续时间分别为0，1，4，6，0，0。采用改进后的模拟植物生长算法，分别对三个子项目进行资源优化，如果按子项目各自达到资源均衡的方案部署工作，该单位的资源需求方差反而高达187.09。对合并后的项目进行优化得到最优解为54.79，相比之下，资源的波动状态得到了有效的缓解。各项工作的安排如表1所示：分别用遗传算法和粒子群算法对该实例进行多次试算，遗传算法的最好的优化结果为56.39，粒子群算法的最好优化结果为54.79。但是在算法稳定性和收敛速度上，粒子群算法略逊于模拟植物生长算法。由此可知，改进后的模拟植物生长算法能够很好的解决多项目资源均衡问题，并且在算法稳定性、计算精度和收敛速度上具有一定的优越性。图4显示了模拟植物生长算法的优化进程，从图中可以看出算法具有非常明显的收敛趋势。5.结论本文将改进的模拟植物生长算法运用到多项目资源均衡优化问题中，构建了多项目资源均衡问题的数学模型，并给出了算法的流程，进行实例验证，得出以下结论。第一，针对多项目之间资源需求冲突的现象，企业需要正确处理整体与部分的关系。企业分别对各个项目进行资源均衡优化，并不能使整个企业的资源分布均衡。企业应将所有项目视为一个整体，统筹安排各项目资源供给，才能更好地减少资源成本。第二，改进的模拟植物生长算法为资源均衡问题提供了一种有效的解决方法。该算法参数设置少、稳定性好、收敛速度快而且计算结果精确，适合大型而又复杂问题的优化，可为现代化的项目管理软件提供技术支持，用以解决实际工程中的资源优化问题。参考文献1艾鑫.多项目管理中资源冲突及优化配置研究D.重庆：重庆大学，2011.2王为新，李原.多项目资源均衡问题及其遗传算法J.计算机应用研究，2006（12）：46-47.3宋述杰.基于基因算法的多工况多资源均衡优化研究D.大连：大连理工大学，2009.4李彤.基于模拟植物生长算法的二级整数规化算法研究D.天津：天津大学，200