面向智能工业的柔性装配批量调度优化策略

高 勃，孙嘉玉，李学汉，赵宏军，王 颖

（1.北京交通大学计算机与信息技术学院，北京 100044；2.北京交通大学电子信息工程学院，北京 100044；3.北京机械工业自动化研究所有限公司，北京 100120）

0 引言

智能制造全流程[1]中的多品种批量柔性生产作业过程[2,3]涉及多种产品[4～10]，每种产品又可以分为若干个调度子批进行加工和生产，每个子批的生产需要多个工艺流程，每个工艺流程可以由多条生产线来完成，因此如何划分子批，并且为每个子批选取合理的加工路线是需要研究的重要决策问题[11～13]。生产总量一定时，批量过小会导致生产线调整时间以及工件搬运时间增加，并且子批数过多使得优化算法的搜索空间增大，算法开销过高。而当批量过大时，同一子批当前工艺流程所需时间变长，造成后续工艺的生产线处于空闲等待的时间过长，生产效率降低。因此本文研究适当的分批策略以及排产顺序和生产线选择的问题，以有效降低生产线不必要的空闲时间，降低算法的计算复杂度，缩短所需的生产时间[8,14～18]。

1 多品种批量柔性生产调度问题建模

1.1 问题描述

以图1所示的芯体某线为例，说明多品种批量柔性生产调度问题。该芯体总线包含三段工艺流程，分别为预装、钎焊和总成，分别包括四条、一条和两条生产线。预计生产的产品类型有I种，生产线的产能及其与产品类型的匹配关系如表1所示。

表1 生产线产能及其与产品品种的关系

图1 芯体某线示意图

在生产过程中产品之间没有优先级之分，但是每种产品都有确定的加工工艺次序，在相应工艺流程加工时，可根据表1选择加工每个子批的生产线。因此整个生产调度流程如图2所示，即根据给定的每种产品的订单需求以及生产线的情况，实现如下的调度任务：结合订单情况，通过优化算法给出每种产品的子批数和每个子批的批量，并将所有子批进行排序，同时为每一个子批选择合适的生产线以及在每条生产线上的开始时间，最终使得完成生产任务所需要的生产时间最短。

图2 生产调度流程示意图

决策时需满足以下约束：1）每种产品都按照预装、钎焊和总成的顺序依次加工；2）每个子批的任一工件的任一工艺流程不能被中断；3）同一子批的每个工件的上一段工艺加工结束才能开始下一段工艺；4）任一子批一旦选定生产线进行加工，加工时间则确定；5）决策结果需满足表1中生产线与产品类型的对应关系以及产能限制。

1.2 数学模型

在数学建模过程中使用到的变量如表2所示。

表2 变量定义表

表2 （续）

进而可以将多品种批量柔性生产的调度问题，建立如下的数学模型：

式(1)是调度优化的目标函数，通过比较不同的方案下所有订单任务加工结束的时间，选择时间最短的方案作为最优的分批调度结果。式(2)中每种产品的每个子批完成最后一段工艺流程时叫做一个子批加工完成；式 (3)表示每个子批的所有工件加工完成叫做子批加工结束；式(4)表示对每种产品的每一个子批的每一个流程有且仅有一条生产线进行生产即可；式(5)表示当两个不同的子批选择同一条生产线进行生产时，需等前一个子批加工结束才能进行下一个子批的生产；式(6)表示生产线的产能限制。

2 基于模拟退火算法的子批划分方案

先进行子批划分的求解，目标是确定每种产品的子批数以及批量。

采用不等批量等分批的情况，具体来说，当每种产品的目标生产量不同时，不同产品划分的子批数是不相同的，但是对于每一种产品都采用等分批的方式，即同一种产品的每一个子批大小相等。因此，每种产品子批数最小值为1，即整批生产，子批数的最大值为Xi，即每一个工件作为一个子批，其他可能的子批数是Xi的约数，然后将产品i进行等量分批。假设Xi=10，可以分为Qi={1，2，5，10}批，则每个子批包含的工件数位Pi={10，5，2，1}。对于多种产品来说，最终的分批情况是从每一种产品的可能分批集合中取出一个值组成最终的分批结果，例如产品j的总量为Xj=15，则Qj={1，3，5，15}，那么同时加工产品i和产品j时可能的分批方案有4×4=16种。随着生产产品种类的增多以及产品总量的增加，可选分批方案的组合数是非常大的，因此采用了模拟退火算法进行分批方案的搜索。

