改进蝙蝠算法求解置换流水线车间调度问题

基于改进型交叉算子的混合流水车间排序求解黄宗南;张博凡;信宁宁【摘要】Hybrid flow-shop is an expansion of permutation flow-shop, and it is more complex. Rational work-piece sequencing can improve the utilization rate of equipments and the economic benefits of enterprises. The variants of canonical crossover operator, which has been studied before, is applied to hybrid flow-shop sequencing. This paper introduces the genetic algorithm process for solving this problem, and analyzes operating principles and characteristics of the variants of canonical crossover operator. At last, an example is tested on enterprise, and the results show that this algorithm has a good performance.%混合流水车间是置换流水车间的扩展,其作业排序更复杂.合理的排序方案能够提高企业设备的利用率和经济效益.在前期研究的基础上,将提出的改进型交叉算子扩展应用到混合流水车间排序问题中.介绍了求解该问题的遗传算法实现流程,剖析了改进型单点交叉算子的操作原理和特点.最后,针对企业实例进行求解,结果表明该算法寻优性能良好.【期刊名称】《制造技术与机床》【年(卷),期】2013(000)003【总页数】4页(P122-125)【关键词】混合流水车间排序;遗传算法;改进型交叉算子;优化【作者】黄宗南;张博凡;信宁宁【作者单位】上海大学机电工程与自动化学院,上海 200072【正文语种】中文【中图分类】TP181;O224混合流水车间是指一批工件在流水线上进行多个阶段的加工，每一阶段至少有一台并行机器;在每一阶段各工件均要完成一道工序，各工件的每道工序可以在相应阶段上的任意一台机器上加工。

有限等待置换流水车间调度问题的IGA算法任魏翔;秦永彬;许道云【摘要】在对经典遗传算法进行研究的基础上,针对具有等待时间置换流水车间调度问题,以最小化最大完成时间为优化目标建立整数规划模型,并提出一种解决该问题的IGA算法;算法中部分染色体的初始种群由原问题所转化而成的具有等待时间两台机器的置换流水车间调度问题的解所组成;交叉方法采用基于顺序和位置相结合的OPX方法;通过对Taillard算例中置换流水车间调度问题基准数据的测试,并对仿真实验的结果进行了分析,验证所提出IGA算法的有效性和可行性.【期刊名称】《计算机测量与控制》【年(卷),期】2015(023)006【总页数】4页(P2086-2089)【关键词】遗传算法;等待时间;最大完成时间;置换流水车间调度【作者】任魏翔;秦永彬;许道云【作者单位】贵州大学计算机科学与技术学院,贵阳550025;贵州大学计算机科学与技术学院,贵阳550025;贵州大学计算机科学与技术学院,贵阳550025【正文语种】中文【中图分类】TP399流水车间调度问题相关研究成果在制造、物流、冶金、采矿、航空以及交通运输等行业已得到广泛应用。

该类问题的研究内容是在满足给定约束条件情况下，合理安排任务的调度顺序以使目标函数值最优。

利用Johnson法则能够在多项式时间内求解具有2台机器的流水车间调度问题。

机器数量大于2的流水车间调度问题经已被证明是NP－Completeness［1］。

精确算法已在多项式时间内无法有效求解该类问题。

因此，针对此类问题已提出各种启发式算法，如CDS［2］、Pamler［3］、Gupta［4］、RA［5］、HEH［6］等。

近年来，各种智能优化算法也被用于求解该类问题，如模拟退火算法［7］、禁忌搜索算法［8］、遗传算法［9］、蚁群算法［10］、粒子群算法［11］、蜂群算法［12］模拟植物生长算法［13］、混合蛙跳算法［14］等。

具有等待时间的流水车间调度问题是一类更为复杂的优化问题，这类问题要求生产线在相邻两道工序的处理之间具有一定的等待时间。

第37卷 第1期2010年1月计算机科学Computer Science Vo l.37No.1Jan 2010到稿日期:2009-02-09 返修日期:2009-05-13刘延风(1970-),男,讲师,主要研究方向为智能优化算法及其应用,E -mail:teach er2003@;刘三阳(1959-),男,教授,主要研究方向为最优化理论与算法。

