基于混合粒子群优化算法的置换流水车间调度问题研究

改进微粒群优化求解置换流水车间调度问题刘延风;刘三阳【期刊名称】《计算机集成制造系统》【年(卷),期】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], 裴小兵;李依臻因版权原因，仅展示原文概要，查看原文内容请购买。

粒子群算法求解作业车间调度问题研究的开题报告一、选题的背景：作业车间调度问题是生产中十分重要的一种问题，涉及工厂、工程、交通、物流等诸多领域。

因此，对于如何有效地解决作业车间调度问题，一直是一个重要的研究方向。

粒子群算法，是一种启发式优化算法，已经在许多优化问题的求解中得到了广泛的应用。

本研究旨在探究粒子群算法在作业车间调度问题中的应用，提出适合该问题的解法。

二、研究的目的和意义：随着生产流程的不断优化，作业车间调度问题的复杂性也在不断增加，对于如何高效、快速地解决这一问题，有着越来越高的要求。

因此，本研究的目的在于探究粒子群算法在作业车间调度问题中的应用，寻找出既可以有效解决问题、又能提高工厂生产效率的算法，以期对相关领域生产的优化和提升有所帮助。

三、研究的方法和步骤：1、对已有的作业车间调度问题的研究进行归纳整理，了解各种算法的优缺点以及存在的问题。

2、针对作业车间调度问题，建立相应的数学模型，明确目标函数和约束条件。

3、研究粒子群算法，并建立适合该问题的算法模型，探究其适用性和实用性。

4、通过计算机模拟实验，不断优化粒子群算法模型，并与其他算法进行对比。

5、根据模拟实验的结果，对所提出的算法模型进行实验验证，以确定最优解，从而验证研究的可行性和有效性。

四、预期研究成果和应用：通过本研究，将对解决作业车间调度问题提供新的思路和方法，提高生产效率，降低成本，提高竞争力。

同时，此研究可为企业在实际生产调度中提供一定的参考依据和技术支持。

五、论文结构：第一章：绪论1.1、选题背景与意义1.2、国内外研究现状1.3、研究目的和方法第二章：作业车间调度问题2.1、问题的定义和分类2.2、问题的数学模型2.3、优化目标和约束条件第三章：粒子群算法3.1、算法原理3.2、算法流程3.3、算法的优点和缺点第四章：粒子群算法在作业车间调度问题中的应用4.1、算法改进和优化4.2、算法实现和计算机模拟实验4.3、与其他算法的对比第五章：实验结果与分析5.1、实验结果展示5.2、结果分析和讨论第六章：总结与展望6.1、研究总结6.2、研究展望六、计划及进度：第一年：1、调研相关文献，撰写文献综述2、理清作业车间调度问题的模型与求解算法3、对粒子群算法进行深入研究，开展实验，根据实验结果对算法进行改进，并进行算法性能分析第二年：1、根据算法性能分析，完善粒子群算法模型2、将问题的实际数据输入模型中进行计算3、算法比对和性能分析第三年：1、进一步深入分析算法效果2、根据实验数据得出结论，并进行实操检验3、论文编写，答辩。

一种新的混合粒子群算法求解置换流水车间调度问题张其亮;陈永生【期刊名称】《计算机应用研究》【年(卷),期】2012(029)006【摘要】For the problem that the PSO is easy to be trapped in local optimal, this paper put forward a hybrid PSO algorithm which combined the iG algorithm. The algorithm judged the particles' status by the change of particles' individual and global best value in continuous generations, and used destruction and construction operation of IG algorithm to mutate the relating particle and the global best position after discovering that the particle was at a standstill or the particle swarm was trapped in local optimal. The new particles being mutated were accepted according to the simulated annealing theory. The mutation of global best particle could guide the particle swarm to escape from the local best value' s limit and increase the diversity of particles , which avoided the particle' s premature stagnation. Simultaneously, the algorithm adopted cycle iterative method in order to get or approach the best result quickly. It searched the best solution step by step on the basis of stage optimization. The paper applied the hybrid PSO algorithm to the permutation Flow-Shop scheduling problem, and compared it with the other representative algorithm. The result shows that the hybrid PSO algorithm can avoid the particle' s premature stagnation effectively and the algorithm is betterthan other algorithms in the quality of searching the best solution.%针对粒子群算法易早熟的缺点,提出了一种结合选代贪婪(IG)算法的混合粒子群算法.算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态,在发现粒子出现停滞或者粒子群出现早熟后,及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异,变异后利用模拟退火思想概率接收新值.全局最优粒子的改变会引导粒子跳出局部极值的约束,增加粒子的多样性,从而克服粒子群的早熟现象.同时,为了使算法能更快找到或逼近最优解,采用了循环迭代策略,在阶段优化结果的基础上,周而复始循环迭代进行求解.将提出的混合粒子群算法应用于置换流水车间调度问题,并在问题求解时与几个具有代表性的算法进行了比较.结果表明,提出的算法能够克服粒子群早熟,在求解质量方面优于其他算法.【总页数】4页(P2028-2030,2034)【作者】张其亮;陈永生【作者单位】同济大学电子与信息工程学院,上海 200331;同济大学电子与信息工程学院,上海 200331【正文语种】中文【中图分类】TP18【相关文献】1.求解流水车间调度问题的混合粒子群算法 [J], 田野;刘大有2.有效的混合粒子群算法求解阻塞流水车间调度问题 [J], 张其亮;陈永生3.求解流水车间调度问题的混合粒子群算法 [J], 齐学梅;罗永龙;赵诚4.一种求解置换流水车间调度问题的多策略粒子群优化 [J], 汤可宗;詹棠森;李佐勇;舒云5.应用改进混合进化算法求解零空闲置换流水车间调度问题 [J], 裴小兵;李依臻因版权原因，仅展示原文概要，查看原文内容请购买。

