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

基于改进型交叉算子的混合流水车间排序求解黄宗南;张博凡;信宁宁【摘要】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]。

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

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

求解零空闲置换流水车间调度问题的离散萤火虫算法
刘长平;叶春明
【期刊名称】《系统管理学报》
【年(卷),期】2014(23)5
【摘要】针对最小化最大完工时间的零空闲置换流水车间调度问题,提出了一种离散型萤火虫优化算法。

基于萤火虫算法优化机理,采用基于工件序列的个体编码方式,重新定义了个体间距离的概念和位置更新公式,并结合交换、插入和逆序操作的局部搜索策略来提高算法性能。

通过典型算例对算法进行了仿真测试和对比,结果表明了所提算法的可行性和有效性,扩展了传统萤火虫算法的求解范围,是解决流水线生产调度问题的一种有效方法。

【总页数】5页(P723-727)
【关键词】流水车间调度;零空闲;最大完工时间;离散萤火虫算法
【作者】刘长平;叶春明
【作者单位】淮阴工学院经济管理学院;东南大学管理科学与工程博士后流动站;上海理工大学管理学院
【正文语种】中文
【中图分类】O229;TH186
【相关文献】
1.基于离散蛙跳算法的零空闲流水线调度问题求解 [J], 王亚敏;冀俊忠;潘全科
2.一种求解混合零空闲置换流水车间调度禁忌分布估计算法 [J], 张晓霞;吕云虹
3.应用改进混合进化算法求解零空闲置换流水车间调度问题 [J], 裴小兵;李依臻
4.求解零空闲流水车间调度问题的离散正弦优化算法 [J], 赵芮;顾幸生
5.置换流水车间调度问题的萤火虫算法求解 [J], 刘长平;叶春明
因版权原因，仅展示原文概要，查看原文内容请购买。

基于双模式PSO算法求解置换流水车间调度问题马祎航;陶文华;刘阳【摘要】针对粒子群算法求解置换流水车间调度这类NP-hard问题存在的早熟问题，本文提出了一种基于随机键编码的双模式飞行粒子群算法。

首先，基于ROV 规则对工件加工顺序进行随机键编码。

其次，粒子在搜索过程中采用带有自适应惯性权重的双模飞行方式来更新位置和速度，避免粒子群陷入早熟收敛状态。

为了提高解的质量，每次迭代过程中对PSO优化得到的种群最优解进行邻域局部搜索。

最后，通过对标准测试集的数值仿真及与其他PSO算法的比较，证实了所提算法求解该问题的有效性与可行性。

%Our objective in this report is to study the permutation flow shop scheduling problem, this paper proposes a dual-mode particle swarm optimization algorithm based on random key code. Based on the ROV rules for random code for the processing sequence;Secondly, particles in the search process use dual flight mode with the adaptive inertia weight to update the position and velocity, avoid particle swarm into premature convergence;In order to improve the quality of the solution, in each iteration the neighborhood local search algorithm is used on PSO optimized solution.Finally a comparison through numerical simulation and comparison of different PSO algorithm on the standard test set, to verify the feasibility and effectiveness of the proposed algorithm to solve the problem.【期刊名称】《电子设计工程》【年(卷),期】2016(024)015【总页数】4页(P1-4)【关键词】置换流水车间调度;粒子群算法;邻域搜索;随机键【作者】马祎航;陶文华;刘阳【作者单位】辽宁石油化工大学信息与控制工程学院，辽宁抚顺 113000;辽宁石油化工大学信息与控制工程学院，辽宁抚顺 113000;中国石油抚顺石化公司烯烃厂辽宁抚顺 113009【正文语种】中文【中图分类】TN081置换流水车间调度问题（Permutation Flow Shop Scheduling Problem，PFSP）是制造系统中重要的规划问题[1]，是在流水车间调度问题的基础上，增加了每台机器加工各工件顺序相同的这一特定的约束条件[2]，已证明3台即为NP-hard问题[3]。

基于改进多目标遗传算法求解混合流水车间调度问题张志鹏;黄明【期刊名称】《计算机应用与软件》【年(卷),期】2015(32)10【摘要】为解决混合流水车间调度问题（HFSP），基于多目标遗传算法和粒子群算法的优点，提出一种多目标混合算法。

