考虑约束松弛的柔性流水调度研究

张翠林，王 烁，王军强

(1．西安航空学院经济管理系，陕西西安 710077)

(2．西北工业大学生产与运作系统性能分析中心，陕西西安 710072)

(3．西北工业大学现代设计与集成制造技术教育部重点实验室，陕西西安710072)

生产调度是制造单元管理与控制的核心，是制造单元实现有序、平稳、高效运转的关键。自1954年Johnson首次进行流水调度问题n/2/F/Cmax研究以来，许多生产调度问题作为复杂的组合优化问题，早已被证明是NP(Nondeterministic Polynomial)难题。调度优化方法主要包括数学规划方法、启发式规则、智能优化算法等。数学规划方法试图获取一定条件下调度问题的精确最优解，一直方兴未艾，包括分支定界法［1－2］、整数规划法［3］等;启发式规则简单易操作，是求解大规模问题的实用方法，在研究与实践中得到广泛应用［4－7］;智能优化算法是利用算法的优化机制和评价机制进行迭代搜索，不断改善可行解，逐渐获得问题的趋优解或次优解，在大规模问题和优化解求解两者之间找到结合点，逐渐成为当前研究的热点［8－10］。

然而，当前调度理论研究成果并未很好地应用到生产实际中。究其原因，现有的研究是先建数学模型再进行优化求解。一旦模型建立，所有约束条件就被确定，模型只能遵从，不能更改，即模型固化了当时时刻的生产条件。而在实际生产过程中，约束并非完全遵照模型最初的设定，很可能随着生产进度的进行和现场工况的变化，部分约束在一定条件和一定代价前提下可以获得一定程度的约束突破。例如，当部分设备加工能力不足时，如果允许工序超越，则调换相关工序次序可缓解设备能力不足带来的加工压力，或者借用其他工段或单元设备能力，以应对能力不足而可能导致的加工进度延迟问题;或者变串行加工为并行加工，通过改变部分设备的加工批量和运转批量，以变批量加工方式调整设备上的负荷。显见，实际生产中，模型可能存在一定修改余地，能力限制存在一定扩张可能。当然，并非所有约束都存在突破可能，而且约束突破肯定是以付出其他代价为前提的。

本文以某加工车间为例，考虑加工批量约束松弛和瓶颈工序顺序松弛，研究柔性流水车间调度(Flexible flow shop scheduling，FFSS)的约束松弛以及对应调度问题。

1 问题描述

本文研究的某加工车间是典型的流水车间，柔性流水车间调度问题一般描述如下:有n种待加工工件 Ji(i=1，2，…，n)，每种工件有 ai个，每个零件表示为Jia(a=1，2，…，ai)，m 种可用于加工工件的机器Mj(j=1，2，…，m)，每种机器有bj个相同并行机，每台机器表示为Mjb(b=1，2，…，bj)，设第k道工序的机器为瓶颈机器。工件Ji的加工过程由m个操作Oi1，Oi2，…，Oim组成，且各工件预先给定的工艺路径均相同，操作Oij的加工时间为Pij，每种机器Mj上可以同时加工相同种类的零件cj个，且机器一旦开始加工不能停止。经典的柔性流水车间问题如图1所示。

图1 柔性流水车间问题示意图

传统的调度问题是基于机器唯一性原则和流水顺序不变原则进行研究，但实际生产中，此约束存在一定程度的松弛:

a．加工批量约束松弛。一台机器同一时刻只能加工一个或一批工件。而实际加工车间同一工序的每次加工批量并不相同，或者前后相邻工序间的加工批量也不尽相同。

b．工艺顺序松弛。加工车间为了缓解瓶颈设备的压力，在允许工序超越的情况下，调换瓶颈工序和其相邻的后续工序的加工顺序，即存在加工顺序局部可调的现象。此问题与工艺路线可变的作业车间调度问题既有相似性又有很大的不同。工艺路线可变的作业车间调度问题指每个零件的加工工艺路线可能有几条，具体选择哪一条工艺路线要视机器的空闲情况和调度问题的目标而定;而该问题加工顺序只是局部调整，并不存在几条不一样的加工路线，即存在工序顺序松弛现象。

