双资源批量生产柔性作业车间多目标调度方法

2015-04-14吴立云

计算机工程与应用 2015年1期

曾强，沈玲，任华，吴立云

1.河南理工大学能源科学与工程学院，河南焦作 454000

2.河南理工大学安全科学与工程学院，河南焦作 454000

1 引言

批量生产是机械工业的主要生产类型，据调查，我国多品种中、小批量生产的产值约占到机械工业总产值的75%～85%[1]。然而，我国批量生产企业的生产效率低下，主要表现在3个方面：（1）设备平均有效时间只有约25%[1]；（2）物料在流动过程中有高达95%的时间处于不增值的活动中（其中大部分时间处于等待活动中）[2-3]；（3）产品的生产周期长，库存成本高，库存周转率远远低于国外先进企业[2，4]。造成生产效率低下的一个主要原因在于生产调度多依赖经验进行，调度方案过于粗放。因此，有必要研究并提出一种有效的批量生产精细化调度方法以辅助生产管理。

双资源批量生产柔性作业车间多目标调度属于批量生产柔性作业车间调度问题之一。文中的双资源是指设备和人力。文中的精细化调度是指对调度问题考虑更精细使调度方案更接近实际应用，在调度方案的获取过程中应用一些精细化调度技术以充分缩短完工时间。这些精细化调度技术主要包括时间分离、平行作业、交叉作业、间隙挤压、人机作业匹配5个方面。时间分离是指将调整时间从工序总时间中分离出来，可使下道工序提前准备，从而可压缩一个调整时间[5-6]。平行作业指相同的产品同时在数台相同或相似的设备上加工[7]。针对批量生产方式，若将同一种产品划分成若干个加工子批（称为批量划分），允许同一种产品的不同加工子批在不同的设备上同时加工，即可实现平行作业。批量划分本身又是一个复杂的优化问题。文献[8]指出加工批量与生产周期存在U型关系，表明理论上存在最佳加工批量。批量划分一般应遵循如下3种原则：最小分批原则、等量分批原则和直接批量原则[5]，论文研究等量分批。批量划分与调度相互影响，对批量划分和调度的处理方式有两种：其一是分步策略，即先划分批量，再进行调度；其二是集成策略，即将批量划分与调度同时进行[9]，本文研究前者。交叉作业指一批制品在上道工序尚未加工完毕时，将已完成的部分制品转至下道工序开始加工[7]。对于批量生产，可考虑将加工子批分解成多个移动子批，生产过程中每加工一个或若干个移动子批就将其搬运至下道工序开始加工，从而实现同一加工子批前后工序的交叉。从生产组织形式上通常采用平顺移动方式。然而，平顺移动方式进一步增加了生产调度的难度。间隙挤压指对于工序的时间安排采用“见缝插针”的方式，在时间轴上从左到右依次搜索加工资源的空闲时间段，将工序安排在该资源的最早可行时间段[10]。这种工序安排方式有利于减少资源的等待时间，加快物料流动，从而提高生产效率。人机作业匹配是指工人、设备与工序应达到准确匹配，否则可能造成调度方案不可行。文献[11-14]均假设若工人能操作某设备，则能操作所有能在该设备上加工的工序，这与实际并不相符。实际生产中，工人往往能操作某设备上的部分工序而不是全部工序，不能简单地说该工人能或不能操作该设备。

基于以上分析，本文提出了一种双资源批量生产柔性作业车间多目标精细化调度方法。针对双资源批量生产柔性作业车间多目标调度问题特点，建立了一类以制造成本最低和完工时间最短为优化目标的双资源等量分批柔性作业车间调度多目标优化模型；提出了5种双资源批量生产柔性作业车间精细化调度技术；针对模型提出并设计了一种改进的NSGA II算法。

2 多目标调度优化模型

2.1 问题描述

车间调度人员需对N种按批量生产方式生产的产品在K台设备、R名工人中安排生产，产品i的加工过程由ni道工序组成。假设：（1）同一工序可选择不同的设备和工人加工，因设备性能、工人技术水平不同，加工时间和调整时间可不同；（2）工序在设备k上由工人r加工的调整时间和加工时间确定，加工子批的装卸时间计算在加工时间内；（3）加工子批按平顺移动方式移动，其移动时间可忽略；（4）加工子批具有相同优先级；（5）加工为非抢占式。要求：合理安排调度方案，在满足上述假设条件及一定约束条件下使制造成本最低、完工时间最短。

2.2 变量定义

为便于模型的描述，定义了如表1所示的变量。表1中，已知Qi、Li、Di、H、Bi、Gi的关系如下：

2.3 优化模型

以制造成本最低、完工时间最短为优化目标，建立一类柔性作业车间等量分批调度多目标优化模型。

