共查询到17条相似文献,搜索用时 375 毫秒
1.
描述了一种解决作业车间调度最短完工时间问题的混合式算法.该算法基于禁忌搜索和转换瓶颈技术.算法中利用了多种禁忌搜索方法.为了得到更好的结果,算法中还引入了倒转技术.从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比当前解决该问题的最高效的启发式算法之一的TSSB算法更好的结果. 相似文献
2.
一种基于禁忌搜索技术的作业车间调度算法 总被引:3,自引:0,他引:3
描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法.该算法基于禁忌搜索技术.算法中利用了新的禁忌搜索方法.从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比当前没有用转换瓶颈技术的禁忌搜索中最好的算法之一的TSAB算法更好的结果. 相似文献
3.
提出一种改进的禁忌搜索算法来求解背包问题.该算法基于禁忌搜索技术,并采用I&D策略,同时设计了两种针对局部最优解的变异算子.改进后的算法能有效地弥补标准禁忌算法对初始解依赖的缺陷,同时也避免了搜索停滞的现象.通过对具体实例和随机问题的测试,表明改进后的禁忌搜索算法有更好的性能. 相似文献
4.
5.
6.
基于禁忌搜索的QoS路由算法 总被引:3,自引:0,他引:3
多约束的QoS路由问题是NP完全问题,该文将禁忌搜索算法引入多约束QoS路由计算中,提出了一种基于禁忌搜索的QoS路由算法QoS_TS。该算法通过设置长期记忆禁忌表和短期记忆禁忌表以及有效的评价函数,保证了算法实现过程中多样化的有效搜索。文章给出了算法实现的具体流程。实验仿真表明,该算法具有较高的搜索效率和较快的收敛性,通过该算法得到的路由不但满足QoS约束要求,同时可以均衡链路负载,减少路由拥塞。 相似文献
7.
8.
针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。 相似文献
9.
本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。 相似文献
10.
11.
Algorithm based on taboo search and shifting bottleneck for job shop scheduling 总被引:1,自引:0,他引:1 下载免费PDF全文
Wen-QiHuang ZhiHuang 《计算机科学技术学报》2004,19(6):0-0
In this paper, a computational effective heuristic method for solving the minimum makespan problem of job shop scheduling is presented. It is based on taboo search procedure and on the shifting bottleneck procedure used to jump out of the trap of the taboo search procedure. A key point of the algorithm is that in the taboo search procedure two taboo lists are used to forbid two kinds of reversals of arcs, which is a new and effective way in taboo search methods for job shop scheduling. Computational experiments on a set of benchmark problem instances show that, in several cases, the approach, in reasonable time, yields better solutions than the other heuristic procedures discussed in the literature. 相似文献
12.
13.
14.
朱敬华 《电脑与微电子技术》2012,(4):12-13,31
通过结合模拟退火算法与禁忌搜索算法的优点,提出一个组合算法,并将其应用到旅行商问题(TSP)中。并用C++实现一般的模拟退火算法和这种组合的模拟退火算法.比较结果显示出这种组合算法可以得到更好的结果。 相似文献
15.
Ant colony optimization combined with taboo search for the job shop scheduling problem 总被引:1,自引:0,他引:1
In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of partial schedules. Besides, a taboo search algorithm is embedded to improve the solution quality. We run the proposed algorithm on 101 benchmark instances and obtain competitive results and a new best upper bound for one open benchmark instance is found. 相似文献
16.
17.
采用并行遗传算法作为全局搜索算法,提出一种混合搜索策略,用于求解模糊Job Shop调度问题.根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法局部搜索能力.针对13个困难benchmark问题的实验结果表明,在较短的时间内,混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%,比TSAB算法提高5.76%.采用的禁忌搜索算法改善了遗传算法的局部搜索能力,说明提出的混合搜索策略是有效的. 相似文献