资源约束项目调度问题的粒子群优化算法求解

介绍了应用粒子群优化算法求解资源约束项目调度问题的实现方法。建立了资源约束项目调度问题的数学模型，提出了确定资源约束项目调度问题解空间的办法。采用不同的策略处理前后约束和资源约束。编制了粒子群优化通用程序并对典型项目实例进行了优化，优化结果验证粒子群优化算法求解资源约束项目调度问题的有效性。

基于Q—学习的超启发式模型及算法求解多模式资源约束项目调度问题

为了更好地解决传统的元启发式算法机制单一和面向问题定制不足等问题,提高算法的整体通用性,本文提出一种基于Q—学习的超启发式模型,并基于该模型设计实现了一种超启发式算法,求解多模式资源约束项目调度问题(MRCPSP)。该模型架构分为高低两层,低层由具有多种异构机制和不同参数的元启发式算子组成,高层则依据Q—学习策略自动选择低层算子。模型将多种优秀的元启发式算法与反馈—学习强化机制有机整合,具备灵活的可扩展性。为检验算法效果,从MRCPSP标杆算例库中选取了上千个规模不等的算例,设计了等价比较实验环节,并与最新公开文献提供的结果进行了比较。结果表明,基于Q—学习的超启发式算法在目标值、通用性、鲁棒性等多项性能指标上均表现优异,可以借鉴应用到其他各种组合优化问题。值得一提的是,针对J30算例的计算结果有多达41个算例获得了比当前公开文献报告的已知最优解更好的结果。

一种求解资源约束项目调度问题的改进引力搜索算法

引力搜索算法虽然具有较强的搜索能力和较快的收敛速度,但是容易陷入局部最优,且求解精度并不尽如人意。针对具有资源和优先关系约束的资源约束项目调度问题,提出一种改进的引力搜索算法(improved gravitational search algorithm, IGSA)。该算法将向心力和混沌机制引入引力搜索算法中,一方面通过在不同寻优阶段对参数进行控制,平衡算法中粒子的探索能力与开发能力,防止算法陷入局部最优,提高解的精度和加快收敛速度;另一方面当随机数大于混沌序列的值时,对生成的解决方案执行插入或交换操作,增强算法的多样性。为了评估算法的有效性,在PSPLIB问题实例J30,J60,J90和J120上进行对比实验,结果表明,相较于对比算法,IGSA在求解RCPSP时能更快更准确地得到项目最小完工时间,且能充分利用资源,避免资源浪费。

求解多模式资源约束项目调度问题的离散粒子群算法

多模式资源约束项目调度问题(MRCPSP)是在传统的资源约束项目调度问题基础上增加多种执行模式和不可更新资源约束条件后,再寻求总完工时间的最小化。为此提出了一种改进的离散粒子群算法(DPSO)用于求解此类问题。为了验证算法的有效性,选取了不同规模的上千算例进行了测试,并与相关文献给出的结果进行了比较,各算例平均偏差均小于其他算法的计算结果,且获得最优解的百分比明显高于文献中其他算法的结果。表明该算法无论在计算精度还是计算效率方面都具有较强的可比性。

基于遗传算法的多模式资源约束项目调度问题研究

为解决多模式资源约束项目调度问题,提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解,基因的值表示任务的优先权和执行模式,每条染色体对应一个满足逻辑关系约束的可行任务排序,根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作,能够使搜索范围遍及整个问题解空间。实际应用表明,该算法能快速求得问题的最优解或近似最优解。

求解资源约束项目调度问题的启发式算法综述

本文综述了求解RCPSP的启发式算法。首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式算法的研究成果。此外,简要介绍除上述两大类启发式算法之外的其他几种启发式算法;最后,对全文进行总结,并指出该领域几个有希望的研究方向。

柔性资源约束项目调度问题的启发式求解方法