（1）目标函数

其中，式（1）表示制造成本最小化，式（2）表示完工时间最小化。

表1 变量定义

（2）决策变量

影响两个优化目标的因素有产品加工批量A={A1，A2，…，AN}，产品移动批量D={D1，D2，…，DN}，设备，工人选择矩阵X和加工子批的加工顺序S。因变量多导致组合空间过大，为提高求解效率，现将问题加以适当简化，即将决策变量取为 X和S，而A和D则由调度人员根据经验和实际需要确定。

（3）约束条件其中，式（3）表示若Ji的工序j-1与j工序所用设备不同，则任意移动子批s的工序j必须在工序j-1完工后才能开始加工；式（4）表示若Ji的工序j-1与工序j所用设备相同，则工序j的第一移动子批下道工序必须在工序j-1全部完工后才能开始准备；式（5）表示任意工序的完工时刻与开始时刻之差不能小于工序总时间；式（6）表示同一设备k、工人r不能同时加工两个工序；式（7）表示某工序唯一由K台设备中的一台、R名工人中的一名独立完成。

3 精细化调度关键技术

本文提出的精细化调度技术如图1和表2所示。图1（a）表示将产品i等量分批得到3个加工子批J1、J2、J3，它们可以选择同种或相似设备和工人进行并行作业；图1（b）表示将加工子批Ji的工序j的总时间分成调整时间（黑色）和加工时间（白色），通过二者的分离可实现下道工序提前准备从而压缩一个调整时间；图1（c）表示通过平顺移动实现交叉作业从而进一步缩短完工时间；图1（d）表示采用“间隙挤压法”在时间轴上从左向右为加工子批Ji的工序j寻找设备k和工人r的共同空闲时间段将该工序插入，从而可减少设备和工人的“时间碎片”并缩短完工时间。表2为双资源人机作业匹配技术，此表表示加工子批Ji的工序j可在设备M3或设备M4上加工，若选择在设备M3上加工，则可行工人有W3和W5，对应的加工参数为 (Ctij33，Stij33，Pcij33，Psij33)和 (Ctij35，Stij35，Pcij35，Psij35)，若选择在设备M4上加工，则可行工人有W2和W4，对应的加工参数为(Ctij42，Stij42，Pcij42，Psij42)和 (Ctij44，Stij44，Pcij44，Psij44)。

图1 精细化调度技术

表2 双资源人机作业匹配技术

4 改进的NSGA II算法

针对模型特点，提出并设计了一种改进的NSGA II算法。

4.1 定义对象

按照文献[15-16]的方法，算法设计中采用面向对象技术来处理复杂的实体关系。在算法中定义了如图2所示的4类对象，其中，Mach（）为设备对象数组，Worker（）为设备对象数组，J为加工子批对象数组，Chr（）为染色体对象数组。各对象属性说明如表3（为便于编写算法，对属性采用了计算机语言取名，这些属性与多目标优化模型中的数学符号有所不同，但含义一致）。

图2 定义对象

表3 属性说明

4.2 算法流程

算法总体流程如图3[15-16]所示。

图3 算法流程图

4.3 获取参数

参数是调度算法进行运算的依据，算法中主要涉及的参数有产品参数（包括各产品产量、加工批量、加工子批数、工序数、移动批量、工艺流程），遗传算法参数（包括种群数popsize、交叉比例cr、变异比例mr、最大迭代次数maxgen）和设备时间状态参数。读取上述参数后，算法根据各产品产量、加工批量将各产品进行分批，得到从1开始依次增大的加工子批J(i)，i∈(1，H)，并对各加工子批J(i)的各属性进行赋值，以便于算法中对J(i)各属性进行调用；同理，算法将设备时间状态参数赋给Mach(i)，i∈(1，K)以备进行间隙挤压安排生产任务。

4.4 编码方式及种群初始化

如式（8）所示，Chr(i).R为n×14的数组（n为工序总数），第1～7列为编码所用，第8～14列为解码所用。其中，第1列为工序号（从1开始依次增1至n），第2列为加工子批号（1～H中的整数，各整数出现的次数为该加工子批对应的工序数），第3列为各加工子批出现的次数，第4列为各工序选择的可行设备索引号，第5列为各工序选择的设备编号，第6列为各工序选择的可行工人索引号，第7列为各工序选择的工人编号。

