首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 140 毫秒
1.
基于遗传算法的多模式资源约束项目调度问题研究*   总被引:2,自引:0,他引:2       下载免费PDF全文
为解决多模式资源约束项目调度问题,提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解,基因的值表示任务的优先权和执行模式,每条染色体对应一个满足逻辑关系约束的可行任务排序,根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作,能够使搜索范围遍及整个问题解空间。实际应用表明,该算法能快速求得问题的最优解或近似最优解。  相似文献   

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

3.
针对双资源约束作业车间调度的双目标优化问题,提出一种继承式遗传算法,通过分支种群继承父辈种群的进化经验.该算法面向双资源约束特点,采用4维染色体编码方式,基于时间窗口比较实现活动化调度,通过资源进化算子提高算法全局搜索能力;基于个体Pareto指数的锦标赛选择策略,有效削弱了染色体Pareto排序级别对个体存活概率的影响以保持群体多样性,并利用精英保留策略提高了解的收敛性.仿真实验与分析结果表明了所提算法具有优良性能.  相似文献   

4.
冯斌  石锦风  孙俊 《计算机工程与设计》2007,28(23):5690-5693,5786
针对现行的遗传算法存在进化速度过慢和过早收敛的局限,以及粒子群优化算法搜索空间有限、容易陷入局部最优点的缺陷,提出将一种基于量子行为的粒子群优化算法应用于作业车间调度问题.将该问题中的每个调度组成一个多维向量,以此向量作为量子粒子群优化算法中的粒子进行进化,由此在解空间内搜索最优解.实例仿真结果表明,该算法收敛速度快、全局收敛性能好,可以得到比遗传算法、粒子群优化算法更佳的调度效果,证明了算法的有效性.  相似文献   

5.
航班降落调度是多约束的整数规划问题,也是组合优化中的典型NP难题之一.针对传统粒子群算法易陷入局部最优和求解组合优化问题能力不强的缺点,提出改进策略.改进的算法通过禁忌搜索策略生成初始粒子群以满足航班调度多约束的限制,引入遗传算法的交叉变异等操作以增强粒子群间信息交流能力,重新定义惯性权重和加速度因子,以增强粒子的多样性和收敛性,加入进化交叉算子以增强粒子的局部寻优能力.通过与修补遗传算法、罚函数遗传算法进行对比,经多次运行后的结果表明,提出的改进算法的局部搜索能力和全局搜索能力都得到增强,同时也验证了算法的可行性和有效性.  相似文献   

6.
传统遗传算法在求解Job Shop调度问题时存在收敛速度慢,易于早熟的缺点。在病毒遗传算法(VEGA)和灾变遗传算法的基础上提出了一种带有灾变因子的病毒遗传算法(IVEGA-C)。该算法在传统遗传算法的基本结构上加入了病毒感染操作和灾变操作,病毒感染操作实现了同代个体之间横向传递进化信息,灾变操作采用灭绝操作。正是这种改进加快了遗传算法的收敛速度,避免了早熟现象和陷入局部最优解。通过仿真实验验证了IVEGA-C算法在解决Job Shop调度问题中的性能优于传统GA算法和VEGA算法。最后给出了应用该算法的一个实例。  相似文献   

7.
夏柱昌  刘芳  公茂果  戚玉涛 《软件学报》2010,21(12):3082-3093
多种群遗传算法相比遗传算法在性能上能够有所提高,但对具有较多局部最优解的作业车间调度问题,多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点.因此,提出了一种求解作业车间调度问题的新算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for job shop scheduling problem).MGA-MBL在多种群遗传算法的基础上通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性;通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群进化的局部搜索能力.由于MGA-MBL采用了全局寻优能力较强的模拟退火算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了算法求解作业车间调度问题的性能.对著名的benchmark数据进行测试,实验结果证实了MGA-MBL在求解作业车间调度问题上的有效性.  相似文献   