该算法引入一种扩展的基于工序的编码，将两种算法产生的最优解分别作为彼此的初始因子，增强了遗传算法的进化速度，有效避免了粒子群算法陷入局部最优，并实现了不同加工路线的生产车间的灵活性调度。

最后通过实例的数值仿真验证了算法的有效性。

%Based on the advantages of multi-objective genetic algorithm and particle swarm optimisation,we proposed a multi-objective hy-brid algorithm for solving hybrid flow-shop scheduling problem (HFSP).It introduces an extended process-based encoding,takes the optimal solutions of these two algorithms as the initial factor for each other,and speeds up the evolution of genetic algorithm as well as avoids PSO falling into local optimum,thus realises the flexible scheduling of production workshops with different processing routes.Finally,through nu-merical simulation of example we verified the effectiveness of the algorithm.【总页数】4页(P291-293,314)【作者】张志鹏;黄明【作者单位】大连交通大学软件学院辽宁大连 116028;大连交通大学软件学院辽宁大连 116028【正文语种】中文【中图分类】TP278【相关文献】1.基于小生境的自适应多目标遗传算法求解流水车间调度问题 [J], 金焕杰;许峰2.多目标混合遗传算法求解流水车间调度问题 [J], 杨开兵3.基于小生境的自适应多目标遗传算法求解流水车间调度问题 [J], 金焕杰;许峰4.新型混合改进遗传算法求解零等待流水车间调度问题 [J], 裴小兵;李依臻5.基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法 [J], 牟健慧;郭前建;高亮;张伟;牟建彩因版权原因，仅展示原文概要，查看原文内容请购买。