具体来说，该算法的搜索空间是所有可能存在的分批策略，每一个策略可以表示成{Q1，Q2…，Qi，…，QI}。第k次迭代时，当前的策略表示成Sk，当前最优的策略表示成S0，同时f（Sk）和f（S0）表示对应分批策略通过生产排产方案能够获得的最大适应度值，具体计算方法将会在下一节中给出，且有f（Sk）＜f（S0）；对于另外一个策略Sm来说，如果f（Sm）＞f（S0），那么Sm=S0；否则，当f（Sm）＞f（Sk）的时候，那么Sk+1=Sm；若f（Sm）＜f（Sk），那么根据下式的接受概率使得Sk+1=Sm，相当于以概率1-PSA，舍弃Sm，意味着与当前分批方案Sk差值越小的方案被接受为下一次迭代策略的概率越大，遵循了择优的原则。需要说明的是，为了加速搜索的过程，Sm的产生是从Sk的领域中随机选取的。邻域意味着两个策略只有其中一种产品的子批数目不同，如{1，3}的邻域包含{1，1}，{1，5}，{3，5}等，但是不包括{2，5}，{2，1}等。

3 基于遗传算法的生产排产方案

3.1 编码方法

结合批量柔性生产的特点，采用基于批量的染色体和基于子批的染色体相结合的编码方式。基于批量的染色体用于给出每种产品采用的子批划分方式，子批数以及各个子批的批量大小。

基于子批染色体采用矩阵编码方法，第一行是工艺编码层，第二行是生产线编码层，第三行是加工时间编码层。其中工艺编码与生产线编码均为显性基因，参与交叉和变异操作，加工时间编码为隐性基因，不需要参与交叉、变异，但是需要根据交叉变异的结果进行重新编码。

工艺编码层采用基于子批的编码方式，即每一个基因都由子批编号表示，同一子批的不同工艺段都由相同的子批编号表示，这些相同编号出现的次序就代表该子批的工艺进行顺序。其中子批编号采用产品类型和子批号配对的形式，即[类型，序号]，如[1，5]表示类型为1的第1个子批。一共有I类产品，每种产品需要生产Qi批，每个批次都经过N段工艺，那么第一行含有个基因，其中有N个重复的基因按照出现的先后顺序分别代表对应子批的工艺流程1到N，保证生成染色体的有效性。

生产线编码层和加工时间编码层都采用基于整数的编码方式。生产线码由生产线编号组成，根据工艺编码层的基因随机选择对应工艺段的可选生产线，将生产线编号填入生产线编码层对应位置，使得生成的生产线编码均为有效编码。加工时间码则根据相应的批量染色体，工艺码和生产线码计算得到。

3.2 解码方法

解码操作与编码操作的过程是相逆的，解码操作是将染色体中每个基因携带的子批加工信息转化为子批加工顺序的信息，进而转换为可行性调度解的过程：首先依据基于子批的染色体编码基因串确定分配到每段工艺的生产线，然后根据基因串上各个子批出现的先后顺序确定每条生产线的各个子批的先后加工顺序。根据染色体解码得到生产排产甘特图，横轴代表时刻，纵轴代表所有的生产线编号，不同颜色的矩形条代表不同的子批，其长度代表加工时间，不同的染色体对应不同的甘特图，从中找出花费时间最小的一个作为最优解。

3.3 适应度函数

适应度函数是遗传算法进行选择操作的重要依据，关系到整个群体的进化行为，其设计取决于所要求解的优化问题[2]。排产方案以最小化最后一个批次的最后一个工件的最后一段工艺的完成时间为目标，因此，为了使非负值的适应度大小能够直观地体现每个染色体的优劣程度，适应度函数设计为：

其中，g（x）为目标函数。适应度函数是目标函数的倒数，目标函数的值越小，相应的适应度值就越大，代表染色体的个体优势越大，那么被选中进行后续进化操作的概率也就越大。

3.4 交叉操作

3.4.1 基于加工工艺编码染色体的交叉

针对子批编号在染色体上出现的顺序进行的交叉操作，操作过程中子批编号与生产线编号的对应关系保持不变。具体操作可以描述为：首选选择待交叉的两条父染色体P1和P2，在两条染色体上随机选择一个基因作为交叉子批，交换P1和P2中该子批在染色体中的位置，其他未选中的子批的顺序从左到右保持不变填入空缺位置，从而获得子代染色体S1和S2。

3.4.2 基于生产线编码染色体的交叉

针对子批的某一工艺段有多条生产线进行的交叉操作，保持各子批编号出现的顺序不变，子批编号与可选生产线编号的对应关系发生改变。具体的操作过程可以描述为：首先产生一个由0/1组成的随机交叉编码串，其总长度与染色体长度相等，然后找到P1染色体中交叉编码串中1对应位置的相应工艺顺序，并与P2染色体中对应工艺的生产线码互换。由于交换的是相同子批的相同工艺的加工生产线，交换后的生产线均为相应工艺的其他可选择的生产线，只需对加工时间码进行相应的重新编码即可得有效染色体。

3.5 变异操作

3.5.1 基于加工工艺编码染色体的变异

