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

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

一种求解工程调度中资源水平问题的遗传算法

结合资源受限情况下工程调度中资源水平问题的特点 ,提出了一种有效的遗传算法 .文中对解的编码方式、遗传算子的定义及算法结构进行了描述 .通过对大量被普遍应用的标准问题的求解实验表明 ,遗传算法是求解 RLP的一种有效算法 .     

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

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

基于文化遗传算法的资源受限项目调度

资源受限项目调度问题作为一类典型的组合优化问题,理论上属于NP难题.本文结合文化算法和自适应遗传算法的优点,提出一种新的智能优化算法--文化遗传算法来求解资源受限项目调度问题.算法设王了两类空间:群体空间和信仰空间.各空间采用不同的自适应遗传算法进行独立进化,进化过程中利用同步式传输方式定期通过接受操作和影响操作来更新信仰空间和群体空间.为避免各空间的局部收敛同题,文中使用正弦函教和余弦函数自适应控制交叉概率和变异概率以保证群体的多样性.通过对标准数据库PSPLIB中的多个问题的仿真,结果表明:此算法在解决资源受限项目调度问题时不仅具有全局收敛性,而且在一定程度上具有较好的收敛速度.     

基于优先规则的活动成本目标资源受限工程调度

首先给出了该问题的数学模型,问题分析得出该问题也是一类NP完全问题,继而讨论了启发式方法进行问题求解的基本思想,基于此,结合活动成本目标的特性提出了问题求解的串行调度方案和并行调度方案,并设计了相应的几种优先规则,分析了算法的时间复杂性.基于改造PSPLIB中的单模式算例测试,并行调度方案的结果大多优于串行调度方案,而在最大最早完成时间和最大活动先序相关成本等两种优先规则下的调度方法计算效果相对较好.     

带有缓冲区的资源受限调度问题的滚动时域求解算法

研究带有缓冲区的资源受限调度问题,设计了两种使用滚动时域策略的启发式算法TWBA和FWBA,通过依次处理一定量任务,尽可能使得调度所产生的费用最小.为了评估算法性能,进行了大量模拟研究,在不同条件下找出相应的最优的处理周期或者是最优决策时刻,仿真结果表明了新算法在应用中有较好的性能,并且得到比在线算法更优的调度结果.     

求解项目调度中资源水平问题的近似算法

针对RLP与RCPSP的相似之处和自身特点，以求解PCRSP的遗传算法为基础，设计了一种求解RLP的基于分支定界策略的近似算法，搜索树的每一节点对应一个RCPSP，通过求解各节点RCPSP来求得RLP的最优调度计划，算法从具有基本资源需求水平的根节点开始，采用宽度优化顺序逐渐提高各种资源的可用量，既有利于资源的均衡利用，又可以通过定界策略有效地控制搜索树的节点数量，结合实例问题说明了基于分支定界策略的近似算法的求解过程，最后通过实例问题对该算法与遗传算法进行求解效果和时间效率的对经，分析了对比结果。     

多执行模式资源受限工程调度问题的优化算法

近几年来,模拟退火（ＳＡ）和遗传算法（ＧＡ）等智能优化方法在求解组俣最优化问题显示出了较强的能力,许多文献报告了它们在这类问题上的应用,有些文献则报告了一些它们的混合算法,然而,定些算法对问题的求解效果因问题的结构不同而有限大差异,它们的成功必须充分结合问题本身的特点,本文针对多执行模式资源受限工程调度问题的特点,设计了一种ＳＡ／ＧＡ混合算法,利用被普遍应用的标准问题对该算法进行了测试,取得了令人满意的结果。     

采用混合策略遗传算法求解一类资源约束最短时间调度问题

资源约束最短时间调度问题是一类ＮＰ完全问题,求解难度相当大,本文提出一种采用混合策略的遗传算求解该类问题,混合策略中包含启发式的调度规则。理论分析表明本文提出的混合策略的遗传算法是全局收敛的,实际应用表明该算法快速有效优于传统算法。     

资源受限单机动态调度的并行GA算法研究

研究资源受限系统动态调度问题，针对时序约束问题提出一种并行遗传算法(PGA)。给出满足排序优先次序约束的一种基因编码方法；采用不破坏优先级可行性的交叉操作，并予以证明：建立一种并行处理机制，使搜索避免出现局优现象。在技术允许情况下，单机动态调度引入抢占式加工方式，会一定程度上提高系统的性能。通过仿真试验验证，并行OA算法可兼顾优化效果和计算效率，解决单机动态调度问题。     