混合粒子群算法在动态车间调度中的应用一、引言随着制造业的高速发展，车间调度问题已经成为制造企业管理中的一个重要课题。

车间调度问题是指在一定条件下，对加工对象在不同机器上的加工顺序及加工时间进行排列，以达到最佳生产效率的问题。

传统的车间调度问题中，主要考虑的是静态环境下的调度问题，即在一定的条件下，进行固定时间段内的产线调度。

在实际生产中，很多生产车间都处于动态变化的环境下，需要对这些动态变化做出及时的调整和优化。

混合粒子群算法是一种新型的优化算法，它是基于群体智能理论和粒子群算法的改进，能够有效解决车间调度问题中的动态环境调度问题。

本文将从混合粒子群算法的原理和特点入手，探讨其在动态车间调度中的应用，并对比传统算法进行分析，以期为实际生产中的动态车间调度问题提供一种新的解决方案。

二、混合粒子群算法的原理和特点混合粒子群算法是一种群体智能优化算法，它的基本原理是模拟鸟群或鱼群的行为，通过个体之间的协同合作和信息共享来寻找最优解。

混合粒子群算法的主要特点如下：1. 采用“粒子”的概念，将问题空间中的每个解看作一个粒子，并通过模拟粒子的速度和位置来寻找最优解；2. 结合了全局搜索和局部搜索的特点，使得算法不易陷入局部最优解，并具有较强的搜索能力；3. 具有较好的鲁棒性和适应性，能够适应不同种类的优化问题，包括动态环境下的优化问题；4. 可以通过合适的参数设置和调整，对不同的问题进行有效求解。

三、混合粒子群算法在动态车间调度中的应用1. 动态车间调度问题的特点在传统的车间调度问题中，通常假设加工时间是固定不变的，而在动态车间调度问题中，加工时间可能会随着生产车间环境的变化而变化。

这就导致了在车间调度过程中，需要针对车间环境实时变化的情况做出相应的优化调整。

这就增加了车间调度问题的复杂性和难度。

2. 混合粒子群算法在动态车间调度中的优势混合粒子群算法具有很好的适应性和鲁棒性，能够很好地应对动态环境下的优化问题。

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]是指在一定的时间内将生产资源与生产任务及设备进行合理的分配，其目的是对某些特定的性能指标进行优化。

混合粒子群算法在动态车间调度中的应用混合粒子群算法是一种基于群体智能优化的算法，通过模拟粒子在搜索空间中的飞行轨迹，来寻找最优解。

它结合了粒子群算法和其他优化方法的特点，能够在动态车间调度问题中获得较好的性能。

动态车间调度问题是指在车间生产过程中，由于机器故障、人员变动、订单变更等因素，导致生产任务的需求发生变化，需要重新安排任务的调度问题。

这种问题具有不确定性和动态性，传统的静态调度算法无法对其进行有效优化。

混合粒子群算法则可以在不同的情况下对任务进行动态调度，以确保生产过程的高效性和灵活性。

1. 任务优先级规则：将任务的优先级作为粒子群算法的搜索方向，根据任务紧急程度和生产周期等因素来确定任务的权重，使粒子群在搜索过程中更加关注优先级高的任务，从而提高任务的执行效率。

2. 任务时序调整：根据车间调度的动态变化，对任务的时序进行动态调整。

在混合粒子群算法中，可以通过修改粒子的速度和位置来实现对任务时序的调整，确保生产任务的有序进行，同时减少任务的延误和重复。

3. 机器资源分配：根据车间资源的实际情况和任务的需求，利用混合粒子群算法进行机器资源的合理分配。

通过优化机器资源的利用，可以提高车间的生产效率和产能，并减少资源的浪费。

4. 环境适应性调整：考虑到车间调度问题的动态性和不确定性，混合粒子群算法可以根据环境的变化自适应地调整搜索策略和参数设置，以适应不同的生产环境和任务需求。

通过不断优化粒子的搜索能力，可以提高算法的搜索效率和稳定性。

混合粒子群算法在动态车间调度中的应用能够有效解决车间调度问题的动态性和不确定性，提高生产任务的执行效率和生产效益。

未来的研究可以进一步探索混合粒子群算法在动态车间调度中的应用，并结合其他优化算法和智能技术，提高算法的性能和适用性。

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

遗传算法和分布估计算法在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]。

基于粒子群算法的车间调度优化研究一、引言随着制造业的发展，车间调度问题日益突出，如何合理地安排生产计划和制定优化的调度策略已成为制造企业竞争力的关键，而粒子群算法正是一种有效的优化算法，被广泛应用于生产调度领域。

二、车间调度问题简介车间调度问题（Job Shop Scheduling Problem）指在有限的资源下，对一个车间中某一特定时期内的作业流程进行合理安排的问题。

其特点在于作业之间有制约关系，每个作业需要在特定的机器上进行加工，时间、机器等资源都是有限的。

三、粒子群算法粒子群算法（Particle Swarm Optimization, PSO）是一种群智能算法，其基本思想是模拟鸟群或鱼群行为，通过某个评价函数进行优化。

在车间调度问题中，可以将PSO应用于寻找最优的调度方案。

其中，每个“粒子”可以看作一个作业流程，每个作业需要遵循各自的加工顺序以及机器的使用限制。