多构造蚁群优化求解置换流水车间调度问题刘延风 刘三阳(西安电子科技大学应用数学系 西安710071)摘 要 针对置换流水车间调度问题,提出了一种多构造蚁群优化求解算法。

在该算法中,蚁群采用两种方式构造解,分别是基于NEH (N aw az -Ensco re -H am,N EH)启发式算法和R ajendran 启发式算法,并根据解的质量,自适应地调整两种构造方式在蚁群中所占的比例。

对置换流水车间调度问题的基准问题测试表明,提出的算法是有效的。

关键词 多构造蚁群优化,置换流水车间调度,N EH 启发式算法,Rajendran 启发式算法中图法分类号 T P38 文献标识码 AMult-i construction Ant Colony Optimization Algorithm for Permutation Flow Shop SchedulingLIU Yan -feng L IU San -y ang(Departmen t of Applied M ath ematics,Xidian U nivers ity,Xi .an 710071,Chin a)Abstract A M ulti Construction A nt Colony Optimizatio n A lg or ithm fo r Permutatio n Flow Shop Scheduling w as pro -posed.In this alg or ithm,so lutio ns ar e constructed thr ough two modes,which are based on N aw az -Ensco re -H am heuris -t ics and R ajendr an heur istics respectiv ely.T hen the pr opor tion of const ruct ion mo des is adjusted adaptively accor ding to qualit y of so lutio n constructed.Simulation results and comparisons based on benchmarks demo nstr ate the effectiveness of the alg or ithm.Keywords Per mut ation flo w sho p scheduling ,M ulti constructio n ant co lony o ptimization,N EH heuristics,Rajendran heur istics1 引言置换流水车间调度问题是许多实际流水线生产调度的简化模型。

多目标置换流水车间调度的改进食物链算法陈可嘉;周晓敏【摘要】An improved food chain algorithm was proposed for permutation flow shop scheduling with multiple objectives of minimizing makespan and total tardiness.Fast non-dominated sorting and crowded distance estimation were introduced into the food chain algorithm to improve the optimization ability based on Pareto optimal solutions.Three typical OR-Library examples were selected to con-duct comparison.Numerical results show that the designed algorithm can obtain much better solu-tions than NSGA-Ⅱ.%针对目标函数为最小化最大完成时间和总延迟时间的多目标置换流水车间调度问题，提出了一种改进的食物链算法。

该算法在食物链算法的基础上，引入基于 Pareto 最优解的快速非支配性排序和个体拥挤距离计算，增强了算法的寻优性能。

对 OR-Library 三个典型算例的优化比较表明，该算法在解的质量上明显超越 NSGA-Ⅱ算法。

【期刊名称】《中国机械工程》【年(卷),期】2015(000)003【总页数】7页(P348-353,360)【关键词】置换流水车间调度;多目标优化;食物链算法;Pareto 最优解【作者】陈可嘉;周晓敏【作者单位】福州大学，福州，350108;福州大学，福州，350108【正文语种】中文【中图分类】F406.2流水车间调度问题作为许多实际流水线生产调度的简化模型，是生产调度中的一个重要研究对象。

求解置换Flow-shop调度问题的改进遗传算法
伊华伟;张秋余
【期刊名称】《计算机工程与应用》
【年(卷),期】2007(43)22
【摘要】提出一种求解置换Flow-shop调度问题的改进遗传算法.该算法采用多个体交叉方式,对交叉过程和变异过程分别进行阈值设置,实现了在优化过程中扩大解空间的搜索范围和保持种群的多样性,从而增大了获得最优解的几率.最后对一系列典型的Benchmark问题进行仿真测试,实验结果证实了该改进遗传算法的有效性.
【总页数】4页(P41-43,82)
【作者】伊华伟;张秋余
【作者单位】辽宁工学院计算机科学与工程学院,辽宁锦州121001;兰州理工大学计算机与通信学院,兰州730050
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.求解置换流水车间调度问题的改进遗传算法 [J], 涂雪平;施灿涛;李铁克
2.利用DNA遗传算法求解Flow-Shop调度问题 [J], 柳毅;叶春明;沈运红
3.求解置换流水车间调度问题的改进遗传算法 [J], 李小缤;白焰;耿林霄
4.一种求解3机Flow-shop调度问题的遗传算法 [J], 陈雄;汤光强;吴启迪
5.应用改进区块遗传算法求解置换流水车间调度问题 [J], 裴小兵;张春花
因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进遗传算法的多目标混合流水线调度问题研究引言多目标混合流水线调度问题是一个普遍存在的问题。

