在实际车间生产过程中，每种工件都会有若干数量。而为尽快完成生产，都会把大批量的产品分成若干子批进行生产。这类关于产品分批生产的问题属于批量流(lot streaming，LS)问题，由Reiter^[1]在1966年首次提出，即按照一定的分批原则，将每一种工件分成若干个小批量，每一个小批量称为子批，并把这些子批按照一定的加工顺序安排到加工设备上的过程。对job shops、flow shops和parallel machines均有批量流问题的研究^[2]。根据分批策略不同，可分为等量分批、可变分批和一致分批^[3]，而对此问题的求解方法主要有整数规划、启发式算法、遗传算法、粒子群算法^[4]。

对批量流问题的研究多集中在flow shops和job shops，对parallel machines方面研究较少。学者邢和张^[5]分析并行机调度中允许产品可拆分的情况下，对没有生产准备和有生产准备两种情况下，分别给出了各种费用目标下的算法。Shim等^[6]考虑与顺序无关的启动准备时间,提出一种分枝定界法求解最小化总体延迟时间的等同并行机分批优化调度问题。Liu^[7]针对两阶段Flow shop中第一阶段存在并行机的情况,采用一致子批和非混排策略,通过启发式算法来求解工件排序问题；Tahar等^[8]对一组相同并行机上的调度问题，考虑作业分批和切换时间的情况下，建立线性规划模型并设计一种改进的启发式算法来对其优化求解；Wang等^[9]使用差分进行算法，以最小化完工时间为目标对并行机分批作业调度进行求解，并提出一种新的交叉和变异方法；而Wang等^[10]以最小化总完工时间对并行机分批调度问题进行研究，对小规模及大规模问题分别提出了融入贪婪搜索的分支定界算法、启发式及元启发式算法进行求解，并证明启发式算法对大规模问题求解表现最好，以上学者均未考虑模具约束问题。史青涛^[11]用遗传算法对单工序并行机批调度问题也进行了研究，对等量及非等量分批都作了分析，但文中染色体编码采用不等长且比较复杂的四维向量表示，也未考虑模具约束限制问题。而赵海丹^[12]用混合整数规划方法及粒子群算法对有模具约束的并行调度问题进行求解；亓宝梁^[13]通过对单机E/T调度问题上已经得到的一些理论成果的研究和总结,设计了多模具并行多机E/T调度问题中公共交货期的估计方法和排序工件的启发式方法，却都未考虑产品的批量流问题。

以某汽车零配车间实际背景，提出了考虑模具约束的并行机批量流调度问题，每种产品都要依靠模具才能进行加工，不同产品所需模具不同，每种产品有多个模具；加工设备是由一组性能相同的设备组成，每台设备可以安装任何一种模具；以最小化最大完工时间为目标进行求解。

1 模型描述

一般的并行机调度(parallel machines scheduling problem，PMSP)问题存在两个基本的问题：既有组合又有排序问题的调度问题，即问题中既包含了排列成分，又包含组合成分，大多数并行机调度问题都是NP完全的^[14]。而当考虑产品分批后，又增加了问题的复杂度。由于实际生产中有模具约束，使能够同时加工某个产品的设备被模具数量限制，即同一时刻加工某种产品的最大设备数等于模具数。因此，限制每种产品的子批个数最多不超过模具数。

1.1 模型假设

车间要对N种产品进行生产，每种产品的数量为J_i，且均可以被分成一定数量的子批进行生产。所有产品只需要一道工序即可完工，可以进行加工产品的设备有M台，均是功能相同的并行机，每个工件可以在任一台设备上进行生产，但需要安装相应的模具，其中每种产品只有一定数量的模具。问题基于以下假设：

1) 所有产品在一定生产周期内的需求计划已知；

2) 每种产品的模具数量确定，加工时间也确定，且同种产品在任何设备上的加工时间相同；

3) 各产品的优先级相同；