本文所研究的问题是柔性流水车间调度问题中的一种特殊情况，即考虑加工批量约束松弛和瓶颈工序顺序松弛的新型柔性流水车间调度问题。

2 数学模型

柔性流水调度研究假设:(1)不考虑零件加工的优先权;(2)操作允许等待，即前一个操作未完成，后面的操作需要等待;(3)在整个加工过程中，零件每道工序的加工时间保持不变;(4)每台设备前都有一个无限容量的缓冲;(5)在零时刻所有零件都可开始加工;(6)工序一旦开始不允许中断;(7)不考虑零件在机器间的转移时间、准备时间。所建数学模型如下:

式中:t为时间间隔，t=1，2，…，T，T表示足够长的时间以使所有的工件都能完成加工;Biajb表示工件Jia在机器Mjb第j工序加工的开始时间;Ciajb表示工件Jia在机器Mjb加工的完成时间。

式(1)为数学模型的目标函数，以最小化调度系统的Makespan为优化目标;式(2)表示在时刻t、处于工序j加工的工件数必须不超过那个时刻可利用的机器数;式(3)表示操作一旦开始就不允许中断;式(4)是顺序约束;式(5)表示工件Jia在机器Mj的时间为加工时间;式(6)表示工件Jia在机器Mjb所占用的所有时间间隔在其完成时间之前;式(7)表示工件Jia在机器Mjb开始时间应在时间间隔(Ciaib－Pij)后;式(8)表示同一时间每台机器最多加工的相同种类工件数量应小于等于机器可以同时加工的工件数;式(9)表示相同机器上，下个零件的开始时间在上个零件结束时间之后;式(10)、(11)、(12)是决策变量;式(12)表示一台机器在相同时刻只能加工相同种类的零件，且当j，b，t不变时，只有一个i能使其值为1，其余均为0。

3 基于遗传算法的求解方法

遗传算法(Genetic Algorithm，GA)具有优良的并行性和全局寻优能力，在求解FFSS时，序号编码方式比非序号编码更直接、更方便，但序号编码的染色体不能在任意位置进行交叉，必须使用PMX、OX和CX等特殊的交叉算子，这些交叉算子遗传操作过程复杂，计算效率不高。李茂军［11－12］等提出的单亲遗传算法(Partheno Genetic Algorithm，PGA)取消了传统序号编码GA的交叉算子，代之以仅在一条染色体上操作的基因重组等遗传算子，简化了遗传操作，提高了计算效率，并且不要求初始群体的多样性，也不存在“早熟收敛”问题［11］。文献［12］证明了PGA的基因重组算子隐含了序号编码TGA的交叉算子的功能，并没有影响进化，并验证了PGA在flow shop问题中的应用效果，因此本文采用PGA进行求解。随机产生初始化染色体种群，计算当代种群中个体适应度，适应度函数以柔性flow shop调度问题的最大完工时间max Ciamb为判断依据，对适应度函数值较小的个体以较大概率进行保留，再通过基因易位操作产生新一代染色体种群，如此循环直到满足终止条件，输出最优调度方案。

3．1 编码

文献［13］针对混合流水车间调度问题设计了如下形式的染色体:

染色体由S个小段组成，每小段表示一道加工工序，每个小段包括L个不同的基因，第p段(1≤p≤S)上的每个基因apq表示第q(1≤q≤L)个工件在第p道工序上加工的机器和加工次序。其中apq由整数和小数两部分组成，整数部分代表工序p加工用的工序序号，小数部分表示在同一台机器上加工发生冲突后的先后顺序。如果某台机器上存在需要加工两个或两个以上的工件的冲突，此时小数部分决定加工它们的先后顺序，较小的数先被加工。

