基于改进NSGA-II算法求解多目标资源受限项目调度问题

资源受限项目调度问题(resource constrained project scheduling problem, RCPSP)要求在满足相关约束的条件下安排各活动开始时间,从而达到某一目标的最优,具有很强的应用背景,并受到众多学者的广泛关注.经典的RCPSP模型以最小化项目工期为单一目标,忽略了资源使用率等因素对项目整体的影响,使其与实际应用仍有较大差距.基于经典的RCPSP模型,引入最优资源均衡为另一目标,将模型扩展为多目标模型,丰富了RCPSP模型的应用场景.同时,考虑到新模型中各活动间存在大量的控制关系,使用传统的启发式多目标算法需要耗费大量的时间对不可行解进行判断,求解性能较低,提出一种新的算法框架NSGA-IIs.该算法框架基于活动间控制关系将各活动分成若干子集,并在初始化和交叉变异等阶段以子集为基本单位产生新的个体,能够较好地避免不可行解的产生,提高算法的效率.使用解集覆盖度作为评价指标,通过实例数据集的实验表明,与已有的求解RCPSP的经典算法相比,所提出的算法具有明显的优越性.     

一种求解多目标资源受限项目调度的遗传算法

采用基于非支配性排序的多目标遗传算法—NSGA－Ⅱ,设计了一种求解多模式、多种类资源约束的多目标资源受限项目调度问题的遗传算法,该算法所设计的编码包含两部分,一部分为一个任务链表,另一部分为任务链表中各任务所对应的执行模式组成的模式向量。将所设计的算法用于求解文献中的以项目总工期和资源均衡为目标的农业项目调度问题,结果表明此算法对于求解多目标资源受限项目调度问题是有效的。     

基于GMOGSO的多目标流水车间调度问题

针对缓冲区有限的多目标流水车间调度问题, 提出一种基于Pareto 最优的广义多目标萤火虫算法. 通过引入交换子和交换序将基本萤火虫算法离散化, 并将算法拓展为全局搜索过程和局部搜索过程. 进化初期采用全局搜索将种群推向较优区域, 进化中后期采用捕食搜索策略使算法主体在全局搜索和局部搜索间智能切换, 从而保证全局与局部的平衡. 动态变步长策略进一步增强了算法搜索能力. 通过算例测试验证了所提出算法的有效性.

     

基于环境经济调度问题的空间自适应划分多目标优化

提出一种基于空间自适应划分的多目标优化算法. 为了增强种群的收敛性和多样性, 多维搜索空间被划分成多个网格, 网格内的粒子通过共享“引导”粒子的经验信息调整自身的速度和位置, 并引入年龄观测器实时记录引导粒子对Pareto 解集所做的贡献, 及时更新引导粒子, 以增强算法的全局搜索能力. 对多目标测试函数以及环境经济调度问题进行了仿真实验, 实验结果表明, 所提出算法能对解空间进行更加全面、充分的探索, 快速找到一组分布具有较好的逼近性、宽广性和均匀性的最优解集合.

     

蚁群算法在资源受限项目调度问题中的应用

资源受限的项目调度问题(RCPSP,Resource-ConstrainedProjectSchedulingProblems)已经被证明是一种NP-hard的组合优化问题,随着问题规模的增大,使用经典的数学方法如数学规划等方法,已经很难解决问题。论文提出了一种用于求解资源受限的项目调度问题的蚁群算法。针对资源受限的项目调度问题的具体特点,提出了蚂蚁巡游网络图的动态生成方式,信息素的表示及更新方式,以及启发信息的计算方法。针对PSPLIB中的测试集对算法中的主要参数进行了优化,最后,使用PSPLIB中的四种测试集对算法进行了测试,计算结果表明了算法的有效性。     

人工蜂群算法求解资源受限项目调度问题

针对资源受限项目调度问题,提出了一种基于人工蜂群算法的优化方法。人工蜂群算法中每个食物源的位置代表一种项目任务的优先权序列,每个食物源的位置通过扩展串行调度机制转换成可行的调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新。实验结果表明,人工蜂群算法是求解资源受限项目调度问题的有效方法,同时扩展调度机制的引入可以加速迭代收敛的进程。     

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

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

多目标资源优化分配问题的Memetic 算法

针对传统算法求解多目标资源优化分配问题收敛慢、Pareto解不能有效分布在Pareto 前沿面的问题, 提出一种新的Memetic 算法. 在遗传算法的交叉算子中引入模拟退火算法, 加强了遗传算法的局部搜索能力, 加快了收敛速度. 为了使Pareto 最优解均匀分布在Pareto 前沿面, 在染色体编码中引入禁忌表, 增加了种群的多样性, 避免了传统遗传算法后期Pareto 解集过于集中的缺点. 通过与已有的遗传算法、蚁群算法、粒子群算法进行比较, 仿真实验表明了所提出算法的有效性, 并分析了禁忌表长度和模拟退火参数对算法收敛性的影响.

     