如何在满足多个优化目标的同时，使得生产效率得到最大化是一个具有挑战性的研究问题。

遗传算法作为一种自适应的、能够处理多目标问题的优化算法，被广泛应用于多目标混合流水线调度问题的解决中。

然而，传统的遗传算法存在一些缺点，例如局部最优解困境和适应度计算不准确等。

因此，改进遗传算法以提高其性能和效率，已经成为了当前研究问题的一个重要方向。

本文主要探讨基于改进遗传算法的多目标混合流水线调度问题的研究。

第一章多目标混合流水线调度问题介绍多目标混合流水线调度问题是一种涉及到多个生产任务的调度问题。

它的目标是在多个生产任务之间，形成一个合理的调度安排，以最大化生产效率和减少生产成本。

混合流水线是一个允许不同类型的任务在同一个流水线上加工的流水线。

例如，汽车生产流水线可以包含从安装车门到涂漆车身等各种任务。

在混合流水线中，每个任务具有不同的处理时间和需要的加工资源。

这就需要进行合适的调度，在保证生产任务完成的时间及质量的同时，最大化生产效率和减少生产成本。

此外，由于混合流水线需要考虑多种不同类型任务的优先级和时间期限，因而涉及到多目标问题的解决。

第二章遗传算法及其改进研究遗传算法是一种能够在搜索空间中找到最优解的算法，它是一种启发式的优化算法。

遗传算法利用生物进化的思想，从个体群体中筛选优秀个体，并对它们进行交叉、变异等操作，以产生下一代个体。

这样，通过不断迭代过程，最终能够找到最优解。

尽管遗传算法被广泛应用于解决多目标问题，但是传统的遗传算法还存在一些弊端。

例如，容易陷入局部最优解困境、适应度计算不准确等问题。

基于此，研究人员提出了许多改进遗传算法，例如粒子群算法、人工免疫算法、差分进化算法、模拟退火算法等。

这些改进算法可以有效地增加算法的收敛速度、避免局部最优解困境、降低适应度计算的复杂性等。

第三章具体实现方案多目标混合流水线调度问题的求解可以使用遗传算法进行优化求解。

求解混合流水车间调度问题的改进型PSO算法张建军;王春芳【期刊名称】《计算机工程与应用》【年(卷),期】2011(047)031【摘要】针对粒子群优化算法易陷入局部最优以及求解生产调度问题时容易重复搜索的情况,结合混合车间调度问题的优化模型,提出一种改进的粒子群优化算法.在算法设计中,引入基于位置相似度的禁忌策略,避免对刚刚搜索过的区域重复搜索和过早陷入局部最优;同时采用线性微分递减方式更新惯性权重,既保证了算法前期有较高的全局搜索能力,又能保证后期有较高的开发能力.最后通过仿真实验,验证算法的有效性.%The problems will be solved in those situations when the PSO is easily converged in local optimal and repeated search in solving production scheduling bined with hybrid flow-shop scheduling optimization model, an improved particle swarm optimization algorithm is constructed.In the algorithm,the taboo strategy of the location-based similarity degree is imported to avoid repeatedly searching area which is searched before and premature local optimum search.Mean-while, another linear differential decrement updating inertia weight strategy is also used to ensure that the algorithm has not only a higher capability in the calculation of the global search,but also to ensure the later development of higher capacity in accelerating convergencerate.Finally,the simulation experiment proves that the algorithm is effective.【总页数】4页(P212-214,219)【作者】张建军;王春芳【作者单位】合肥工业大学计算机与信息学院,合肥230009;合肥工业大学机械与汽车工程学院,合肥230009【正文语种】中文【中图分类】TP18【相关文献】1.基于双模式PSO算法求解置换流水车间调度问题 [J], 马祎航;陶文华;刘阳2.改进差分进化算法求解混合流水车间调度问题 [J], 张源;陶翼飞;王加冕3.新型混合改进遗传算法求解零等待流水车间调度问题 [J], 裴小兵;李依臻4.改进PSO-GA算法求解混合流水车间调度问题 [J], 于蒙;刘德汉5.帝国竞争算法求解资源约束混合流水车间调度问题 [J], 李俊青;李荣昊;陶昕瑞;曾清清;耿雅典因版权原因，仅展示原文概要，查看原文内容请购买。

