(完整版)智能算法在柔性车间调度中的应用

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。

关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度

0.前言

柔性作业车间调度问题(Flexible job-shop

sche- duling problem, FJSP)是传统作业车间调度

问题的扩展，是实际生产中迫切需要解决的一类问

题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。

作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。

1.蚁群算法在作业车间的应用[2]

以3个工件2台机器的问题作为例子，如图1。

图1 三个工件两台机器的JSP问题

为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对

值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。

这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。

另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的：

T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。

参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。

蚁群算法已经被成功地运用于10个工件、10

台机器和10 个工件、15台机器的JSP例子中，该

算法总能得到最优解的 10%以内的解，只是该方法

的计算复杂性占用了部分执行时间，但我们仍可以认为这是一个比较有希望的结果。

2.遗传算法在作业车间调度中的应用

2.1 遗传算法编码和解码[3]

编码与解码是指染色体和调度解之间进行相互

转换，是遗传算法成功实施优化的首要和关键问题。对于传统的作业车间调度问题，大多数研究采用基

于工序的编码。但是柔性作业车间调度问题不仅要

确定工序的加工顺序，还需为每道工序选择一台合

适的机器，仅采用基于工序的编码方法不能得到问

题的解。因此，对于柔性作业车间调度问题，遗传算法的编码由两部分组成，第一部分为基于工序的编码，用来确定工序的加工先后顺序；第二部分为

基于机器分配的编码，用来选择每道工序的加工机器。融合这两种编码方法，即可得到柔性作业车间

调度问题的一个可行解。

2.1.1 基于工序的编码

这部分编码染色体的基因数等于工序总数，每

个工件的工序都用相应的工件序号表示，并且工件

序号出现的次数等于该工件的工序数。根据工件序

号在染色体出现的次序编译，即从左到右扫描染色体，对于第 k 次出现的工件序号，表示该工件的第k 道工序。对表 1 所表示的柔性作业车间调度问题，一个基于工序编码的基因串可以表示为[1 2 2 1 3 1 2 3]，其中 1 表示工件 J1，2 和 3 意义相同。基因串中的 3 个 1 依次表示工件 J1 的 3

个工序，分别为工序 1、工序 2 和工序 3。

2.1.2 基于机器分配的编码

设工序总数为 l，工序号分别用 1, 2, 3,?, l 表示。对于这 l 道工序，形成 l 个可选择机器的子集{S1, S2, S3,?, Sl}，第 i 个工序的可加工机器集合表示为Si，Si 中元素个数为 ni，表示为{mi1, mi2,?, mni}。基于机器分配的编码基因串的长度为l，表示为[g1, g2,?,gi,?,gl]。其中第 i 个基因

gi 为[1, ni]内的整数，是集合 Si 中的第 gi 个

元素 mgi，表示第 i 个工序的加工机器号。具体

地说，若第 1 道工序有三台机器作为可选择机器，则 n1 = 3。设 S1 = {M11, M12, M13}，则第 1 道工序有 M11, M12, M13 这 3 台机器作为可选机器，根据 g1 的值从集合 S1 中确定加工第 1 道工序所用的机器。若 g1= 1，则机器 M11 为加工第 1 道工序所用的机器。以此类推，确定加工第 2, 3,?, l 道工序所用的机器。对于表 1 所示的柔性作业车间调度问题，总共有 8 道加工工序，假设基于机器分配编码的基因串为[2 1 2 3 1 2 3 2]，则表示这 8 道工序的加工机器号分别为[2 2 3 5 2 3 4 4]。

解码时先根据基于机器分配编码的基因串选择每道工序的加工机器，然后按基于工序编码的基因串确定每台机器上的工序顺序。但是确定每台机器上的工序顺序时，按一般解码方式只能得到半主动调度，而不是主动调度。这里介绍一种插入式贪婪解码算法，能保证染色体经过解码后生成主动调度。该解码算法描述如下：按照工序在该序列上的顺序进行解码，序列上第 1 道工序首先安排加工，然后取序列上第 2 道工序，将其插入到对应机器上最佳可行的加工时刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的地方。

2.2 交叉操作

交叉操作是将种群中两个个体随机地交换某些基因，产生新的基因组合，期望将有益的基因组合在一起。染色体中两部分基因串的交叉分别进行，其中第一部分基于工序编码基因串的交叉操作采用张超勇等[8]提出的 POX 交叉算子，第二部分基于机器分配编码基因串的交叉采用一种新提出的多

点交叉方法。

2.2.1 基于工序编码基因串的交叉

这部分交叉操作的过程为：将所有的工件随机分成两个集合 J1 和 J2，染色体子代 1/子代 2 继承父代 1/父代 2 中集合 J1 内的工件所对应的

图2 基于工序编码的交叉

基因，子代 1/子代 2 其余的基因位则分别由父代2/父代 1 删除已经继承的基因后所剩的基因按顺序填充，交叉操作过程如图2所示。

2.2.2基于机器分配编码基因串的交叉