四、粒子群算法的优化方案针对车间调度问题，可以利用粒子群算法来优化调度方案。

首先，预设初始的调度方案，每个“粒子”对应一种调度序列。

通过模拟粒子群的移动，可以不断地更新优化方案。

当粒子到达局部最优解时，可以利用群体智能的方式，寻找更优解。

在实际应用中，需要考虑的因素有很多，如机器利用率、工期、作业数量等等。

因此，在进行优化时需要根据实际情况进行调整，以达到最优的结果。

五、案例分析以一个简单的加工流程为例：有三台机器，分别为M1、M2、M3，需要进行5个作业的加工。

每个作业只能在特定的机器上加工，并且必须按照指定的加工顺序进行。

每个作业加工的时间分别为：J1（M1：1，M2：2，M3：2）、J2（M1：4，M2：2，M3：3）、J3（M1：3、M2：1、M3：4）、J4（M1：2、M2：4、M3：3）、J5（M1：3、M2：2、M3：1）。

现有一个调度方案，如何利用粒子群算法进行优化？首先，可以将每个作业看作一个“粒子”，根据指定的加工顺序，设置初始调度方案为J1-J2-J3-J4-J5。

改进粒子群优化算法求解车间调度问题研究改进粒子群优化算法求解车间调度问题研究摘要：设计一个高效的车间调度方案，对于提高产能和降低生产成本有着重要意义。

本文利用粒子群优化算法（PSO）来解决车间调度问题，并对其进行改进。

通过引入局部搜索和多目标方法，提高了算法的搜索能力和求解速度。

实验结果表明，改进的粒子群优化算法在车间调度问题中具有较好的性能和鲁棒性。

一、引言车间调度问题是生产管理中的重要问题之一，其目标是合理安排生产过程中的机器和工人，以最小化生产时间和生产成本，同时满足各种约束条件。

在实际生产中，车间调度问题往往是一个复杂的组合优化问题，涉及到多个工序、多个作业和多个资源的分配，具有计算复杂度高、搜索空间大的特点。

粒子群优化算法是一种启发式自适应的全局优化算法，基于群体智能和演化计算的思想。

其仿真过程类似于鸟群觅食的行为，通过不断调整粒子的状态来寻找全局最优解。

粒子群优化算法具有简单、易实现、收敛速度快等优点，在解决复杂优化问题中有广泛的应用。

二、粒子群优化算法的基本原理粒子群优化算法的基本原理包括粒子的位置、速度更新和社会经验、个体经验的信息更新等过程。

每个粒子的位置表示解向量，速度表示解向量的方向和步长。

粒子根据当前位置和速度的信息更新个体最优解和全局最优解，并改变其速度和位置。

通过迭代最大化粒子群的整体经验来实现搜索全局最优解。

三、改进粒子群优化算法的思路为了提高粒子群优化算法的求解效果，本文提出了以下改进思路：1.引入局部搜索机制。

针对车间调度问题的特点，引入局部搜索机制来加速算法的收敛速度。

在全局搜索的基础上，通过搜索邻域解空间，寻找更有可能是全局最优解的候选解。

通过局部搜索机制的引入，可以提高算法的搜索能力和求解效果。

2.利用多目标方法。

车间调度问题通常涉及到多个目标函数的优化，如最小化生产时间和最小化生产成本。

传统的粒子群优化算法只能处理单目标问题，无法同时优化多个目标。

本文利用多目标方法，通过权重优化策略将多个目标函数统一化为一个目标函数，从而实现多个目标的协调求解。

基于粒子群算法的车间调度问题优化研究车间调度问题是生产过程中一个重要的环节，它决定了生产效率和产品质量。

在实际生产中，合理的调度可以减少生产成本、提高生产效率，并且在满足客户需求的前提下，最大程度地降低库存，提高企业竞争力。

因此，如何针对车间调度问题进行优化研究，具有重要的实际意义。

传统的求解车间调度问题的方法主要有贪心法、遗传算法、模拟退火等，但是这些方法都有其局限性。

因为这些方法不能够找到全局最优解，因为这些方法都是基于确定性的搜索策略。

而粒子群算法(PSO)就是一种新兴的求解优化问题的算法。

粒子群算法是一种群智能算法，其基本思想源于鸟类的迁徙和鱼群游动的行为。

粒子群算法的求解过程就是一群粒子在搜索空间中随机游动，在不断地交流和合作中，逐步地找到最优解。

具体而言，粒子群算法是从很多不同的个体中产生出全局最优解的一种群体智能优化方法。

在求解车间调度问题时，粒子就是任务编号，每个粒子的位置就是任务处理机的编号，每个粒子的速度就是任务在两个处理机之间的交换顺序。

以上是基于粒子群算法的理论基础，接下来，本文将从算法流程、调度问题建模、算法设计和实验结果等方面分析基于粒子群算法的车间调度问题优化研究。

一、粒子群算法的流程粒子群算法主要分为初始化、粒子初始化、粒子更新、适应度计算、全局最优解更新、跳出条件等几个步骤。

1.初始化根据实际的生产需求，确定任务数量、处理机数量、任务处理时间等参数。

将这些参数输入到程序中，并根据其特定的属性完成初始化。

2.粒子初始化程序为每个任务产生粒子，并为每个粒子随机产生一个解。

这个解实际上就是任务在处理机之间的交换顺序，在任何一种情况下，粒子和处理机之间的关系都是确定的。

