蚁群-粒子群算法求解多模式资源受限项目调度问题

通过分析多模式项目调度问题的特点,提出一种主、从递阶结构的蚁群粒子群求解算法。算法中,主级为蚁群算法,完成任务模式选择;从级为粒子群算法,完成主级约束下的任务调度。然后,以工期最小和资源均衡分配为目标设计蚂蚁转移概率、模式优选概率和任务优选概率。最后,针对PSPLIB中的测试集对算法主要参数进行优化,并通过与其他算法比较验证了算法的有效性。

一种求解多模式资源受限项目调度问题的新方法

针对多模式项目调度问题特征,提出一种蚁群&遗传混合求解算法。该算法以工期最小化为目标,在满足资源和时序约束前提下,设计蚂蚁任务模式优选概率、信息素更新方式、遗传算子。在算法求解过程中,蚁群算法通过人工蚂蚁在有向网络图上巡游逐个确定任务模式,生成任务模式链表。在此基础上,遗传算子对任务模式链进行改进,并利用串行进度生成机制生成可行的项目调度方案。最后,利用PSPLIB测试集验证了算法的有效性。

带有活动重叠的多模式资源受限项目调度问题

为了缩短项目工期、优化资源利用效率,研究了带有活动重叠的多模式资源受限项目调度问题,构建了活动重叠—返工时间因子矩阵,对多模式下的活动重叠和返工时间进行了完整的数学描述,以最小化项目工期为目标,建立了带有活动重叠的多模式项目调度优化模型;设计了改进的遗传算法并对问题进行求解,在经典的双链编码遗传算法的基础上,设计对初始种群活动链的预处理阶段以加速算法的求解效率,并针对多模式活动重叠问题设计了专门的解码方法。通过实验研究验证了该算法较其他方法具有更好的求解能力和表现,以一个小规模算例演示了模型在处理工期缩短问题上的有效性。通过全因子实验设计分析了问题参数对缩短项目工期的影响,为项目管理者确定项目调度方案提供了决策依据。

基于遗传算法的多模式资源受限项目调度问题

针对多模式资源受限项目调度问题,采用问题任务链表和模式链表的双链表结构的编码方式、串行调度生成方案的解码方式对传统遗传算法进行改进,并通过交叉、变异、选择等算子进行全局性概率搜索确定较优方案。针对PSPLIB中的基准问题对该算法进行验证,证明该算法的有效性。

多模式资源受限项目调度问题的混合遗传算法

多模式资源受限项目调度问题是一种NP难的组合优化问题.提出了与基于关键链的启发式算法相结合的二层混合遗传算法对该问题进行求解.在由上层算法确定的调度顺序下,下层遗传算法结合基于关键链的启发式算法,对系统资源重新优化配置,使算法加速向最优解区域收敛,并在下层设计了随迭代代数增加的可变变异概率,以避免早熟收敛.利用标准问题库对算法进行测试,分析问题参数与算法参数对算法结果的影响,发现实验结果的绩效随迭代数的增加而提高,算法耗时随任务数和迭代数的增加而增加.数值测试结果验证了算法的可行性和可靠性.

多模式资源受限项目调度问题的优化方法

为求解多模式资源受限项目调度问题,提出了一种结合粒子群优化算法(PSO)和基因表达式编程(GEP)的混合优化算法。其中,PSO用来提供活动执行模式组合,GEP用来构造在给定活动执行模式下的调度规则。调度规则由项目状态和活动属性构成,与其他优化方法相比,这是一种新的编码方式与求解方法,也更符合实际应用。对于粒子所表达的不可行活动模式的组合,设计了粒子调整算法,以满足项目调度中可更新资源和不可更新资源总数的约束。最后给出了混合优化算法求解步骤,并采用该算法对项目实例进行了计算与分析,验证了算法的有效性。

多模式资源受限项目调度问题的双目标优化

除了追求项目工期最短,减少资源需求量波动也是项目管理者需要考虑的问题,但在实际项目执行时,追求较均衡的资源需求量则有可能导致项目延期,因此需要进行项目工期和资源均衡程度的权衡。综合考虑资源的多样性与活动的多执行模式,以项目工期和资源均衡为优化目标,建立多模式项目调度问题的双目标优化模型。提出一种基于非支配排序遗传算法的双目标混合遗传算法来求解问题的帕累托最优解,在算法中设计违背约束的惩罚方法和可行解的筛选过程。通过算例分析验证模型与算法的有效性,并分析网络参数和资源强度对帕累托解集的影响,说明求解帕累托解集的必要性,为项目管理者确定项目调度方案提供决策依据。

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

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

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

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

多模式资源受限项目调度问题的混合优化算法研究

基于可抢占式的多模式资源受限的项目调度问题,本文充分利用遗传算法全局搜索能力强和禁忌搜索局部搜索能力强的特点,提出一种引入禁忌机制的遗传算法混合优化求解策略,可有利于帮助搜索程序提高寻优能力,并探讨算法中各参数的选取、设置及算法的实现方法。通过对标准数据库(PSPLIB)中的多模式资源受限项目调度问题的实例进行验算及与其他优化方法的结果比较,验证了本文所提方法的有效性和优越性。