这部分基因串采用一种新的多点交叉的方法，交叉操作的过程为：首先随机产生一个由 0、1 组成与染色体长度相等的集合 Rand0_1，然后将两个父代中与 Rand0_1 集合中 0 位置相同的基因互换，交叉后得到两个后代。图 2 显示了两个父代基因父代 1/父代 2 交叉后得到的两个子代基因子代 1/子代 2 的过程。此外，对于部分柔性作业车间调度问题，当交叉产生的机器号大于对应工序可利用的机器总数时，在该工序加工机器中随机选择一台机器加工 (加工时间短的优先选择)。

图3 基于机器分配编码的交叉

2.3 变异操作

变异操作的目的是改善算法的局部搜索能力，维持群体多样性，同时防止出现早熟现象。对于改进遗传算法，基于工序编码和基于机器分配编码的变异分别设计如下。

2.3.1 基于工序编码的变异

这部分基因实施插入变异，即从染色体中随机选择一个基因，然后将之插入到一个随机的位置。

2.3.2 基于机器分配编码的变异由于每道工序都可以由多台机器完成，所以随机选择两道工序，然后在执行这两道工序的机器集合中选择一台机器，并将选择的机器号置入对应的基于机器分配编码的基因串中，这样得出的解能确保是可行解。

2.3.2 基于机器分配编码的变异

由于每道工序都可以由多台机器完成，所以随机选择两道工序，然后在执行这两道工序的机器集合中选择一台机器，并将选择的机器号置入对应的基于机器分配编码的基因串中，这样得出的解能确保是可行解。

2.4 选择操作

在遗传算法中，选择是根据对个体适应度的评价从种群中选择优胜的个体，淘汰劣质的个体。在改进遗传算法中，选择操作采用最佳个体保存和锦标选择两种方法。最佳个体保存方法就是把群体中适应度高的个体不进行配对交叉而直接复制到下一代中，DE JONG[9]最早对这种方法作了定义。在本文的改进遗传算法中，最佳个体保存方法是将父代群体中最优的 1%个体直接复制到下一代中。锦标

选择是由 GOLDBERG 等[10]提出的，它是从种群中随机选择两个个体，如果随机值(在 0～1 之间随机产生)小于给定概率值 r(概率值 r 是一个参数，一般设置为 0.8)，则选择优的一个，否则就选择另一个；被选择的个体放回到种群，可以重新作为一个父染色体参与选择。

2.5 基于柔性作业车间调度问题的改进遗

传算法

在传统遗传算法求解调度问题时，交叉产生的子代总是被接受，这可能造成优良解被丢失或破坏，因此传统遗传算法易于早熟且收敛慢。求解柔性作业车间调度问题比传统调度问题更复杂，它首先确定工序的加工顺序，接着为每道工序选择一台加工机器；前者由染色体中基于工序编码的基因串确定，后者由基于机器分配编码的基因串确定，结合这两个基因串可得到一个可行解。针对柔性作业车间调度问题的这些特点，提出一种双层子代产生模式的改进遗传算法，它的交叉操作过程为：对于两个父代中基于工序的编码的基因串交叉 n 次，基于机器分配编码的基因串交叉 n×k 次；具体地说，基于工序的编码的基因串每交叉一次产生两子代，基于机器分配编码基因串就交叉 k 次，这样能为这两子代分配更合适的机器，使子代能更好地继承父代的优良特征。这样两个父代相当于交叉了 n×k 次，从所有后代中选择最优的两个染色体存入下一代。测试结果显示该方法求解柔性作业车间调度问题比传统遗传算法更有效。改进遗传算法的步骤如下。

(1) 初始化随机产生P 个染色体个体，P 为种

群规模。

(2) 评价每个个体适应度值。

(3) 判断是否达到终止条件，若满足则输出最

优解；否则转步骤4。

(4) 将1%最优个体直接复制到下一代中。

(5) 按选择策略选取下一代种群。

(6a) 若两父代个体适应度不相等并满足交叉

概率P c，基于双层子代产生模式对两父代个体进行交叉，即基于工序编码的基因串交叉n 次，基于机

器分配编码的基因串交叉n×k 次，从所有后代中选择两个最优的染色体作为下代。

(6b) 按变异概率P m，进行变异操作生成新个体。

(7)生成新一代种群，返回到步骤(3)。

3.粒子群算法在柔性作业车间中的应用[4]

3.1.1 FJSP描述

FJSP问题可以描述为:作业车间存在 M种工件在 N台机器上加工,工件 Mi各有 Ji道工序 (不指定工序的加工机器,允许工序从被选机器中任意选择 )。工件的工序是预先确定的,每道工序可以在一台或多台不同的机器上加工。R ijegk和 X ijk为决策

变量。

调度目标是为每道工序选择合适的机器 , 以

及确定每台机器上各工序的最佳加工顺序, 使系

统的总目标达到最优。并且加工过程需要满足以下假设和约束条件 :所有机器一开始均处于空闲

状态 ;在零时刻, 所有的工件都可被加工;工序一旦进行 , 不能中断;不同工件的工序之间没有先