3.粒子更新在粒子更新过程中，程序会适用旋转操作来改变粒子的解，这个操作会为每个粒子计算一个适应度值。

在这个收敛的过程中，每个粒子都有其特定的速度和位置，通过这个处理方式来优化算法。

4.适应度计算适应度计算的主要任务是用来评估和记录群体中每一个粒子的适应度值。

基于PSO 的置换流水车间调度算法周　驰,高　亮,高海兵(华中科技大学工业工程系,湖北武汉430074) 摘　要:　置换流水车间调度问题(PFSP )是典型的具有工程背景的组合优化问题.对该问题的研究具有重要的理论意义与应用价值.本文针对PFSP 问题提出了新的基于粒子群优化(PS O )的调度算法.论文分析了广义粒子群优化(G PS O )模型中信息流动拓扑结构的缺陷,提出新的基于种群的元启发式算法信息共享机制SIS M.基于SIS M 信息共享机制的PS O 调度算法利用PFSP 问题的邻域知识指导个体的局部搜索.与历史文献中该问题的代表性算法比较,该算法可在调度质量与计算费用之间获得较好的平衡.仿真实例验证了该调度算法的有效性.关键词:　粒子群优化;置换流水车间调度;信息共享机制;邻域知识中图分类号:　TP38 文献标识码:　A 文章编号:　037222112(2006)1122008204Particle Swarm Optimization Ba sed Algorithm forPermutation Flow Shop SchedulingZH OU Chi ,G AO Liang ,G AO Hai 2bing(Department o f Industrial Engineering ,Huazhong University o f Science and Technology ,Wuhan ,Hubei 430074,China )Abstract :　Permutation Flow shop scheduling (PFSP )is a complex combinatorial optimization problem with strong engineer 2ing background ,and is of great importance in both theory and application.In this paper ,a new PSO based flow shop scheduling al 2gorithm is proposed to generate optimized PFSP schedule.First ,limitation of information sharing mechanism in GPSO model is ana 2lyzed and new population based information sharing strategy is proposed.PFSP scheduling algorithm based on new information shar 2ing strategy utilizes problem 2concerned knowledge to direct its search in the local search pared with representative PFSP scheduling algorithms ,the proposed algorithm can obtain good balance between quality of schedule and computational cost.Simulation results validate its efficiency.K ey words :　particle swarm optimization ;permutation flow shop scheduling ;information sharing strategy ;neighborhood knowledge1　引言 置换流水车间调度(Permutation Flow Shop Scheduling Prob 2lem :PFSP )是制造系统中重要的规划问题.该问题一般可以描述为:n 个待加工的工件J ={1,2,…,n},需要在m 台机床M ={1,2,…,m}上完成加工.每个工件包含m 道加工工序O j 1,O j 2,…,O jm ,其中O jk 代表工件j 在机床k 上加工时间为p jk 的工序.PFSP 规定:(1)每个工件在机床上的加工顺序相同;(2)每台机床上工件的加工顺序相同;(3)每台机床每次最多只能加工一个工件;(4)每个工件每次只能由一台机床加工.优化调度的目的是在该问题的所有可行调度中确定每个工序的开始时间s ij ,使总完工时间C max 最小即:C 3max =min (C max )=min {max (s ij +p ij ):ΠJ i ∈J ,M j ∈M},满足以上条件的工件加工顺序即为置换流水车间调度的最优解.车间生产环境中优化调度的自动生成是智能制造领域的重要研究内容.PFSP 调度算法通过对制造过程进行作业计划,以实现流水车间环境下生产过程的优化调度.PFSP 广泛应用于实际生产,尤其适用于单件大批量生产背景的制造企业.对流水车间生产的优化调度可有效提高制造资源利用率与企业生产效益.置换流水车间调度的常用方法大致可分为三类[1]:构造启发式方法(如G upta 、Johns on 、Palmer 、C DS 、NEH 等)、运筹学方法(如分枝定界法、割平面法、动态规划法等)、基于人工智能的元启发式算法(如模拟退火、禁忌搜索、遗传算法、蚂蚁算法等).PFSP 问题的构造启发式算法可以在较短时间内获得调度问题的解.但是该类方法在构造调度的过程中依赖根据问题局部信息设计的调度规则,所获得的调度一般为局部最优解.运筹学方法的应用受问题规模与计算费用的限制.对于类似PFSP 的复杂组合优化问题,该类方法难以在有限时间内获得问题的优质解.基于物理或仿生学机理的一类元启发式调度算法能够在可行时间内以较大概率获得该类问题的最优解或近似最优解,成为各种车间调度问题最常用的算法.粒子群优化(Particle S warm Optimization :PS O )是受鸟群捕食启发产生的元启发式算法.PS O 通过种群内粒子之间的合收稿日期:2005203215;修回日期:2006206210基金项目:国家自然科学基金(N o.50305008)第11期2006年11月电 子 学 报ACT A E LECTRONICA SINICA V ol.34　N o.11N ov.　2006作与竞争产生的群体智能指导优化搜索.与遗传算法比较, PS O保留了基于种群的全局搜索策略,其优化机理清晰易懂,搜索模型步骤简单,计算费用较低.该算法已在切削参数优化[2]、PI D控制器的参数设计[3]、补偿电容器配置优化[4]等工程优化问题获得成功应用.本文将基于PS O的算法用于PFSP 优化调度的生成,针对遗传算法与广义粒子群优化模型(G P2 S O)中信息共享机制的缺陷,论文提出新的基于群体智能思想的信息共享机制.该信息共享机制可维持算法在全局搜索与计算费用之间良好的平衡.基于新的信息共享机制的PS O调度算法充分利用PFSP问题本身的邻域知识指导算法的局部搜索,很大程度地避免了PS O的随机策略导致的盲目搜索.2　广义粒子群优化算法211　PSO信息共享机制与广义粒子群优化模型K ennedy和Eberhart受鸟群觅食行为的启发,1995年提出粒子群优化算法(Particle S warm Optimization:PS O)[5].最初的设想是仿真简单的社会活动,研究并解释复杂的社会行为,后来发现该算法可以用于优化问题的求解.但是,传统粒子群优化算法局限于速度-位移更新算子,不能有效拓展到离散及组合优化领域.针对连续变量优化问题的速度-位移更新模型使用实数编码,编码的每一维代表独立的变量,不能反映编码中参数间的顺序或其它约束关系.针对粒子群优化算法在解决组合优化问题上的局限性,我们分析了粒子群算法的优化机理,并在此基础上提出了广义粒子群优化模型(G PS O).模型中粒子的更新操作仅为抽象概念,因此基于该模型的算法实现需要设计具体的更新算子.粒子可以以多种形式从其个体及邻域极值获得更新信息.以遗传操作为例,粒子可通过与个体极值及邻域极值进行交叉获得更新信息,并通过线性下降的变异进行随机扰动并趋于局部搜索.以此模型为基础,我们提出采用遗传操作作为粒子更新策略,并成功解决了TSP问题[6].212　GPSO信息共享机制的缺陷分析基于G PS O模型的算法(包括传统PS O算法),其信息共享机制中均采用相同的信息流动拓扑结构,其潜在缺陷在于算法中的每个粒子过于贪婪地获取更新信息,使得粒子的搜索性能受其个体与邻域极值的影响较大,种群容易局部收敛.相对于进化算法,传统PS O算法在连续优化问题显示出较快的收敛速度与较高的收敛精度.需要指出该优势的获得与PS O算法求解问题的解空间分布有关.对于局部最优解遍布整个解空间的复杂组合优化问题,该信息拓扑结构将会导致相对进化算法更严重的早熟现象.针对基于G PS O模型的上述缺陷,本文提出的基于群体智能的信息共享机制,可作为通用的信息共享机制适用于所有基于种群的元启发式算法. 213　基于群体智能的信息共享机制SISM2.3.1　记忆信息机制记忆机制是PS O、蚁群算法AC O、禁忌搜索T abu Search等元启发式算法取得成功的关键因素.此外,研究发现在其它元启发式算法中引入记忆功能可显著改进算法性能.例如遗传算法保留精英解的策略本质上属于对迭代过程中种群最优解的记忆.S A中引入记忆功能可提高算法的收敛稳定性.因此记忆依然作为本文信息共享机制中信息的核心来源.2.3.2　新的信息共享机制基于SIS M的算法种群中的核心部分为记忆库.记忆库保存一定比例的记忆个体,一般占种群规模的15%～20%.新的信息共享机制表达如下:算法种群保证一定规模的记忆库,种群中个体的每次迭代均从自身记录的记忆个体及记忆库中随机抽样的记忆个体获得更新信息;种群的每次更新均同时完成对记忆库的更新,同时对更新后种群中一定比例的劣质解进行启发式初始化.对记忆库的更新采用以下原则:(1)更新种群中最优的记忆个体优于记忆库的最差个体,(2)为保证记忆库中粒子的分布性,该更新记忆个体的编码及目标函数在记忆库中唯一,对于组合优化问题主要是保证个体间海明距离尽量小.为在保证多样性的同时提高计算效率,本文做了简单处理,即只通过目标函数的差异性判断多样性,仿真实验证实了该方法的有效性.2.3.3　SISM信息共享机制的改进分析SIS M信息共享机制中的个体从记忆库而不是邻域极值获得更新信息.记忆库中的个体为种群中具有分布性的较优记忆信息的集合.个体不仅依赖自身经验获得的记忆信息,而且借鉴种群中其他个体的成功经验.相对于遗传算法的信息共享机制,个体从记忆库中获得更新信息同时保留了较大的信息流动效率.另一方面,记忆库个体为随机抽样选择,且记忆库本身具有分布性.因此相对于G PS O的信息共享机制,基于SIS M算法局部收敛的概率较低.3　基于粒子群优化的流水车间调度算法311　基于PFSP邻域知识的局部搜索针对问题知识设计的局部搜索是邻域搜索元启发式算法的关键组成部分.研究表明对于车间调度问题包括JSP与FSP 等,可行调度的关键块中工序的局部移动是该类问题最有效的更新算子之一.PS O算法是基于群体智能的元启发式算法.信息共享机制中更新算子的设计是算法实现的关键步骤.文献[7]对置换流水车间调度中基于关键路径的邻域结构进行了系统的研究.本文PS O算法中基于PFSP邻域知识的局部搜索采用该邻域结构.基于该邻域结构的局部搜索示意图如图1所示.调度问题的邻域结构需要根据问题的具体特点设计.例如针对JSP问题各机器上工件的加工顺序及各工件的工序加工顺序均不相同的特点,对该问题的编码及邻域结构需要以9002第　11　期周　驰:基于PS O的置换流水车间调度算法工序为单位进行设计.PFSP问题中,各工件的工序加工顺序及工件在机器上的加工顺序一致.而且PFSP问题的约束较少,工件的邻域移动无任何限制即工件以任意方式的移动均不会产生非法解.因此PFSP调度的邻域移动以工件为单位,无须深入到每道工序.对车间调度问题的研究表明,关键路径上工序块内部的移动对调度的质量无任何改进.因此本文以关键块之间工序的插入作为该类问题的邻域移动策略.基于任意两个关键块的全邻域结构具有完备的邻域空间,但是基于该结构的邻域移动,在待插入的邻域位置离当前工序较远的情况下更倾向于全局搜索.此外实验证明该邻域结构往往导致算法的冗余搜索甚至迂回搜索.为提高算法的局部搜索效率,本文的邻域结构定义为当前关键块中的各工序向其邻接块内移动的集合.图1中的箭头标出移动的位置.对于块B i上的一道工序o k(k表示整个关键路径中该工序的序号).设M p k表示将工序向紧前块中的移动集合,M s k表示将工序向紧后块中的移动集合,π(m)表示经过移动m得到的新调度,则当前调度π的邻域可表示为:N(π)={π(m)|m∈(M p1∪M s1)∪(M p2∪M s2)∪…(M p n∪M s n)}.算法以N(π)中Makespan最小的邻域调度作为局部搜索的更新调度.为防止迂回搜索,算法以一定的概率选择工序的插入位置.312　PFSP调度算法本文基于PS O的PFSP调度算法采用SIS M信息共享机制.结合PS O算法特点,SIS M信息共享机制中的记忆个体对应于PS O的粒子的个体极值,记忆库即为PS O种群中最优的个体极值的集合.基于SIS M信息共享机制的PS O调度算法在挖掘自身群体智能的同时充分利用PFSP邻域知识进行局部搜索,其详细流程如图2所示.该算法采用基于工件的顺序编码方案,并选择最大完工时间Makespan作为解的评价标准. PS O算法在初始化过程中使用NEH、Palmer与C DS生成启发式初始解.初始种群中的其它粒子使用随机初始化.若算法以到达最大迭代次数或在指定迭代次数内调度的质量无改进,则算法停止.该算法的关键步骤为更新算子的设计与基于调度问题邻域知识的局部搜索.31211　更新算子的设计基于PFSP的遗传调度算法针对顺序编码设计了大量成功的遗传操作如P MX,OX,LOX等.考虑到基于P MX交叉操作的遗传算法在求解PFSP问题的成功经验.本文基于PS O的PFSP调度算法采用P MX交叉作为粒子的更新算子,用于从个体极值及记忆库中随机选择的记忆粒子获得更新信息. 31212　基于邻域知识的局部搜索粒子在从算法自身的种群中获得更新信息后,利用优化问题本身的特征设计的邻域知识进行局部搜索.针对车间调度问题的基于关键路径的邻域移动已经形成了较为系统的知识体系,在理论方面已经比较成熟.大量仿真实验验证了该邻域结构的有效性.基于该邻域结构设计的模拟退火与禁忌搜索算法已成为求解车间调度问题最有竞争力的元启发式算法.针对PFSP问题的邻域搜索的详细描述见311节.Initialize the particle population:generate randomly a set of permutation FSP schedules.D o{　F or each particle s i(t)do{ Evaluate with objective function defined as C max(si) Set individual best schedule p i(t): if C max(s i(t))≤C max(p i(t-1)) p i(t)=s i(t) Update mem ory in formation pool if rand()≤p Update PFSP schedule through PMX cross over with p i(t) else Obtain new PFSP schedule through PMX cross over with m i(t) Local search procedure: F or each operation in each critical block B i do{ Insert it before each operation in its previous critical block B i21or next one B i+1 Output the best neighbor schedule with minimum C max } }}While stopping criteria are not satis fied图2　基于SIS M信息共享机制的PS O调度算法流程4　实例仿真与结果分析 实验采用OR LI B中的PFSP实例(T aillard系列问题)进行测试.实验运行的计算机配置如下:处理器为Intel Celeron C oppermine Process or(0118μm),主频为1.0G,物理内存为128M B.实验运行获得的仿真结果如表1所示.为体现本文算法的优势,选择部分文献中有代表性的PFSP调度算法进行比较.表中PS O为本文提出的算法,T A为历史文献给出的T ail2 lard问题的C max上界.E VIS为文献[8]的遗传算法,RS A代表文献[9]的改进模拟退火算法,HS A为文献[10]的混合模拟退火算法,TS为文献[11]的禁忌搜索算法.需要说明的是所有的计算时间都根据机器类型按照同一标准进行了折算.图3以直方图的形式给出各种算法测试PFSP实例得到的相对误差性能比较.横坐标代表问题类型,纵坐标代表距离问题已知上界的相对误差.需要说明的是对于简单的测试实例如20×5与50×5问题,以上算法都可收敛到最优解.因此各种算法0102 电 子 学 报2006年表1　不同调度算法的PFSP 测试实例仿真结果Problem T AE VISRS AHS ATSPS OC maxC maxT (s )C maxT (s )C maxT (s )C maxC maxT (s )20×51278127849.01127812.4812780.06127812780.0320×101582158889.01158214.621582 3.0615821582 1.6020×2022972297211.63229721.462301 3.06229722970.0350×527242724142.962724 2.592724 2.0427*******.0250×1030253063390.25302527.4330257.143037302575.3750×2038753896901.42388654.823911211.1438863868218.43100×554935493629.33549311.025502 2.0454*******.04100×10577058621231.42577666.10577425.505776577058.25100×20628665672246.586319188.066434473.3063306258354.65200×101086810957126.7910872168.191096127.54108721087219.87200×201129411818216.1011359416.5411483435.541139311286584.27500×2026189274961271.852********.20268143674.0426316261722836.02的相对误差未能在图3中显示.由表1与图3的统计结果可知,本文基于SIS M 信息共享机制的PS O 调度算法总体性能优于其它算法.根据表1的性能指标,尽管基于个体搜索的模拟退火与禁忌搜索的计算费用指标在某些实例中略有优势,但是本文基于PS O 的PFSP 算法具有更好的全局收敛性.对于所有PFSP 测试问题,PS O 产生的最优调度的C max 指标最优,其中4个测试实例的C max 指标优于历史文献中给出的上界.与基于种群的遗传调度算法E VIS 比较,PS O 算法的调度质量与计算费用指标均有显著提高.综上所述,基于PS O 的调度算法在保证收敛速度的情况下,提高了调度质量和收敛稳定性.仿真实验的统计结果验证了本文SIS M信息共享机制与基于邻域知识的局部搜索的有效性.5　结论 针对基于种群的元启发式算法2PS O 与G A 信息共享机制的缺陷,本文提出新的基于群体智能的信息共享机制SIS M.SIS M 机制以记忆信息为核心,并引入记忆库概念,该模型每次迭代均对记忆库进行更新.通过记忆库中记忆个体的分布性及随机启发式初始化替换种群中的劣质解的策略,基于SIS M 机制的算法可保持全局搜索与局部搜索之间的良好平衡.本文将根据问题邻域知识设计的邻域结构引入PS O 调度算法的局部搜索模块中,用于指导算法的邻域搜索,避免了粒子大量盲目的更新操作.基于种群的随机搜索策略与基于知识的邻域搜索的有效融合,既保证了算法的全局优化特性,又提高了算法中有效信息的流动效率,加快了算法收敛速度.实验结果显示,基于以上策略的PS O 调度算法可在较短的时间内获得调度问题的满意解,从而验证了以上策略的有效性.本文的SIS M 信息共享机制和基于问题知识的邻域搜索可以作为通用的策略推广到其它基于种群的元启发式算法及制造领域中的其它调度问题.参考文献:[1]高海兵,周驰,等.广义粒子群优化模型[J ].计算机学报,2005,28(12):1980-1987.Gao Hai 2bing ,Zhou Chi ,et al.General particle swarm opti 2mization model [J ].Chinese J ournalof Computers ,2005,28(12):1980-1987.(in Chinese )[2]Nowicki E ,Smutnicki C.A fast tabu search algorithm for thepermutation flow 2shop problem[J ].European J ournal of Opera 2tional Research ,1996,91:160-175.[3]K im G H ,George L.Genetic reinforcement learning approachto the heterogeneous machine scheduling problem [J ].IEEE Transaction on Robotics and Automation ,1998,14(6):879-893.[4]Low C ,Y eh J Y,et al.A robust simulated annealing heuristicfor flow shop scheduling problems [J ].International J ournal of Advanced Manufacturing Technology ,2004,13:762-767.[5]Nearchou A C.A novel metaheuristic approach for the flowshop scheduling problem[J ].Engineering Applications of Arti 2ficial Intelligence ,2004,17:289-300.[6]Daya M B ,Fawsan M A.A tabu search approach for the flowshop scheduling problem [J ].European J ournal of Operational Research ,1998,109:88-95.[7]Nowicki E ,Smutnicki C.A fast tabu search algorithm for thepermutation flow 2shop problem[J ].European J ournal of Opera 2tional Research ,1996,91:160-175.[8]K im G H ,George L.Genetic reinforcement learning approach tothe heterogeneous machine scheduling problem [J ].IEEE T rans 2action on Robotics and Automation ,1998,14(6):879-893.[9]Low C ,Y eh J Y,et al.A robust simulated annealing heuristicfor flow shop scheduling problems [J ].International J ournal of Advanced Manufacturing Technology ,2004,13:762-767.[10]Nearchou A C.A novel metaheuristic approach for the flowshop scheduling problem [J ].Engineering Applications of Ar 2tificial Intelligence ,2004,17:289-300.[11]Daya M B ,Fawsan M A.A tabu search approach for the flowshop scheduling problem [J ].European J ournal of Operational Research ,1998,109:88-95.作者简介:周　驰　男,1981年生于湖北省枣阳市,华中科技大学工业工程系硕士研究生,研究方向为计算智能、运筹学与优化.E 2mail :catecheng @1102第　11　期周　驰:基于PS O 的置换流水车间调度算法。