针对资源间可相互替换的柔性资源约束项目调度问题,提出一种启发式求解方法。该方法以项目活动网络图以及活动、资源间的相互关系为基础,对传统并行调度产生方法进行了改进,设计了一种更有效的柔性资源替代方法。该替代方法首先为同一时刻所有可调度活动分配所需的各类资源,然后以各类资源的剩余情况以及资源之间的替代关系为基础,优先选择剩余量最大的资源进行替代,保证活动都尽可能最早开始,以最小化项目工期。通过与现有方法的对比分析,验证了启发式求解方法的有效性,同时开发了操作简便的柔性资源约束项目调度系统。

随机资源约束项目调度问题基于序的果蝇算法

针对项目活动工期为随机变量的资源约束项目调度问题,提出一种基于序的果蝇算法.为了实现随机环境下解的有效评价,提出一种预选机制,并采用基于序的最优计算量分配技术.为了使果蝇算法能够求解资源约束项目调度问题,采用交换操作执行果蝇算法的嗅觉搜索,并采用保优更新操作执行视觉搜索.为了均衡算法的局部搜索和全局搜索能力,在标准果蝇算法中引入了协作进化环节并采用两点交叉操作加以实现.在不同随机分布的情况下,采用标准测试集进行仿真测试.与现有算法的比较结果验证了所提预选机制和基于序的果蝇算法的有效性.

基于模拟退火差异演化算法的资源约束项目调度问题研究

资源约束项目调度问题是工程管理领域研究的热点之一,但无论是模型构建还是求解均有一定的难度,尤其是模型求解已被证明是NP-hard问题。鉴于此,构建了以工期最短为优化目标的项目调度模型,为便于求解,将模型的显性约束和隐性约束做了适当处理,并利用差异演化算法较强的记忆能力和全局收敛能力以及模拟退火的局部跳出能力,将模拟退火算法和差异演化算法进行有效结合。通过工程实例,分别采用遗传算法、差异演化算法以及模拟退火差异演化算法进行求解。结果表明,3种算法都可以收敛到最优解,但论文算法具有较大的搜素范围与局部寻优能力,同时求解的稳定性指标明显优于遗传算法和差异演化算法。

折现流多模式资源约束项目调度问题研究

针对带折现现金流的多模式资源约束项目调度问题研究,在考虑实际工程中对最终净现值产生影响的多种因素的基础上,建立以最大化现金流净现值为优化目标的非线性数学模型,提出一种改进的遗传模拟退火算法对模型进行求解.该算法利用遗传算法进行全局并行搜索,种群每个新产生的个体在交叉和变异后采用模拟退火技术进行局部串行优化,使之移动到最近的局部最优点再进入下一代迭代.采用针对活动的整数编码方式,基因的值表示活动的优先权和执行模式,每个个体对应一个满足时序约束和资源约束的项目调度方案.仿真结果表明,新算法能有效地对多模式资源约束项目调度问题做出合理调度,使项目收益最大化,并且比传统的遗传算法具有更高的求解质量和求解效率,为承包商在项目投资和进度管理上提供了定量化决策支持.

一种资源约束项目调度问题的遗传算法

资源约束项目调度问题是项目管理研究的大问题,对于项目管理的研究者和实践者都非常重要,该问题理论上属于NP难题。针对经典资源受限项目调度问题,本文结合教学算法和遗传算法,提出了一种新的智能优化算法——教学遗传算法来求解。通过对资源受限项目调度标准数据集PSPLIB中多个项目调度问题的仿真及与现有文献中的相关算法的比较,验证了所提算法的有效性。

基于CPM的多模式资源约束项目调度建模与复杂度分析