4) 每个子批只包含一种产品，且不能被分割，子批一旦开始加工就不可中断；

5) 每台设备同一时刻只能加工一个子批，且按单个工件顺序加工，每个子批同一时刻只能被一台设备加工；

6) 同一台设备连续加工不同产品时需要有调整时间，且调整时间是个定值；

7) 所要加工的产品均已准备好，且所有设备的第一个子批不需要调整。

基于以上假设，模型的目标是在有模具数量限制的情况下，确定合适的分批方案及子批在每台设备上的调度，从而使最大完工时间最短。其相关参数、变量及数学模型如下。

1.2 定义变量

参数：

　 N为产品的种类；

　 M为设备数量；

　 J_i为第i种待加工产品数量；

　 J_ij为第i种产品第j个子批；

　Mo_i为第i种产品的模具数；

　 t_i为加工第i种单个工件所需时间；

　 T为连续加工不同产品所需换模时间。

变量：

　 B_i为第i种产品的子批个数；

　BN_ij为第i种产品第j子批的数量；

　 x_ijk= $\left\{ \begin{array}{l}1,\\0,\end{array} \right. $ 1为第i种产品的第j子批在设备k上加工；

　 y_ijk= $\left\{ \begin{array}{l}1,\\0,\end{array} \right. $ 1为设备k上加工完第i种产品的第j子批需要换模；

　 C_k为第k台设备上所有产品加工所需时间。

2.3 模型建立

目标是最小化最大完工时间。

$\quad\quad\min\; \max \left( {{C_k}} \right),k = 1,2, \ldots ,M;$

(1)

$\quad\quad{C_k} = \mathop \sum \limits_{i = 1}^N \mathop \sum \limits_{j = 1}^{{B_i}} \left( {{\rm{B}}{{\rm{N}}_{ij}}{x_{ijk}}{t_i} + T{y_{ijk}}} \right){\text{。}}$

(2)

s.t.

$\quad\quad 0 {\text{≤}} {B_i} {\text{≤}} {\rm{M}}{{\rm{o}}_i},i = 1,2, \ldots ,N;$

(3)

$\quad\quad{\rm{B}}{{\rm{N}}_{ij}} = \left[ {\frac{{{J_i}}}{{{B_i}}}} \right],\forall i,1 {\text{≤}} j {\text{≤}} {B_i} - 1;$

(4)

$\quad\quad\mathop \sum \limits_{j = 1}^{{B_i}} {\rm{B}}{{\rm{N}}_{ij}} = {J_i},i = 1,2, \ldots ,N;$

(5)

$\quad\quad\mathop \sum \limits_{k = 1}^M {x_{ijk}} = 1,i = 1,2, \ldots N;j = 1,2, \ldots ,{B_i}{\text{。}}$

(6)

式(1)为目标函数，满足约束情况下，使得最大完工时间最小化；式(2)为每个设备上的最大完工时间；式(3)保证每种产品的最大子批数小于此产品的模具数；式(4)、(5)为等量分批策略，尽量保证每个子批数量相等，且所有子批数量与此产品的生产批量相等，其中[ ]表示取最近整数；式(6)保证同一子批同一时刻只能被一台设备加工。

假设一个小规模算例，有2台设备，3个产品，加工数量分别为7，5，2，模具数量分别为2，2，2，加工时间为3，4，2，换模时间为2，使用此案例数据，用LINGO 17.0对模型求解，得到最优解为25，其分批数量为1，1，2，如图1。很容易算出，该问题的最优解是25，从而验证了模型的正确性。

2 算法设计

智能算法越来越多地被运用到解决复杂的生产调度中，据以上所提出的并行机批量流调度问题，不仅要考虑分批数量还要考虑各设备的任务分配及各子批的排列顺序，使得模型求解过程更加复杂。为了解决此问题，设计了一种遗传和差分进化混合的算法DEGA。差分进化算法是一种基于种群的智能优化算法，不依赖问题的特征信息，借助于种群个体之间的差分信息对个体形成扰动来探索整个种群空间，并利用贪婪竞争机制进行优化，寻求问题的最优解。与遗传算法类似，通过变异、交叉、选择等操作进行求解，其具有高可靠性、强鲁棒性以及良好的优化性能^[15]。

2.1 编码与解码

考虑分批数量及子批排序，采用实数与符号混合编码方法，其设计如下：

$\quad\quad{B_1}{B_2} \ldots {B_n}\left| {{J_{11}} \ldots {J_{1{\rm{M}}{{\rm{o}}_1}}} \ldots {J_{n1}} \ldots {J_{n{\rm{M}}{{\rm{o}}_n}}}} \right|{\rm{M}}{{\rm{J}}_1} \ldots {\rm{M}}{{\rm{J}}_k}{\text{。}}$

其中B₁ B₂…B_n表示N种产品的子批个数，属于实数编码，其长度与产品种数相同，为N；MJ₁ … MJ_k表示每个设备分配的子批数量，属于实数编码，其长度与设备台数相同，为M，而其数量总和等于模具数总和。J₁₁…J_1Mo1…J_n1…J_nMon表示子批标示，属于符号编码，如13表示第1种产品第3个子批。为了使总染色体长度一定，以最大模具数进行子批标示，假如产品1有3个模具，则子批标示为11，12，13。而由于B₁≤Mo₁，若B₁=2，则子批13的数量0，依此类推，其长度为所有产品模具数总和。第1段和第3段的相对位置则分别表示产品种类和设备编号，即各自第1个位置分别表示第1种产品和第1台设备，其他依此类推。

解码过程如下。假设有3台设备，3种产品，产品的数量分别为10，15，20，模具数为2，2，3，一个可行的染色体为2 1 3|32 21 33 31 11 12 22|2 2 3。第1段染色体为2 1 3，表示第1种产品分成2批，子批数量分别为5，5，第2种产品分成1批，子批数量为15，第3种产品分成3批，子批数量为7，7，6。将其依次分配给第2段对应的位置，未分配的记为0。第3段表示3台设备上的子批分别为32(7) 21(15)；33(6) 31(7)；11(5) 12(5) 22(0)，括号内是对应子批的数量。

2.2 适应度函数

以式(1)为模型的适应度函数，即最小化最大完工时间。

2.3 DEGA算法操作

DEGA混合算法流程如图2所示。

2.3.1 变异操作

由于染色体包含实数和符号编码，对于实数编码部分采用差分变异，而符号编码部分采用遗传变异。进行差分变异操作时，采用自适应变异的算子。

$\quad\quad\lambda = \exp \left( {1 - \frac{{{G_{\rm m}}}}{{{G_{\rm m}} + 1 - g}}} \right),$

(7)

$\quad\quad F = {2^\lambda }{F_{0,}}$

(8)

$\quad\quad{v_i}\left( {g + 1} \right) = {x_{r1}}\left( g \right) + \left( {{x_{r2}}\left( g \right) - {x_{r3}}\left( g \right)} \right)F{\text{。}}$

(9)

以上式中：F₀为变异算子；G_m为最大进化代数；g为当前进化代数，v_i(g+1)为变异后的第g+1代种群中第i个个体，x_r1(g)、x_r2(g)和x_r3(g)为g代中不同的个体。在算法初期变异算子为2F₀，个体具有较大的多样性，避免早熟。随着算法的进展，变异算子逐渐降低，最后接近F₀，保留优良信息，避免最优解遭到破坏，增加搜索到全局最优解的概率。

进行遗传变异时，采用DM(displacement mutation)变异，即从父代个体中选择一个子位串，然后再随机在剩下的位串中选择一个位置，并插入该子位串，如图3所示。

2.3.2 交叉操作

对实数编码部分使用差分进行二项式交叉，符号编码部分使用OX(order crossover)。

二项式交叉操作的方程为

$\quad\quad{u_{i,j,g}} = \left\{ {\begin{array}{*{20}{l}}{{v_{i,j,g}},}&{{\rm{rand}}\left( {0,1} \right) {\text{≤}} {\rm{CR}}{\text{或}}j = {j_{{\rm{rand}}}};}\\{{x_{i,j,g}},}&{\text{其他。}}\end{array}} \right.$

(10)

其中，j=1,2,…,D，D为进行二项式交叉染色体长度，j_rand为[1，D]内随机整数，CR∈(0,1)为交叉率。

OX操作，从其中一条染色体中随机选几个交叉点，然后找到另一条染色体中被选基因对应的位置，将被选基因按顺插入到相应位置。反过来类似。其交叉操作如图4所示。

由于实数编码部分有数量约束，包括最大最小及总和约束，会出现非法个体，因此会通过修复策略进行非法个体的修复。

2.3.3 选择操作

选择操作采用精英保留和竞争选择结合的策略，即把进化后的种群和父代两个种群中的最优个体(称为精英个体)保留到子代中，然后把除最优个体外的其他个体进行竞争选择策略保留到子代中，直到子代种群个体数量达到种群规模为止。

3 案例分析 3.1 算例验证

为了验证算法的求解能力及有效性，将模型中的产品批量及模具数量均设置为1，换模时间设置为0时，模型就变成传统并行机模型，以此对文献[16]、[17]中的算例进行求解，算法参数：

种群大小N_p=20；最大迭代次数G_m=100；变异率R_m=0.3；交叉率C_m=0.8；缩放因子F₀=0.5。对各个案例运行50次得到如表1结果。

BF、WF、AF分别表示最优解、最差解及平均值。从表中可以看出，DEGA算法在处理传统并行机问题上，其求解能力要好于文献[17]中的结果，证明了DEGA算法的优越性及有效性。

3.2 案例介绍

根据实际情况，假设一个小型的有模具约束的并行机批量流问题。案例中包含6种产品，4台设备，每种产品对应有一定数量的模具。详细信息如表2。

针对以上产品加工信息，按照目前车间手工排产策略，将每种产品按照模具数量等量分批，例如产品1，其加工批量是400，模具数量为3，可以等量分批为3个子批：133，133，134。依此方法，对其他产品进行分批，然后再按顺序将所有子批分配分配到空闲的设备上，只要设备空闲，就对未生产的产品子批进行加工。具体的生产甘特图如图5。

由上图可以看出，按照目前手工排程的结果，其最大完工时间为1 114 min，换模时间为13次，多台设备的空闲率较大。

3.3 实例结果分析

使用Matlab运行算法，除了以上产品信息外，其他相关参数如下。

种群大小N_p=50；最大迭代次数G_m=200；变异率R_m=0.3；交叉率C_m=0.8；缩放因子F₀=0.5。

求解得到的最优解为：(1 2 3 2 1 2 | 12 21 23 32 43 62 63 11 13 42 53 33 41 51 22 31 52 61 | 7 4 3 4)，其中第一段即为最优分批方案。算法优化过程中其目标函数(最大完工时间)随迭代次数曲线如图6；图7为优化后的甘特图。其中最大完工时间为980 min，换模次数7次，最大完工时间较优化前减少约12%，且各台设备负荷均匀。

4 总结

对实际中大多数生产车间都会考虑将批量生产的产品分成子批进行生产的问题，建立了考虑模具约束的并行机批量流目标优化模型，并设计了DEGA算法进行求解。对传统并行机问题算例进行求解，结果表明了该模型及算法的有效性和可行性，并对实际案例进行优化求解，给出了较优的的分批方案及子批在设备上的生产排序，其最大完工时间较之前有着明显的减少，由于实际问题中不可避免地有插单生产等情况，后续考虑对动态排程问题进行研究。