基于粒子群优化算法的车辆调度优化研究车辆调度问题在物流领域中具有重要的意义。

随着物流业的发展和技术的进步，对车辆调度的要求越来越高。

粒子群优化算法作为一种基于群体智能的优化算法，已被广泛应用于车辆调度优化问题中。

本文旨在研究基于粒子群优化算法的车辆调度优化方法，并对其进行探讨。

首先，我们对车辆调度问题进行形式化描述。

车辆调度问题可以简单地定义为在给定的时间段内，将若干车辆分配到若干任务上，并满足一定的约束条件，使得车辆的总成本最小化。

其中，任务之间可能存在时间窗口约束、车辆容量约束以及任务执行顺序约束等。

车辆调度问题通常是一个NP-hard问题，在实际应用中，往往需要采用启发式算法进行求解。

粒子群优化算法是模拟鸟群觅食行为的一种群体智能优化算法。

其基本思想是通过模拟鸟群中个体之间的信息交流和合作，以寻找最优解。

粒子群优化算法的核心是将解空间中的潜在解看作粒子，通过不断更新粒子的速度和位置，使得粒子向全局最优解逼近。

在基于粒子群优化算法的车辆调度优化方法中，首先需要将车辆调度问题转化为一个数学模型。

常用的数学模型包括路径表示法、时间窗表示法和随机Google地图表示法等。