式（8）所示的染色体编码的获得过程如下：（1）为Chr(i).R的第1列赋从1～n的工序号；（2）根据J(j).gxs，j∈(1，H)生成合法的加工顺序编码赋给Chr(i).R的第2列；（3）算法判断第2列各位上的数字分别出现的序号赋给Chr(i).R的第3列；（4）令j=1，2，…，n，对每个j产生1～J(Chr(i).R(j，2)).gx(Chr(i).R(j，3)).kxsbs的随机整数赋给Chr(i).R的第j行第4列；（5）令j=1，2，…，n，对每个j将J(Chr(i).R(j，2)).gx(Chr(i).R(j，3)).kxsbh(chr(i).R(j，4))赋给Chr(i).R的第j行第5列；（6）令j=1，2，…，n，对每个j，产生1～J(Chr(i).R(j，2)).gx(Chr(i).R(j，3)).kxsb(Chr(i).R(j，4)).kxgrh的随机整数赋给Chr(i).R的第j行第6列；（7）令j=1，2，…，n，对每个j将J(Chr(i).R(j，2)).gx(Chr(i).R(j，3)).kxsb(chr(i).R(j，4)).kxgrh(Chr(i).R(j，6)) 赋给Chr(i).R的第j行的第7列。可见，通过这种方式获得染色体编码保证了可行性。

令i=1，2，…，popsize，对Chr(i)，按照上述过程对Chr(i).R赋值，重定义Chr(i).O(2)，2为目标数，从而完成种群初始化。

4.5 交叉操作

仅针对加工顺序采用置换交叉方式进行交叉[17]。具体交叉操作如下：为保证不破坏同一加工子批各工序之间的先后顺序，交叉过程固定一个父体加工顺序编码中某个加工子批号不动，将另一父体加工顺序编码中除该加工子批号以外的加工子批号从上到下依次填入本父体加工顺序编码中，同时将对应的可行设备索引号、可行设备号、可行工人索引号和可行工人号一同交换。

4.6 变异操作

分别针对加工顺序、加工设备和工人采用分段变异方式进行变异[13]。具体变异方式操作如下：

（1）加工顺序变异

对Chr(i)，产生一个1～n之间的随机整数mp，以mp为基准在Chr(i).R的第2列向上向下分别寻找与Chr(i).R(mp，2)相同的位置，设为k1、k2且k1＜k2（若向上未找到则令k1=1，若向下未找到令k2=n），再产生一个k1+1～k2的随机整数j，将Chr(i).R(mp，2)、Chr(i).R(mp，4)、Chr(i).R(mp，5)、Chr(i).R(mp，6)、Chr(i).R(mp，7)移动到j行之前。

（2）设备变异

对Chr(i)，产生一个1～n之间的随机整数mp，再产生 1～J(Chr(i).R(mp，2)).gx(Chr(i).R(mp，3)).kxsbs的随机整数赋给Chr(i).R第mp行第4列，同时将J(Chr(i).R(mp，2)).gx(Chr(i).R(mp，3)).kxsbh(chr(i).R(mp，4))赋给Chr(i).R的第mp行第5列。产生1～J(Chr(i).R(mp，2)).gx(Chr(i).R(mp，3)).kxsb(Chr(i).R(mp，4)).kxgrs的随机整数赋给Chr(i).R第mp行第6列，同时将J(Chr(i).R(mp，2)).gx(Chr(i).R(mp，3)).kxsb(Chr(i).R(mp，4)).kxgrh(chr(i).R(mp，6))赋给Chr(i).R的第mp行第7列。

（3）工人变异

对Chr(i)，产生一个1～n之间的随机整数mp，产生1～J(Chr(i).R(mp，2)).gx(Chr(i).R(mp，3)).kxsb(Chr(i).R(mp，4)).kxgrs的随机整数赋给Chr(i).R第mp行第6列，同时将J(Chr(i).R(mp，2)).gx(Chr(i).R(mp，3)).kxsb(Chr(i).R(mp，4)).kxgrh(chr(i).R(mp，6))赋给Chr(i).R的第mp行第7列。

4.7 解码操作

解码操作的目的是计算Chr(i).R的第8～14列值，其中第8列为调整时间，第9列为加工时间，第10列为开始准备时刻，第11列为开始加工时刻，第12列为完工时刻，第13列为调整成本，第14列为加工成本。解码思路如下：从第1道工序开始，根据Chr(i).R的第1～7列值，可以从J数组中读取相应的Ct、St、Pc、Ps值，在安排各工序的起始时刻时考虑平顺移动，即按照平顺移动方式找到某工序的最早开始加工时刻和最早完工时刻，然后根据Mach数组采用“间隙挤压”技术在时间轴上从上到下寻找对应设备号和工人号的共同空闲时间段，若该空闲时间段能容纳该工序，则将该工序以最早开始加工时刻和最早完工时刻安排在该空闲时间段，同时更新相应设备和工人的空闲时间段，否则继续寻找下一个共同的空闲时间段。在得到R的第8～14列之后，将第12列之最大值赋给Chr(i).O(1)，将Chr(i).R的第13、14列之和赋给Chr(i).O(2)，至此解码结束。

