改进猫群算法求解置换流水车间调度问题

改进微粒群优化求解置换流水车间调度问题刘延风;刘三阳【期刊名称】《计算机集成制造系统》【年(卷),期】2009(015)010【摘要】To solve permutation flow shop scheduling problems, an Improved Particle Swarm Optimization(IPSO) algorithm was proposed. Firstly, each sequence of jobs was generated by greedy randomized adaptive search based on heuristics. The initial best position of each particle was no longer the randomly generated initial position of each particle, it was converted from above sequence of jobs. Then, a swap-based local search was applied for the best position of each particle. Finally, the simulation results based on benchmarks demonstrated the effectiveness of IPSO.%针对置换流水车间调度问题,提出了一种改进微粒群优化的求解算法.首先,由基于启发式信息的贪婪随机自适应算法得到工件加工顺序,个体最优的初始值不再是随机生成的初始值,而是由该工件加工顺序转化而成;然后,对个体最优解进行了交换型部搜索;最后,通过对Car系列和Rec系列基准的测试,表明了该算法的有效性.【总页数】6页(P1968-1972,1985)【作者】刘延风;刘三阳【作者单位】西安电子科技大学,应用数学系,陕西,西安,710071;西安电子科技大学,应用数学系,陕西,西安,710071【正文语种】中文【中图分类】TP18【相关文献】1.改进猫群算法求解置换流水车间调度问题 [J], PEI Xiaobing;YU Xiuyan2.应用改进区块遗传算法求解置换流水车间调度问题 [J], 裴小兵;张春花3.求解改进布谷鸟算法的置换流水车间调度问题 [J], 邴孝锋; 陶翼飞; 董圆圆; 孙思汉4.改进粒子群算法求解置换流水车间调度问题 [J], 张源;王加冕5.应用改进混合进化算法求解零空闲置换流水车间调度问题 [J], 裴小兵;李依臻因版权原因，仅展示原文概要，查看原文内容请购买。

改进激素算法求解置换流水车间调度问题
郑堃;练志伟;王玉国;朱长建;顾新艳;刘轩
【期刊名称】《电子科技大学学报》
【年(卷),期】2022(51)6
【摘要】遗传算法中由于激素调节的选择、交叉以及变异算子存在较大目标函数
值失调的问题,提出了基于改进激素浓度计算法的自适应遗传算法(IHCCM-IAGA)。

IHCCM-IAGA采用基于工件排列的编码方式,并利用反向学习法初始化种群,提高了初始解的质量;针对两点交叉(TPX)算子存在冗余度高、效率低等问题,提出了改进型TPX(ITPX),并引入优良基因库及免疫因子,实现两种交叉方式,同时监控整个进化过程,避免了优质染色体的丢失;设计了多种扰动保持丰富的多样性结构以及相关的局
部搜索算法组合成变异算子,建立种群湮灭算子,并设置湮灭因子来引导变异算子中
的局部搜索。

将IHCCM-IAGA应用于置换流水车间调度问题中,并进行该问题标
准算例的各项测试,结果表明IHCCM-IAGA切实有效。

【总页数】14页(P890-903)
【作者】郑堃;练志伟;王玉国;朱长建;顾新艳;刘轩
【作者单位】南京工程学院汽车与轨道交通学院;中德智能制造研究院
【正文语种】中文
【中图分类】TP391
【相关文献】
1.改进猫群算法求解置换流水车间调度问题
2.应用改进区块遗传算法求解置换流水车间调度问题
3.求解改进布谷鸟算法的置换流水车间调度问题
4.改进粒子群算法求解置换流水车间调度问题
5.应用改进混合进化算法求解零空闲置换流水车间调度问题
因版权原因，仅展示原文概要，查看原文内容请购买。