其中，路径表示法将车辆和任务集合之间的关系表示为一条路径，时间窗表示法将任务的时间窗口和服务时间等因素纳入考虑，而随机Google地图表示法则通过获取实时路况数据进行车辆调度。

接下来，我们将车辆调度问题转化为粒子群优化算法的优化问题。

粒子群优化算法的目标是寻找最小化或最大化目标函数的最优解。

在车辆调度问题中，我们可以将总成本作为目标函数，考虑车辆的行驶里程、时间窗口约束、车辆容量约束以及任务执行顺序等因素。

通过不断更新粒子的速度和位置，使得粒子向全局最优解逼近，从而得到最优的车辆调度方案。

在实际应用中，还需要考虑一些改进和优化的方法。

一方面，可以引入局部搜索机制，加快粒子的收敛速度。

局部搜索机制使得粒子在搜索过程中更容易找到局部最优解，并以此为基础进一步探索全局最优解。

序列流水车间调度问题的混合粒子群优化算法研究的开题报告一、研究背景和意义随着工业生产的发展，调度问题越来越受到人们的关注。

序列流水车间调度问题是其中一个重要的问题，在生产中具有重要的意义。

在序列流水车间生产中，工件经过一系列的工序，每个工序都需要特定的机器和时间。

为了提高生产效率，需要对机器的调度进行优化，从而缩短生产周期，提高生产效率和品质。