后约束 ,工件之间具备相同的优先级;各工件的准备时间和移动时间计入加工时间;同一工件工序间的加工顺序约束;同一机器上一个加工任务完成后

才能开始另一个任务的加工资源约束。

3.1.2 FJSP多目标优化模型

本文面向的柔性作业车间多目标调度考虑 3个优化目标 (T, C, D)。 T、C、D分别表示制造工期、加工成本和工件提前/拖期惩罚值。

通过工厂日历、订单交货期和车间加工情况分析确定工件 i的最早交货期 D′i和最晚交货期时间 Di, Ei是工件 i的完工时间。同时根据工件的交货优先级确定不同工件的提前惩罚系数 ri和拖期惩罚系数 wi。

3.2 CDMOPSO算法

在 MOPSO运算过程中, 各粒子向所经历的某个非支配的历史位置 (Pb)学习, 同时从外部种群中按照一定规则选择一个解作为引导者 (Gb),在外部种群中存储从开始到结束运行时粒子群所发现的非支配解。在运算过程中不断更新外部种群,在运行结束时其中的解基本就是最终输出结果。MOPSO算法位置更新公式仍相似于单目标优化 ,即

3.2.1 编码和解码

FJSP问题的解包含机器选择和工序调度 , 因

此编码也要反映这两方面的内容 ,为此使用基于

工序和机器的两层编码方案[ 15] 。粒子的位置向

量用 2 个相互对应的 L维向量 Xp[ L]和 Xm[ L]

来表示 , L 是工件的总工序数。表 1所示是一个 3 ×4的 FJSP 粒子编码。

解码时 ,先通过粒子的 Xm[ L]向量值确定工序的加工机器 ,同时将对应的 Xp[ L]

向量转换为一个有序的操作表,向量中的顺

序决定了工序调度的优先级。然后根据该表, 将工序按其调度的优先顺序在指定的机器

上以最早允许加工时间进行加工 ,产生调

度方案。

3.2.2 计算位置和速度

粒子的速度矢量也由 2部分组成 , 即 Vp[ L]

和Vm[ L]来表示 , 分别根据式 (6)来计算。 Xp[ L]和 Xm[ L]根据式(7)来计算。由于 FJSP是满足优

先权约束的整数规划问题,因而粒子在更新时还需

进行修正。对计算得到的新值 X′p[L]的各分量先

按升序排列 ,再根据排序结果重新排列 Xp[ L]的

各分量。粒子的位置更新过程如表 2和表 3所示。

因为FJSP中工序存在机器约束的情况, 在Xm[ L]的粒子更新时需要进行修正:①若该分量所对应的工序只存在一台机器能够加工,则选择该工序所对应机器序号更新 Xm[L]的分量值。②若存在l台机器能够加工该分量对应的工序,其 Xm[ L]的分量对应值为 k1, k2, …,kl,Xm[ L]的分量值 x 在计算后得到x′,则对|ki-x′|(i=1, 2, …, l)进行排序, 选出其最小值 k* ,该分量值更新为

x=k*。

3.2.3 多目标粒子群算法的改进

PSO应用于多目标问题时最重要的操作是保持Pareto最优解集的多样性和更新粒子群的全局最优值。本文提出的 CDMOPSO算法 ,借鉴密集距离计算方法对个体按密集距离排序 , 同时采用精英策略保留进化过程中的优势个体 ,从而保持 Pareto 集的多样性和更新全局最优值 , 并引入小概率的变异机制增强算法的全局寻优能力。主要采用如下:

策略: (1)外部种群更新和缩减

在多目标进化算法中 ,精英策略是在外部种群中存储每代进化过程中产生的非支配优势个体, 并排除外部种群中可能产生的劣势个体 ,从而有利于保证多目标进化算法的收敛性和多样性。本文采用精英策略保留每代进化过程中产生的非支配个体。设内部粒子群为 P, 外部优势种群为 A,在粒子群完成一代飞行后, 首先选出 P中的非支配个体, 然后将所有非支配个体拷贝到 A, 并且删除 A中的重复个体和被支配个体。若 A中个体数超过其种群规模 S,基于 Deb在 NSGAⅡ中提出的个体密集距离计算方法[ 17] , 计算 A中所有个体的密集距离并按降序排列。仅保留前 S个个体, 删除多余的最密集个体。否则,不对 A进行缩减操作。该方法既通过精英策略保留运算过程中的优良粒子 ,同时保证了外部种群的规模, 避免了运算过程中随着循环代数的增加非支配个体数增多,从而保证

了运算的效率; 同时 ,当外部种群个体数超过其规模时 ,删除多余的最密集个体,保留分散个体 ,从而有效保证了 Pareto 前沿的均匀分布。

(2)全局最优值更新

完成外部种群 A的更新和缩减之后 ,需更新内部粒子群 P的全局最优值。 Gb从 A中选择一个处于最分散区域的个体, 引导粒子群向 Pareto最优前沿分散区域的进化。 Gb的更新分为两种情况: ①当 A中仅包含边界个体时 ,即 A中所有个

