基于二进制粒子群优化算法的车间作业调度问题的研究软件工程.doc

安徽新华学院2016届本科毕业论文（设计） 本科毕业论文（设计）题目：基于二进制粒子群优化算法 的车间作业调度问题的研究姓 名： 学 号： 专 业： 院 系： 指导老师： 职称学位： 完成时间： 2016年5月14日 教务处制 安徽新华学院本科毕业论文（设计）独创承诺书本人按照毕业论文（设计）进度计划积极开展实验（调查）研究活动，实事求是地做好实验（调查）记录，所呈交的毕业论文（设计）是我个人在导师指导下进行的研究工作及取得的研究成果。据我所知，除文中特别加以标注引用参考文献资料外，论文（设计）中所有数据均为自己研究成果，不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的工作已在论文中作了明确说明并表示谢意。毕业论文（设计）作者签名： 日期： 基于二进制粒子群优化算法的车间作业调度问题的研究摘 要车间作业调度问题是当今社会研究最热门的课题之一，如何实现先进制造和提高生产效率是一个企业管理的管理和控制核心。经过几年的发展，智能计算渐渐被应用到了调度问题中，如模拟退火算法、遗传算法等。而本文利用二进制粒子群算法来解决车间作业调度问题。首先对车间作业调度问题和二进制粒子群算法理论进行具体介绍。接下来选择典型的Jop-Shop调度问题作为算法的实验对象，并且建立数学模型，通过MATLAB对算法进行编程求解。通过实验，表明二进制粒子群优化算法在求解车间作业调度问题的有效性和正确性。关键词：二进制粒子群；作业调度；数学建模Research on job shop scheduling problem based on binary particle swarm optimization algorithmAbstractJob shop scheduling problem is one of the most popular topics in todays society. How to implement advanced manufacturing and improve production efficiency is the core of the management and control of enterprise management. In recent years, a variety of intelligent computing methods have been applied in the scheduling problem, such as simulated annealing algorithm, genetic algorithm, etc. In this paper, the binary particle swarm optimization algorithm is used to solve the job shop scheduling problem. Firstly, the job shop scheduling problem and the binary particle swarm optimization algorithm are introduced in detail. Next, the typical Jop-Shop scheduling problem is chosen as the experimental object, the mathematical model is established, and the solution is solved by MATLAB programming. Through experiments, the validity and correctness of the binary particle swarm optimization algorithm in solving the job shop scheduling problem is indicated.Key words: Binary particle swarm; job scheduling; mathematical modelingII 目 录 1 绪 论11.1研究背景和意义11.2 国内外研究现状21.2.1 车间作业调度研究现状21.2.2 粒子群算法研究现状21.2.3 JSP中粒子群算法研究现状和存在问题31.3本文的研究内容32 车间作业调度问题42.1 车间作业调度问题描述42.2 车间作业调度问题的分类及特点52.3 车间作业调度问题的优化方法63 粒子群算法的改进83.1 粒子群优化算法的思想与原理83.1.1粒子群算法的基本思想83.1.1粒子群算法的基本原理93.2 参数的意义及选择标准103.4适应度函数103.6动态非线性动态变化惯性权重113.6.1算法改进的原理113.7二进制粒子群算法模型124 基于二进制粒子群优化算法的车间作业调度问题模型134.1 车间作业调度具体问题描述及约束条件134.1.1 JSP问题的具体描述134.1.2 约束条件134.3 应用二进制粒子群算法求解JSP问题144.3.1基于工序的编码方案144.3.2粒子的编码和粒子的初始化144.3.3调度方案的生成144.3.4二进制粒子群算法求解JSP问题的步骤164.4 系统仿真及结果分析174.5 本章小结185 总结与展望185.1 总结185.2 展望19致 谢19参考文献201 绪 论1.1研究背景和意义由于科学技术的发展以及生产了水平的提高，生产规模也在逐渐的扩大，其随之带来的激烈的市场竞争以及资源的急缺。面对这些问题，企业更加迫切的需要一种有效的生产方式，在控制较低成本的情况下拥有高质量的商品，能够及时供应市场需求。因此，如何优化资源配置已经成为全社会关注的焦点问题。然而，解决资源优化配置的一个有效的途径就是调度。追求先进制造和高效率生产，就要依赖于对有效的调度方法和技术应用与研究。而应用于车间作业的调度优化工作有利于提高生产效率，能够降低生产成本等方面。目前国内外许多学者围绕调度算法的研究取得了较大的发展，也存在一些问题，例如神经网络而言，如果求解调度问题的复杂度高，利用神经网络实现起来就很不容易，又如遗传算法求解调度问题时收敛率不高，容易陷入局部最优值。因此，研究出一种合适的调度算法具有重大理论意义以及实用价值。粒子群算法1（也称为微粒群算法）是由美国的Kennedy博士和Eberhart博士在1995年提出。是一种基于群智能的优化算法，它是群智能研究领域中的一个新的分支，可通过个体之间的协作来寻找最优解。这种算法本身带有操作简单，容易实现而且没有很多参数需要调整等优点。因此，一经提出，便引起了很多学者的广泛关注，目前已经有效应用于函数优化、神经网络训练等领域中，是解决全局优化问题的一种有效方法。通过查阅有关粒子群算法的文献发现，由于粒子群的相关参数属于连续实数域，所以只适合求解连续空间问题。在众多文献中还发现由于粒子群在求解连续空间域的优化问题时表现的良好的性能，促进了对应用与离散空间问题的研究，如组合优化问题的研究等。将粒子群应用于车间作业调度问题中，是粒子群算法的一个重要的研究内容和研究方向。1.2 国内外研究现状1.2.1 车间作业调度研究现状调度领域开始了理论研究源于在1954年Johnson对两台机床Flow-Shop 型调度问题进行研究后，提出的解决n/2/F/Cmax2（n个工件2台机器的Flow-Shop型调度的最小流程周期问题）的优化算法。该算法一经提出就在当时的学术界引起了很大的反映。此后学者们开展了大量对调度复杂性的研究。因此，车间调度领域取得了大量的研究成果。学者们研究出各种解决车间调度问题的求解算法，如遗传算法2、模拟退火法3、神经网络法4、调度规则算法5及各种混合算法6。其中，优先调度算法应用到实际生产系统中车间作业计划问题的复杂性和规模较小。是一种最为实用和有效的算法。虽然它存在在调度解的优化性能方面欠佳的缺点，但求解速度快，容易得到满意的调度解，这也基本上满足实际生产系统的车间管理的要求。我国大多数企业的车间作业的分配和调度基本上是靠调度员的经验进行的，这种技术比较落后。由于具有并行性和鲁棒性的优点，遗传算法在众多调度方法中脱颖而出，更多的应用在了车间作业调度问题中。但是，我国研究工作分布特别不均匀。因此，在车间作业调度问题的研究还需要投入大量的精力进行。神经网络是我国比较早采用来解决车间调度问题的一种方法。继而，学者们相继提出大量解决车间调度问题的方法，促动了我国对车间调度问题研究的进展。目前，随着智能调度理论的迅速发展，智能理论调度越来越显示出优势，也成为一种发展的方向。1.2.2 粒子群算法研究现状粒子群算法凭着拥有有操作简单且没有很多参数，成为群智能研究中一个新的研究方向，当时刚一提出，迅速掀起了一股算法研究的热潮。但是随着应用领域变广，粒子群算法在很多复杂的问题求解受到局限，因此，对粒子群算法改进以便适应于相应的问题就显得非常有意义。根据解空间的不同可以将粒子群改进分类为离散粒子群算法与连续粒子群算法。经典的粒子群算法利用实数对位置矢量以及速度矢量进行编码，然后在连续的空间对粒子位置进行更新操作，所以经典粒子群算法在解决连续空间优化问题上具有一定的优势。从粒子群算法问世之后，相继众多学者对此进行了很多改进措施，改善了算法的性能，使得可以求解一些离散优化问题。但是粒子群在解决离散空间问题人存在着很多的缺点，因此，很多学者对原始的粒子群算法进行改进，来提高算法的性能。在粒子群算法中有3个因子：学习因子c1和c2、惯性权重。学习因子c1和c2代表调节微粒自身和全局最优位置飞行的步长。后来提出了惯性权重的概念，经过大量的研究证明其合理性。1.2.3 JSP中粒子群算法研究现状和存在问题1.研究现状 目前粒子群在解决连续空间函数优化问题上做了很大的贡献，已有大量的研究成果。继而经过众多学者不断对粒子群算法的改进，提高粒子群的性能。目前很多学者将遗传算法、粒子群算法和模拟退火算法应用于解决柔性车间制造系统的调度问题7中，用最小生产托期为最优目标，取得了很好的效果，很多实验证明了粒子群算法在车间调度上应用的可行性和有效性。2.存在的问题 粒子群的提出最先是用来解决连续空间最优化问题的算法，现如今解决车间调度这种属于离散空间非数值优化问题，是存在一定的缺陷的，大部分调度问题都属于NP-hard难题。通过查阅大量的文献来看，目前粒子群算法具有容易陷入局部最优值的缺点与其他进化类算法相似。因此，需要对算法进行改进，改变算法的性能以便于摆脱局部最优解的限制，使得能让粒子群算法更好的解决车间作业调度问题。1.3本文的研究内容本文针对车间调度问题的特点，对粒子群算法进行改进为二进制粒子群优化算法，应用解决车间作业调度问题中。本文的主要内容和章节安排如下：第1章 绪论绪论中介绍到课题所研究的背景以及意义，详细描述国内外对车间作业调度问题和粒子群研究的现状，以及本文的主要内容。第2章 车间作业调度问题的有关内容本章对车间作业调度问题进行了详细描述；阐述了它的分类，如单机调度问题、流水车间调度问题以及这些分类的特点；还给出了车间作业调度问题的优化方法。第3章 介绍有关于粒子群算法详细的阐述了粒子群优化算法，包括粒子群算法的起源、基本原理和数学模型。通过总结粒子群算法的缺点，改进为二进制粒子群优化算法。第4章 基于二进制粒子群优化算法的车间作业调度问题模型本章将会构建基于二进制粒子群优化算法的车间作业调度问题的模型，提出解决的编码方案，并通过与经典调度问题对比，证明改进算法的可行性和有效性。2 车间作业调度问题2.1 车间作业调度问题描述车间作业调度问题模型一般描述如下：有n个工件，每个工件包含一定数量的工序，同工件的各工序之间存在一定的工艺约束（即工艺路线或加工路径），不同工件包含的工序数量及工艺路线存在差异；这些工序需要在m台机器上进行加工，各道工序有一定的加工时间。同时，在实际加工过程中要满足一些其他特殊性约束，例如，机器的设备出现故障，随机因素等等。调度的目标就是以一种有效合理的加工顺序来满足一定的高效率低成本等一系列性能指标集。本文研究的车间作业调度最终目标为以最小化最大完成时间。调度问题的数学描述如下：有个工件，每个工件都具有一定的工序，在台机器上加工，将第工件在第台机器上加工表示为，将将第工件在第台机器上加工时间表示为，为已知的量，加工工艺表已知。近几年，由于日渐成熟恶先进制造技术以及车间调度理论的不断完善，使得实际车间调度具有随机性、不确定性等特点。车间调度问题通常满足如下约束条件：（1）同一个机器上在某一时刻只能处理一个任务；（2）每个任务不能同时在两台机器上被处理；（3）一台机器要保证完成加工一道工序不间断，加工完成之后才可加工另一道工序。（4）保证机器无故障；（5）每个工件的加工路线是固定的；（6）工件加工允许等待。车间作业调度的数学描述为：目标函数： （2-1） （2-2） （2-3） （2-4） （2-5） （2-6） 这里表示工件i在机器k上的完成时间，表示工件i在机器k上的加工时间。公式（2-1）代表在所有工件在所有机器上加工完成的前提下的目标函数；公式（2-2）表示工件的工序加工的先后条件约束；公式（2-3）表示机器加工的顺序。2.2 车间作业调度问题的分类及特点车间调度问题来源于实际生产中，每一个调度问题都会拥有独自的调度目标来衡量。从而分类标准也就因此有所差异，主要分为：（1）根据生产环境的因素分为可确定下调度问题和随即性调度问题。（2）根据生产加工系统的复杂性可分为：单机调度问题8：即一台机器进行所有工件加工的操作；流水车间调度问题9：即每个工件的工序相同，加工约束条件相同，所有的工件的所有任务都在这些相同的设备上进行加工；以及车间调度问题。（3）根据加工的特点分为动态调度问题和静态调度问题。 车间作业调度主要有以下特点：（1）复杂性车间作业调度的复杂性有很多原因，生产因素的多样化是其中之一，还有再生产过程中的某些性能指标的约束，在计算上往往是N-hard难题。随着计算量的逐渐增大，解决这样的问题，一般常规的方法是行不通的。（2）随即性由于生成环境的不断变化，车间作业调度问题另外一个特点应运而生，具有很大的随机性。这种随机性还来源于系统在运行的过程中随即不断出现的干扰。比如设备突然出现故障、人员误操作等。生产调度需要根据特殊情况进行动态调整。（3）约束性车间调度问题中存在很多的约束条件，例如，工件加工的开始时间，工件的工序，以及机器的操作顺序等。 2.3 车间作业调度问题的优化方法 随着国内外对车间作业调度问题研究的成果不断涌现，有着不同种的求解方法，但是总体可分为近似求解法和精确求解法。如下图所示：图2-1 车间生产作业调度的方法分类1、数学归纳法10 依据运筹学的基本理论和方法，在满足约束条件下，使用枚举的方法来求解。由于这种算法在对于车间作业调度问题的求解中，如果问题稍微复杂就会存在着很大的不足。所以只能用于求解比较简单调度问题。2、规则调度法11 这些方法是通过对一些规则和信息的启发下进行推理和计算出问题的最优解的。主要分为：启发式图搜索法、拉格朗日松弛法、基于启发式规则的调度算法。其优点是根据自己已有的知识和经验对所求问题进行求解，来产生解决方案效果更好。但是也存在着缺点，由于求解规模较大的问题，导致效率不高，表现出的性能不是很好。所以还需要进一步的研究和探索。3、智能搜索算法12 几年来新兴了一种科学方法，即计算机智能，随着研究不断深入，智能理论和计划计算的不断成熟，形成的一个新的方法。以至于后来学者研究出很多关于智能方法，众多方法都有各自的优点。例如遗传算法操作简单；人工神经网络存储空间大，有自学习的功能，容错性好，很容易于分类；蚁群算法计算简单，收敛速度快；模拟退火算法拥有很强的搜索能力，不容易陷入局部最优。但也有很多缺点，比如遗传算法，它在求解组合优化问题时，若是规模很大，就会存在由于搜索空间大，导致搜索时间较长，容易导致早熟收敛等问题；人工神经网络存在学校效率比较差，计算速度慢，精度不高等问题等。4、离散事件仿真13 主要用来测试固定的调度算法，由于受到模型，仿真实验数据等方面制约，造成结果很难反映实际情况。这种算法在研究生产作业调度问题上存在和很大的弊端。 3 粒子群算法的改进3.1 粒子群优化算法的思想与原理3.1.1粒子群算法的基本思想在大自然中，存在着各种各样的生物，他们拥有群体，都具有一定的群体行为。众多学者主要的研究领域之一就是利用观察探索自然界生物群体生活产生的规律应用在计算机上来构建群体模型。群体行为的复杂性都是由一个个简单的个体行为组成的。粒子群算法，最早是由J.Kennedy和R.eberthart通过对鸟类群体行为的研究的基础上共同提出的，他们构建了鸟类仿真模型，经过不断地修正，以一个粒子代表群体中的一只鸟，结合智能型和社会性的信息交流，来促使群体每一个粒子都能够搜索到最优的位置。人工生命学者Reynols在仿真中采用三条件单的规则14：（1）群体中的每个个体都向远离距离自己最近的个体方向运动，用来避免碰撞。（2）所有的个体都向着目标点运动；（3）所有的个体都向着群体的中心运动。综上三条规则提出的背景是研究自然界中生物群体行为的基础上。是粒子群算法的基本思想之一。另一个基本思想是由社会学家Boyd与Richerson研究人类决策过程时，提出的个体学习和文化传递的概念。以下两种信息进行决策（1）自身的经验（2）他人的经验3.1.1粒子群算法的基本原理粒子群算法依据个体适应度大小进行操作的，这与其他优化算法相类似，都是基于“群体”与“进化”的思想。在求解过程时，将每一个粒子假设成一个没有体积和质量的粒子，但是拥有飞行速度。对于目标函数来说，值越小，对应的适应度越优化。求解过程如下：，在n维空间的一个解用位置来表示；速度是微粒在n维空间飞行的飞行速度；速度是微粒i对目标函数的最优值。 （3-1）表示微粒i经过了t次迭代后，产生相对目标函数，最优的一代微粒，式（3-1）为求解方法。在求解最优目标函数时，设置初始化s个微粒，定义在t次迭代中目标函数对应的适应度最优的微粒。求解如（3-2）式 （3-2）综合以上定义的和的求解方法，结合粒子群优化算法的基本思想，总结出粒子群优化的基本求解方法： （3-3） （3-4）粒子群优化算法中速度进化方程如式（3-3），其中与表示加速常数，一般取值区间在在之间，与为之间的随机数。式（3-4）表示粒子群优化算法的位置进化方程。3.2 参数的意义及选择标准（1）粒子的数目S：粒子数目的设置一般依赖于问题的复杂度，一般情况下设置为20至60个。依据经验表明，对于一般的问题，二十个粒子就足够了，粒子数目越多，搜索的全局最优的可能性就比较大，但是运行时间较长，所以要根据实际情况来不断地调整。（2）粒子的长度N：粒子长度越长，问题越复杂。（3）最大速度:在每一维空间中都有一个最大限制值，在之间变化。如果设置过大，就会导致粒子在飞行运动时很可能飞过最优解区域；如果设置太小，使得离子移动距离很短，就会导致一旦陷入局部最优解中，不能跳出局部最优解区域。（4）与表示加速常数，代表粒子个体认知，代表社会认知。这两个参数的设置直接影响个体经验和群体经验的作用程度。一般情况下设置为2。（5），：这两个为（0,1）之间的随机数。确保粒子运动的随机性。（6）适应度函数：也可表示为目标函数。（7）终止条件：迭代次数大于或者等于最大迭代次数。3.4适应度函数PSO算法的收敛速度和收敛精度直接受到适应度的选取的影响。一般用目标函数作为适应度函数来衡量粒子群全局最优。本文使用最小化最大完工时间作为评价可行调度解是否达到最优的适应度函数。3.6动态非线性动态变化惯性权重3.6.1算法改进的原理粒子群优化算法的参数有粒子群总数N，加速常数和。惯性权重，最大速度，粒子群算法的参数较少，但是和以及对算法有着较大的影响。所以，很多学者针对这三个参数做出了大量的研究。刚开始，惯性权重被取为一个常数，但是在后期的研究结果表明呈线性变化的使得实验结果更好。经查大量查阅文献发现，大多数使用惯性权重线性递减的粒子群算法来解决具体实际问题中。如下： （3-5）迭代次数最大用表示，算法刚开始运行的时候，的值比较大的时候，粒子在空间范围比较大里搜索很有利。在算法的尾端，接近收敛的情况下，将的值取较小，这样对在局部范围内搜索比较有利，以便于增加找到最优解的可能性。经过查看大量的文献，总结经验发现，一般取为0.40.9范围内15。但是也存在不足的地方：由于在粒子最早期迭代的时候速度过快，会使得在局部搜索能力变弱，往往容易错过最优解的位置；相反的在迭代后期，速度较慢，使得全局搜索的能力也减弱，导致已于陷入局部最优解。依据文献经验可看出，惯性权重线性递减的粒子群算法比较易于实现，而且大大提高了算法的寻优性能，所以该算法得到了广泛的应用。但是要用线性策略解决非线性问题，验证的成果很有可能不尽人意，而且粒子群算法的搜索过程是一个很复杂的非线性过程。因此，本文引入动态非线性动态变化的，以下，其它条件不变，只改变速度更新公式为： （3-6） （3-7）惯性权重的最大值为，惯性权重的最小值。迭代次数最大表示为，t表示当前迭代的次数。经过大量实验证明，当=1.2，=0.4的时候，粒子群寻优性能最好。3.7二进制粒子群算法模型1997年Kennedy和Eberhart提出改进粒子群算法，设计了二进制版本的粒子群算法，应用解决离散空间组合问题，自提出后，大量研究都将其应用在解决组合优化问题中，例如01背包问题16，经济规划17，和生物信息18等。二进制粒子群算法，粒子是由二进制编码组成，速度更新公式保持改变，位变量值取1的机会，主要是由二进制位经过公式（1）来产生速度，然后将速度的值转换成变化的概率。构建二进制粒子群模型，设置粒子每一维的和限制位0或者1，但是速度不限制，当粒子速度更新位置时，把设置大一点，粒子的更有可能选1，否之选0。 （1）使用Sigmoid函数19把速度的值映射到区间0,1来表示取1的概率。Sigmoid函数： (2)我们将位置取1的概率用表示。粒子改变其位值利用公式（3） （3）是一个区间为0,1的一个随机数，设置参数，以防止接近1或0，来限制的范围，表示为。以速度限制来最终限制位的概率情况。4 基于二进制粒子群优化算法的车间作业调度问题模型4.1 车间作业调度具体问题描述及约束条件4.1.1 JSP问题的具体描述JSP问题描述的是n个工件在m台机器上加工，并且每个工件都需要m道工序，才可以完成加工，并且加工工艺中给定每道工序加工需要的时间。已知条件有以下：（1）工件集,表示第i个工件，；（2）机器集，表示第i台机器，；（3）工序集,其中，表示第i个工件的第K道工序。，；。（4）工件的每个工序的加工时间，代表工件i的第K道工序加工需要的时间。，。4.1.2 约束条件车间作业调度问题的约束条件如下：（1）同一个机器上在某一时刻只能处理一个任务；（2）一道工序在一台机器必须完成加工，才可以加工另一个工件；（3）保证m台机器都加工了工件；（4）每个工件优先级相同车间调度问题中存在很多的约束条件，例如，工件加工的开始时间，工件的工序，以及机器的操作顺序等。本文的优化目标是所有机器完工时间最短。 4.1.3 目标函数以上的定义，之前提到本文主要采用最后完成作业的时间最小。在本文JSP寻找的调度为： （4-1） 这里表示为一个调度，看作为在调度里，工件的完成时间，目标是需找一个用时最少的调度。这里的目标函数用来判断粒子位置的好坏的适应值函数。 4.3 应用二进制粒子群算法求解JSP问题4.3.1基于工序的编码方案 本文采用一种基于工序的编码方案20。本文将粒子在空间每一维的分量都编码为一个工件号，粒子在飞行过程中，出现同样的分量为同一个工件的不同工序，本文通过粒子分量出现的次序来决定是一个工件号的第几道工序。每个粒子代表工件的一个排序。需要注意的一点是，当粒子迭代更新的时候，改变的是粒子中的向量值，不是向量的排序。4.3.2粒子的编码和粒子的初始化在二进制粒子群里，表示微粒i的位置。在本文中，假设三个工件在三台机器上加工，且每个工件都有三道工序，如2 1 3 1 2 2 3 1 3则对应的粒子编码为X=010 001 011 001 010 010 011 001 011初始粒子群的数量设为N，二进制粒子群中部分粒子最开始处于最优，和全局最优。采用基于工序的编码方案，使得另外部分的初始种群也生成本身最优和全局最优。采永这种方式可以使得得到的数据具有一定的分布性和差异性。4.3.3调度方案的生成1、调度方案的生成将粒子群中粒子向量的各个分量进行从小到大的排序，然后交换操作排序X中对应的工序号。将yi向量按照从小到大的顺序依次排列。变换得到操作顺序表，当Yi向量在每一次迭代中位置发生的变化，使得对应的Xi的操作顺序也不断的变化，这样就形成了不同的调度方案。这里我们用表4-1所示的33调度问题来说明基于工序的编码。表4-1 33车间作业的加工数据工件号工序1工序2工序3N1M1（3）M2（3）M3（2）N2M1（1）M3（5）M2（3）N3M2（3）M1（2）M3（3）在表4-1中，N代表工件，M代表机器，如M2(3)表示工件N1的第一个工序在M2机器上需要加工的时间为3。假设给定一个粒子的编码为010 001 011 001 010 010 011 001 011其中，一个编码对应一个工件，重复的编码代表工序，所以一个编码出现了3次。粒子的第一个编号010表示作业2的第一个操作，因为010是第一次出现，第一个四个编号1表示作业001的第二个操作，以此类推。若用oijk表示工件i的第j道工序在第k台机器上加工。我们依据对应表的关系，可以总结出相对应的有序操作排列O211 O111 O312 O122 O223 O232 O321 O133 O333，得到如表4-2所示的每个工件的加工顺序与加工机器的对应关系。表4-2 33车间作业的有序操作表粒子010001011001010010011001011工件号N2N1N3N1N2N2N3N1N3操作序列O211O111O312O122O223O232O321O133O333机器M1M1M2M2M3M2M1M3M3使用甘特图表示粒子的调度方案，如下图4-1所示。图 4-1 33车间作业调度的甘特图从上图可以看出，三台机器所对应完成加工时间分别是6,10,12。从中可以看出，最大完成加工时间为12。编码方式以及解码过程通过上述分析，可以看出有效的保证了每个工件前后顺序的约束限制，很好的映射了调度问题的解空间。4.3.4二进制粒子群算法求解JSP问题的步骤假设给定粒子群为N个，维数为D，依据二进制粒子群算法原理以及车间作业调度问题的结合方法，主要步骤如下:Step1:设置粒子最大迭代次数，设置变量存储当前的迭代次数，对粒子群的参数进行设置初始化。Step2:使用随机函数对粒子进行初始化，随机的产生粒子的位置和速度；Step3:对粒子群中的每个粒子进行二进制编码，生成有次序的操作表；Step4:利用目标函数求解出粒子的适应度值；Step5：通过公式对粒子的速度进行更新，更新粒子的位置。Step6：判断是否达到最大迭代次数，如果没有达到，继续Step3，且，否之，继续执行Step7:输出粒子在搜索到全局最优值时，所对应的工序序列。就是最优调度值。二进制粒子群优化算法求解JSP问题流程图如图4-3所示。图 4-2 二进制粒子群优化算法求解车间作业调度问题的基本流程图4.4 系统仿真及结果分析本实验使用FT06基准测试问题对二进制粒子群算法应用在车间作业调度问题的性能分析进行验证。本文以MATLAB环境，使用标准粒子群算法和二进制粒子群算法求解车间调度问题。如下图加工工艺表：表4-3 66加工工艺表工件机器编号/加工时间工序1工序2工序3工序4工序5工序613/11/32/64/76/35/622/83/55/106/101/104/433/54/46/81/92/15/742/51/53/54/35/86/953/92/35/56/41/34/162/34/36/91/105/43/1粒子群算法和二进制粒子群算法的参数设置：粒子规模N=30,迭代的最大值=100，当前初始迭代次数为0，二进制粒子群算法惯性权重，；粒子群算法的惯性权重，。设置这两种算法分别进行8次，得到的最优解，收敛的代数，平均值、CPU的运行时间，如表4-4所示。工序调度图以及甘特图如下图 4-3所示：表4-4 两种算法比较结果次数标准PSOBPSO最优解CPU（ms）收敛代数最优解CPU(ms)收敛代数1561297675610243225714496655175330357130165541622314551450665612413355815076453140034656128665571664357591513675515013685513156355126037平均值56.61389.765.455.11433.133.5表4-3 最优值收敛曲线从上表可以看出，二进制粒子群算法最先找到最优解，并且收敛速度也比粒子群算法好，虽然时间上相对久一点，但是并不影响整体优点。从上图也可以很清晰的看到二进制粒子群算法的收敛速度很快，最早找到最优解。表4-4 二进制粒子群算法的工序调度结果甘特图4.5 本章小结本章阐述了改进的二进制粒子群优化算法应用到车间作业调度问题中，在分析了车间作业调度问题编码方案的产生，提出以基于工序的编码方案，来详细描述二进制粒子群优化算法求解车间作业调度问题的具体步骤，最后通过仿真实验对问题进行求解。实验结果证明二进制粒子群算法可以达到目标问题预期最小值，并且与标准粒子群算法的对比，二进制粒子群优化算法在解决车间作业调度问题上收敛速度很快，尤其在维数增加的过程中，容易跳出局部最优，验证了二进制粒子群优化算的有效性。5 总结与展望5.1 总结本文针对粒子群算法的分支二进制粒子群算法与对车间作业调度问题的研究与应用方面分析。首先提出粒子群算法，总结分析粒子群算法的缺点，提出一种改进算法，即二进制粒子群算法，详细介绍二进制粒子群算法的原理，建立二进制粒子群算法模型，对车间作业调度问题进行建模，结合二进制粒子群算法解决车间作业调度问题，进行仿真实验，分析总结基本一致，实验结果证明，在大多数测试函数中，二进制粒子群算法比遗传算法速度快，尤其在维数增加的过程中。二进制粒子群算法的随机性很强，但是二进制粒子群算法收敛的时候，容易错过全局最优，而且它的随机会随着迭代次数的增大逐渐增强。5.2 展望粒子群算法提出之后的短短数十年的时间，得到很大的发展。早期主要应用在连续空间数值优化的领域，经过这几年很多学者的不断思考与研究，粒子群算法在组合优化领域的应用越来越多，尤其是调度领域。依据大量关于生产调度中的粒子群优化算法的文献，本论文主要研究了改进为基于二进制粒子群优化算法的求解步骤与应用效果，取得了一些成果。但是针对生产调度问题的随机性和复杂性，二级制粒子群优化算法在一些方面还需要进一步的研究。（1） 本文在研究车间作业调度问题时，没有具体考虑到实际生产过程中的随机性和不确定因素。（2） 本文研究的车间作业调度问题比较简化，相比之下，考虑实际情况，设计出高效的算法显得很重要。（3） 算法证明收敛性没有很好的体现，所以，算法的收敛性研究与证明是我进一步研究的方向。致 谢时间飞快，大学生活即将结束，四年里，从专业的不知所云到拥有一定的专业技能，经历了很多很多，我学到了很多只是，也认识了很多很好的朋友，认识了优秀的老师。他们带给我的知识、经验都是我一辈子难以忘怀的回忆。毕业如期而至，完成这篇毕业论文，我最想感谢的就是我的导师李敬明老师，从论文的题目、思路、方法等无一凝聚着李老师的心血和汗水。没有李老师的帮助，我是不能够顺利完成论文的撰写。在这一段时间里，我每每遇到问题，李