基于现有算法，混合粒子群优化算法（MPSO）是一种有效的优化算法，可以用于序列流水车间调度问题。

MPSO 算法将粒子群算法 (PSO) 和其他优化算法（例如模拟退火算法、遗传算法、 Hill-climbing 算法）的优点融合在一起，可以得到更好的优化结果。

二、研究目的本研究的主要目的是探究混合粒子群优化算法在序列流水车间调度问题优化中的应用效果，并针对其改进点进行探讨。

具体包括以下几个方面：1. 分析序列流水车间调度问题的基本形式和特点，探究MPSO 算法的适用性和局限性。

2. 改进传统MPSO 算法，提出一种适用于序列流水车间调度问题的新型MPSO算法，以提高算法的优化性能和搜索效率。

3. 实现序列流水车间调度问题算法的程序，并通过实验证明该算法的有效性和实用性。

三、研究内容为了实现研究目的，本研究将包括以下几个关键内容：1. 根据序列流水车间调度问题的特点，设计合适的目标函数和约束条件。

2. 分析现有MPSO 算法的基本思想和流程，了解其优点和不足。

3. 提出一种改进的MPSO算法，探索其在序列流水车间调度问题中的应用效果。

4. 实现设计的MPSO算法，进行相关实验，对算法的效率和优化结果进行分析和比较。