8.
主要利用差分进化算法来研究时间约束下的多出救点应急物资调度优化问题。针对传统差分进化算法搜索速度慢、易陷入局部最优解的缺点,提出一个并行协同差分进化算法,将该算法应用于时间约束下的多出救点应急物资调度优化,建立相应的数学模型,在此基础上设计相应的算法。实例验证表明,同遗传算法、标准差分进化算法相比,该算法在解决具有时间约束的多出救点应急物资调度优化问题方面具有较快的搜索速度和较好的寻优能力。  相似文献   

9.
实施遗传算法的多Agent系统的构建与实现   总被引:1,自引:1,他引:1  
针对常规遗传算法的不足,该文引入智能体技术实施遗传算法,所构建的多Agent系统能从进化环境中获取表征目前进化状态的有用信息,动态地调整进化参数,监控并调度进化操作,以期快速高效地搜索到全局最优,从而提升GA的优化性能。多个实例试验表明该算法能改善常规遗传算法的欠缺,显示出超越常规遗传算法的优良性能。  相似文献   

10.
资源约束项目的改进差分进化参数控制及双向调度算法   总被引:1,自引:0,他引:1  
针对资源约束项目调度组合优化难题,提出一种改进的动态差分进化参数控制及双向调度算法.通过参数时变衰减与个体优劣评价,自适应控制个体进化参数,提高算法的收敛性能、勘探与开发最优解的能力;基于动态差分进化(Dynamic differential evolution, DDE),提出一种双向调度算法,使用满足任务时序约束的优先数编码、交替正向反向调度,结合标准化编码调整与精英保留的种群随机重建策略,建立了一种高效稳健的双向编码调整机制.通过著名的项目调度问题库(Project scheduling problem library, PSPLIB)中实例集测试,并与其他文献算法比较最优解平均偏差率,验证了所提算法的有效性与优越性.  相似文献   

11.
The multi-mode resource-constrained project scheduling problem (MRCPSP) involves the determination of a baseline schedule of the project activities, which can be executed in multiple modes, satisfying the precedence relations and resource constraints while minimizing the project duration. During the execution of the project, the baseline schedule may become infeasible due to activity duration and resource disruptions. We propose and evaluate a number of dedicated exact reactive scheduling procedures as well as a tabu search heuristic for repairing a disrupted schedule, under the assumption that no activity can be started before its baseline starting time. We report on promising computational results obtained on a set of benchmark problems.  相似文献   

12.
在资源受限项目调度问题中,将可更新资源进一步拓展为具有胜任力差异的人力资源,建立考虑胜任力差异的人力资源受限多目标项目调度问题模型.该模型是对传统多模式资源约束项目调度问题更接近研发项目群实际的扩展.针对模型提出两阶段优化算法,第1阶段是项目时序约束优化阶段,采用蚁群算法(ACO)进行任务列表的优化求解,通过对信息素增量规则的改进、串联进度生成机制(SSGS)及资源冲突消解策略的使用,使蚁群算法的求解效率和质量得以提高;第2阶段是资源约束优化阶段,以第1阶段求得的优化任务列表为输入,逐项对人力资源约束进行核查与调整,最终生成项目调度的优化方案.数值实验表明,考虑胜任力差异的数学优化模型更符合研发项目群管理实践,同时两阶段算法在求解质量方面具有良好性能.  相似文献   

13.
This paper investigates the budget variant of the discrete time/cost trade-off problem (DTCTP). This multi-mode project scheduling problem requires assigning modes to the activities of a project so that the total completion time is minimized and the budget and the precedence constraints are satisfied. This problem is often encountered in practice as timely completion of the projects without exceeding the budget is crucial. The contribution of this paper to the literatures is to describe an effective Benders Decomposition-based exact algorithm to solve the DTCTP instances of realistic sizes. Although Benders Decomposition often exhibits a very slow convergence, we have included several algorithmic features to enhance the performance of the proposed tailored approach. Computational results attest to the efficacy of the proposed algorithm, which can solve large-scale instances to optimality.  相似文献   