体的密集距离为无穷大 , Gb则从中随机选择一个边界个体。②当 A中包括若干个密集距离不为无穷大的个体时,则随机选择一个密集距离较大的个体作为G d ,其计算公式为

(3)小概率的变异机制

MOPSO算法具有收敛速度快的特点, 但过快

的收敛速度会造成搜索范围受限, 导致收敛到局

部最优Pareto前沿, 并非全局最优的Pareto前沿。因此本文在算法中引入2种基于不同编码的变异

操作以摆脱局部最优点的吸引, 对粒子位置产生

小范围扰动, 以提高种群多样性和扩大算法搜索

空间。c td表示A中第t代的解在第d维上的密集

程度。

以c td来反映A的密集程度, 当A变密集时, 即

c t d≤D d(D d为事先设定的密集程度指标值), 则对内部种群P中所有粒子的d维分量x t id按照变异概率p m1 、p m2 (p m1 、p m2为[ 0, 1]区间内的较小值)执行如下2种变异操作:①对X p[ L] 进行基于工序顺序的变异, 再将变异前后适应度值较优的个体保留下来。

②对X m[ L]进行基于机器选择的变异, 把可加工该道工序的所有机器放进一个集合, 进行变异时则从该工序对应的机器集合中随机选择一个机器来替换原有机器, 再将变异前后适应度值较优的个体保留下来。

CDMOPSO算法流程图如下

4.结语

本文介绍了柔性作业车间的调度问题及其对于企业提高生产效率的重要性。针对柔性作业车间调度问题，提出了蚁群算法、遗传算法以及改进后的粒子群算法在生产调度中的应用。基于不同算法的特点，蚁群算法和遗传算法可以直接用于解决生产调度问题，而粒子群算法由于其连续性，必须先将粒子群算法离散化，然后用于解决生产调度问题，故介绍了一种适用于生产调度问题的CDMOPSO算法。经参考文献中的试验验证，用智能算法得出的作业车间生产调度规划能有效提高车间生产效率。

参考文献

[1]张静.机遇混合离散粒子群算法的柔性作业车间调度问题研究[D ].浙江工业大学，2014

[2]江烨，李莉.蚁群算法在生产调度中的应用[J ].计算机工程，2005

[3]张超勇，饶运清.柔性作业车间调度问题的两级遗传算法[J ].机械工程学报，2007

[4]王云，冯毅雄.基于多目标粒子群算法的柔性作业车间调度优化方法[J ].农业机械学报，2011 [5]杨晓梅，曾建潮.遗传算法求解柔性job shop调度问题[J ].控制与决策，2004

(完整版)智能算法在柔性车间调度中的应用

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。 关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言 柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度 问题的扩展，是实际生产中迫切需要解决的一类问 题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。 作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。 图1 三个工件两台机器的JSP问题 为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对 值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。 这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。 参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。

柔性工作车间调度问题的多目标优化方法研究

第15卷第8期计算机集成制造系统 Vol.15No.82009年8月 Computer Integrated Manufacturing Systems Aug.2009 文章编号:1006-5911(2009)08-1592-07 收稿日期:2008207208;修订日期:2008209201。Received 08J uly 2008;accepted 01Sep.2008. 基金项目:国家863/CIMS 主题资助项目(2007AA04Z190,2008AA042301);国家自然科学基金资助项目(50835008,50875237)。Found ation i 2 tems :Project supported by t he National High 2Tech.R &D Program for CIMS ,China (No.2007AA04Z190,2008AA042301),and t he National Natural Science Foundation ,China (No.50835008,50875237). 作者简介:魏　巍(1982-),男,辽宁沈阳人,浙江大学CAD &CG 国家重点实验室博士研究生,主要从事产品配置优化、产品信息建模、多目标 优化和先进制造技术等研究。E 2mail :boyweiwei @https://www.wendangku.net/doc/358224219.html, ;+通信作者E 2mail :fyxtv @https://www.wendangku.net/doc/358224219.html, 。 柔性工作车间调度问题的多目标优化方法研究 魏　巍1,谭建荣1,冯毅雄+1,张　蕊2 (1.浙江大学流体传动及控制国家重点实验室,浙江　杭州　310027; 2.华晨金杯汽车有限公司,辽宁　沈阳　110044) 摘　要:针对各工件目标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多目标优化数学模型。针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto 进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto 综合最优解。最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题。 关键词:柔性车间调度;多目标优化;遗传算法;强度Pareto 进化算法中图分类号:TP278 文献标识码:A Multi 2objective optimization method research on flexible job shop scheduling problem W EI Wei 1 ,TA N J ian 2rong 1 ,F EN G Yi 2x iong +1 ,Z HA N G Rui 2 (1.State K ey Laboratory of Fluid Power T ransmission &C ontrol ,Zhejiang University ,Hangzhou 310027,China ; 2.Shenyang Brilliance J INB EI Automotive Corporation Limited.,Shenyang 110044,China ) Abstract :To solve the multi 2objective optimization problem in flexible job shop scheduling ,the multi 2objective sched 2uling optimization model ,namely the cost 、quality and term ,was constructed.While the traditional genetic algo 2rithm which combined random weigh could not solve the multi 2objective scheduling optimization problem commend 2ably.An improved strength Pareto evolutionary algorithm was employed to optimize the multi 2objective optimization model parallelly.As a result ,the optimal schema of flexible job shop scheduling was presented in the form of Pareto optimal sets.At last ,an instance related with the project in the air separation equip industry was given to prove that the proposed method could solve multi 2objective optimization problem in flexible job shop scheduling effectively.K ey w ords :flexible job shop scheduling ;multi 2objective optimization ;genetic algorithm ;SPEA2 0　引言 柔性作业车间调度问题(Flexible Job Shop Scheduling Problem ,FJ SP )是指带有机器可选柔性的车间调度问题。相对经典作业车间调度问题,FJ SP 突破了资源唯一性限制,每个工序可由多个不 同的机器完成,更加符合实际的生产环境。因此,研 究FJ SP 具有重要的理论价值和应用意义。 在处理FJ SP 问题上,文献[1]提出分布法,其基本思想是将机器分配问题和调度问题分开考虑,以降低FJ SP 问题的复杂性。文献[2]～文献[4]分别采用贪婪法、模拟退火算法和禁忌搜索法对FJ SP 问题进行优化求解。文献[5]在遗传算法框架的基础上,通过加权系数法将多目标问题转化为单目标