求解置换流水车间调度问题的Memetic算法苏志雄;伊俊敏【摘要】针对以最小化最大完工时间为目标的置换流水车间调度问题,建立了0-1型混合整数线性规划模型.在对模型进行Benders分解的基础上,提出了问题的求解策略,进而设计了一种Memetic调度算法,并探讨了基于组合规则的种群初始化方法和混合遗传操作.为了提高算法的搜索效率,采用了更加高效的适应度值计算方法以及两种邻域搜索方法.最后,基于Benchmark算例的仿真实验结果表明了该算法的有效性,可以找到26个算例中的17个最优解(65.38％),且其平均相对误差的均值仅为0.88％.【期刊名称】《厦门理工学院学报》【年(卷),期】2015(023)006【总页数】5页(P25-29)【关键词】生产调度;置换流水车间;Memetic算法;邻域搜索【作者】苏志雄;伊俊敏【作者单位】厦门理工学院管理学院,福建厦门361024;厦门理工学院管理学院,福建厦门361024【正文语种】中文【中图分类】F273;TP278流水车间调度问题通常可以描述为n个工件要在m台机器上加工，每个工件有m 道工序，每道工序都要在不同的机器上加工，所有工件的加工顺序都相同，各工件在各机器上的加工时间已知，调度目标是确定每台机器上工件的加工顺序及开工时间，使得特定的性能指标最优。

置换流水车间调度问题(permutation flow shop scheduling problems,PFSP)是对流水车间调度问题的进一步约束，即约定每台机器上所有工件的加工顺序相同，其解空间的规模为n!，远远小于流水车间调度问题的规模(n!)m。

PFSP中的最小化最大完工时间问题，利用三元组表示法可以记为此类调度问题是研究流水车间调度问题最为自然的起点，其研究成果可以为更加复杂的实际调度问题研究提供基础，因此研究和开发高效的生产调度算法具有非常重要的理论意义和应用价值。

由于此类调度问题的NP难特性[1]，精确算法只能求解很小规模的算例，而启发式算法[2-5]可以在很短的时间内获得调度解，但是其求解质量和通用性较差。

改进启发式的并行蚁群算法在置换流水线调度问题上的应用的开题报告1. 研究背景流水线调度问题是一种经典的优化问题，尤其在制造业中有着广泛的应用。

在流水线调度问题中，需要对一些作业任务的执行顺序进行调度，以使得整个流水线的效率最大化。

同时，为了最大化流水线的效率，还需要考虑到一些限制条件，例如各个作业之间的依赖关系、流水线上的空闲时间等。

同时，在解决流水线调度问题时，我们也可以采用启发式算法，例如蚁群算法等。

但是在处理大规模的流水线调度问题时，传统的单个蚁群算法已经无法满足要求。

因此，引入并行蚁群算法可以有效提高解决问题的效率和精度。

2. 研究内容本文将主要研究如何改进启发式的并行蚁群算法在置换流水线调度问题上的应用。

具体来说，本文将探索以下研究内容：（1）对传统的蚁群算法进行改进，以提高算法的效率和精度。

例如，可以引入局部搜索算法、双向搜索算法等，以克服传统蚁群算法的局限性；（2）采用并行化的方法，使得算法能够处理更大规模的流水线调度问题。

并且，可以通过多处理器或者GPU等平台进行并行计算，以充分利用硬件的性能；（3）对算法进行实证研究，验证改进的算法在流水线调度问题中的实际应用效果，并与其他现有的算法进行比较。

3. 研究意义本研究将在以下方面具有重要意义：（1）对于流水线调度问题的解决，提供了一种新的、高效的算法。

（2）对于并行算法的研究，为其他类型的优化问题提供了一些新的思路和方法。

同时，可以进一步探索并行算法的性能极限。

（3）验证算法的实际效果，为现实问题的解决提供了一些参考。

同时，也可以为流水线调度问题的实际应用提供一些改进的建议。

4. 研究方法本文采用实证研究的方法。

具体来说，将首先对现有的蚁群算法进行改进，并采用并行化的方式对算法进行优化。

然后，通过对流水线调度问题进行实验研究，验证算法的实际应用效果，并与其他现有算法进行比较。

最后，对实验结果进行分析和总结，提出改进建议。

5. 预期结果本研究预计可以实现以下结果：（1）改进的启发式算法能够更快、更准确地解决流水线调度问题。