采用双点逆序变异法，在变异过程中子批编号出现的顺序发生改变，但是子批编号与生产线编号的对应关系保持不变。具体的变异过程可以描述为：首先，在父染色体P1上随机地挑选两个变异点；然后将P1上两个变异点之外的基因原封不动地遗传到子染色体S5中，基因值和位置顺序均保持不变；之后将P1上两个变异点之内的基因顺序逆转同时遗传到子染色体S5中，最后得到新的子染色体S5。

3.5.2 基于生产线编码染色体的变异

采用两点变异法，选取两点分别修改对应可选择的生产线编码，并修改加工时间。具体的过程描述为：首先在父染色体P1上随机地选取两个变异点；在子染色体上将这两个基因位上的生产线编码改为其他可选的生产线；将父染色体P1中除了两个变异点之外的基因值遗传到子代S6中，基因值和位置顺序均保持不变，最后得到新的子染色体S6。

3.6 选择操作

选择策略是算法对群体进行“优势选拔”的操作，目的是将群体中具有竞争优势的优质个体遗传到下一代。采用精英保留机制，具体过程为：首先，计算父代种群以及经过交叉和变异操作以后后生成的新种群中每一个个体的适应度值，然后选出适应度值最高的P个个体形成子代种群。

4 基于分批的多品种柔性生产调度

通过将模拟退火算法和遗传算法相结合，得出多品种柔性生产线上的批量调度优化方案，具体流程图如图3所示。

图3 多品种柔性生产批量调度流程图

5 实验验证

5.1 实验环境及参数设置

采取2.1节给出的柔性生产线模型，其中每种产品与每条生产线的对应关系以及每种产品的完成每个流程段上的加工时间如表3所示。

表3 产品与生产线对应关系及生产用时

模拟退火算法的迭代次数选取所有可能的分批方案的50%，遗传算法的迭代次数为GEN=50，种群规模为50，交叉概率为0.9，变异概率为0.1，使用MATLAB搭建了实验环境，进行了仿真实验。

5.2 每种产品生产需求总量相同时的分批调度方案

首先针对每种产品的生产总量相同时的批量调度情况进行了仿真，在这种情况下，每种产品的子批数是相等的，每个子批的大小也是相同的，以每种产品的生产总量为10，20和100三种情况为例，分批结果和调度结果如表4所示。

表4 每种产品生产总量相同时的分批以及生产排产结果

此外，以每种产品的总量都是20为例，对所有可能的分批方案的生产用时进行了曲线绘制，如图4所示。

图4 每种产品生产总量为20时最短完工时间与分批子批数的关系

该图横轴表示每种产品的子批数量，纵轴表示完成所有订单生产任务的总用时。当子批数为1时，表示整批生产的情况，即不进行批量划分，但是由于生产总量比较大，需要等待一整批在一个工艺流程段完成生产以后才能开始下一个工艺流程，会造成比较长的等待时间，从而得出的生产用时较其他分批情况要长；随着子批的增多，生产用时逐渐缩短，但是减小的速度逐渐变小，当子批数为20时，表示每种产品的每个工件都作为一个子批进行生产，在不考虑中间操作环节所需要的时间消耗的情况下，可以有效缩短生产线等待的时间，因此所需要的时间最小。但是实际操作中子批划分过小会造成中间操作增多，因此选取比较合理的中间值作为实际生产的最优分批方案来进行批量调度比较合理。值得注意的是，所选择的方案相比整批方案，所需的完工时间呈现大幅度的降低，并且与单个产品作为一个子批的情况相比，所需的完工时间相差不大。

5.3 每种产品生产需求总量不同时的分批调度方案以及生产排产甘特图

为了更加符合实际的生产情况，进一步仿真了每种产品的需求生产总量不同时的分批以及生产调度结果，如表5所示。

表5 每种产品生产总量不同时的分批和生产排产结果

根据上表可知当生产总量Xi比较小的时候，子批数量Qi也比较小，随着Xi的增加，Qi也相应增加，但是子批的批量Pi与总量Xi的大小相关性不大。

以表5中第一行为例，图5给出了最终的生产排产甘特图，横轴表示生产用时，纵轴代表生产线编号，矩形条表示产品i的第j个子批在每个工艺段所选择的生产线上的生产用时，总的生产用时为186。可以看出每种产品的每一个子批的加工顺序都符合2.1节给出的工艺流程，加工时间和生产线选择符合表3的前提条件。

图5 生产排产甘特图

6 结语

采用模拟退火算法与遗传算法相结合的方法解决了多品种柔性批量作业的分批调度问题，得出了子批与批量柔性分批及工艺流程与生产线优化调度策略，进而可以在给定订单生产总任务量的情况下得到最优的柔性分批以及批量调度的生产排产方案，并且针对每种产品的子批数和批量大小对生产效率的影响进行了实验仿真与分析，实验结果表明了所提方案的有效性和可行性。

后续研究需增加约束条件比如订单优先级和缓存区限制等，使研究方案更加符合工厂的实际生产，寻求合理的方法解决实际的多目标优化问题。