杜 轩，廖天怡，李宝万
(1.三峡大学 机械与动力学院，宜昌 443002；
2.三峡大学水电机械设备设计与维护湖北省重点实验室，宜昌 443002)
J钢琴制造公司是国内一家大型的钢琴制造企业，生产八大系列的立、卧式钢琴，具备年产50000台的生产能力。在实际生产过程中，钢琴部件产品种类多，数量大，而且不同产品之间工艺具有很大的差异，为缩短产品生产周期、提高生产效率、降低生产成本,研究钢琴生产的批量调度问题具有很好的理论和实际应用意义。
批量生产调度问题除了考虑加工资源的分配和加工排序问题，还要考虑生产批量的优化，是一个典型的NP难题，许多学者针对其进行了研究，巴黎[1]对批量装配的柔性作业车间问题进行建模，运用了粒子群算法求解装配车间批量调度问题，但是未考虑在车间实际生产中，调整时间对批量调度的影响。周超[2]针对柔性作业车间采用遗传算法求解等批量调度问题,虽然证明了等量分批调度方案优于整体调度方案，但是并没有进一步考虑非等量分批的情况。王海燕[3]等人根据车间机器负荷大小，提出预划分子批方案，结合自适应的差分进化算法求解多资源车间调度问题。为批量调度问题提供了一种很好的子批划分思路。曾垂飞[4]针对装配车间批量调度问题，比较整体集成优化策略、分层迭代优策略以及双层进化策略下的等量分批方案和不等量分批方案,证明了不等量分批的调度方案优于等量分批的调度方案,但在算法计算效率和收敛速度仍有改进空间。鞠全勇［5］等人以每个工件作为一个批量，在进化过程中把排序相邻的同类工件合并为一个子批次，将粒子群算法和遗传算法相结合，提出批量生产优化调度策略，该方法能有效解决小批量问题，但在问题规模增大时，会对求解效率产生影响。
本文以钢琴生产中的木壳生产区作为研究对象，结合车间调度生产实际，建立了包含批量优化的钢琴生产批量调度模型，基于不等量分批策略，利用多色集合围道矩阵建立了描述工件批量、工序以及机器之间约束关系的约束模型；
提出了基于模型约束的遗传算法。在遗传操作过程中，结合约束模型，完成交叉、变异以及适应度值计算等步骤。在搜索的过程中，利用约束模型保证在有效的解空间中进行搜索，以此提高搜索效率，降低算法复杂度，最后将本文提出算法的优化结果与其他算法的优化结果及实际生产数据进行对比和分析，验证模型和算法的有效性和可行性。
1.1 钢琴生产外壳部件批量调度问题描述
以J钢琴生产公司为例，主要有木壳生产区、音板生产区、马克生产区以及钢琴装配区四个车间，钢琴木壳生产区主要以生产钢琴外壳部件为主,包括门边框、踏瓣档、琴脚、琴凳等钢琴木壳部件。钢琴根据尺寸、工艺、加工操作的不同，产品品种可划分为200多种型号，而同一型号的钢琴大概需要与其配对的外壳部件高达30种左右，木壳生产区的木壳部件种类繁多，属于典型的多品种、小批量生产模式，而车间生产管理主要采取整批调度的生产方式，导致车间机器利用率低，从而出现产品生产周期长，交货延迟的现象，成为企业的瓶颈生产区。图1为木壳生产区外壳加工过程的示意图。
图1 钢琴外壳加工过程示意图
木壳车间的批量调度问题具体可以描述为：有N种钢琴木壳工件（以下简称工件）的需要在M台机器上完成精修、铣型、打眼、砂光等工序的加工，每种工件的生产批量为Q，各种工件的加工工序有一定差异，且每个工序的加工时间不同，根据生产需要,每种工件能够分成一个或者若干个子批加工。批量调度主要解决的问题是：优化各子批的工件数量，并为各子批工件安排加工机器，同时确定每台机器上各子批工件的最优加工顺序，在满足各种约束的条件下使全部工件的完工时间最短。根据实际情况，在钢琴生产批量调度中应满足以下假设：
1）在零时刻，所有不同类型的工件均可以在合适的机器上进行加工；
2）为准确计算工件的完工时间，除了工件在机器上的加工时间，还应考虑工件开始加工前的准备时间。而同一工件的不同批次如在同一机器上加工顺序相邻时，后一批次的准备时间可以不考虑。
3）每台机器在同一时刻只能加工一个工件。
4）同一批次的工件一旦进行加工便不能中断。
5）任何一个子批只能在本批次全部工件的前一道工序完成后,才能进入后一道工序的加工。
1.2 数学模型
基于上述假设，以工件完工时间最短为优化目标，建立木壳生产区批量调度模型：
式中：
i——工件编号，i=1,2,......N；
j——工序编号；
k——工件批次号，k=1,2,......,BNi；
m——机器编号，m=1,2,......,M；
Cijkm——工件i的第k个子批的第j道工序在机器m上的完工时间；
BNi——工件i划分的子批数目；
BNmin——工件i划分的最小子批数目；
BNmax——工件i划分的最大子批数；
DMi——工件i初始加工批量；
BDik——工件i的第k个子批批量大小；
δikjm——为0-1变量；
minVm——机器最小加工批量；
maxVm——机器最大加工批量；
CMijkm——工件i的第k个子批的第j道工序在机器m上的完工时间；
SMijkm——工件i的第k个子批的第j道工序在机器m上的开始加工时间；
rm——0-1变量；
QTijm——工件i第j道工序在机器m上的调整时间；
tijm——工件i的第j道工序在机器m上的单件加工时间；
δikjm——工件i第k个子批第j道工序是否在机器m上加工。
式(1)把所有工件完工时间最小作为优化目标，式(2)～式(8)描述了约束条件。式(2)表示子批约束，要求子批数目必满足须范围约束，而子批范围可根据工件加工批量和并行机器数目设定；
式(3)表示同一工件的各子批批量总和为工件的加工量；
式(4)表示工件各子批的批量必须满足机器的批量加工能力范围；
式(5)表示工件i第k批的第j个工序在机器m上加工的约束关系；
式(6)表示当机器m上待加工子批次任务和前一子批次任务的工件号和工序号都相同即rm＝0时，否则为1。该批次调整时间可忽略不计；
式(7)表示工序约束,工件i的第k个子批在m机器上的完工时间必须大于下一个工序的开始时间。式(8)表示任何一台机器必须在上一个子批全部完成后才可以进行下一个子批次的加工。
2.1 多色集合理论
多色集合理论一种将系统理论和信息处理理论相结合的数学工具,它的核心思想是通过对不同的对象（产品、设计过程、工艺过程和生产系统等）采用相同的数学模型进行仿真。描绘元素间的层次结构和复杂关系，通过集合层和逻辑层对信息进行组织和处理。通过数量层解决低层次的数量大小问题。多色集合理论对问题形式化研究有明显的优势,被广泛应用于产品概念设计建模、零件制造工艺建模、产品装配工艺建模和公差信息建模等领域[6]。
在多色集合中，元素和集合都能够被同时涂上一些不同颜色来表示研究对象和元素的性质。用集合和元素着色的关系描述不同对象之间的逻辑关系和数量约束关系。常常采用“围道”的概念代替‘颜色’来抽象和概括现实系统中对象性质、属性和特征[7]。
2.2 围道矩阵约束模型
以4×6的作业车间为例，假设每种工件初始批量为40。每种工件最大可分成3个子批，其具体加工时间如表1所示。
表1 零件加工时间表
在上述批量调度问题中,存在以下几种约束关系：
1）工件批量可以划分为多个批量不等的子批进行加工，但同一工件的子批批量必须满足批量总和不变的数量约束关系；
2）工件在加工的过程中，工序之间存在先后加工的顺序约束关系；
3）工序在加工机器的选择上，存在约束关系；
基于多色集合围道矩阵的约束模型可以很好地描述子批批量、工序以及机器之间的逻辑和数量关系，在逻辑层描述子批加工顺序之间的约束关系；
在数量层描述子批批量大小之间的约束关系。如图2和图3所示。
图3 数值围道矩阵
图2中F1～F12表示工序；
M1～M6表示工件加工过程中能够选择的机器；
O1～O12表示在机器上加工的12个子批工件，为了加以区别工件子批，分别用数字1表示子批标号。
图2 逻辑围道矩阵
在约束模型中，逻辑层的[A×F(a)]描述了不同子批与加工工序以及加工工序与机器之间的对应关系。可以确定子批加工工序以及可加工工序的机器。例如：
描述了拥有工序1的子批为编号为1,2,3的子批，而且工序1能够在机器M1，M2，M3上的任意一台机器上完成加工。
数值层的约束模型[A×F(a)]进一步描述了子批之间以及工序与机器之间的数量层约束关系。可以确定工件的批量值以及工序在机器上的单件加工时间，例如：
描述了子批1,2,3的批量值分别为10,17,13；
工序1在机器，上单件加工时间为2,3,4个单位加工时间。
3.1 基于多色集合约束模型的遗传算法流程
遗传算法本质上是采用的无约束搜索，因此在遗传搜索中容易产生大量的无效解，从而影响算法的求解效率。针对批量调度这个复杂的约束优化问题，本文将多色集合约束模型与遗传算法相结合，基于多色集合模型约束的遗传算法(CMGA)流程图如图4所示。
图4 基于多色集合模型约束的遗传算法流程图
3.2 基于约束模型的编码
染色体采用四元组矩阵形式来描述，矩阵染色体的每个基因由子批值、工序值、批量值以及机器值的四元组构成。初始化时，基因中的子批值和工序值可以通过搜索约束模型的逻辑矩阵确定，批量值在初始化时随机产生，但必须满足式(3)和式(4)的约束关系,机器值为子批工序可选择的加工机器,也可以通过搜索约束模型的逻辑围道矩阵获得。假定在某次分批调度问题中，有2种工件，初始批量为40,工件均划分为3个子批。1～3为工件1的三个子批编号，4～6为工件2的三个子批编号，则为该问题的染色体矩阵编码可以用图5来表示。四元组基因在染色体矩阵中的先后位置表示该基因的子批工序的排序，每个基因的批量值和机器值描述了子批批量和加工该工序的机器。
图5 矩阵编码染色体
3.3 基于约束模型的解码
解码时，由于采用四元组染色体矩阵的编码方式，因此可以直观、简明的读取子批工序的排序信息、子批批量信息以及可加工该道工序的的机器信息。为了避免无效解的产生，采用基于约束模型的解码方式,其步骤如下：
步骤1：搜索约束模型的逻辑矩阵，挑出各行中的第一个不为零的子批工序，由于子批工序在逻辑矩阵中是按先后顺序排列，这样保证了同一子批每个工序之间的先后关系约束；
步骤2：在四元组染色体矩阵中，找出包含步骤1所挑出的子批工序的基因的列下标，选择列下标最小的基因，并读取基因上的子批值和工序值，作为第一个加工工序；
步骤3：将第步骤2中选出的子批值和工序值，在逻辑矩阵中置换成零；
步骤4：重复上述步骤，直至所有矩阵染色体中的基因全部取出为止。
3.4 选择操作
CMGA采用精英保留策略与轮盘赌相结合的方法，轮盘赌用来随机选择参加遗传操作的个体，保证个体的多样性。精英保留策略用于从所有新生成的个体中选择优良个体构造下一代种群，保证算法的收敛性。
3.5 交叉操作
矩阵染色体包含了批量划分、加工任务分配以及子批排序的信息。CMGA采用顺序交叉(OX)的方式。由于四元组基因的子批值和工序值表示子批的加工顺序，因此这里看成一个整体进行变换。四元组基因中的子批值和工序值由约束模型的逻辑矩阵唯一确定，采用顺序交叉的方式，不仅保证了基因值的唯一性，而且还能将父代优良基因片段遗传到下一代。而基因位的机器值的变叉，通过交换父代的染色体矩阵中含有相同子批值和工序值的基因位上的机器值，即完成机器值的交叉操作。但是四元组基因的批量值在经过OX交叉后，会产生溢出值或者缺失值，因此需要进行修复，这里结合约束模型的数值矩阵进行基因批量值的修复。其具体步骤如下：
步骤1：搜索交叉后的子代染色体，计算第1个工件第1个工序的所有子批批量和；
步骤2：搜索约束模型的数值围道矩阵，将步骤1计算出的批量总和与数值矩阵中父代染色体工件1的子批批量总和作比较，如果两者不等，则需要对子代中基因位的批量值进行修复,修复的过程中，交叉范围内的子批批量值不变，修改在交叉范围外的子批批量值,使其重新满足批量划分约束；
反之则无需修改批量值；
步骤3：将同一子批其他工序的批量值更改为修复后的数值；
步骤4：按照步骤1至步骤3的操作顺序，依次对染色体矩阵中后续工件的基因值进行修复，直至所有变换后的子代染色体基因的批量值全部被修复为止。
3.6 变异操作
CMGA的变异操作需要对加工顺序、加工机器及子批批量进行修改，因此采用了两基因位交换和单点基因位变异相结合的方法。
1）交换变异
交换变异通过交换两个基因的位置实现批次排序信息的变换,对应的机器和子批批量信息不变，变异后的染色体对应一个有效解，无需对其进行修复。
2）单点变异
单点变异，通过修改一个基因值的机器及子批批量信息产生新的染色体，需要通过搜索约束矩阵选择合适的机器，以及修复子批批量值以保证新个体的有效。
变异过程如下：
（1）子批批量变异。以图5矩阵部分基因片段为例,假设随机选择第5个基因为变异点，对应的基因值为（2,1,10,3），表示工件1中第2个子批的第1个工序在第3台机器上加工，加工批量为10。假定其批量值突变为12，如图6(a)所示。
然后，将该子批的批量全部修改，如图6(b)所示。
其次，通过搜索图5染色体中工件1不同子批的批量总和为42，不满足约束矩阵中的加工批量值约束（40），需要进行修复。算法随机生成工件1另外两个子批的批量为11、17，保证批量和为40，如图6(c)所示。
最后，将同一子批其他工序的批量值更改为修复后的数值，如图6(d)所示。
图6 批量值修复
（2）机器值变异。以图5矩阵部分基因片段为例，假设随机选择第4个基因为变异点，对应的基因值（1,2,15,2），表示工件1中第1个子批的第2个工序在第2台机器上加工，如图7(a)所示。通过搜索约束模型的逻辑矩阵中能加工该工序的机器,如图2中，可以加工该工序的机器有（2,4,5），随机选择一个值替换当前基因位的机器值即可。假定某次变异选择的“4”，如图7(b)所示。
图7 机器值变异示意图
3.7 适应度值计算
每一个染色体矩阵解码后均为一个可行调度方案，采用四元组染色体矩阵编码方式，解码后可以直观读取工序加工顺序信息、批量划分信息以及批量加工任务分配信息。将调整时间考虑到适应度值的计算当中，根据先到先加工规则的调度规则，通过搜索约束模型的数值矩阵，读取子批工序单件加工时间，乘以对应子批批量值，便可计算出子批的完工时间，能够快速的完成适应度值的计算，大大简化了计算复杂度。
为了验证算法的性能，采用文献[2]中的算例进行测试说明。其中，每种工件初始批量为8，加工数据具体数据如表2所示。图中均为单件加工时间。
表2 4×6作业车间工件加工表
针对此算例，采用本文提出的基于约束模型的遗传算法求解该问题，设定最小加工批量为1，交叉率Pc=0.85，变异率Pm=0.1，种群大小为50。求得的整体调度、等量分批调度以及不等量分批调度工件最优批量划分方案结果如表3所示，对应最优解甘特图如图8、图9和图10所示，其中图8最优生产周期为141，图9为103，图10为101。
图8 整体分批策略最优甘特图
图9 等量分批策略最优甘特图
图10 不等量分批策略最优甘特图
表3 CMGA算法最优批量划分方案
针对此算例，还将本文算法的计算结果与文献[2]和文献[3]的计算结果对比如表4所示。
表4 计算结果对比
计算结果表明，批量调度的生产周期明显优于整体调度,不等量分批调度的生产周期要小于等量分批调度的结果。本文的模型中考虑了调整时间，调度结果，更加合理。从图8～图10的显示结果可以看出，批量调度使得机器空闲时间和完工时间明显缩短。由于约束模型与GA的结合，虽然不等量分批调度问题更加复杂，但是求解效率得到明显提升。文献[3]经过500次迭代，得到整体调度的优化结果，而本文的CMGA只需50代，即可得到相同的优化结果。即使在考虑批量优化的情况下，问题复杂度增加，CMGA也能在较短的时间内得到满意的优化结果。
为了进一步验证算法的有效性，以J钢琴公司木壳车间实际加工数据，对本文提出的批量调度方法进行了验证。加工机器信息表如表5所示，工件工序实际加工时间如表6所示。工件初始加工批量单位为件，单件加工时间单位为min。
表5 机器信息
表6 工件加工信息表
采用本文提出的基于约束模型的遗传算法算法求解6×8钢琴外壳部件生产车间实例，算法参数设置为：迭代次数为500次，种群规模为50，交叉变异概率分别为0.85和0.1，运行20次，得到的最优批量划分结果如表7所示，所对应的甘特图如11所示。
表7 6×8规模车间实例最优分批方案
图11 6×8实例最优甘特图
针对6×8钢琴木壳生产车间调度实例，当前车间实际生产周期为2340min，通过本文提出的算法求出的最优生产周期为1930min，效率提高了21.2%。
本文通过分析J钢琴公司外壳生产车间批量调度问题，以完工时间为优化目标。考虑车间工序约束、机器约束以及实际加工批量约束，并且考虑了实际生产过程中的调整时间，建立批量调度问题模型。提出一种四元组基因值的矩阵方式编码，将多色集合约束模型与遗传搜索相结合，求解钢琴批量调度问题，对比整体调度策略、等量分批策略和不等量分批策略的优化结果，显示出采用不等量分批策略更有利于减少机器的空闲，能有效缩短完工时间，从而提高生产效率。并将模型与算法应用于钢琴制造企业实际调度问题中，获得了较好的结果，进一步验证了本文提出的模型和算法的可行性和有效性。
猜你喜欢 批量工序工件 120t转炉降低工序能耗生产实践昆钢科技(2022年2期)2022-07-08批量提交在配置分发中的应用科学家(2021年24期)2021-04-25曲轴线工件划伤问题改进研究装备制造技术(2020年11期)2021-01-26大理石大板生产修补工序详解(二)石材(2020年4期)2020-05-25土建工程中关键工序的技术质量控制建材发展导向(2019年10期)2019-08-24考虑非线性误差的五轴工件安装位置优化制造技术与机床(2019年7期)2019-07-22三坐标在工件测绘中的应用技巧现代机械(2018年1期)2018-04-17基于VBA井斜数据批量校正方法录井工程(2017年4期)2017-03-16人机工程仿真技术在车门装焊工序中的应用工程建设与设计(2016年1期)2016-02-27在数控车床上批量钻铰孔类工件的实践制造技术与机床(2015年10期)2015-04-09