流水车间调度问题的研究-周杭超

流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品

混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==L L 。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。

置换流水车间调度问题的MATLAB求解

物流运筹实务课程设计 题目：置换流水车间调度问题的MATLAB求解置换流水车间调度问题的MATLAB求解

目录 一、前言 (5) 二、问题描述 (6) 三、算法设计 (7) 四、实验结果 (15)

摘要 自从Johnson 1954年发表第一篇关于流水车间调度问题的文章以来．流水车间调度问题引起了许多学者的关注。安排合理有效的生产调度是生产活动能井然有序开展，生产资源得到最佳配置，运作过程简明流畅的有力保证。流水车间调度问题是许多实际流水线生产调度问题的简化模型。它无论是在离散制造工业还是在流程工业中都具有广泛的应用。因此，对进行研究具有重要的理论意义和工程价值。流水线调度问题中一个非常典型的问题，而置换流水线调度问题作为FSP问题的子问题，是一个著名的组合优化问题。该问题是一个典型的NP难问题，也是生产管理的核心内容。随着生产规模的扩大，流水线调度问题的优化对提高资源利用率的作用越来越大，因此对其研究具有重要的

理论和现实意义。 关键字：流水车间，单件小批量生产，jsp模型，Matlab 前言 企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中,所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。车间生产计划与控制的核心理论是调度理论。车间调度问题是一类重要的组合优化问题。为适应订货式、多品种、小批量生产的需要,引进了置换流水车间调度概念。在置换流水车间调度优化后,可以避免或大大减少流程工作时间、提高生产效率。因此,研究成组技术下车间调度问题是很有必要的。生产调度，即对生产过程进行作业计划，是整个个先进生产制造系统实现管理技术、优化技术、白动化与计算机技术发展的核心。置换流水车间调度问题是许多实际生产调度问题的简化模型。生产计划与调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。调度问题是组合优化问题，属于NP问题，难以用常规力一法求解。随着制造业的快速发展，大规模定制生产、全球化制造等思想的提出，使车间调度问题呈现出以下的新特点:约束条件多，时间复杂度高，空问复杂度高。这将导致在许多情况下，求解所建立的数学模型的快速性无法满

基于文化遗传算法求解柔性作业车间调度问题