蚁群算法在资源受限项目调度中的应用

本文描述了在应用蚁群算法求解资源受限项目调度问题时,蚂蚁如何在项目网络图上巡游并动态生成最优解,以及蚁群信息素的更新方式和多种启发式信息的定义方法,验算了算法在不同的参数组合下对测试案例的求解效果。     

不确定可靠性优化问题的多目标粒子群优化算法

针对元件可靠性为区间值的系统可靠性优化问题, 提出一种区间多目标粒子群优化方法. 首先, 建立问题的区间多目标优化模型; 然后, 利用粒子群算法优化该模型, 定义一种不精确Pareto 支配关系, 并给出编码、约束处理、外部存储器更新、领导粒子选择等关键问题的解决方法; 最后, 将该方法应用于可靠性优化问题实例, 验证了方法的有效性.

     

基于多班教学优化的多目标分布式混合流水车间调度

单工厂环境下的混合流水车间调度问题已受到广泛关注,而多工厂环境下的分布式混合流水车间调度问题(distributed hybrid flow shop scheduling problem,DHFSP)研究进展则较小.针对考虑顺序相关准备时间的DHFSP,提出一种多班教学优化(multi-class teaching-...     

求解异构并行机调度问题的混合多目标教-学优化算法

以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。     

不确定资源约束下项目鲁棒性调度算法*

在跨企业项目中,由于资源可用时间具有不确定性,从而使得项目计划具有易变性。针对这一问题,首先采用模糊集对项目的不精确时间参数和资源不确定性进行了表示,并在同时考虑调度的质量鲁棒性和解的鲁棒性情况下,定义了调度的鲁棒性度量,进而开发了遗传算法来求解不确定资源约束下的项目鲁棒性调度问题。最后,给出了应用实例,并通过仿真分析说明算法的有效性。该算法已被应用到跨企业项目管理系统中,获得了良好的效果。     

基于环境Pareto 支配选择策略的有约束多目标差分进化算法

在处理有约束多目标问题的进化算法中, 目前普遍采用Deb 教授提出的约束占优的直接支配选择策略. 在约束处理中, 优秀不可行解与优秀可行解同样重要, 但在直接支配选择策略中, 不可行解被选择的几率很小. 针对此问题, 设计一种环境Pareto 支配的选择策略, 并基于此提出用于解决有约束多目标问题的差分进化算法. 对经典测试函数进行仿真计算, 结果表明, 与其他算法相比, 所提出的算法具有更高的收敛性和稳定性.

     

不确定资源受限项目调度研究综述

不确定资源受限项目调度问题(RCPSP)是研究在不确定环境和有限资源约束下如何合理安排项目活动,以实现既定目标的最优化.不确定RCPSP具有很强的工程背景,在学术和应用上均具有很高的研究价值,但存在大规模、强约束、多极小、多目标和不确定等诸多复杂性,求解非常困难.为此,介绍了不确定RCPSP的数学描述和几种具体形式,重点综述了不确定RCPSP的算法进展,并归纳了相关的应用成果,最后指出了有待进一步研究的若干方向和内容.     

基于个人偏好的多目标优化问题目标权重计算方法

针对多目标优化过程中如何根据个人偏好确定各目标权重的问题,提出一种约束优化方法以获得各目标的最佳权重.首先,将目标权重计算问题转化为综合适应度最大方差计算问题;然后,将个人偏好转化为最大方差问题不等式约束条件;最后,利用遗传算法和梯度投影法求解约束优化问题以获得最佳的目标权重.在电力机车故障维修策略决策过程中应用该算法计算各部件经济性、安全性等目标权重,实验结果验证了所提出方法能够获得满足个人偏好的最佳目标权重.     

自适应动态重组多目标粒子群优化算法

提出一种自适应动态重组粒子群优化算法. 该算法采用凝聚的层次聚类算法, 将种群分成若干个子群体, 用一个精英集对非支配解进行存储; 根据贡献度和多样性, 对各子群体的粒子和整个种群进行自适应动态重组; 同时引入扰动算子对精英集存储的非支配解进行扰动, 实现对精英集进行动态调整. 利用具有不同特点的测试函数进行验证并与同类算法相比较, 结果表明, 所提出的算法可加快收敛速度, 提高种群的可进化能力.

     

趋磁性细菌多目标优化算法

提出趋磁性细菌多目标优化算法(MTBMO).该算法以趋磁性细菌优化算法(MBOA)中磁小体(MTSs)的生成机制为基础,设计适用于多目标优化的新型MTSs磁矩调节机制,确保群体的收敛性;同时采用基于混沌变异的替换方法取代MBOA中的磁小体替换机制来增强群体的多样性.通过标准函数测试和与现有多目标优化算法的比较表明,MTBMO对于求解多目标优化问题(MOPs)是可行且有效的.     

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

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