此编码方式无法对批量约束松弛问题进行求解，因此本文在文献［14］的基础上做了如下改进:

a．apq改由3位数组成。百位表示工件在该道工序的第(apq/100)台并行机上加工，十位和个位用确切的数字表示工件在该机器上的加工次序，如apq=302表示工件q的第p个工序在该工序的第3台并行机上第2个加工。

b．在同一个工序同一台机器上加工的工件，其编码的十位数和个位数表示的加工次序必须是从1开始并且连续地递增，不能跳跃递增。例如不允许工序1在第一台机器上加工的编码为101、103。

c．允许同一工序同一机器上不同工件具有相同的编码，即表示几个不同的工件在该机器上同时加工(同时开始同时结束)，但是不同工件的个数要小于等于该机器上允许同时加工的零件数。

d．由于假设只有相同种类的零件才能同时加工，所以相同的编码只能出现在同一种类的零件中。

例如，某车间有2类工件，第1类工件有3个，第2类工件有4个。每类工件都有3道工序:第1道工序的并行机机器数为2，第2道工序的并行机机器数为3，第3道工序的并行机机器数为1。用此编码方式，得到此柔性flow shop调度问题的一个染色体为:

该染色体第1行表示第1道工序:工件3在并行机1上第1个加工，在并行机2上依次加工的工件号为1，5，2，6，4，7。第 2 行表示第 2 道工序:工件1在并行机1上第1个加工，工件3，6在并行机2 上加工，加工次序为工件 3，6，工件 2，4，5，7 在并行机3上加工，加工次序为工件2，5，4，7。第3行表示第3道工序:工件1，3在并行机1上第1个同时开始加工，工件2在并行机1上第2个开始加工，工件5，6在并行机1上第3个同时开始加工，工件4，7在并行机1上第4个同时开始加工。

3．2 选择算子

采用基于轮盘赌的比例选择法确定哪些个体被选择进行基因移位操作。为防止过早收敛，本文采用非线性排序来确定个体被选择的概率，首先将种群中各染色体按适应度值从高到低进行排序，使得排在前面的适应度值较高的个体被选择到的概率ui也较大。

式中:λ为常数。

3．3 基因移位算子

基因移位操作是按一定的概率把一条染色体中的一个(或一些)子串中的基因依次后移，并把该子串的最后一个基因移到最前面的位置，移位是在同一条染色体中进行。基因移位的子串及其长度是随机的。本文采用的基因移位示意图如图2所示。

图2 基因移位示例图

3．4 解码

编码操作和遗传操作会得到不同的染色体，这些染色体必须利用解码技术才能被转化成各个机器上工件的实际加工顺序。本文解码算法的伪代码如下:

For i=1∶n(工件总数)

Bia1b=0(初始值设为0)

//工件Jia在第一道工序的机器M1b的开始时间

Cia1b=Bia1b+T1，b，ia，n－ 1

//下一个零件的开始时间为上一个零件的结束时间

B(ia)'1b=Ciajb

End

For x=2∶m //第x道工序:

For i=1∶n(工件总数)

//C(ia)'xb为在机器Mxb上加工工件Jia前一个工件的结束时间

//Cia(x－1)(ax－1，ia/100)为工件 Jia上一道工序的结束时间，即两者都有空闲时才能加工

//ax－1，ia/100表示工件 Jia在第 x 道工序的加工机器。

End

End

Output:makespan=max［Ciam1，Ciam2，…，Ciamn］。

4 算例及结果分析

算例来自某车间实际算例。该车间有2类工件，第1类工件有3个，第2类工件有4个。工艺顺序为:粗车—精车—拉床—加工中心，每道工序并行机的数量分别为2，3，2，3。其中拉床为瓶颈设备。当瓶颈设备繁忙时，可以调换零件在拉床和加工中心的加工顺序。每个工件在每道工序上加工的时间已知，见表1。

表1 工件、工序、机器与加工时间表