第16卷第4期计算机集成制造系统 Vol.16No.42010年4月 Computer Integrated Manufacturing Systems Apr.2010 文章编号:1006-5911(2010)04-0861-06 收稿日期:2009204220;修订日期:2009209216。Received 20Apr.2009;accepted 16Sep.2009. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Found ation item :Project supported by t he National Natural Science Foundation , China (No.70771008,70371057). 作者简介:李铁克(1958-),男,吉林长春人,北京科技大学经济管理学院教授,博士生导师,主要从事先进制造管理、生产计划与调度、智能算 法等的研究。E 2mail :tiekeli @https://www.wendangku.net/doc/358224219.html, 。 基于文化遗传算法求解柔性作业车间调度问题 李铁克,王伟玲,张文学 (北京科技大学经济管理学院,北京　100083) 摘　要:在分析柔性作业车间调度问题特性的基础上,提出了一种采用主群体空间和信仰空间的双层进化结构的调度算法。该算法采用优良调度方案的知识信息构成信仰空间;提出一种二维矩阵的集成编码;基于工序顺序编码和基于机器分配编码的两种交叉和变异算子在主群体空间进行传统的遗传操作;通过具有自学习特点的相似性选择算子,使子代更好地继承父代的优良特征。通过典型算例的计算实验,表明算法在计算效率和求解质量上均具有较好的效果。 关键词:柔性作业车间调度;文化算法;遗传算法;选择算子中图分类号:TP301.6 文献标志码:A Solving flexible Job Shop scheduling problem based on cultural genetic algorithm L I Tie 2ke ,W A N G Wei 2ling ,Z HA N G Wen 2x ue (School of Economics &Management ,University of Science &Technology Beijing ,Beijing 100083,China )Abstract :Based on the analysis of the characteristics of Flexible Job Shop Scheduling (FJ SP )problem ,the double 2layer evolution scheduling algorithm with f rame population space and belief space to solve FJ SP was proposed.This algorithm adopted usef ul knowledge of excellent scheduling schemes to form belief space.A two 2dimensional matrix integrated coding was put forward.Traditional genetic operations were conducted in f rame population space among two effective crossover operators and mutation operators ,which were designed on the basis of the integration of ma 2chine assignment and operation sequence for the genetic algorithm.By selection operators with similar self 2learning char 2acteristics ,son 2generations inherited excellent characteristics from parent 2generations.Experimental results indicated that the proposed algorithm outperformed the current approaches in computation efficiency and solution quality.K ey w ords :flexible Job Shop scheduling ;cultural algorithm ;genetic algorithm ;selection operator 0　引言 柔性作业车间调度问题(Flexible Job 2shop Scheduling Problem ,FJ SP )是经典作业车间调度问题(Job 2shop Scheduling Problem ,J SP )的扩展[1]。在J SP 中,仅考虑工件具有唯一确定的加工工艺路线的情况。而在FJ SP 中,每道工序可以在多台机器上加工,工件具有可选择的加工路线,并且在不同机器上加工所需的时间不同,因此FJ SP 比J SP 更 接近实际制造环境,是实际生产中亟需解决的一类调度问题。 FJ SP 不仅需要确定工件的加工顺序,还要确定某道工序由哪台机器加工。因此,FJ SP 是比J SP 更为复杂的N P 2hard 问题,一般不存在有效的多项式算法[2]。现有的研究方法主要分为精确算法、启发式规则[3]和元启发式算法(如模拟退火、遗传算法(Genetic Algorit hm ,GA )等)[4]。其中精确算法无法对大规模FJ SP 进行有效求解;启发式规则求解

基于深度强化学习的柔性车间调度问题现代研究

基于深度强化学习的柔性车间调度问题现代研究 摘要本文针对多目标柔性作业车间调度问题进行研究，分别以机器总负荷和设备利用率为性能指标，建立了多目标柔性作业车间调度模型。由于传统的企业调度算法忽略了历史数据的价值，在实时事件发生后不能快速响应支持，同时为了迎合“智慧工厂”的趋势，提出了一种适用于柔性作业车间调度的深度强化学习方法，实现了从状态输入到行为输出的直接控制。最后，通过实验案例验证了该方法在解决多目标柔性作业车间调度问题的可行性和有效性。 关键词柔性作业车间调度；深度强化学习；状态编码；多智能体 前言 近年来，市场中定制化服务已经成为一种普遍需求，“随需应变”的理念得到了企业管理者的高度重视。柔性生产是指通过先进制造设备来实现多品种、小批量的生产方式，其主要优点是增强了制造企业的灵活性和应变能力，提高了设备利用率。柔性作业车间调度问题（Flexible job-shop problem，FJSP）是传统作业车间调度问题的重要扩展，是目前车间调度问题的研究热点。 与传统的作业车间调度问题相比，柔性作业车间调度问题减少了机器能力约束，是更为复杂的NP-hard问题。目前的相关研究主要集中在算法效率改进[1-3]、问题实际化[4-7]、优化目标扩展[8-10]三个方面。在柔性作业车间调度问题上一般采用两种方法求解：启发式方法和集成方法[11]。问题实际化的研究主要通过加入更多生产相关约束，使得问题模型更加贴近实际生产。许多学者在上述三个方面进行了深入的研究，但是他们对于企業过去的生产调度历史数据并没有进行关注，忽略了其价值。 随着“中国制造2025”的提出，智能制造成为推进该项战略的重要举措。智能制造包括了智能制造技术和智能制造系统。深度强化学习作为一种端对端的感知与控制系统，为构建智能化的生产调度系统提供了重要指导和有效支持。 本文针对柔性作业车间调度问题，以最小化机器总负荷和最大化设备利用率为目标。通过对生产状态的编码，将每个工件构建为一个智能体。采用多智能体Actor-Critic算法，使得工件智能体学习彼此协作，为求解多目标柔性作业车间调度问题提供一种智能化的方法。 1 多目标柔性作业车间优化建模 1.1 问题描述 nm的FJSP问题可以描述为：一个拥有m台机器的加工系统，加工处理n 个工件。其中每个工件包含一道或者多道工序，每道工序可以在一台或者多台机器上进行加工处理，且相对应的加工时间取决于所分配的机器能力。对于该类问

流水车间调度问题的研究-周杭超

流水车间调度问题的研究-周杭超

流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品

混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。

流水车间调度问题的研究周杭超

流水车间调度问题的研究 机械工程学院2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品

混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。

基于改进遗传算法的柔性作业车间调度

