车间作业调度研究范文

《机械设计与制造工程杂志》2014年第六期

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所示。传统的调度问题是基于机器唯一性原则和流水顺序不变原则进行研究，但实际生产中，此约束存在一定程度的松弛:a．加工批量约束松弛。一台机器同一时刻只能加工一个或一批工件。而实际加工车间同一工序的每次加工批量并不相同，或者前后相邻工序间的加工批量也不尽相同。b．工艺顺序松弛。加工车间为了缓解瓶颈设备的压力，在允许工序超越的情况下，调换瓶颈工序和其相邻的后续工序的加工顺序，即存在加工顺序局部可调的现象。此问题与工艺路线可变的作业车间调度问题既有相似性又有很大的不同。工艺路线可变的作业车间调度问题指每个零件的加工工艺路线可能有几条，具体选择哪一条工艺路线要视机器的空闲情况和调度问题的目标而定;而该问题加工顺序只是局部调整，并不存在几条不一样的加工路线，即存在工序顺序松弛现象。本文所研究的问题是柔性流水车间调度问题中的一种特殊情况，即考虑加工批量约束松弛和瓶颈工序顺序松弛的新型柔性流水车间调度问题。

2数学模型

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

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

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。用此编码方式，得到此柔性flowshop调度问题的一个染色体为:该染色体第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基因移位算子基因移位操作是按一定的概率把一条染色体中的一个(或一些)子串中的基因依次后移，并把该子串的最后一个基因移到最前面的位置，移位是在同一条染色体中进行。基因移位的子串及其长3．4解码编码操作和遗传操作会得到不同的染色体，这些染色体必须利用解码技术才能被转化成各个机器上工件的实际加工顺序。本文解码算法的伪代码如下:

4算例及结果分析

算例来自某车间实际算例。该车间有2类工件，第1类工件有3个，第2类工件有4个。工艺顺序为:粗车—精车—拉床—加工中心，每道工序并行机的数量分别为2，3，2，3。其中拉床为瓶颈设备。当瓶颈设备繁忙时，可以调换零件在拉床和加工中心的加工顺序。每个工件在每道工序上加工的时间已知，见表1。采用仿真软件进行仿真，软件平台为:Win—dows7操作系统。取基因移位操作概率为0．8，变异概率为0．05，种群规模为30，仿真代数为100。当不考虑本文所提的约束松弛条件，只是按照传统的FFSS进行排程，所得结果如图3所示，其Makespan为25。当只考虑加工批量约束松弛时，所得结果如图4所示，其Makespan为22，比不考虑加工批量约束松弛调度Makespan缩短12%。当只考虑瓶颈工艺顺序松弛时的调度结果如图5所示，其Makespan为22，比不考虑瓶颈工艺顺序松弛调度Makespan缩短12%。调整加工顺序的工件是零件2和零件3。从图4、图5可知，考虑加工批量约束松弛和瓶颈工艺顺序松弛时，得到的调度结果更优，比不考虑约束松弛得到调度的Makespan缩短了12%。显而易见，根据现场工况调整部分约束，不仅可以缓解设备能力不足带来的生产压力，更能为生产变更或生产调整提供更多的选择余地。因此在实际的生产过程中，考虑约束松弛具有较强的实际意义。

5结束语

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

作者：张翠林王烁王军强单位：西安航空学院经济管理系西北工业大学生产与运作系统性能分析中心西北工业大学现代设计与集成制造技术教育部重点实验室