改进并行蚁群算法求解置换流水线调度问题
黄华;肖菁;张军
【期刊名称】《计算机工程与设计》
【年(卷),期】2010(031)003
【摘要】为了解决置换流水线的调度问题,提出了改进的并行蚁群算法.针对置换流水线问题本身的特性,在蚂蚁系统算法(ACS)的基础上,设计出了新的启发式信息算法.在计算大数据量的情况下,通过设计的新规律对数据进行分组,并对分组进行并行计算,然后合并各组最优解来问题的最优解.实验结果表明,该改进方法行之有效,新的启发式信息提高了解的质量,而按数据规律的分组并行不仅缩小查找最优值时间,相比于随机分组的并行算法,更加提高了解的质量.
【总页数】4页(P582-585)
【作者】黄华;肖菁;张军
【作者单位】中山大学,软件学院,广东,广州,510275;中山大学计算机科学系,广东,广州,510275;中山大学计算机科学系,广东,广州,510275
【正文语种】中文
【中图分类】TP18
【相关文献】
1.改进蝙蝠算法求解置换流水线车间调度问题 [J], 周宗渠;田大钢
2.求解置换流水线调度问题的改进萤火虫优化算法 [J], 张丽红;余世明
3.求解零空闲流水线调度问题的改进蚁群算法 [J], 张风荣;段俊华;庞荣波;韩红燕
4.改进的蚁群算法求解置换流水车间调度问题 [J], 张丽萍
5.改进布谷鸟搜索算法求解置换流水线调度问题 [J], 彭勇; 郑慧君
因版权原因，仅展示原文概要，查看原文内容请购买。

改进的蚁群算法求解置换流水车间调度问题张丽萍【摘要】In order to avoid the shortcomings of ant algorithm for solving permutation flow shop scheduling problem that easily fall into local best situation and long calculation time, in this paper, an improved Max-MinAnt System (MMAS)algorithm which apply Nawaz-Enscore-Ham ( NEH ) heuristic algorithm to enhance the quality of the initial solutions and further improve the search capabil-ities through regulation of adaptive strategies is proposed . Finally we use the proposed algorithm to solve Taillard benchmarks set . Compared with other approaches , the experimental results show the effectiveness of the proposed algorithm .%针对蚂蚁算法在求解置换流水车间调度问题时易陷入局部最优以及计算时间较长的缺点，对最大最小蚂蚁系统( MMAS )进行了改进。

在该算法中，采用 NEH 启发式算法提高初始解质量，并通过自适应的调节策略进一步提高蚁群算法的搜索能力。

运用提出的混合算法求解 Taillard 基准测试集，并将测试结果与其他算法进行比较，验证了该调度算法的有效性。

2020年软 件2020, V ol. 41, No. 6作者简介: 张源(1996–)，男，研究生，主要研究方向：流水车间调度算法；王加冕(1994–)，男，研究生，主要研究方向：流水车间系改进粒子群算法求解置换流水车间调度问题张 源，王加冕（昆明理工大学机电工程学院，昆明 650500）摘 要: 针对置换流水车间调度问题，本文以最小化最大完工时间为优化目标建立仿真模型，并设计一种改进粒子群算法（IPOS ）进行求解。

为克服标准粒子群算法寻优结果稳定性差的缺点，首先，该算法结合NEH 算法生成初始种群；其次，在迭代进化中引入自适应权重系数和学习因子；最后，在粒子的个体极值搜索中引入模拟退火算法的Metropolis 准则。

将改进前后的粒子群算法分别进行仿真优化实验，实验结果验证了该算法的优越性和有效性。

关键词: 置换流水车间；粒子群算法；NEH 算法；Metropolis 准则；最小化完工时间 中图分类号: TP391.9 文献标识码: A DOI ：10.3969/j.issn.1003-6970.2020.06.023本文著录格式：张源，王加冕. 改进粒子群算法求解置换流水车间调度问题[J]. 软件，2020，41（06）108 111+131An Improved Particle Swarm Optimization Algorithm is Proposed toSolve the Displacement Flow Shop Scheduling ProblemZHANG Yuan, WANG Jia-mian(College of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500)【Abstract 】: Aiming to the permutation flow shop scheduling problem, a simulation model was established with the goal of minimizing the maximum completion time, and an improved particle swarm optimization (IPOS) algorithm was designed to solve the problem. In order to overcome the poor stability of the optimization results of the standard particle swarm optimization algorithm, firstly, the algorithm combines with NEH algorithm to generate the initial population. Secondly, adaptive weight coefficient and learning factor are introduced into iterative evolution. Finally, the Metropolis criterion of simulated annealing algorithm is introduced into the individual extremum search of par-ticles. The particle swarm optimization (pso) algorithm is simulated and optimized before and after the improvement. The experimental results verify the superiority and effectiveness of the algorithm.【Key words 】: Permutation flow shop; Particle swarm optimization algorithm; NEH algorithm; Metropolis criterion; Makespan0 引言车间生产调度问题[1]是指在一定的时间内将生产资源与生产任务及设备进行合理的分配，其目的是对某些特定的性能指标进行优化。