采用仿真软件进行仿真，软件平台为:Windows 7操作系统。取基因移位操作概率为0．8，变异概率为0．05，种群规模为30，仿真代数为100。

当不考虑本文所提的约束松弛条件，只是按照传统的FFSS进行排程，所得结果如图3所示，其Makespan为25。当只考虑加工批量约束松弛时，所得结果如图4所示，其Makespan为22，比不考虑加工批量约束松弛调度Makespan缩短12%。

图3 传统FFSS的甘特图

图4 考虑加工批量约束松弛的甘特图

当只考虑瓶颈工艺顺序松弛时的调度结果如图5所示，其Makespan为22，比不考虑瓶颈工艺顺序松弛调度Makespan缩短12%。调整加工顺序的工件是零件2和零件3。

图5 考虑瓶颈工艺顺序松弛的甘特图

从图4、图5可知，考虑加工批量约束松弛和瓶颈工艺顺序松弛时，得到的调度结果更优，比不考虑约束松弛得到调度的Makespan缩短了12%。显而易见，根据现场工况调整部分约束，不仅可以缓解设备能力不足带来的生产压力，更能为生产变更或生产调整提供更多的选择余地。因此在实际的生产过程中，考虑约束松弛具有较强的实际意义。

5 结束语

本文立足企业生产实际，突破传统调度中假设满足机器唯一性和流水顺序不变等的约束，通过考虑加工批量约束松弛和瓶颈工序顺序松弛，得到了Makespan性能更优的调度方案。考虑约束松弛进行调度优化不仅缓解了设备能力不足带来的生产压力，更为生产调度管理人员实施调度提供了更多的选择，也为分析调度约束、提高调度性能提供了实用的分析工具。未来考虑多种混合约束松弛进行约束柔性流水调度研究，并将此研究推广到作业车间的调度研究中。

［1］ BRAH SA，HUNSUCKER JL．Branch and bound algorithm for the flow shop with multiple processors［J］．European Journal of Operational Research，1991，51(1):88 －99．

［2］ MOURSLIO，POCHET Y．A branch and bound algorithm for the hybrid flow shop［J］．International Journal of Production E-conomics，2000，64(13):113 －125．

［3］ SAWIK T．Integer programming approach to production scheduling for make to order manufacturing［J］．Mathematical and Computer Modeling，2005，41(1):99 －118．

［4］ WITTROCK R J．An adaptable scheduling algorithms for flexible flow lines［J］．Operations Research，1988，33(4):445 － 453．

［5］ LIU Z，XIE J，LIJ，et al．A heuristic for two stage no wait hybrid flow shop scheduling wit h a single machine in either stage［J］．Tsinghua Science and Technology，2003，8(1):43－ 48．

［6］ LEE GC，KIM Y D，CHOISW．Bottleneck focused scheduling for a hybrid flow shop［J］．International Journal of Production Research，2004，42(1):165 －181．

［7］ 王柏琳，李铁克．等待时间受限的置换流水车间调度启发式算法［J］．管理科学学报，2012，15(6):22 －32．

［8］ HALL N G，SRISKANDARAJAH C．A survey of machine scheduling problems with blocking and no － wait in process［J］．Operations Research，1996，44(3):510 －525．

［9］ 唐海波，叶春明，刘长平，等．基于知识进化粒子群算法的模糊交货期流水车间调度问题［J］．计算机集成制造系统，2012，18(4):807 －812．

［10］ 顾文斌，唐敦兵，郑堃，等．基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究［J］．机械工程学报，2012，48(14):177 －182．

［11］ 李茂军，朱陶业，童调生．单亲遗传算法与传统遗传算法的比较研究［J］．系统工程，2001(1):61－66．

［12］ 李茂军，童调生．单亲遗传算法在Flow－Shop问题中的应用［J］．系统工程与电子技术，2000，22(6):84－86．

［13］ 崔建双，李铁克，张文新．混合流水车间调度模型及其遗传算法［J］．北京科技大学学报，2005，27(5):624－626．