为有效降低多模式资源约束项目调度模型的复杂度和解空间,构建3类混合整数线性规划模型。运用紧上界TTUB缩减时间序列T的上界和关键路径法缩减各项活动结束时间的上下界,以降低模型复杂度和解空间。为验证改进模型的有效性,从MRCPSP标杆案例库中选取1106组规模不等的算例进行求解。结果表明,基于CPM的多模式资源约束项目调度模型解空间更小;决策变量同比缩小3~65倍,约束数同比缩小1~4倍;平均求解时间同比减少53%~112%,求解性能显著优于其他模型。为验证紧上界T_(TUB)的参数α性能,1106组算例结果表明,α越接近1,模型的复杂度越低,解空间越小。但随着算例规模增加,算例可行解探寻难度增加。因此,对大规模算例,α值应适当放宽。

一种施工场地制约下的空间干涉型资源约束项目调度问题

施工场地有限普遍地存在于以地铁建设为典型代表的一类大型复杂工程项目中,同时空间干涉严重阻碍了项目进度的顺利实施。首先,构建包含空间资源约束的整数规划模型。其次,设计出基于空间资源布局算法的修正调度计划生成机制,将其作为解码策略嵌入遗传进化过程,形成求解本文模型的混合遗传算法。最后,对基准算例J30进行空间资源参数配置获得适合问题的测试算例S-J30,实施大规模数值测试实验。将经典资源约束项目调度问题的工期(理想的项目工期)作为本研究问题目标值的下界,设计实验测试指标。研究表明,所提出的混合遗传算法能够有效减少项目工期偏差,并且具有良好的适应性和稳定性。

基于改进多种群遗传算法的多目标资源受限项目调度问题研究

多目标资源受限项目调度问题普遍存在于生产经营活动中,具有较高的实用价值。本文提出了一种改进的多种群遗传算法以解决多目标资源受限项目调度问题,为改变现有算法计算步骤理解困难、不易推广的特点,巧妙地通过平移工作解决此类问题,算法首先对工作的优先级进行随机编码,然后根据工序约束进行解码,并根据解码结果安排工作调度,同时为防止无效迭代,融合了禁忌搜索的思想。最后,通过PSPLIB标准算例库中算例进行实验,实验结果表明该算法在具备较高精度的同时,兼顾了快捷性和简洁性。

多资源约束的项目调度问题离散粒子群算法

提出了一种求解多资源约束项目调度问题的离散粒子群算法。调度方案采用了优先权整数编码方法,使用稀疏存储邻接矩阵判定先后约束,使用活动单位时间推迟策略来满足资源约束。算法的创新点在于直接使用了整数编码的调度方案参与迭代计算,并依据计算结果提供的信息做出位置交换。不但解决了处理离散整数编码粒子的难题,而且容易实现,亦可推广至类似整数编码优化问题。测试用例计算结果表明了算法的可行性和有效性。

面向资源约束项目调度的二阶段帝国竞争算法

资源约束项目调度问题是一类经典的组合优化难题,有着广泛的工程应用背景。自20世纪60年代起,该问题的优化方法层出不穷,但大多数智能优化算法在该问题空间中搜索表现一般。针对这一挑战,提出了一种二阶段演化帝国竞争算法(TSE-ICA)。首先,基于由关键路径法得到的组块提取策略,提出两种分别用于种群多样性开发和高效收敛的同化算子,通过在不同阶段选择合适的同化算子实现二阶段演化框架的构建。其次,基于组块的改进革命机制包含插入和乱序两种邻域搜索策略,帝国竞争机制则通过收集不同帝国的收敛信息实现参数的自适应调整;最后,利用记忆库引导种群进化,提高算法的收敛速率。TSE-ICA的最佳参数设置由Taguchi法的实验设计方法确定。数值实验面向典型实例库PSPLIB中的3个实例集J30、J60和J120对TSE-ICA执行了性能测试,并基于两种评价标准与17种先进的元启发式算法进行性能对比。实验结果显示,TSE-ICA具有较好的优化性能和收敛效率,初步验证了所提改进机制的有效性和所提算法的问题适用性。

甲供非商品化资源约束下可中断项目群调度模型