求解置换流水车间调度问题的一种混合算法【摘要】置换流水车间调度问题是一类经典的组合优化问题，智能优化算法是求解该问题的首要方法。

遗传算法和分布估计算法在PFSP问题上均存在着一定的缺陷，即无法平衡局部搜索和全局搜索。

为了克服它们的缺陷，本文将分布估计算法与遗传算法结合，并引入模糊逻辑控制来调节两种算法的参与率，最后用基准算例的测试结果证实了本文所设计的混合算法是有效的。

【关键词】置换流水车间调度；分布估计算法；遗传算法；模糊逻辑控制0.前言置换流水车间调度问题（PFSP）是对经典的流水车间调度问题进行简化后得到的一类子问题，最早在石化工业中得到应用，随后扩展到制造系统、生产线组装和信息设备服务上[1]。

该问题一般可以描述为，n个待加工工件需要在m 台机器上进行加工。

问题的目标是求出这n个工件在每台机器上的加工顺序，从而使得某个调度指标达到最优，最常用的指标为工件的总完工时间（makespan）最短。

PFSP最早由Johnson于1954年进行研究[2]，具有NP难性质[3]。

求解方法主要有数学规划，启发式方法和基于人工智能的元启发式算法[4]。

数学规划等适用于小规模问题，启发式方法计算便捷，却又无法保证解的质量。

随着计算智能的发展，基于人工智能的元启发式优化算法成为研究的重点。

遗传算法（GA）是研究与应用得最为广泛的智能优化算法，利用遗传算法求解PFSP问题的研究也有很多。

遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。

然而，遗传算法通常存在着过早收敛，容易陷入局部最优的现象。

导致这一现象的原因在于遗传算法的交叉、变异操作具有一定的随机性，在求解PFSP问题的过程中往往会破坏构造块，产生所谓的连锁问题。

为了克服遗传算法的缺陷，研究人员提出了一种不进行遗传操作的分布估计算法[5]（EDA）。

EDA是一种运用统计学习的新型优化算法。

相比GA，EDA在全局搜索上有较大的优势，而局部搜索能力不足，同样会导致局部最优[6][7]。

改进的粒子群算法求解置换流水车间调度问题摘要:针对置换流水车间调度问题，提出了一种改进的粒子群算法进行求解。

改进算法引入了判断粒子群早熟的方法，并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异，利用模拟退火思想概率接收新的最优粒子。

种群最优粒子的改变会引导粒子群跳出局部极值的约束，从而克服粒子群的早熟状态。

通过对置换流水车间调度问题中car系列和rec系列部分基准数据的测试，证明了该算法的有效性。

关键词:粒子群算法；多样性；局部收敛；置换流水车间调度improved particle swarm optimization for permutation flowshop scheduling problemzhang qi.liang1,2*，chen yong.sheng1，han bin21. college of electronic and informationengineering,tongji university, shanghai 200331,china2. college of electricity and information engineering, jiangsu university of science and technology, zhangjiagang jiangsu 215600, chinaabstract:to solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. improved algorithm introduced a method to judge the prematurity state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature convergence, simulated annealing method was used to accept the new particle.the mutation for best particle can guide the particle swarm to escape from the local best value’s limit and overcome the particles’ premature stagnation.the simulation results based on car andrec’benchmarks of permutation flowshop scheduling problem proved the effectiveness of the proposed algorithm.to solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. improved algorithm introduced a method to judge the premature state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature convergence, and used simulated annealing method to accept the new particle. the mutation for best particle can guide the particle swarm to escape from the local bestvalue s limit and overcome the particles premature stagnation. the simulation results based on car and rec benchmarks of permutation flowshop scheduling problem prove the effectiveness of the proposed algorithm.key words: particle swarm optimization (pso); diversity; local convergence; permutation flowshop scheduling0 引言置换流水车间调度问题(permutation flowshop scheduling problem，pfsp)是一类经典的加工调度问题。