置换流水车间调度问题的离散粒子群优化算法第13卷第2期集美大学学报(自然科学版)Vol .13 No .2 2008年4月Journal of J i m ei University (Natural Science )Ap r .2008[收稿日期]2007-08-28 [修回日期]2008-03-05[基金项目]福建省自然科学基金资助项目(2006J0018);福建省青年人才科技创新基金(2006F3013)[作者简介]宁正元(1957—),男,教授,从事计算智能、算法设计与分析等方向的研究.[文章编号]1007-7405(2008)02-0097-05置换流水车间调度问题的离散粒子群优化算法宁正元,林大辉,李丽珊,钟一文(福建农林大学计算机与信息学院,福建福州350002)[摘要]提出了一种求解置换流水车间调度问题的离散粒子群优化算法.在该算法中,定义粒子的位置为作业的置换,粒子的速度为置换中作业的交换,根据离散量运算的特点,对粒子的运动规则进行了重新定义.采用变邻域搜索算子和逆序算子来保持粒子群的多样性和提高算法的局部求精能力,使算法在空间探索和局部求精间取得了较好的平衡.在Taillard 测试问题集上对算法性能进行了仿真实验,结果表明,离散粒子群优化算法具有良好的性能.[关键词]离散粒子群优化;置换流水车间调度问题;变邻域搜索;逆序算子[中图分类号]TP 301[文献标志码]A0 引言置换流水车间调度问题PFSP (Per mutati on Fl owshop Scheduling Pr oble m )是一类经典的加工调度问题,该问题可描述为:n 个作业以相同的顺序依次在m 台机器上流水加工,约定每一时刻每台机器最多只能加工一个作业,并且每一作业只能在一台机器上加工,已知各作业在各机器上的加工时间,要求确定所有作业的加工顺序,使得某项指标最小.若指标为最终加工完成时间,即makes pan,则此问题通常记为n /m /P /c max .PFSP 的求解方法通常可分为精确方法、构造型方法及基于计算智能的方法等[1].由于问题本身是NP -困难的,精确方法(如列举法、分支定界、动态规划等)计算量和存储量大,仅适合于小规模问题.构造型方法通过一定的规则来构造问题的解,如NEH 法[2]等,这类算法能快速构造解,但通常解的质量和算法通用性较差.基于计算智能的算法,特别是基于混合策略的算法,通常能产生较好的结果,比如文献[3]提出的结合遗传算法G A (Genetic A lgorithm )和模拟退火算法的G AS A 算法、文献[4]提出的结合蚁群优化ACO (Ant Col ony Op ti m izati on )算法和局部搜索算法的AM 算法及文献[5]提出的结合经典粒子群优化PS O (Particle S war m Op ti m izati on )算法和变邻域搜索VNS (Variable Neighborhood Search )算法[6] 的PS O VN S 算法.PS O 算法最早是由Kennedy 和Eberhart[7-8]提出的,它的基本原理源于对鸟群捕食行为的仿真.与ACO 算法类似,PS O 算法是一种基于群智能方法的优化技术,同时还与G A 类似,是一种基于进化的优化工具.目前,PS O 算法在解决组合优化问题中的应用主要有两条途径:一是利用经典的连续PS O 算法,比如,文献[9]使用PS O 算法去解决单一机器调度问题,它采用随机键表示法去表示粒子的位置,通过根据粒子在每一维的值对作业进行排序,就可以把粒子的位置映射为一个合法的调度,文献[5,10]也用相同的方式把连续PS O 算法应用到PFSP 及单一机器带权总拖期调度问题的求解中.显然,这些方法并没有充分考虑到离散型组合优化的特点,不可避免地存在表示冗余大、搜索效率低等缺点.另一种方式最早由Clerc [11]提出,它根据组合优化的特点,定义相应的离散粒子群优化DPS O (D iscrete Particle S war m Op ti m izati on )算法,采用这种思想,文献[12-13]分别提出了集美大学学报(自然科学版)第13卷求解旅行商问题和二次分配问题的DPS O 算法,都具有良好的性能.与文献[12-13]类似,本文提出了一种求解PFSP 的DPS O 算法,与文献[5]使用连续PS O 算法去处理PFSP 不同,DPS O 算法根据PFSP 及离散量运算的特点,定义粒子的位置为作业的置换,粒子的速度为置换中的作业的交换,并对粒子的运动规则进行了重新定义,与文献[5]类似,采用VNS 算法来平衡算法的空间勘探与局部求精能力,但VNS 算法的具体实现与文献[5]不同,同时,还使用了逆序算子来进一步提高粒子群的多样性.在Taillard 测试问题集上对DPS O 算法的性能进行了测试,结果表明它具有良好的性能.1 粒子群优化算法根据粒子对粒子群中的其它粒子的感知程度,可以把PS O 算法分为全局PS O 算法和局部PS O 算法,全局PS O 算法中的每个粒子能知道粒子群中所有粒子中的历史最好解,而局部PS O 算法中的粒子只知道某种近邻结构中的最好解.PS O 算法通常采用随机化的方式去为粒子产生初始位置和速度(随机初始解),在此之后,在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解,叫做个体极值点(用p best 表示其位置),全局版PS O 算法中的另一个极值点是整个种群目前找到的最好解,称为全局极值点(用g best 表示其位置),而局部版PS O 算法不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用l best 表示其位置).粒子的信息可以用N 维向量表示,把粒子的位置表示为X =(x 1,x 2,…,x n ),而把粒子的速度表示为V =(v 1,v 2,…,v n ),其他向量类似.式(1)和式(2)是粒子速度和位置的更新方程(对局部PS O 算法,用l best 替换式(1)中的g best ):v t+1j=w v t j +c 1r 1(p best t j-x t j )+c 2r 2(g best t j -x tj ),(1)x t+1j=x t j +v t+1j .(2)其中:w 是惯性系数,其主要作用是产生扰动,以防止算法的早熟收敛;c 1和c 2是加速系数(或称学习因子),分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长,若太小,则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去,或飞过目标区域,合适的c 1和c 2可在加快收敛速度的同时还能不易陷入局部最优,通常令c 1=c 2=2;r 1和r 2是[0,1]之间的随机数.2 求解PFSP 的离散粒子群优化算法与PS O 算法类似,DPS O 算法的关键就是要根据问题领域定义粒子的位置和速度的表示,同时,根据离散量的运算特点,定义这些量的运算规律和粒子的运动方程,下面对求解PFSP 的DPS O 算法的基本量及其运算法则进行描述.211 粒子的位置粒子的位置X 是一个N 维向量(它是n 个作业的一个置换,直接表示一种调度方案),在X 中,维表示调度顺序,每一维的数据表示作业,粒子的位置X 可表示为:X =(x 1,x 2,…,x i ,…,x N ),1≤i ≤N ,1≤x i ≤N ,N 是作业数.212 粒子的速度速度V 的作用是改变粒子的位置,与粒子的位置X 的定义类似,速度V 是一个N 维向量,表示为:V =(v 1,v 2,…,v i ,…,v N ),1≤i ≤N ,1≤v i ≤N .速度V 的每一维上的数据有二种含义,如果v i 等于0,表示空操作,即如果用该分速度作用某一个位置,它将不影响位置上相应维的数据,而如果不等于0,表示把此位置的相应维上的数据修改为v i ,它实际上是一种交换操作,即交换X 中的作业v i 和x i ,由于速度的作用只是交换X 中的作业,这样就保证了X 在任意V 的作用下依然是n 个作业的一个置换,亦即保证了解的可行性.89?第2期宁正元,等:置换流水车间调度问题的离散粒子群优化算法213 位置与速度的加法运算位置与速度的加法运算实现了粒子位置的移动,使粒子进入了一个新的位置,表示为:X =X +V .新位置的每一维的数据依次由式(3)的操作确定:if v i =0,s wap (x i ,v i )else,(3)式中s wap (x i ,v i )表示交换X 中的作业x i 和v i .214 位置的减法两个位置X 2和X 1相减的结果是一个速度V ,表示V =X 2-X 1,它表示如果把V 作用在X 1上将得到位置X 2,可以通过下述过程来计算:比较X 1和X 2在每一维i 上的值,如果相同,则使v i 等于0,如果不同,则使v i 等于x 2,i ,即V 中的任意一个元素可表示为:v i =if x 1,i =x 2,i ,x 2,ielse .(4)215 速度的数乘速度的数乘具有概率意义,它可以表示为:V 2=c ?V 1,c ∈[0,1].式中c 是一个常数,它具有概率的意义,在实际计算V 2时,对V 1中的每一维的速度v 1,i ,生成一个0到1之间的随机数rand,如果rand 小于c,则使v 2,i 等于v 1,i ,否则,v 2,i 等于0,即V 2中的任意一个元素可表示为: v 2,i =v 1,iif rand ≥c,0else .216 速度的加法两个速度相加,得到的新速度表示为:V =V 1+V 2,其中每一个速度分量v i 定义为:v i =v 1,i if (v 1,i ≠0and v 2,i =0)or (v 1,i ≠0and v 2,i ≠0and rand <0.5),v 2,i ,式中rand 是一个0到1之间的随机数.217 粒子的运动方程由于离散量运算的特殊性,对粒子的运动方程作了修改,取消了原有的惯性项,即式(1)中右边的第一项,因为速度的定义使位置的运动是一步到位的,所以它已经意义不大,粒子的运动方程具体描述如下:V =c 1(X p best -X )+c 2(X g best -X ),X =X +V .(5)由于惯性的主要作用是产生扰动,维持粒子群的多样性,没有它的作用,DPS O 算法将迅速陷入早熟,本文把VNS 算子作用到每个粒子上,它既能提高粒子个体的适应性,又能提高群体的多样性,为了进一步提高群体的多样性,当发现粒子个体极值停滞时,采用逆序(inversi on )算子来进一步提高群体的多样性.3 变邻域搜索算子VNS 算法是近年来新涌现的一种计算智能方法,它通过系统性地改变邻域搜索中的邻域结构,使算法获取全局最优解的可能性比用单个邻域结构的搜索算法高[6].本文所使用的VNS 算子采用了两种邻域结构,即交换邻域和插入邻域,位置X 的交换领域是交换X 中任意2个作业所产生的集合,而插入领域是将X 中的任意一个作业插入到任意一个其他位置所产生的集合,在此基础上定义了交换邻域搜索算子S wap (X )和插入邻域搜索算子Insert (X ),它们都采用首次改进的策略,为了增加随机性,邻域搜索的顺序用随机的方式产生,在此基础上,采用I nsert 为第一邻域,S wap 为第二邻域,定义VNS 算子的伪代码为:99?集美大学学报(自然科学版)第13卷重复下述操作:重复下述操作: insertI m p r oved =I nsert (X );直到insertI m p r oved 等于false;s wap I m p r oved =S wap (X );直到s wap I m p r oved 等于false .4 仿真实验及结果采用全局版PS O 实现了DPS O 算法,在根据式(5)修改了粒子的位置后,把VNS 算子作用到每个粒子上,以提高粒子的适应值.在Taillard 标准测试问题集上进行了仿真实验,与文献[4]相同,选用其中从20×5到100×20的9个不同维数的测试问题,每一种维数有10个不同的问题实例.对DPS O 算法在带VNS 算子(表示为DPS O VN S )和不带VNS 算子(表示为DPS O )的情况下的性能进行了对比实验,DPS O VN S 算法由于使用了VNS 算子和逆序算子,它可以有效地保持粒子群的多样性,所以粒子群可以比较小,仿真表明,取粒子数为10就能产生满意的结果.为了选择确定参数c 1和c 2的值,在20×10和50×10测试集上进行了仿真,结果表明c 1和c 2的鲁棒性较强,比如,在0101到0150之间,其结果都比AM 算法的结果好,在后面的仿真中,c 1和c 2都设置为0110;对DPS O 算法,由于比较容易陷入早熟收敛,所以要求粒子群足够大,实验中取粒子数为2×n ×m .表1是在Taillard 测试问题集上的性能比较.其中AM 的数据来源于文献[4],是4种不同策略的最佳解,其中蚁群的大小为10;PS O VNS 的数据来源于文献[5],粒子群的大小为2倍的作业数,迭代次数为100,每个测试用例运行5次,取平均值.DPS O VN S 算法和DPS O 算法在每个测试用例运行20次,取平均值.表1中最后一列是DPS O VN S 算法的迭代次数,在所有问题集上,DPS O VN S 算法的迭代次数与粒子群数的乘积都小于PS O VNS 所使用的值,为公平比较,使DPS O 算法与DPS O VNS 算法的运行时间相当.表1中所给出的计算结果均表示为相对于标准测试库中给出的最好结果的平均百分比偏差.表1 在Taillard 测试问题集上与其它算法的性能比较Tab 11 S i m u l a ti o n re su lts com p a ri ng w ith o the r a l go rithm s o n T a ill a rd p r o b l em se tn ×mNEH AM PS O VNS DPS O DPS O VNS 迭代次数20×53.6630.0410.280.8850.04110020×104.6010.2270.702.2920.091 10020×203.7310.1810.562.0710.08010050×50.7270.0080.180.59 20.00520050×105.0731.1811.043.1070.92220050×205.9711.932 1.714.6841.583200100×50.5270.0080.110.4670.004200100×102. 2150.3700.671.7680.364200100×204.2751.8781.283.6281.064200从表1中可以看出,在所有的测试问题上,DPS O VNS 、A M 和PS O VNS 都远远好于NEH 算法,与PS O VNS 相比,DPS O VNS 算法在所有问题上都具有更好的性能,与A M 相比,DPS O VNS 算法只是在20×5问题上相同,在其它问题上都优于A M 的结果,而DPS O 算法尽管比NEH 好,但和使用了邻域搜索算法的DPS O VNS 、A M 和PS O VNS 算法相比有明显的差距,充分说明了VNS 算子能有效地提高DPS O 算法的性能.5 结论以求解PFSP 为例,提出了一个DPS O 算法的具体实现,算法中使用VNS 算子和逆序算子来保持粒子群的多样性和提高算法的局部求精能力,使算法在粒子群比较小的情况下依然能在空间探索和局001?第2期宁正元,等:置换流水车间调度问题的离散粒子群优化算法部求精间取得较好的平衡,仿真实验表明DPS O 算法具有良好的性能,说明如果能够针对问题的特点,重新定义DPS O 算法的位置、速度等量及其运算规则,DPS O 算法能够很好地应用到NP -困难的组合优化问题的求解中.[参考文献][1]王凌.智能优化算法及其应用[M ].北京:清华大学出版社,施普林格出版社,2001:1702174.[2]韦有双,杨湘龙,冯允成.一种新的求解Fl ow -shop 问题的启发式方法[J ].系统工程理论与实践,2000,20(9):41247.[3]王凌,郑大钟.求解同顺序加工调度问题的一种改进遗传算法[J ].系统工程理论与实践,2002,22(6):74279.[4]王笑蓉,吴铁军.Fl owshop 问题的蚁群优化调度方法[J ].系统工程理论与实践,2003,23(5):65271.[5]T ASGETI RE N M F,SE VK L IM ,L I A NG Y C,et al .Particle S war m Op ti m izati on A lgorith m for Per mutati on Fl owshopSequencing Pr oble m [C ]//Ant Col ony Op ti m izati on and S war m I ntelligence:the 4th I nternati onal Workshop.Berlin: Sp ringer 2Verlag,2004:3822390.[6]MLADE NOV I C ’N,HANSE N P .Variable neighborhood search [J ].Computers and Operati ons and Research,1997,24:102721100.[7]KE NNE DY J,E BERHART R.Particle S war m Op ti m izati on [C ]//I EEE I ntl Conf on Neural Net w orks .New Jersey:I EEE Service Center,1995:194221948.[8]E BERHART R,KE NNE DY J.A Ne w Op ti m izer U singParticle S war m Theory [C ]//Pr oc of the Sixth I nternati onal Sy m 2posiu m on M icr o Machine and Hu man Science .Ne w Jersey:I EEE Service Center,1995:39243.[9]C AG N I N A L,ES QU I V E L l S,G ALLARD R.Particle S war m Op ti m izati on f or Sequencing Pr oble m s:A Case Study [C ]// Pr oceeding of the 2004Congress on Ev oluti onary Co mputati on .O reg on:I EEE Press,2004:5362541.[10]T ASGETI RE N M F,SE VK L IM ,L I A NG Y C,et al .Particle S war m Op ti m izati on A lgorith m f or Single Machine T otalW eighted Tardiness Pr oble m [C ]//Pr oceedings of the 2004Congress on Evoluti onary Computati on .O regon:I EEEPress,2004:141221419.[11]CLERC M.D iscrete particle s war m op ti m izati on [M ].Berlin:Sp ringer 2Verlag,2004:2192240.[12]钟一文,杨建刚,宁正元.求解TSP 问题的离散粒子群优化算法[J ].系统工程理论与实践,2006,26(6):88294.[13]钟一文,蔡荣英.求解二次分配问题的离散粒子群优化算法[J ].自动化学报,2007,33(8):8712874.D iscrete Parti cle Swar m O pti m i za ti on A lgor ith m forPer m ut a ti on Flowshop Scheduli n g ProblemN ING Zheng 2yuan,L IN Da 2hui,L IL i 2shan,Z HONG Yi 2wen (College of Computer and I nf or mati on Science,Fujian Agriculture and Forestry University,Fuzhou 350002,China ) Abstract:A discrete particle s war m op ti m izati on algorithm was designed t o tackle the per mutati on fl ow 2shop scheduling p r oble m (PFSP ).It defined the per mutati on of j obs as the positi on of the particle,and it defined the s wap of j obs in permutati on as the vel ocity of the particle .Based on the characteristics of the oper 2ati ons of discrete variables,it redefined the move ment rules of the particle .A variable neighborhood search operat or and an inversi on operat or were used t o keep the diversity of s war m and i m p r ove the algorith m πs inten 2sificati on ability .U sing those operat ors,the p r oposed algorithm could get a good balance bet w een exp l orati on and exp l oitati on .I n order t o observe its perf or mance,si m ulati on experi m ents were carried on Taillard πs benchmark p r oble m s .The results show that it can p r oduce good results .Key words:discrete particle s war m op ti m izati on;per mutati on fl owshop scheduling p r oble m;variable neighborhood search;inversi on operat or(责任编辑陈敏)101?。