不可更新资源的约束会导致项目群中各合同项目开工延误甚至施工中断。针对不可更新资源受限理论研究存在的局限性,开展了多种甲供非商品化资源(NCRPE)约束下可中断项目群调度问题的研究。首先,由于资源分配多样性会给项目群进度造成不确定性影响,围绕项目群工期—延误成本双目标优化模型展开研究,采用改进编码方式的多目标粒子群算法(MOPSO)进行求解,获取项目群的资源分配方案,利用串行调度生成机制(SSGS)得到项目群进度计划;其次,将MOPSO算法和NSGA-II算法进行对比,通过IGD和HV两个指标来衡量MOPSO算法求解该问题的有效性;最后,结合实际案例,对模型进行求解分析。在甲供非商品化资源约束和项目可中断情况下,构建的项目群调度模型能够有效地实现项目群工期和合同项目延误成本的双目标优化。研究成果为业主合理分配NCRPE以及进行项目群调度提供理论依据。

面向资源约束的电动公交车充电调度策略

为减少公交运营成本、合理制定插入式充电模式下公交总站的电动公交车充电调度方案,本文基于帝国竞争算法提出了一种面向资源约束的公交车充电调度策略(RCO-CSS)。基于电动公交车运营的时空特点和充放电特性,应用多技能资源约束多项目调度问题(MSRC-MPSP)运筹规划思想对电动公交车充电问题进行抽象建模,以车队规模与充电桩数量为主要资源参数,以最小化充电成本和日均设备购置成本为目标,构建资源约束充电调度模型,进而设计一种二阶段演化帝国竞争算法(TSE-ICA)对模型进行求解,输出最佳的充电调度方案及匹配的行车运营计划。采用4个分别包含5、10、20和36条线路的公交运行实例对RCO-CSS进行了性能评估与有效性验证。在实例探讨中,首先运用Taguich法对资源参数进行了敏感性分析,发现资源越宽裕,模型输出的日充电费用越小,但车辆与充放电设备平摊至每日的购置成本越大;其次,将TSE-ICA与其他4种先进的元启发式算法进行实验数值对比,验证了所提算法的寻优性能;最后,通过与无序充电调度策略和常规有序充电调度策略进行比较,证明了RCO-CSS能够更好地降低用电成本、设备购置成本和电池充放电次数。基于MSRC-MPSP和TSE-ICA的RCO-CSS为公交运营商制定充电调度方案和行车运营计划提供了一种可行且敏捷高效的新思路。

柔性资源约束的资源水平项目调度问题

为解决单件企业对柔性资源的高效均衡使用问题,提出了柔性资源约束的资源水平项目调度问题,设计了基于两级映射网络的柔性资源模型表达任务-能力-资源的关系,建立了问题的数学模型。为求解该模型,提出基于改进串行调度生成模式和网络最大流柔性资源分配模型的路径重连算法。基于改进串行调度生成模式对标准串行调度生成模式进行改进,使生成的调度更有利于资源水平。基于网络最大流的柔性资源分配模型反映了任务-能力-资源关系的本质,有效解决了柔性资源分配问题。通过在改造的项目调度测试问题集上进行数值实验,证明了该算法具有较高的求解质量和较好的时间性能。

求解资源受限项目调度问题的约束规划/数学规划混合算法

利用约束规划(constraint programming,CP)与数学规划(mathematical programming,MP)结合的方法求解调度问题已经获得了一些较好的研究成果,正成为调度问题研究领域的一个新的热点研究方向.本文针对求解资源受限项目调度问题(RCPSP)的整数规划模型,设计了基于CP技术的问题和模型预处理方法,证明了整数规划模型的有效不等式定理,提出了通过将项目子网络图转化为加权最大团问题求解后获得有效不等式的方法.引用标准问题库PSPLIB中的一组典型问题进行求解实验,结果表明本文提出的有效不等式可以明显改进模型的求解质量和时间性能.论文最后对实验结果进行了深入讨论,讨论了未来的研究方向.