求解约束优化问题的改进蝙蝠算法
龙文;张文专
【期刊名称】《计算机应用研究》
【年(卷),期】2014(31)8
【摘要】针对基本蝙蝠算法求解精度低、易陷入局部最优的缺点,提出一种改进的蝙蝠算法用于求解约束优化问题.该算法利用佳点集方法构造初始种群以维持群体的多样性,引入惯性权重以协调算法的勘探和开发能力.为了避免算法陷入局部最优,对当前全局最优解进行多样性变异操作.通过对四个标准测试函数和化工应用的仿真实验并与其他算法进行比较,结果表明了该算法具有较强的全局搜索能力.
【总页数】4页(P2350-2353)
【作者】龙文;张文专
【作者单位】贵州财经大学贵州省经济系统仿真重点实验室,贵阳550004;贵州财经大学贵州省经济系统仿真重点实验室,贵阳550004
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.求解双边装配线第Ⅰ类平衡问题的改进离散蝙蝠算法 [J], 詹慧文;罗亚波
2.改进蝙蝠算法求解置换流水线车间调度问题 [J], 周宗渠;田大钢
3.基于改进正则化蝙蝠算法求解第一类Fredholm积分方程 [J], 张新明;刘一博
4.求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法 [J], 张瑾;洪莉;戴二壮
5.求解全局优化问题的改进蝙蝠算法（英文） [J], 汪春峰;马民;申培萍
因版权原因，仅展示原文概要，查看原文内容请购买。

118 •电子技术与软件工程 Electronic Technology & Software Engineering数据库技术• Data Base Technique【关键词】静态流水车间 生产调度 遗传算法1 引言目前，制造业虽然发展快速，但是很多制造业企业的生产车间还是在使用以人的经验为主的生产调度方式。

生产一线工人主要依靠自己日积月累的经验来进度产品生产的调度，在这种模式下很难实现生产的标准化，很容易产生生产设备使用不均衡、浪费时间等问题。

这一系列文体的产生无形之中推动了生产方式的创新，科学合理的基于人工智能化的生产调度方式由此产生。

静态流水车间是在开始调度之前全部工件就已经做好即将加工的准备，假设不会发生突发故障，开始加工后工件像流水一样流入流出。

在这种车间模式下所有的工件加工步骤都是一样的。

Johnson[1]最先解决了两台机床的flowshop 调度问题，从此专家学者么开始了对于不同类型车间的调度问题的研究。

在此之前的生产调度问题的解决全是依靠工人们积累的经验来解决的，后来人们开始使用运筹学、线性规划、拉格朗日松弛、分支定界法等应用数学的方法来解决生产调度问题。

再后来人们开始引入算法，依靠智能算法去解决生产中的调度问题，例如启发式算法，Rajendran 和求解静态流水车间调度的改进遗传算法文/顾蕾Ziegler[2],Wang 等[3]就依靠启发式算法解决了某些类型车间的调度问题。

当前情况下，相对来说由Framinan 和Leiste[4]给出的一种构造型启发式算法，算是最优的启发式算法。

最近时间，人们对于遗传算法的研究越来越深入，更多的学者开始选择使用遗传算法来解决各种类型车间的调度问题[5-7]。

但是标准的遗传算法本身就存在一定的缺陷，例如容易出现早熟或者容易陷入局部最优。

这些缺点如果在算法实际执行之前不解决的化，就会带入到实际的应用当中，那么我们得出的所谓的最优解很有可能并不是最优解。