改进的粒子群算法在动态车间调度问题研究

改进的粒子群算法及其在Job-Shop问题中的应用ImprovedParticleSwarmOptimizationandItsApplicationin第2章作业车间调度2.1引言作业车间的调度问题是工业生产当中原料采购、生产制造、企业管理的核心环节，高效的作业车间调度系统已成为智能化工业不可缺少的部分。由于企业生产制造不比实验室，面临更多的不可抗力因素，并且作业车间调度问题本身属于不确定问题，很难找到最为有效、唯一的调度算法求解车间调度问题。故此，促使众多科研人员不断更新新的更加智能优化算法用来求解车间调度问题，降低企业成本，提高企业效率，增强企业竞争力。2.2车间调度问题2.2.1调度问题分类根据以往的研究结果，大体可以把车间调度问题分为两类：（1）根据调度方法不同，可以分为静态调度和动态调度。静态调度中调度的任务是离线进行分配的，即在工件在加工之前，先把调度任务分配好，加工时间和工序在加工过程中不允许改变，加工机器不允许故障，是在一种理想情况下进行的调度任务；动态调度中调度的任务是线上进行的，可以根据加工实际情况调整加工顺序，例如增加订单、取消订单、机器故障等缺陷，动态调度更加符合实际生产需求。（2）根据加工工序不同，可以分为流水车间调度和作业车间调度。流水车间调度是指多个工件在多台机器上加工，其每个工件的每道工序相同；作业车间调度是在流水车间调度基础上，每个工件的每道工序不同，作业车间调度更加符合实际生产需求。2.2.2问题描述作业车间调度问题可以看成是以时间为参考量的最佳性能指标集。具体描述如下：一批N个待加工工件在M台机器上准备进行加工，在一定的限制条件下，通过调度系统，对加工工件及加工机器合理安排，在保证产品质量的情况下，最短时间完成加工任务，从而降低企业的生产成本，提高生产效率。作业车间调度中一般限制条件如下：每个工件加工工序不能改变；每个工件加工时间确定，加工机器确定，且中途不能更改；同一时间一台机器只能加工一个工件；无特殊指定，工件加工优先级一样。表2.1车间调度问题中常见数学模型符号数学符号含义N待加工工件总个数；J加工工件集合；M加工机器集合；M加工时间，Mt={MM运转时间，Mr={2.2.3调度问题表示方法作业车间调度问题有多种表示方法，最为常见的有析取图描述法、甘特图表示法等等。本文以甘特图表示法为例，甘特图表示法是以活动列表和时间刻度表示出特定项目顺序与持续时间关系，横坐标表示时间刻度，纵坐标表示项目刻度，在车间调度问题中，纵坐标表示加工机器，以矩形框的形式表示加工进程，同时矩形框长短表示加工时间刻度，甘特图表示法以简单、醒目、易懂等特点，在调度问题中能直观地反应加工顺序和进程关系而被广泛使用。表2.2以3×3车间调度问题为例，其甘特图如图2.1。表2.23×3作业车间调度问题加工时间、加工机器矩阵工件加工时间J469J53-J645加工机器JMMMJMM-JMMM工件J1需要经过3道加工工序，由图加工时间矩阵可知第1道工序所需时间为4，第2道工序所需时间为6，第3道工序所需时间为9；在加工机器矩阵可知工件J1第1道工序在M1机器上加工，同理可知，其第2、3道工序分别在M2、M3图2.1实例最优解甘特图2.2.4调度问题求解方法车间调度问题一经提出，国内外科研人员便对其开展研究工作，早期科研人员因为面对较为简单的调度系统，采取比较简单的方法，针对简单调度系统，大都数为精确求解算法；随着工业的发展，遇到的车间调度问题规模越来越大，问题本身越来越复杂，简单求解算法不再适用复杂的车间调度问题，科研人员转而研究更多近似优化算法如图2.2。图2.2求解车间调度问题方法分类在实际的生产调度问题中，调度规模一般较大，难以适用精确求解算法，或需要花费较大代价求解最优值，相比之下，求解近似最优解较为容易，在大多数情况下已经能够满足车间调度需求，获得较为满意的解。因此，近似求解方法越来越受到研究人员的青睐。近似求解算法总体可分为人工智能法和邻域搜索法，人工智能法是模拟人或自然界某些生物思维过程和生活习惯的行为算法。算法主要包括粒子群算法、神经网络算法、蚁群算法等；邻域搜索法是较为通用的近似算法，其算法核心是将当前最优解进行迭代临近搜索，以达到最优解目的，由于邻域搜索步伐较小，其算法容易陷入局部极值，单独依靠邻域搜索算法很难达到全局搜索的目的，因此，邻域搜索算法大多数与全局搜索算法配合使用，以达到全局搜索的效果。邻域搜索算法主要包括遗传算法、模拟退火算法、混沌算法等。神经网络算法(Neural

networkalgorithm)是依据人类脑部组织结构和运行机制研究后提出来的智能算法，具有并行处理、分布式信息存储、自组织自学习能力等特点。该算法长期被用作动态、不确定因素的车间调度问题。1990年，Rabelo等人最早利用神经网络算法求解车间调度问题。蚁群算法(antcolonyoptimization)最早由MarcoDorigo在1992年提出，模拟自然界蚂蚁觅食行为演化而来的概率型算法，王硕提出参数自适应蚁群算法求解车间调度问题，蚁群算法虽适应能力强，但其也存在参数较多，不易控制，收敛速度慢等缺点。遗传算法(GeneticAlgorithm)是通过模拟自然进化过程搜索最优解而形成的仿生优化算法。由于优化不依赖迭代，具有很强的鲁棒性和全局搜索能力，从而广发应用于路径规划、车间调度等各个领域。模拟退火算法(Simulatedannealingalgorithm)思想来源于固体退火降温过程的模拟，是一种较强的局部搜索算法，1983年Kirkpatrick等人将该算法应用于调度系统中，取得了较大成就，而后不断应用于车间调度系统中。模拟退火算法凭借其较强的局部搜索能力，与其他全局搜索算法有机结合，在车间调度问题上被广泛应用。2.3本章小结本章详细阐述了车间调度系统的理论知识，从车间调度问题分类、问题描述、问题表示方法、求解方法等角度全面阐述车间调度问题，对后面动态车间调度问题的解决奠定了基础。

第3章混合粒子群算法研究3.1引言粒子群优化算法是通过模拟自然界中鸟群觅食行为抽象出来的群智能优化算法，现已被广泛应用到作业车间调度、路径最优化选取、神经网络治疗等多个领域。本章结合实际应用过程中的问题及粒子群算法特点，提出一种混合粒子群算法。3.2标准粒子群算法标准粒子群算法是在1995年由R.Eberhart和J.Kennedy两位研究学者提出来的，是一种群智能优化算法，通过自然界中鸟群觅食行为抽象出来的优化算法，它把实际问题遍历区域看成搜索空间，将鸟群中的个体看作单独粒子，搜索空间中每个粒子均有自己的初始位置和初始速度，当鸟群中发现有觅食食物时，搜索空间中的每一个粒子受自身和其他粒子影响，重新赋予位置及速度，以此类推，通过多次迭代搜索，直至找到目标位置。粒子群算法是一种并行算法，其原理简单易懂，参数少，目前已经用于最优路径选取、作业车间调度、神经网络治疗等领域。3.2.1粒子群算法的数学模型由N个粒子组成的一个群体，在D维的搜素空间中，xi表示第iVit+1=ωXit+1=Xi在粒子速度更新公式中，ω为惯性权重，Vi为粒子速度，c1、c2为学习因子，γ1、γ2为[0,1]区间随机数，为调节系数，Vit、Xit分别表示粒子i在第t次迭代更新后粒子的速度与位置，Pit、P3.2.2粒子群算法基本操作步骤标准粒子群算法处理优化问题操作步骤如下：步骤一：初始化粒子。在D维搜索空间中随机初始化种群粒子N，并赋予每个粒子初始速度v。步骤二：适应度函数评价机制。对搜索空间中每个粒子进行适应度评价机制，判断粒子当前最优解位置。步骤三：迭代更新。通过迭代更新和适应度函数判断，更新每个粒子位置及迭代速度，更新当前最优位置及全局最优位置。步骤四：找出最优解。依据寻优精度，判断是否结束寻优过程。如达到寻优精度或迭代次数，符合条件，找到最优解，结束寻优算法；如没有达到寻优精度或迭代次数，返回步骤二，继续验证适应度函数，进行迭代寻优更新。适应度函数一般为目标函数，根据求解问题的不同而不同，适应度值越高，代表所得解越好，越接近目标位置，一般使用f(开始开始粒子初始化适应度函数评价更新个体极值及全局极值更新粒子速度及位置达到最大精度或最大迭代次数结束NY图3.1粒子群算法流程图3.3混合粒子群算法PSO算法尽管具有原理简单、参数少、容易实现等诸多优点，但是由于每次迭代更新需要通过自身认知和社会其他粒子影响的共同作用下进行的，进而导致使粒子容易陷入局部最优区域而找不到全局最优解。本文对粒子群算法进行如下改进：添加局部搜索算法，提高算法搜索精度，动态调节种群多样性，从根源消除算法容易陷入局部极值的缺点。3.3.1局部搜索算法鉴于PSO算法搜索精度低，容易陷入局部极值等缺点，因此提高局部搜索精度、增强种群多样性成为提高优化算法得整体思路，在优化算法中，惯性权重值得引入，使得算法在搜索初期对搜索空间中所有粒子进行全局大范围搜索，体现了智能算法得全局性，随着更新迭代的进行，逐步搜索到某一局部区域，算法只会在局部内进行搜索，而无法跳出当前局部搜索空间，这一现象被称为陷入局部极值。在粒子迭代过程中，搜索空间中设定有多个局部极值，在PSO算法中，粒子更新会同时收到自身惯性及周围粒子影响进行搜索，进而随机性陷入某一个局部极值无法跳出。本文引入模拟退火机制，实现局部搜索的精确搜索，引入变异策略，增强种群多样性，跳出局部最优概率。3.3.2退火机制模拟退火机制可理解为三个阶段：（1）加温。假定固态物体内部粒子原先处于不平衡状态，当把固态物体加热，内部粒子会因为温度的升高而偏离相对稳定的状态，直到液化固态物体，内部粒子打破原来状态，达到相对均匀。（2）平衡。当外界不再加热，物体由于自身温度高于外界温度，将与外界进行温度置换，物体内部粒子能量减少，当物体与外界温度一致时，此时物体内部能量最少，系统达到平衡。（3）冷却。当进一步将物体冷却，系统内能量进一步减少，物体内部粒子相对稳定，系统达到稳定。模拟退火算法具有很好的局部搜索能力，主要因为它可以接受比当前解更差的解，在模拟退火算法初期，随着温度的升高，算法不接受或小概率接受最优解，逐渐到算法后期，随着温度降低，最优解接受概率较高，可以容纳比当前最优解较差的解，有利于算法跳出局部极值。模拟退火算法思想如下：(1)产生可行邻域解。模拟退火算法是邻域搜索算法，利用Metropolis接受机制，有几率产生比当前全局最优粒子差的邻域解，使算法有概率跳出局部极值。设优化目标函数为f(x)，当前迭代次数时全局最优解为f(x1)，产生邻域解为f(p由此公式可以看出，当df<0时，一定会产生新的邻域解，即还有达到局部最优状态；当df≥0时，算法以exp−dfT概率接受邻域解，即当前全局最优解好于邻域解时，产生概率p是温度T(2)初温及降温设定。初温设定一般较大，能够使得所有转移状态都被接受，但也不宜过大，否则算法搜索时间过长，本文取T0=1000作为初始温度。其降温公式为：Tt=T0(3)终止温度。当模拟退火算法内、外循环在每一次迭代没有产生新的更新状态或已经达到设定的温度下限，即看成完成寻优任务，终止循环。3.3.3编码与解码优化问题中粒子编码就是所求优化问题得所有解得表达方式。编码得选取直接影响粒子群算法得优化性能，需符合调度方案，可以映射调度问题得解空间，能够适应粒子群算法中位置、速度得迭代更新。在车间调度问题中，粒子编码可以选取得种类很多，可从工件、工序、机器等进行编码，比较编码复杂性和时间复杂度来说，本文选取工序编码方式进行。解码是相对于编码而言的，简单概括编码是将具体问题抽象化，建立数学模型，便于求解，解码是将所得数据还原具体问题当中，从而进行评估、选择。现有3个工件需要加工，每个工件需要加工3道工序，采用工序编码，下图给出一组可行解。131321223图3.23×3问题可行解编码如图所示，图中1、2、3代表工业生产中工件编码，在可行解编码中出现的位置代表加工的有效顺序，以第一件工件为例，出现的位置分别为1号、3号、6号位，即代表工件1分别在对应的位置进行工序1、工序2、工序3得加工工作，以此类推，图1只是给出一个可行编码解，代表工件加工顺序优先级。3.3.4交叉与变异交叉与变异操作是遗传算法得重要手段，是通过生物进化而得来的准则。交叉操作是指子代中继承父代有利基因，淘汰不利基因；变异是将原有基因序列某一片段进行修改，进而增强子代基因，通过交叉变异操作可以提高子代基因种类。由粒子群公式可以看出，粒子迭代后速度更新由自身与群体其他粒子均有影响，正是因为由本身历史最优粒子和全局最优粒子得影响下，保持向全局最优粒子靠拢，从而实现子代更新迭代。由此可知，交叉操作是父代在参考群体搜索经验当中进行的，子代在继承父代有利基因外，还将继承群体经验中交叉变异后的有利基因，这样增加了跳出局部极值得概率。粒子群算法不能动态实现种群更新，本文引入交叉变异操作提高粒子群算法种群动态更新。（1）交叉操作。选定需要进行交叉操作的两个父代粒子x1、x2，将x1粒子随机选中和保留粒子的基因位，并记录选中基因个数，在x2粒子随机选中与x1粒子选中基因相同的对应基因位，并保留其所在基因，复制到新一代y粒子当中，将x1粒子中未选中基因按照顺序重新插入到y粒子中，所得新的基因序列即为交叉操作所得粒子。交叉操作示意图：图3.3交叉示意图（2）变异操作。在粒子群算法中引入变异操作，也是提高种群多样性的有效途径，引导算法指向更高的适应度函数进化，在邻域搜索算法中，引入变异操作，使粒子产生邻域解，增强种群多样性，有易于跳出当前迭代极值，实现全局搜索。在基于工序编码的车间调度问题当中，变异操作是随机选择父代中一个粒子基因片段的不同基因位进行互换，需要强调的是，一个基因片段可以互相调换多组基因位，如果调换位置基因位相同，则父代基因与变异后子代基因相同，则实质上没有进行变异。以3×3车间调度问题为背景对其变异过程如图3.4所示：图3.4变异示意图3.4静态车间调度求解混合粒子群算法根据车间调度问题提出，为了验证混合粒子群算法在车间调度问题中的应用，首先采用静态车间调度问题，采用MATLAB测试软件进行模拟仿真实验，验证结果。3.4.1建立数学模型确定车间调度问题的输入输出是建立数学模型的关键，我们以工件个体及加工时间为输入对象，输出则以甘特图表示最佳调度流程，经过限制条件、智能算法优化、最终达到求解最优值。车间调度问题输入输出模型图如下：图3.5车间调度问题输入输出模型图3.4.2仿真实验本文选取较为常见的FT06实例进行仿真测试实验，FT06实例描述为一批待加工6个工件，6台加工机器，每个工件需要加工6道工序，求解如何加工工件顺序使得加工时间最少，效率最高。具体工件及加工时间如下表：表3.1FT06车间调度数据表工件机器号/加工时间13/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/1FT06实例问题目前达到的最好解为55。利用混合粒子群算法求解的FT06问题得出甘特图如图3.6，图中以工件加工总消耗时间为横坐标，以工件编号为纵坐标，以矩形框表示工件加工顺序。为了进一步验证混合粒子群算法在实例当中收敛性、鲁棒性，同时选取了DPSO、GA算法进行模拟对比实验，在FT06实例问题上三种算法分别求解10次，每种算法迭代200次，选取每一次迭代全局最优解平均值做出如图3.7所示，图中以每种算法迭代次数为横坐标，以每次迭代中全局最优值平均值为纵坐标。从图中可以看出，混合粒子群算法在收敛速度和收敛效果上都比DPSO、GA算法要好。图3.6甘特图6×6车间调度输出图图3.7三种算法收敛性比较图3.5本章小结本章首先介绍了标准粒子群算法的基本原理，数学模型和操作流程，依据粒子群算法参数特点对其容易陷入局部极值缺陷进行改进，提出局部范围精度搜索，引入交叉变异策略，提出邻域值操作方法，提高种群多样性，从而跳出局部极值，增强算法鲁棒性，最后通过静态车间调度问题，引入具体实例，以混合粒子群算法及SPSO、GA算法进行可行性实验测试，对比得出混合粒子群算法无论在收敛速度及收敛精度上都取得较好效果。

第4章混合粒子群算法在动态车间调度问题中的应用4.1引言目前对车间调度算法的研究大多数都是针对静态车间调度问题，是在固定工件个数、固定加工工序、固定加工时间等一系列外界条件下进行的，但是在实际的工业生产中，工件加工往往不能遵循预先设定好的程序持续进行，由此动态车间调度被越来越多的人接受和采用，动态车间调度是在静态车间调度问题基础上提出来的，增加了由企业内部和外部环境带来的加工风险，例如：加工机器损坏、加工原料紧缺、客户加急订单、取消现有订单等等，这些突然情况导致无法延用原来固定不变的优化算法。因此对动态车间调度问题研究，更贴合实际应用。4.2动态车间调度问题4.2.1问题描述以往研究的车间调度问题对条件的设定一般是固定的，例如加工的工件个数、加工所需的机器特定，每个工件加工时所需时间一经确定将不再更改，在调度算法开始前所有工件都已准备就绪等等，这类已经确定好的调度问题被称为静态调度问题，而实际生产过程中，由于自身不可抗力因素或外部环境因素影响，导致无法按照指定原有计划进行，这类生产调度问题被称为动态车间调度问题。简而言之，动态车间调度是在静态车间调度问题上增添突发事件而产生的，即动态车间调度系统是静态车间调度系统基础上添加突发事件等不可抗力因素形成的，如图4.1。图4.1动态车间调度与静态车间调度关系图4.2.2动态调度模型分类在实际生产环境中，由于自身或外界不可抗力因素导致需要进行动态调节原有调度事件成为动态事件。根据Suresh等人对动态车间调度问题中动态事件的研究，一般分为以下三种动态事件。（1）工件突发事件。该事件包含由于工件问题导致的不可继续进行的突发事件，例如工件原材料缺损、工件加工过程中作废、工件优先级变化等等。（2）工序突发事件。该事件包含加工工序操作阶段导致无法进行的事件。例如某件工序加工延时、加工质量不合格重新加工等。（3）机器突发事件。该事件主要由于机器损坏导致加工无法正常进行的突发事件。针对以上几种动态突发事件，在实际生产过程中可能同时或多个出现，本文在研究中为了简化操作，只考虑单一突发事件情况。4.2.3动态调度窗口当生产调度系统发生动态事件时，打破原有调度规则，我们把产生动态事件时调度窗口称为动态调度窗口，如图4.2重调度动态窗口，横坐标为生产加工时间，纵坐标为加工机器，在ti时刻，由于发生动态调度，机器不再执行原有调度程序算法，暂停执行，此时如图4.2所示，M1、M2、M3已加工完成部分工件，M1图4.2重调度动态窗口4.2.4动态调度策略一般当突发事件发生时，动态调度策略大体分为两类：突发事件调度，即一旦有突发事件，系统会自动响应，进行重调度算法；周期性调度，系统每隔指定时间重调度算法。本文采用突发事件重调度策略，即生产调度系统在执行调度方案时，以遵照最开始调度方案进行调度工作，在调度开始之前，设定所有调度系统中原材料及加工机器均已准备好，一旦发生重调度，会对现有资源进行重新整理分配，图4.3是根据事件驱动重调度策略进行重调度示意图，调度系统会实时监测有无突发事件，一旦检测成功，将触发调度系统，启动重调度算法。图4.3事件驱动重调度示意图4.3动态调度问题求解基于突发事件的动态调度策略，可以及时对系统采取重调度处理。利用动态调度窗口可知，当发生重调度时可看做成一个静态调度结束，另一个静态调度开始，故而可以把动态调度问题看成是多个静态调度问题的结合，如全程仅存在一个静态调度即没有发生过重调度事件，因此，动态调度问题求解可看成一个或多个静态调度求解问题。4.3.1数学模型修正当调度系统发生重调度时，相当于又开启一项新的静态调度，新开启的静态调度与最开始的静态调度初始状态不同，重调度时机器的状态和加工的工件状态不一样，在进行粒子群算法重调度之前，需要进行数学模型修正。（1）利用加工时间修正。由于突发事件是随机的，所以当启动动态调度窗口时，工件可能会处于三种状态，未加工工件将不再进行加工工作；正在加工工件为不打断问题连续性，将继续加工至完成；已加工完成工件退出加工流程。（2）利用机器修复时间修正。当启用动态调度窗口时，机器同样可能处于三种状态，机器处于空闲状态，将暂停加工工作；机器正在加工过程中，为不打断问题连续性，将继续加工至完成；机器处于故障状态，设定机器预计修复时间，则重调度中机器响应时间为预计修复时间。如图3.3重调度数学模型修正。如图3.4所示，3台机器分别进行工件加工工作，当t=15时机器2发生故障，预计修复时间为5，则机器1在t=15时，处于空闲状态，可以立即进行重调度；机器2在预计修复时间结束后可启用重调度，即t=20；机器3当前正在加工工件，为不打断问题连续性，当工件加工完成时t=22，可参与重调度。综上所述，机器可利用时间矩阵为Tr图4.4机器修复模型4.3.2动态事件处理根据混合粒子群算法及动态调度窗口技术对动态车间调度问题进行求解，本文分别对加急订单、取消订单、机器故障三种突发事件进行讨论，一般解决步骤如下：（1）根据数学修正模型，确定重调度时刻（2）根据重调度，判定工件加工时间、加工机器、机器可利用三种调度模型状态（3）根据调度模型，开启重调度。本节以3×3模型调度实例讲解在紧急订单、取消订单、机器故障三种不同情况下发生突发事件处理办法。初始调度时，机器可利用状态矩阵为TrJt=245利用混合粒子群算法进行优化后得出在初始调度系统中最优粒子排序为：S=3图4.5初始调度系统最优解甘特图假设在T=3时刻发生动态事件，按以下三种情况分别讨论。（1）加急订单。调度系统在t=3时刻发生重调度，假设新增加急订单为4号工件，其工件加工时间矩阵为T4=3，5，6，加工机器矩阵为M4=3，2，1，如图4.5所示，在t=3时刻，1号机器正在加工1号工件，t=4时刻加工完成；2号机器正在加工2号工件，在图4.6加工时间、加工机器变化矩阵图其中0代表无需加工操作，再根据Tr（2）取消订单。假设t=3时刻取消工件3订单，调度系统为节约加工材料，立即取消加工操作，则机器可利用矩阵为TrJt3=450（3）机器故障。在生产得实际工作当中，机器故障引发动态事件占所有动态事件很大概率，假设在t=3时刻机器2发生故障，预计修复时间为4，即t=3时刻机器2不再进行加工工作，为了避免加工工件损坏，我们考虑在故障机器没有进行加工完成得工件都需重新加工当前工序，根据订单加急原理，机器可利用矩阵为TrJt3=4504.4仿真实验本节将利用混合粒子群算法求解动态车间调度问题，继续采用FT06实例进行验证。前面已经对FT06在静态调度情况下进行仿真实验，本节仍然以最短加工时间为优化目标，讨论在加急订单、取消订单、机器故障三种情况下混合粒子群算法在动态车间调度问题求解。按照FT06实例，则有工件加工时间矩阵及机器加工矩阵如下：Jt=136（1）加急订单。假设在t=20时刻，新增加急订单7号工件，加工时间矩阵为T7=6，3，8，5，4，9图4.6加急订单甘特图（2）订单取消。假设t=30时刻，取消工件4、5加工工序，启动重调度，利用混合粒子群算法求解最优解为52，甘特图如图4.7。图4.7订单取消甘特图（3）机器故障。假设t=26时刻，机器4故障，预计修复时间为9，利用混合粒子群算法求解最优解为57，甘特图如图4.8。图4.8机器故障甘特图根据以往用遗传算法求解动态车间调度问题，本文将混合粒子群算法与遗传算法在动态车间调度问题进行比较，得出如下结果：4.5本章小结本章对动态车间调度问题进行详细研究，从动态车间调度问题分类，分析调度问题中动态事件数学建模类型，提出动态调度窗口，列举加急订单、取消订单、机器故障三种突发事件，结合混合粒子群算法进行仿真模拟实验，最后与遗传算法进行比较分析，验证混合粒子群算法在动态车间调度过程中取得较好效果。

第5章总结与展望5.1总结制造业是我国经济发展和经济繁荣得关键，为我国经济发展提供强大动力，提升制造业产品多元化、提高生产效率、提升质量是进一步提高我国制造业生产智能化得关键一步。一个好的生产调度系统会大幅提升生产效率，降低生产成本，因此，研究车间调度问题具有实际应用价值。本文详细介绍了粒子群算法基本原理、参数设置、操作流程等，并与其他智能算法混合形成新的智能算法，应用于车间流水调度问题当中，从稳定性、寻优精度等角度提高算法性能。现将本文研究工作总结如下：（1）详细阐述车间调度问题的分类、问题描述、表示方法及求解方法，介绍车间调度当前研究现状及存在问题。（2）介绍标准粒子群算法基本原理、参数设置、数学模型及其在车间调度问题中的计算步骤，并依据粒子群算法及车间调度问题特点，提出在粒子群算法基础上增加交叉变异、引入退火机制的混合粒子群算法，从而增强种群多样性，提高局部搜索能力，引入除自身及全局其他粒子对其影响的额外信息参考点，提高算法搜索能力。（3）使用MATLAB软件模拟测试混合粒子群算法在静态车间调度系统中的应用，使用FT06实例对其混合粒子群算法收敛性、鲁棒性进行验证，并与其他优化算法进行比较，验证混合粒子群算法具有较强的搜索能力及收敛性能。（4）从动态车间调度问题的分类、动态调度窗口、动态调整策略及数学模型修复等方面介绍动态车间调度问题重难点，采用动态调度窗口及动态调度策略修正重调度所用资源，分别在加急订单、取消订单、机器故障三种突发情况下重启调度系统，并将仿真结果与蚁群算法进行对比分析，验证混合粒子群算法在动态车间调度问题中性能。实验结果证明，混合粒子群算法相比其他算法寻优能力更强，精度更高，在实际生产过程中应变能力更好。5.2展望动态车间调度问题是一项相对复杂的工程问题，由于时间和知识水平的限制，对于此项问题研究还不够深入，还有很多需要优化改进的地方，需要进一步研究：本文设定优化目标为单一优化目标，即最优目标为单一个体，而在实际生产过程中，往往要综合考虑产品性能、加工成本、生产效率等等，目标生产不仅仅为单一目标，需要进一步研究多目标优化效果。在混合粒子群算法中本文采取两种优化算法混合取得的效果，可以考虑多种优化算法混合，进一步提升算法鲁棒性。在针对动态车间调度问题中，忽略不同生产时期对产品的不同要求，不具有随时随地调节生产时间、生产精度等，算法具有一定强制性，一旦设定参数值将整个周期不能更改。

参考文献[1]越民义,韩继业.N个零件在M台机床上加工顺序问题[J].中国科学:1975,5:462-470.[2]何霆,刘飞,马玉林.车间生产调度问题研究[J].机械工程学报:2000,36(05):97-02.[3]Gavett,J.Threeheuristicrulesforsequencingjobstoasingleproductionfacility[D].ManagementScience,1965,11(08):166-176.[4]GereWS.Heuristicsinjobshopscheduling[D].ManagementScience:1966,13(08):167-190.[5]MA.Cruz-Chavez.Neighborhoodgenerationmechanismappliedinsimulatedtojobannealingshopschedulingproblems[J].InternationalJournalofSystemsScience:2015,46(15):2673-2685.[6]T.M.Willems.Implementingheuristicsasanoptimizationcriterioninneuralnetworksforjob-shopscheduling[J].JournalofIntelligentManufacturing:1996,6(12):377-387.[7]K.KurbelA.Comparisonofjob-shopschedulingtechniques:Simulatedannealing,geneticalgorithms,andmathematicaloptimization[J].1995,37:581-593.[8]Liu,SQ.MetaheuristicsforminimizingthemakespanoftheDynamicshopschedulingproblem[J].AdvancesInEngineeringSoftware,2004,36(7):199-205.[9]HoogeveenH.WoegingerGJ.Averydifficultschedulingproblemwithcommunicationdelays[J].OperationsResearchLetters:2001,29(5),241-245.[10]鞠全勇，朱剑英.基于混合遗传算法的动态车间调度系统的研究[J].中国机械工程:2007,1(1):40-43.[11]ZhangRui,WuCheng.Ahybridimmunesimulatedannealingalgorithmforthejobshopschedulingproblem[J].AppliedSoftComputingJournal:2010,10(14):79-89.[12]R.Eberhart,J.Kennedy.ANewOptimizerUsingParticleSwarmTheory[C].InProceedingsof6thInternationalSymposiumonMicroMachineandHumanScience:1995:39-43.[13]彭虎,田俊峰,邓长寿.求解约束优化问题的动态邻域粒子群算法[J].计算机应用研究:2011,28(07):2476-2478.[14]KennedyJ,EberhartR.Adiscretebinaryversionoftheparticleswarmalgorithm[C].ProceedingoftheWordMulticonferenceonSystematics,CyberneticsandInformatics.1997:104-4019.[15]JohnsonS.Optimaltwoandthreestageproductionscheduleswithsetuptimesincluded[J].NavalResearchLogisticsQuarterly,1954,21:61-68.[16]赵志刚,苏一丹.带自变异算子的粒子群优化算法[J].计算机工程与应用,2006