第39卷 第7期2007年7月 哈 尔 滨 工 业 大 学 学 报 J OURN AL OF HARBI N I NSTI T UTE OF TECHNOL OG Y Vo l 139N o 17Ju.l 2007 基于改进遗传算法的柔性作业车间调度 席卫东1,2 ,乔 兵1 ,朱剑英 1 (1.南京航空航天大学民航学院,南京210016,E 2m ai:l x wdn@j 163.co m;2.远东控股集团,江苏宜兴214257) 摘 要:应用遗传算法解决柔性作业车间调度问题,针对柔性作业车间问题的特点提出了一种新颖直观的双子串基因编码方法,并设计了独特的交叉和变异算子,从而取消了运用遗传算法求解作业车间问题时为使基因合法化而进行的基因修复和重建过程,仿真结果表明用该遗传算法解决柔性作业车间调度是有效的.关键词:柔性作业车间;遗传算法;作业车间调度中图分类号:TP18;TP 273 文献标识码:A 文章编号:0367-6234(2007)07-1151-03 A genetic a lgor ith m for flexi b le job shop schedu li ng based on t wo 2sub str i ng gene cod i ng m ethod XIW e i 2dong 1,2 ,Q I A O Bing 1 ,Z HU Jian 2ying 1 (1.The College of C i vil Avi atio n ,N an ji ng University of Aero nauti cs and Astronautics ,Nanji ng 210016,Ch i na ,E 2m a i:l x wdn@j 163.co m;2.F ar EastH oldi ng Gro up Co .,LTD ,Y i xi ng ,214257China) Abstr act :A novel genetic algorithm f or solvi n g flexi b le job shop scheduling prob le m is elaborated .An intui 2ti v e gene cod i n g method ,called t w o-substri n g gene cod i n g ,and a spec ial cross operator aswell as a mutation method are proposed .By doing tha,t the repa iring process to va lida te the schedu le gene is successf ully can 2ce lled .The co mputer si m u lations are carried out and the results are worked ou t to sho w the eff ecti v eness of the proposed a l g orithm.K ey w ord s :flexi b le j o b shop;genetic algorithm ;j o b shop schedu li n g 收稿日期:2005-04-29. 作者简介:席卫东(1967)),男,博士研究生; 朱剑英(1937)),男,教授博士生导师. 作业车间调度问题(JSSP :Job Shop Schedu 2li n g Prob le m )通常出现在工业制造环境中,为了完成一个作业,必须按顺序在若干台机器上处理一系列不同工序,并且同时有若干个作业需要完成,管理人员必须根据作业的生产方式和工艺要求设计一个调度表,以获得某种生产指标的最优化,如加工周期最短、设备利用率最高等. 在古典作业车间调度中约定,任一工序只能由指定的某台设备加工,而在柔性作业车间调度(FJSSP :Flexible JSSP)中,则允许工序由一个机床集合中的任意一台加工,这更符合实际的生产状况,调度的目的是将工序分配给各机床,并对各机床上的工序进行排序以使完成所有工序的时间最小化.FJSSP 比JSSP 更为复杂,因为FJSSP 不但 需要确定所有工序在所有机器上的安排,而且还要确定每一台机器上工序的序列. JSSP 已被证明为NP-hard 问题 [1] .由于它的 高度并行性和重要的实际意义,学者们对其进行了广泛的研究,并提出了许多算法.这些算法可以分为下面几类:启发式方法、人工智能方法、最优化方法和近似最优法 [2] .近年来,对于这类具有高度 并行性和复杂性的问题,学者们提出了一些非经典、非线性的求解方法,获得了很好的效果 [3] ,如神 经网络算法、模拟退火算法、遗传算法等.其中,由于遗传算法(GAs)良好的全局搜索性能、内在的并行处理能力及其在解决TSP 一类组合优化问题方面的成功应用,引起了JSS P 研究人员的重视,Gen and Cheng [4] 提供了一个很好的关于G As 应用于JSSP 研究的综述并提出了若干JSSP 遗传算法,但是对于应用G A s 解决FJSSP 却未做研究.基于上述分析,本文试图采用遗传算法来解决FJSSP .

基于遗传算法的流水车间调度问题

中文摘要 流水车间调度问题是研究多个工件在若干个机器上的加工次序的问题，有效的调度算法对企业提高生产效率有着重要作用。本文使用遗传算法求解流水车间调度问题，把一个染色体编码成若干个自然数，表示相应工件的排序权值；通过简单交换两个父代的若干相同位置的基因，产生能够继承父代优良特性的子代；并且采用均匀变异，更好地保持种群中的基因的多样性。实验表明，该方法能取得较好的效果。 关键字：遗传算法，流水车间调度方法，实数编码，基因链码，群体，适应度。