柔性资源受限的多模式项目调度问题的建模

将资源受限的多模式项目调度问题中的资源拓展为柔性资源,建立了柔性资源受限的多模式项目调度问题的混合整数规划模型。基于PROGEN生成了项目非虚活动数目为10的2 500个算例,利用XPRESS软件进行了精确求解。对5种项目特征参数即项目网络复杂度、能力需求强度、能力供给强度、资源柔性值和资源数目与问题求解难度、项目总完工时间和项目资源利用率之间的关系进行了分析。指出资源柔性值和资源数目的增加虽然能够减少项目完工时间平均值,但是也可能导致资源利用率平均值的下降,对柔性资源进行合理调度才是项目管理的关键。

基于免疫遗传算法的多模式资源受限养护工程调度问题研究

公路养护工程项目调度通常会受现场资源与施工工期的限制,针对基本遗传算法不能有效解决多模式资源受限养护工程调度问题(MRCPSP),将生物免疫系统中抗体多样性的维持机制应用到养护工程调度管理,构建一种采用双链表结构编码方式(随机优先权值链表和模式链表)、串行调度生成机制解码方式的免疫遗传算法,通过选择、交叉、变异和记忆库更新算子进行全局搜索确定较优项目调度方案.运用PSPLIB问题库中的基准问题对该算法进行验证,以证明该算法的可行性和有效性.

基于改进遗传算法的船舶维修项目调度问题研究

船舶维修项目调度问题是典型的受优先关系和维修空间限制的资源受限项目调度问题。针对该问题,文章建立了一种船舶维修项目调度数学模型,并提出了改进遗传算法进行求解。基于问题的特征,改进遗传算法主要采用解码与编码策略、选择操作、交叉操作以及变异操作等方法平衡算法的探索和探寻能力。最后,采用工程实例验证了模型的合理性和算法的优越性。

一种求解资源受限多项目调度问题的分解算法

针对资源受限多项目调度的多目标优化问题,采用约束逐层分解策略,提出了依次处理项目时序约束和资源约束的两阶段分解算法。第一阶段为时序约束优化阶段,采用蚁群算法进行任务列表的优化求解。通过改进信息素增量规则并采用并联进度生成机制,提高蚁群算法的求解效率和质量。其中,在构建任务合成链表的过程中遇到并联活动抢夺资源情形,采用基于熵权的逼近理想解排序法和基于有序加权平均算子的多属性决策方法来确定活动的综合权重,并依据权重对冲突活动进行排序,实现资源的冲突消解。第二阶段为资源约束优化阶段,以获得的优化任务合成链表为输入,逐项进行资源能力约束的核查与调整,最终生成项目调度的优化方案。通过多项目算例仿真结果验证了所提方法的有效性。

一种求解资源受限项目调度问题的自适应遗传算法

遗传算法(GA)应用在经典资源受限项目调度问题中取得了显著的效果。本文提出了一种新的编码方法,亦即在任务链表后面加上两个基因,一个是表示解码规则的S/P基因,另一个是表示解码方向的F/B基因,由这两个基因同时控制任务链表的解码规则和解码方向。为了验证其有效性,选用标准数据库PSPL IB中的156个例子进行验证,结果表明:本算法优于采用编码为任务链表和带有S/P基因的任务链表的两个遗传算法。本算法的设计思想对于解决相关组合最优化问题具有一定的指导意义。

求解模糊资源受限项目调度问题的遗传算法

本文研究了以排序健壮性最大为优化目标的具有模糊加工时间和模糊交货期的资源受限项目调度问题,采用六点模糊数表示模糊加工时间和模糊交货期,引入了2种模糊数的弱比较方法,即重心距离法和积分值法.针对这一优化问题设计了一种基于任务链表编码形式的遗传算法.数值实验结果表明该算法优于文献中的相关算法,同时实验结果也表明基于2种模糊数的弱比较方法对算法性能影响较弱.

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

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

带转移时间的资源受限项目鲁棒调度优化

为使项目在面临活动工期扰动时尽可能按照基准调度计划稳定执行,针对带转移时间的资源受限项目调度问题提出鲁棒调度与资源分配集成优化方法。分别从资源转移关系、活动时差、随机活动工期三个不同角度设计三种解鲁棒性代理指标,构建了两个混合整数规划模型(MinEA,MaxPF)和一个随机规划模型(MinTPC),并分别采用精确方法和禁忌搜索启发式算法求解;在此基础上提出MinTPC+MaxPF混合优化策略。仿真实验结果表明,MinTPC+MaxPF方法在项目解鲁棒性和质鲁棒性两方面均能获得最优绩效;MinEA方法的解鲁棒性优于MinTPC,而后者的质鲁棒性优于前者。所研究的模型和方法,可以为项目决策者在工期不确定环境下协调活动进度安排和优化资源转移提供指导,提升项目计划鲁棒性,提高企业的经济效益。

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

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

柔性资源受限的多项目调度问题研究

对国内外关于资源受限的多项目调度问题及柔性资源的现状进行研究,将资源受限的多项目调度问题中的资源拓展为柔性资源并展望了柔性资源受限的多项目调度问题的研究方向。