四、研究方法本研究将运用对序列流水车间调度问题的分析和对混合粒子群优化算法的了解，提出一种改进的算法。

具体研究方法包括：1. 设计MPSO算法：在MPSO算法的基础上，针对序列流水车间调度问题的优化，提出一种新的算法进行优化，设计约束条件和目标函数。

基于粒子群优化算法的调度问题研究1. 引言调度是生产和运营管理中的一个重要问题，涉及到资源的合理利用和任务的高效执行。

随着科技的发展，粒子群优化算法（Particle Swarm Optimization，PSO）作为一种新兴的启发式算法，逐渐应用于各种调度问题的优化中。

本文旨在研究基于粒子群优化算法的调度问题，并深入探讨其局限性和改进方向。

2. 粒子群优化算法的基本原理粒子群优化算法源于仿生学中的群体行为，模拟鸟群或鱼群等生物的群体行为。

通过模拟每个“粒子”的位置和速度变化，以达到全局最优解的寻找。

算法的基本步骤为：初始化粒子群的位置和速度，计算适应度函数，更新粒子的速度和位置，更新群体的最优位置。

3. 粒子群优化算法在调度问题中的应用3.1. 单机调度问题单机调度问题是指在单个资源上执行多个任务的问题。

通过将任务抽象成粒子的位置和速度，并定义适应度函数，可以利用粒子群优化算法求解最优的任务调度顺序。

例如，考虑任务的完成时间、资源的利用率等指标，通过不断迭代更新粒子的位置和速度，最终得到最优的调度方案。

3.2. 多机调度问题多机调度问题是指在多个资源上执行多个任务的问题。

该问题较为复杂，需要考虑资源间的协调和任务间的依赖关系。

通过将资源和任务抽象成粒子的位置和速度，并定义适应度函数，可以利用粒子群优化算法求解最优的资源分配和任务调度顺序。

例如，考虑任务的执行时间、资源的负载均衡等指标，通过不断迭代更新粒子的位置和速度，最终得到最优的调度方案。

4. 粒子群优化算法的局限性尽管粒子群优化算法在调度问题中具有一定的优势，但也存在一些局限性。

首先，算法容易陷入局部最优解，导致无法找到全局最优解。

其次，算法对于问题的建模和参数的选择要求较高，需要针对具体的调度问题进行不断调整和优化。

最后，算法的计算复杂度较高，对于大规模的调度问题难以进行高效的求解。

5. 粒子群优化算法的改进方向为了克服粒子群优化算法的局限性，研究者们进行了大量的探索和改进。

置换流水车间调度问题的离散粒子群优化算法第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?。