共查询到19条相似文献,搜索用时 46 毫秒
1.
最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PHlp,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PHlp. 相似文献
2.
针对以总完工时间最小为目标的无等待流水调度问题提出一个启发式算法和禁忌搜索算法相结合的混合禁忌搜索算法HTS(Hybrid Taboo Search):以启发式算法产生的解作为初始解,通过禁忌搜索提高解的质量.实验结果表明:提出的HTS性能上优于经典的RC1、RC2、PH1(p)和DS算法. 相似文献
3.
利用迭代变化邻域搜索算法(IVNS)求解最小化总完工时间的有准备时间无等待流水车间调度问题. 设计局部搜索算法需要考虑3个关键因素:所用邻域、解评估和局部最优的克服. 因此,定义了3个较大规模邻域以扩大搜索范围. 为加速解评估,利用目标增量来避免重新计算每个解的目标函数值,使相邻解比较只需常量时间,NEH插入算法的时间复杂度降低一阶. IVNS通过切换邻域和扰动重启,来克服局部搜索易于陷入局部最优解的缺点. 通过与求解该问题的当前最好算法在5400个标准算上,以相同CPU时间进行的实算比较,实验结果统计分析验证了IVNS的寻优性能明显优于参照算法. 相似文献
4.
针对无等待流水车间调度问题,提出一种基于种群迭代的改进贪婪算法解决以最小化最大完工时间为目标的此类问题。首先,采用改进NEH(Nawaz–Enscore–Ham)算法提升初始种群的质量,提高种群的多样性,并得出初始解,确定最优个体;其次,采用种群迭代贪婪算法对确定的种群序列进行破坏与重新构建,将新序列插入指定位置,并对获得的候选方案进行本地搜索,获得新的解决方案,同时取代劣势解决方案;最后,通过仿真实例将种群迭代贪婪算法与其他智能优化算法在平均相对偏差率、最佳相对偏差率、算法收敛性上进行对比,结果表明种群迭代贪婪算法求解所提问题的高效性和稳定性。 相似文献
5.
6.
在分析大规模无等待流水调度问题特点的基础上,提出了利用相邻工件间完工时间距离求最小化完工时间的方法;通过研究工件插入和工件对的交换对最小化完工时间的影响,提出一种邻域迭代搜索算法,该算法降低了求解完工时间的时间复杂度,大大提高了算法效率;为避免算法在邻域搜索过程中陷入局部最优,将变邻域结构算法的思想应用于其中.仿真结果表明,所提出的算法能高效率解决大规模无等待流水调度问题,所得结果令人满意. 相似文献
7.
以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。 相似文献
8.
针对无等待流水车间调度问题,提出了一种新颖的量子萤火虫优化算法用于最小化总完工时间.首先,将量子进化机制嵌入萤火虫算法中,并设计一种快速的局部邻域搜索方法,在每次迭代时只搜索部分邻域,同时采用目标增量计算邻域解变化,这样极大地加快了算法迭代速度,加速了算法收敛.最后,应用Taillard基准测试实例仿真,与目前较优的启发式算法IHA(improved heuristic algorithm)和群智能算法DGSO(discrete glowworm swarm optimization)、 GA-VNS(genetic algorithm-variable neighborhood search)及DHS(discrete harmony search)相比较,产生最好解的平均百分比偏差均下降了40%以上.实验结果验证了所提算法在求解无等待流水调度中的优越性. 相似文献
9.
10.
零空闲流水车间问题(NIFSP)是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。 相似文献
11.
Nicholas G. Hall Gilbert Laporte Esaignani Selvarajah Chelliah Sriskandarajah 《Journal of Scheduling》2003,6(4):339-354
Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results. 相似文献
12.
13.
提出了一种基于粒子群和遗传算法的新混合算法。该算法首先将样本集分为N组,每一组分别进行不同参数的粒子群或遗传运算,在每一步的迭代中选取了粒子群算法和遗传算法的最优值作为全局最优,使每一步的迭代都优于单一的PSO和GA算法,进而提高了算法整体的性能。与其他混合最优化算法不同的是,该算法没有破坏粒子群和遗传算法的独立性,而是仅通过全局最优样本把两个算法结合在一起。在经典测试函数的仿真实验中,新算法表现了更好的寻优性能及寻优稳定性。 相似文献
14.
马超邓超熊尧吴军 《计算机研究与发展》2013,50(11):2278-2286
粒子群算法(particle swarm optimization, PSO)原理简单、搜索速度快,但前期容易“早熟”.遗传算法(genetic algorithm, GA)具有很强的全局搜索能力,但收敛精度不高.综合考虑二者优缺点,把遗传算子引入PSO算法中,并采用交叉搜索的方法,调整惯性权重以及变异方式使粒子得到进化,当粒子种群进化到一定层度后,对部分粒子进行变异处理,这样不仅避免算法陷入局部最优解,而且获得较高收敛精度和执行能力,可解决工程中非线性、多极值的问题.据测试函数以及与其他寻优算法的对比分析表明,此混合策略在求解精度、搜索效率和处理不同复杂度问题等方面都有很好的优越性,具有满足工程需要的能力. 相似文献
15.
16.
17.
18.
总结单纯形搜索算法的核心思想.然后提出单纯形交叉方向算子和最优小生境、次差小生境与最差小生境3个概念.在最优小生境中采用单纯形搜索算法得到局部极值,在最优小生境与次差小生境之间用单纯形交叉方向算子产生优秀个体,而在最差小生境中采用受限单纯形搜索产生优秀个体,从而构成基于单纯形的小生境混合遗传算法SimplexNich-HGA.最后用SimplexNiche-HGA、单纯形混合遗传算法Simplex-HGA 以及基本遗传算法SGA求函数Rosenbrock的极值,并进一步用SimplexNiche-HGA和Simplex-HGA 求多峰值函数Shubert的极值,验证算法的正确性和求多峰值函数的极值的效率. 相似文献
19.
多阶段混合Flow Shop调度问题及其遗传求解算法 总被引:5,自引:0,他引:5
针对多阶段混合Flow Shop 调度问题的一般结构和不同的调度目标函数,提出混合整数规划模型,并基于问题的结构特点设计了遗传求解算法。计算实验结果表明,遗传算法对于不同规模和结构的问题具有良好的适应性和求解性能 相似文献