共查询到18条相似文献,搜索用时 79 毫秒
1.
为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。 相似文献
2.
为了解决单一算法求解Job Shop调度问题存在的不足,该文提出了一种混合算法,将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况,提出了一种基于关键工序的邻域搜索方法,将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力,提高了蚁群算法的优化能力,达到改善Job Shop调度问题解的质量。实验结果表明,混合算法在较短的时间内,找到了FT10、LA24、LA36等典型benchmarks问题的最优解,得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。 相似文献
3.
本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。 相似文献
4.
针对以总完工时间最小为目标的无等待流水调度问题提出一个启发式算法和禁忌搜索算法相结合的混合禁忌搜索算法HTS(Hybrid Taboo Search):以启发式算法产生的解作为初始解,通过禁忌搜索提高解的质量.实验结果表明:提出的HTS性能上优于经典的RC1、RC2、PH1(p)和DS算法. 相似文献
5.
针对最小化最大完成时间的有限缓冲区流水线调度问题(LBPFSP),提出一种混合蝙蝠算法(HBA)。在算法设计中,采用基于SPV的编码规则以实现连续的实数向离散的作业序列的转变,在种群初始化时引入NEH启发式算法,为提高算法的搜索效率,以一定的概率执行基于Pairwise的邻域搜索。对标准测试问题在不同缓冲区下的最优值进行仿真并与其他算法进行对比,并对基于Pairwise的邻域搜索的执行概率值对算法性能的影响进行讨论,其结果验证了HBA求解LBPFSP的有效性。 相似文献
6.
7.
8.
9.
针对哈里斯鹰算法(HHO)求解作业车间调度问题(JSP)时存在寻优能力差、易陷入局部最优等缺点提出了混合哈里斯鹰算法(HHHO)。首先,在种群初始化阶段引入混沌理论增加种群多样性;其次,在HHO搜索前期采用能量非线性递减和量子计算增强算法全局探索能力,在搜索后期采用邻域搜索算法增强算法局部开发能力;最后,选取了FT和LA系列算例测试了算法的性能,并与其他先进元启发式算法对比,验证了HHHO在求解JSP时的有效性和优越性。 相似文献
10.
针对最小化最大完工时间的作业车间调度问题(JSP),提出一种结合帝国主义竞争算法(ICA)和禁忌搜索(TS)算法的混合算法。混合算法以帝国主义竞争算法为基础,在同化操作中融入遗传算法中的杂交算子和变异算子,使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点,引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略,使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力,通过对13个经典的Benchmark调度问题进行仿真测试,并与近年4种新型混合算法进行对比分析,实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。 相似文献
11.
12.
求解Job Shop调度问题的一种新的邻域搜索算法 总被引:2,自引:0,他引:2
利用了混合邻域结构进行搜索来求解Job Shop调度问题.算法使用的混合邻域结构不仅使邻域搜索具有效率,而且有助于搜索有效地跳出局部极小值的陷阱,让计算走向前景更好的区域.算法采用的“单机调度”和“同工件工序调整”的跳坑策略能够帮助搜索找到更好的局部极小值.采用国际文献中所有的10工件10机器算例以及另外7个难算例作为本算法的测试实验集,与目前国际上最好的近似算法和另外一种先进算法进行了比较.实算结果验证了算法的寻优性能. 相似文献
13.
研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search (SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果 改进了6.06%,并明显优于多点下降算法. 相似文献
14.
15.
In previous work, we developed three deadlock removal strategies for the job shop scheduling problem (JSSP) and proposed a hybridized genetic algorithm for it. While the genetic algorithm (GA) gave promising results, its performance depended greatly on the choice of deadlock removal strategies employed. This paper introduces a genetic algorithm based scheduling scheme that is deadlock free. This is achieved through the choice of chromosome representation and genetic operators. We propose an efficient solution representation for the JSSP in which the job task ordering constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided, thus resulting in increased efficiency. A mutation-like operator geared towards local search is also proposed which further improves the solution quality. Lastly, a hybrid strategy using the genetic algorithm reinforced with a tabu search is developed. An empirical study is carried out to test the proposed strategies. 相似文献
16.
陈友文 《计算机与数字工程》2009,37(7):35-37
合理的任务调度算法可以在很大程度上提高网格系统的利用率。针对网格环境异构、分布等特点,提出了基于禁忌搜索算法(TS)的双层结构网格任务调度算法,仿真实验表明,该方法具有良好的解质量和搜索能力,对异构系统中的任务调度具有较好的处理结果。 相似文献
17.
研究多次抢占式资源受限的项目调度问题,假设任意时间点可作为资源抢占节点且抢占次数不受限制,建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法(GA)局部搜索能力缺陷,在算法中引入禁忌搜索(TS)进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数,并以标准算例集(Project Scheduling Problem Library,PSPLIB)对算法进行可行性检验。实验结果表明,资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期,设计的算法对问题求解效果良好。 相似文献