14.
刘涛  刘民  张龙  路深  张亚斌 《控制工程》2005,12(2):104-106
研究了施工项目进度调度问题,提出了一种基于启发式规则和遗传算法的综合智能优化算法,并在施工项目调度问题的描述、带资源约束的施工项目调度问题的分解方法、遗传算法的编码、交叉、变异方法和解码方法等方面进行了研究。不同规模的数值计算结果表明,该算法在解决复杂工程施工项目调度问题上具有良好的性能,并能较好地适用于带时序、资源约束的施工项目调度问题。  相似文献   

15.
In this paper, the resource-constrained project scheduling problem with multiple execution modes for each activity is explored. This paper aims to find a schedule of activities such that the makespan of the schedule is minimized subject to the precedence and resource constraints. We present a two-phase genetic local search algorithm that combines the genetic algorithm and the local search method to solve this problem. The first phase aims to search globally for promising areas, and the second phase aims to search more thoroughly in these promising areas. A set of elite solutions is collected during the first phase, and this set, which acts as the indication of promising areas, is utilized to construct the initial population of the second phase. By suitable applications of the mutation with a large mutation rate, the restart of the genetic local search algorithm, and the collection of good solutions in the elite set, the strength of intensification and diversification can be properly adapted and the search ability retained in a long term. Computational experiments were conducted on the standard sets of project instances, and the experimental results revealed that the proposed algorithm was effective for both the short-term (with 5000 schedules being evaluated) and the long-term (with 50000 schedules being evaluated) search in solving this problem.   相似文献   

16.
项目优化调度的多智能体社会进化算法   总被引:2,自引:0,他引:2  
结合多智能体系统、进化算法以及关系网模型,提出了一种多智能体社会进化算法用于求解项目活动的一个最优调度顺序以使整个工程的工期最短,每个智能体生存于环境中,为了增加自身能量将与其邻域展开竞争及协同操作,同时可利用自身的知识进行自学习来增加能量,根据项目优化调度的问题特点,设计了智能体的竞争行为、协同行为以及自学习行为,通过对PSPLIB中的标准问题进行测试,同时与其他启发式算法相比较的仿真实验结果表明该算法具有良好的性能,能在较短的时间内寻找到十分接近"最优解"的调度序列.  相似文献   

17.
路深  刘民  吴澄  张亚斌  张龙 《控制工程》2005,12(1):11-14
介绍了带流水作业的工程项目调度问题,这是项目网络中带有流水作业子网络的项目调度问题。它不仅带有常规的时序和资源约束,还带有流水作业所带来的特殊约束。首先给出了带流水作业工程项目调度问题的描述;进而提出一种解决该问题的遗传算法。该算法引入了基于项目划分的编码方式,将个体划分为流水基因段和非流水基因段,并分别进行遗传操作。最后对提出的算法进行了数值计算验证,结果表明了算法的有效性。  相似文献   

18.
Mode identity and resource constrained project scheduling problem (MIRCPSP) is a substantial generalization of the well-known multi-mode problem. It arises when certain activities in the project are interdependent. That is, the set of all activities in the project are partitioned into disjoint subsets where all activities forming one subset have to be processed in the same mode. This paper addresses project scheduling problem with resource and mode identity constraints to minimize the project makespan. This problem is strongly NP-hard and three meta-heuristic algorithms namely imperialist competitive algorithm, simulated annealing and differential evolution are proposed to solve it. In order to improve the quality of the employed algorithms a local search and learning module is combined with the meta-heuristic algorithms. The performance of the algorithms is evaluated on 180 test problems by statistically comparing their solution in term of the objective function and computational times. The obtained computational results indicate that the integration of the learning module and the proposed algorithm is efficient and effective.  相似文献   

19.
A genetic algorithm for multiprocessor scheduling   总被引:6,自引:0,他引:6  
The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented  相似文献   

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

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号