外文摘要 Abstract: Flow-shop scheduling problem study the problem the processing sequence of A plurality of workpieces on some working machine,and it makes good effects on proving production efficiency to the industries with effective methods.In the case,we deal with flow-shop scheduling problem using a algorithm,the Genetic Algorithm.There is a chromosome we've just coded into some natural numbers to represent the weight order of these workpieces; exchanging simply two fathers' places of some gene to produce new children that carried good feature on two fathers;we also use the Uniform Mutation,and it keeps its diversity of gene on the population.This experiment show this method can achieve good results. Key Words: Genetic Algorithm, Flow-shop scheduling problem，natural number coding，genic bar code,group，fitness.

求解柔性作业车间调度问题的两级邻域搜索混合算法

第51卷第14期2015年7月 机械工程学报 JOURNAL OF MECHANICAL ENGINEERING Vol.51 No.14 Jul. 2015 DOI：10.3901/JME.2015.14.175 求解柔性作业车间调度问题的两级邻域搜索 混合算法* 赵诗奎 (济南大学机械工程学院济南 250022) 摘要：针对柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)，以优化最大完工时间为目标，提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法，构造邻域结构，对关键路径上的关键工序进行移动，实现邻域搜索，以改进当前解；设计针对FJSP问题特点的两级邻域搜索方式，第一级邻域搜索为跨机器移动工序，将工序移动到除当前加工机器之外的其他可选机器上，第二级邻域搜索为同机器移动工序，将工序在当前加工机器上进行移动；给出两级邻域搜索相应的保证可行解工序移动条件；兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力，利用遗传算法实现全局搜索，两级邻域搜索实现局部搜索；采用国际通用的FJSP问题基准算例进行测试，验证了所提方法的有效性。 关键词：柔性作业车间调度问题；两级邻域搜索；邻域结构；遗传算法 中图分类号：TP301 Bilevel Neighborhood Search Hybrid Algorithm for the Flexible Job Shop Scheduling Problem ZHAO Shikui (School of Mechanical Engineering, University of Jinan, Jinan 250022) Abstract：For the flexible job shop scheduling problem (FJSP), in order to optimize the maximum completion time, a hybrid algorithm mixed with bilevel neighborhood search and genetic algorithm is proposed. The neighborhood structure is constructed by using machine idle time to reduce the maximum completion time. In order to improve the current solution, critical operations of the critical path are moved to achieve neighborhood search. The method of bilevel neighborhood search is designed according to the characteristics of FJSP. The first level neighborhood search is the cross-machine moving operation, and the operation is moved to other optional machines in addition to current processing machine. The second level neighborhood search is the same-machine moving operation, and the operation is moved on current processing machine. Operation moving conditions corresponding to the bilevel neighborhood search are given to ensure feasible solutions. Both of global search ability and local search ability of FJSP solving algorithm are considered, and to use genetic algorithm to achieve global search, bilevel neighborhood search to achieve local search. The internationally accepted FJSP benchmark examples are adopted to test the validity of the proposed method. Key words：flexible job shop scheduling problem；bilevel neighborhood search；neighborhood structure；genetic algorithm 0 前言 高效的生产调度优化技术对于提高制造系统生产率和设备资源利用率，缩短产品制造周期具有 * 国家自然科学基金(51405193)、山东省优秀中青年科学家科研奖励基金(BS2014ZZ013)和济南大学博士基金(XBS1427)资助项目。20141011收到初稿，20150420收到修改稿十分重要的意义。随着加工技术、自动化技术的发展，柔性制造系统和数控加工中心等带有一定柔性的生产系统逐渐出现，具有柔性机器选择的柔性作业车间成为企业应对动态突变市场环境和机器故障等突发事件的有力工具，柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)逐渐成为研究的焦点问题。FJSP问题是传统作业车间调度问题(Job shop scheduling problem，JSP)的延伸，它突破

基于机制设计的柔性流水车间调度问题的研究与分析

目录 摘要.............................................................. I Abstract ......................................................... I II 第一章绪论 .. (1) 1.1研究背景与意义 (1) 1.2国内外研究现状 (3) 1.3本文研究内容 (5) 1.4本文组织结构 (7) 第二章流水车间调度问题及经典算法介绍 (8) 2.1调度问题模型及分类 (8) 2.2经典调度算法 (9) 本章小结 (12) 第三章混合搜索机制粒子群算法 (13) 3.1问题描述 (13) 3.2混合搜索机制粒子群算法 (14) 3.3实验仿真及算法分析 (22) 本章小结 (29) 第四章双目标零等待柔性流水车间调度问题算法 (30) 4.1问题描述 (30) 4.2产生初始种群的五种启发式算法 (31) 4.3精英粒子群算法 (32) 4.4联姻帝国竞争算法 (38) 4.5实验仿真及算法分析 (44) 4.5.1数据生成 (44) 4.5.2算法性能指标 (44) 4.5.3算法参数 (45) 4.5.4仿真实验 (48) 本章小结 (55)

第五章基于算法机制设计的柔性流水车间调度问题算法 (56) 5.1机制设计问题描述 (56) 5.2基于算法机制设计的柔性流水车间调度问题模型 (57) 5.3柔性流水车间调度问题的诚实机制设计 (59) 本章小结 (62) 第六章总结与展望 (63) 致谢 (65) 参考文献 (66) 附录 (69) 图版 (70)