5 案例分析

以Excel 2007及其VBA为编程工具实现了上述算法，并通过重庆某船舶配套企业某机械加工车间的应用案例对本文方法进行了有效性验证。该车间在某调度周期内计划由10台数控设备（编号为D001～D010），7名工人（编号为W001～W007）来完成4种产品(P1～P4)的生产。产品生产量Q1～Q4分别为120件、100件、80件、100件。各产品加工工艺参数如表4，表中Ct为工序单件加工时间（单位为h），St为加工子批的调整时间（单位为h），Pc为单位时间加工成本（单位为元/h），Ps为单位时间调整成本（单位为元/h）。从表4可见：（1）工序总时间被分离成准备时间St和加工时间Ct；（2）因设备为数控设备，由不同的工人操作时单件加工时间相等，但因工人熟练程度和水平不同，导致同一工序由同一设备不同工人加工时的调整时间不同；（3）同一工序的单位时间加工成本和单位时间调整成本因设备和工人不同而有所差异；（4）设备、工人和工序进行了更细致的匹配，因工序技术要求不同，某工人能操作某设备并不代表能操作由该设备承担的所有工序，具体如何匹配根据实际情况而定。取popsize=50，maxgen=200，cr=0.6，mr=0.4。

表4 产品工艺参数

图4 加工批量变化对Pareto解集的影响

为验证等量分批对生产效率的影响，建立了4种典型分批方案：（1）加工批量120-100-80-100；（2）加工批量60-50-40-50；（3）加工批量 30-25-20-25；（4）加工批量20-20-20-20。取移动批量与加工批量相等。分别对以上4种方案运用相同的工艺参数和遗传参数进行进化计算，将得到如图4所示的Pareto图。从图4可得到如下两个结论：（1）在一定范围内，加工批量越小，完工时间越短，但加工批量不宜过小；（2）加工批量越小，制造成本越高。产生这种调度结果的原因是，在一定范围内，随着加工批量减小，加工子批数增加，使同一产品可分成更多的加工子进行并行作业，这种并行作业对完工时间带来的正效应大于因调整时间增加对完工时间带来的负效应，从而使完工时间得以缩短；若加工批量过小，并行作业对完工时间带来的正效应可能小于调整时间增加量对完工时间带来的负效应，从而使完工时间得以延长；从制造成本的角度来看，加工批量越小，加工子批数增加，调整次数及调整成本必然上升，使制造成本上升。从图4可见，方案（2）是比较合理的分批方案。

为进一步验证平顺移动对生产效率的影响，取加工批量60-50-40-50，建立3种移动分批方案：（1）移动批量60-50-40-50；（2）移动批量 15-10-10-10；（3）移动批量5-5-5-5。分别对以上3种方案运用相同的工艺参数和遗传参数进行进化计算，得到如图5所示的Pareto图。从图5可得结论：通过将加工批量分成移动批量进行平顺移动可使调度方案的完工时间缩短，但移动批量也不宜过小，移动批量过小，移动次数增加，不仅给物料搬运人员造成较大工作量，而且完工时间的缩短会不太明显。

图5 移动批量变化对Pareto解集的影响

图6 某Pareto解对应的加工子批甘特图

图7 某Pareto解对应的设备甘特图

图8 某Pareto解对应的工人甘特图

图6～图8分别是某Pareto解（完工时间为149.5 h，制造成本为48 093.1元）对应的加工子批甘特图、设备甘特图和工人甘特图。图6中每一行横道代表一个加工子批的生产作业计划，从图6中可见，4种产品被分成8个加工子批，以左上角的横道为例说明其中文字和数字的含义，符号“s”代表调整时间，图中用绿色绘出，符号“r”代表工序，1.1.1代表产品1的第1个加工子批的第1道工序；文字“D008”代表该工序被安排在设备D008上加工；文字“W005”代表该工序由工人W005操作；46.6～85.6代表从46.6 h开始该工序的加工到85.6 h完成该工序的加工。从图6可见部分工序加工时间段产生一定程度的重叠，例如r1.1.1（46.6～85.6）和r1.1.2（78.2～110.6）发生了重叠，产生这种重叠现象的原因正是因为在解码过程中采用了平顺移动的效果，通过平顺移动，同一加工子批的下道工序可提前开始加工，从而产生时间上的重叠。图7中每一行横道代表一台设备的生产作业计划，从上到下分别为D001～D010的生产作业计划；图8中每一行横道代表一名工人的生产作业计划，从上到下分别为W001～W007的生产作业计划。