Memetic algorithm for multi-mode resource-constrained project scheduling problems

A memetic algorithm （MA） for a multi-mode resourceconstrained project scheduling problem （MRCPSP） is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called ＂strategic oscillation＂ to make the search process have a higher probability to visit solutions around a ＂feasible boundary＂. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.     

Hybrid ant colony optimization for the resource-constrained project scheduling problem

To solve the resource-constrained project scheduling problem (RCPSP), a hybrid ant colony optimization (HACO) approach is presented. To improve the quality of the schedules, the HACO is incorporated with an extended double justification in which the activity splitting is applied to predict whether the schedule could be improved. The HACO is tested on the set of large benchmark problems from the project scheduling problem library (PSPLIB). The computational result shows that the proposed algorithm can improv...     

活动成本目标MMRCPSP并行调度方案

给出了考虑可重用资源约束的活动成本目标多模式资源受限工程调度问题的数学模型,结合多模式问题的特性给出了并行调度方案,提出了一种活动—模式联合调度策略,并设计了模式的优先调度规则,其中考虑了活动先序相关成本因素,包括悲观的先序相关成本因素、乐观的先序相关成本因素和折衷的先序相关成本因素。基于改造PSPLIB的算例测试表明,在考虑折衷的先序相关成本因素时所取得的计算效果相对较好,可以在现实工程调度中作为主要优先规则来使用。     

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

设计了一种求解模糊多目标资源受限项目调度问题的遗传局域搜索（GLS）算法,目标是生成近似有效解集以便决策者在决策过程中有更多的选择．算法利用线性加权效用函数将多目标组合优化问题转换为单目标组合优化问题,通过系统的方法生成目标权系数向量,对于每次生成的权系数向量,调用GLS算法求解以极小化效用函数为单一目标的子问题,由此生成的近似有效解集更加具有多样性．实验结果表明：本文算法可以针对多目标资源受限项目调度问题生成较好质量的近似有效解集,在多数指标上优于其它两种对照算法．     

SOLVING RESOURCE—CONSTRAINED PROJECT SCHEDULING PROBLEMS WITH BI—CRITERIA HEURISTIC SEARCH TECHNIQUES

In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm forsolving multiple resource-constrained project scheduling problems. The heuristic solves problems intwo phases. In the pre-processing phase, the algorithm estimates distance between a state and the goalstate and measures complexity of problem instances. In the search phase, the algorithm uses estimatesof the pre-processing phase to further estimate distances to the goal state. The search continues in astepwise generation of a series of intermediate states through search path evaluation process withbacktracking. Developments of intermediate states are exclusively based on a bi-criteria new stateselection technique where we consider resource utilization and duration estimate to the goal state. Wealso propose a variable weighting technique based on initial problem complexity measures.Introducing this technique allows the algorithm to efficiently solve complex project schedulingproblems. A numerical example illustra     

关键链项目调度模型及遗传算法求解

对项目管理的关键链方法(CCM)进行了研究.在资源受限项目调度问题(RCPSPs)模型的基础上,引入关键链方法,建立了关键链项目优化调度模型.提出了一种基于优先权的关键链计划生成方案,该方案根据任务优先权排序生成积极计划,定义项目唯一关键链.将输入缓冲区作为虚任务对项目计划进行二次调度,解决了在嵌入输入缓冲区时产生的资源冲突问题.设计了一种混合遗传算法寻找最优任务优先权排序,实现对CCM项目优化调度模型的求解.最后,通过大量的仿真测试验证了所提出的模型和算法的有效性.     

项目进度中的离散时间-费用决策问题研究

离散时间-费用权衡问题(DTCTP)是项目进度文献中被研究最多的双目标优化问题,它通常以三种形式出现:1)P1:截止日期问题;2)P2:预算问题;3)P3:工期-费用曲线问题.然而,对问题研究都集中在P1上,P2被关注较少.首先建立了与一般项目网络对应的P2的数学模型,在分析模型特征基础上,设计求解模型的遗传算法.最后,通过3个数值实例,验证模型的正确性和算法的有效性.