共查询到18条相似文献,搜索用时 125 毫秒
1.
资源受限项目调度问题是最具代表性的一类项目调度问题,是很多实际调度问题的抽象表示,属于NP-hard问题,对于大规模问题难以求得全局最优解。文中提出了问题的整数规划模型,通过将模型分解为约束主问题和子问题设计了求解线性松弛模型的列生成方法,然后通过分支定价寻找问题的整数解。在求解过程中引入松弛变量解决模型伪不可解的问题,设计了剪支策略和分支策略,并根据不同情况提出了两种缩小解空间的方法。在PSPLIB基准数据集上,对于有30个工序的问题,所提算法在10 m内能够求出480个问题中的301个问题的当前最优解;对于有60个工序的问题,在20 m内能够求出480个问题中的269个问题的当前最优解;对于有90个工序的问题,在30 m内能够求出480个问题中的263个问题的当前最优解。同时,算法使用缩小解空间策略后,超时算例的个数明显减少,优化初始解的性能得到明显提升。以上实验结果表明,所提算法具有较好的求解能力。 相似文献
2.
针对资源受限项目调度问题,提出了一种基于人工蜂群算法的优化方法。人工蜂群算法中每个食物源的位置代表一种项目任务的优先权序列,每个食物源的位置通过扩展串行调度机制转换成可行的调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新。实验结果表明,人工蜂群算法是求解资源受限项目调度问题的有效方法,同时扩展调度机制的引入可以加速迭代收敛的进程。 相似文献
3.
蚁群算法在资源受限项目调度问题中的应用 总被引:5,自引:0,他引:5
资源受限的项目调度问题(RCPSP,Resource-ConstrainedProjectSchedulingProblems)已经被证明是一种NP-hard的组合优化问题,随着问题规模的增大,使用经典的数学方法如数学规划等方法,已经很难解决问题。论文提出了一种用于求解资源受限的项目调度问题的蚁群算法。针对资源受限的项目调度问题的具体特点,提出了蚂蚁巡游网络图的动态生成方式,信息素的表示及更新方式,以及启发信息的计算方法。针对PSPLIB中的测试集对算法中的主要参数进行了优化,最后,使用PSPLIB中的四种测试集对算法进行了测试,计算结果表明了算法的有效性。 相似文献
4.
5.
《数字社区&智能家居》2008,(Z2)
本文描述了在应用蚁群算法求解资源受限项目调度问题时,蚂蚁如何在项目网络图上巡游并动态生成最优解,以及蚁群信息素的更新方式和多种启发式信息的定义方法,验算了算法在不同的参数组合下对测试案例的求解效果。 相似文献
6.
采用基于非支配性排序的多目标遗传算法—NSGA-Ⅱ,设计了一种求解多模式、多种类资源约束的多目标资源受限项目调度问题的遗传算法,该算法所设计的编码包含两部分,一部分为一个任务链表,另一部分为任务链表中各任务所对应的执行模式组成的模式向量。将所设计的算法用于求解文献中的以项目总工期和资源均衡为目标的农业项目调度问题,结果表明此算法对于求解多目标资源受限项目调度问题是有效的。 相似文献
7.
资源受限项目调度问题(resource constrained project scheduling problem, RCPSP)要求在满足相关约束的条件下安排各活动开始时间,从而达到某一目标的最优,具有很强的应用背景,并受到众多学者的广泛关注.经典的RCPSP模型以最小化项目工期为单一目标,忽略了资源使用率等因素对项目整体的影响,使其与实际应用仍有较大差距.基于经典的RCPSP模型,引入最优资源均衡为另一目标,将模型扩展为多目标模型,丰富了RCPSP模型的应用场景.同时,考虑到新模型中各活动间存在大量的控制关系,使用传统的启发式多目标算法需要耗费大量的时间对不可行解进行判断,求解性能较低,提出一种新的算法框架NSGA-IIs.该算法框架基于活动间控制关系将各活动分成若干子集,并在初始化和交叉变异等阶段以子集为基本单位产生新的个体,能够较好地避免不可行解的产生,提高算法的效率.使用解集覆盖度作为评价指标,通过实例数据集的实验表明,与已有的求解RCPSP的经典算法相比,所提出的算法具有明显的优越性. 相似文献
8.
资源受限工程调度问题的优化方法综述 总被引:3,自引:0,他引:3
由于资源受限的工程调度问题在理论上和实际中具有重要意义,近年来,国内外关于这一问题的优化方法有了较大的发展,因此根据收集到的资料,对求解这一问题的分支定界算法、基于优先规则的启发式算法、样本算法以及智能优化算法的最新发展进行简要概述,并指出了该问题未来的研究方向。 相似文献
9.
资源受限的项目调度问题的求解算法 总被引:1,自引:0,他引:1
本文建立了不确定资源环境下的资源受限的项目调度模型,用不确定规划的方法将不确定问题转化为等价的确定性问题,并给出了一个解决该问题的二阶段算法及实例。 相似文献
10.
11.
12.
13.
14.
15.
16.
研究多次抢占式资源受限的项目调度问题,假设任意时间点可作为资源抢占节点且抢占次数不受限制,建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法(GA)局部搜索能力缺陷,在算法中引入禁忌搜索(TS)进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数,并以标准算例集(Project Scheduling Problem Library,PSPLIB)对算法进行可行性检验。实验结果表明,资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期,设计的算法对问题求解效果良好。 相似文献
17.
18.
基于关键链的资源受限项目调度新方法 总被引:25,自引:0,他引:25
针对资源受限项目调度问题(RCPSPs)的实际需求建立了多目标优化调度模型,综合运用现有研究成果,设计了基于关键链的项目调度方法。该方法首先采用基于优先规则的启发式算法生成工期最小的近优项目计划,再在该计划中嵌入输入缓冲和项目缓冲,保证项目计划在非确定环境下的稳定执行。论文引用RCPSPs的标准问题库PSPLIB中大量案例对算法进行了的仿真试验,结果表明本文方法较传统项目调度方法有很大改进,论文最后对仿真结果进行了深入讨论,并指出了未来的研究方向。 相似文献