多层级装配作业车间等量分批策略与调度算法

黎英杰，刘建军，陈庆新，毛 宁

(广东工业大学 广东省计算机集成制造重点实验室,广东 广州 510006)

0 引言

装配作业车间是作业车间的一类现实化扩展，经由加工和组装两个阶段完成装配型产品制造，其调度问题既要考虑任务的工艺顺序约束，还要考虑任务间的装配关联约束，即关联零部件只有齐套才能开始装配[1]。相比作业车间调度问题(Job-shop Scheduling Problem, JSP)研究，装配作业车间调度问题(Assembly JSP, AJSP)的研究相对较少，且其生产调度更具挑战性[2]，目前主要分为不对装配体调度[3-4]和对装配体调度[5-8]两大类，前者假定最终产品的所有零部件齐套之后才开始装配作业，调度时只需附加一定的装配工期，不涉及具体的装配工序调度，适用于产品结构简单或装配时间相对加工时间较短的情况；后者需要同时考虑多层级物料清单(Bill of Material, BOM)结构中所有零部件的加工工序和装配工序调度，因此具有更高的复杂度。

多层级AJSP是将加工和装配一同处理的综合调度问题，也是一类典型的分层耦合约束(Hierarchically Coupled Constraint, HCC)优化问题[8]，其最终产品的总装开工时间受制于所需部件的完工时间，而上级部件的装配开工时间又受制于其直属零件/子部件的完工时间。随着产品复杂度的上升，多层级AJSP所含零部件工艺路径和工时需求也将呈现高度的差异性，导致满足此类分层耦合约束的进度协同更加复杂，现实生产中常表现为严重的装配前等待问题。因此，研究构建高效的多层级装配作业车间调度算法具有重要的意义，遗传算法因在理论研究和实际应用上基础很深而被广泛采用。然而，各级零部件间的制约关系使得基于传统遗传算法的全域搜索算法的搜索过程产生大量不可行解，需要额外的解码和修复操作，因此求解效率极低，难以满足现实需求。目前已有少量研究将搜索限定在可行域内，例如ZHAO等[5]设计了基于虚拟零部件级别的分区编码方式，但是给不存在顺序约束关系的零部件之间强加约束，缩小了算法的搜索空间；SHI等[6]提出一种基于工序约束链编码的遗传算法，保证了初始解的可行性与完备性；王福吉等[7]和ZOU等[8]针对AJSP，通过设计编码方式和遗传进化算子将算法限定在可行域内进行搜索，并与标准遗传算法进行对比，验证了算法的合理性和优越性。

然而，上述针对装配产品算法的研究均未考虑任务分批，实际生产中的产品往往具有一定批量，批量生产中的任务通常被允许分批生产和传输，该类问题被称为分批调度问题[9]，其涉及任务分批和子批调度两个子问题。已有研究将装配作业车间与分批调度结合，发现分批生产能够提高车间流动性，实现更灵活的进度协同并提升车间性能[10-12]。但是此时对多层级装配型产品进行任务分批调度时，子批任务之间不仅需要满足装配顺序约束，还需满足装配子批的批量需求，即各装配子批只有等到有相应批量的子属工件完工才可开工，由于零部件子批之间存在动态变化的分层耦合约束，导致上述传统遗传算法的进化算子不再适用，本文给出多层级装配作业车间分批调度模型，提出该类车间基于可行域搜索的遗传算法，其设计初始种群生成方式和交叉变异算子时考虑了批量变化导致的分层耦合约束的动态性，验证了算法的基础性能表现，并基于等量分批策略提出加工/装配两阶段分批策略，最后通过实验揭示了各分批策略下3类典型结构产品调度性能的差异性，对比了协同复杂性导向策略和随机搜索策略下算法求解性能的差异。

1 研究问题及数学模型

1.1 多层级装配作业车间分批调度问题描述

多层级装配产品BOM以不同复杂程度装配树的形式生成，FRY等[13]基于结构共性抽取3类典型结构：①Flat型，包括单层树形结构，由零件直接装配成产品；②Tall型，包括多层树形结构，但其中每个父节点有且仅有两个子节点；③Complex型，是由Flat型和Tall型产品结构复合而成的多层树形产品结构，其中至少有一个父节点包含两个以上子节点，如图1所示。

不同结构的装配产品具有不同的装配层级和零部件装配关系，其操作优先级结构与生产任务间的协同性均不同[14]，且在实际生产中对交货期设置规则选用[15]、调度方案设定[16]等的需求也存在差异化，因此在调度时考虑产品结构具有重要的现实意义。本文将重点面向上述3类不同结构复杂程度的多层级装配作业车间分批调度问题展开研究，即在AJSP基础上考虑零件分批加工和部件分批组装，实现同类零件/部件的分批传输和并行生产，从而协同生产进度并缩短生产周期。该分批调度问题描述为：有p个待交付产品，P={Ph|h=1,2,…,p}，每个产品Ph的需求数量为DMh，其BOM结构属于3类典型结构中的一种，产品Ph所含零件在a台加工机器M={Mi|i=1,2,…,a}上加工，所含部件在b个装配单元F={Fi|i=1,2,…,b}中组装，其中零件(部件)每道加工工序(装配工序)只能由1台加工机器(1个装配单元)完成；优化问题是如何对所有产品包含的所有零部件类进行分批，并为划分而得的子批确定其在相应机器/单元上的加工/组装序列，以最小化所有产品的最大完成时间。

在生产调度过程中有以下基本假定：①在零时刻，所有零件子批均可被加工；②加工机器与装配单元在生产过程中正常运行，不会出故障；③不同种类工件加工或装配时需要工序准备时间，同类零部件连续加工/装配时不需要工序准备时间(第1个工件除外)，工序准备时间是与工序有关的常量，与每批工件包含的工件个数无关；④批次的装卸时间并入加工时间；⑤不同子批工件的工序之间没有先后约束；⑥每个工件在任意一台机器上的加工/装配工序有且只有一个；⑦每台机器(每个装配单元)任一时刻只能加工(装配)一个工件，任一工件同一时刻只能被一台机器加工；⑧工序一旦开工就不能中断。

1.2 多层级装配作业车间分批调度模型的构建

1.2.1 模型相关参数及定义

模型构建过程中涉及的参数符号及含义说明如下：

p为待交付产品类型数；

Ph为第h类产品；

DMh为产品h的需求数量；

CNh为产品h下属所有零部件的类型数；

a为加工机器数量；

b为装配单元数量；

M为加工机器集合；

F为装配中心集合；

TM为加工任务集合；

TA为装配任务集合；

CFi为加工机器Mi或装配中心Wi上的装夹类型；

Lhj为产品h的第j类工件批次；

mhj为产品h的第j类工件批的工序数量；

Pthjk为Lhj第k道工序的零件加工或部件装配时间；

SUhjk为Lhj第k道工序的准备时间,同一个批次的各个工件之间可共享准备时间；

Qhj为Lhj的批量大小；

SNhj为Lhj的子批数量；

Fhj为Lhj的装夹类型，同一类工件的子批在各道工序的装夹类型均相同，否则不同；

Lhjs为Lhj的第s个子批任务；

Qhjs为Lhjs的批量大小；

Pthjsk为Lhjs第k道工序的加工或装配时间；

SUhjsk为Lhjs第k道工序的准备时间;

Sthjsk为Lhjs第k道工序的开始时间；

Cthjsk为Lhjs第k道工序的完工时间；

Vhjsk表示工件子批装夹类型与机器当前装夹类型是否相同，即能否共享准备时间，是则Vhjsk=0，否则Vhjk=1；

MShjsk为Lhjs第k道工序所对应的加工机器或装配单元，MShjsk∈M，F；

Zhjsk表示MShjsk上进行加工或装配的子批是否为Lhjs,是则Zhjs=1，否则Zhjs=0；

Lh′j′s为Lhjs在同一加工机器或装配中心(MShjsk=MSh′j′s′k′)上的紧后任务;

QUhj为Lhj直接子节点上工件类型的数量，即该部件由几种工件组装而成，Lhj∈TA；

Uhj为Lhj直接子节点上工件的集合，表示该部件直属工件的具体构成，Lhj∈TA；

Thjq为Lhj直属工件中的第q类工件，q=1,2,…,QUhj，Lhj∈TA，Thjq∈Uhj；

Thjqx为Lhj直属工件中第q类工件的第x个子批；

Qhjqx为Thjqx的批量大小；

CThjqx为Thjqx的完工时间。

1.2.2 数学模型

基于上述的符号定义，本文构建了以最小化工件最大完工时间为目标函数的多层级装配作业车间分批调度模型：

min(C)=maxCthjsk。

(1)

s.t.

(2)

1≤SNhj≤Qhj,SNhj∈N+,h∈[1,p],

j∈[1,CNh]；

(3)

h∈[1,p],j∈[1,CNh]；

(4)

Sthjs0=Cthjs0=0,h∈[1,p],

j∈[1,CNh],s∈[1,SNhj],Lhjs∈TM；

(5)

j∈[1,CNh],s∈[1,SNhj],k∈[1,mhj]；

(6)

Sthjs(k+1)≥Sthjsk+PthjskQhjs+VhjskSUhjsk,h∈[1,p],

j∈[1,CNh],s∈[1,SNhj],k∈[1,mhj]；

(7)

h∈[1,p],j∈[1,CNh],s∈[1,SNhj],

q∈[1,QUhj],Thjq∈Uhj,Lhj∈TA；

(8)

Sthjs(k+1)≥Cthjsk,h∈[1,p],j∈[1,CNh],

s∈[1,SNhj],k∈[1,mhj]；

(9)

s∈[1,SNhj]；

(10)

Cthjsk≤Sth′j′s′k′,

h,h′∈[1,p],j,j′∈[1,CNh],s,

s′∈[1,SNhj],

k,k′∈[1,mhj],MShjsk=MSh′j′s′k′；

(11)

Pthjsk=Pthjk,h∈[1,p],j∈[1,CNh],

s∈[1,SNhj],k∈[1,mhj]；

(12)

SUhjsk=SUhjk,h∈[1,p],j∈[1,CNh],

s∈[1,SNhj],k∈[1,mhj]。

(13)

其中：式(1)为目标函数最大完工时间，用最晚完工的工件子批时间表示；式(2)表示产品与其所含工件的数量关系，而且工件拆分后各个子批批量的总和与拆分前的工件批量相等；式(3)为对工件拆分的子批数量的约束；式(4)表示采用等量分批的方法对工件进行拆分，当工件不可完全等量拆分时，将剩余部分工件并入最后一批工件进行加工；式(5)表示所有零件子批在零时刻均能被加工；式(6)表示只有工件装夹类型与机器当前装夹类型相同，即在同一个工件批的子批之间才能共享准备时间，否则不能共享准备时间；式(7)表示工件的前后工序约束关系；式(8)表示部件子批首道装配工序的开工时间在其直属工件相应子批批量完工之后；式(9)表示同一工件子批前工序完工与后工序开工的排队等待时间约束；式(10)表示任意一类工件在任意一台加工机器或装配中心上的工序数只能有一个；式(11)限定了同一机器上紧前紧后任务的时间约束；式(12)和式(13)表示同一批工件各个子批的工序加工/装配时间与工序准备时间相同。

2 批量划分策略与集成优化算法

2.1 批量划分策略

分批调度虽然能减小多品种小批量制造车间的设备闲置时间，缩短产品完工时间，但是过小的批量也会显著增加不同子批生产切换带来的准备时间(准备时间占比越大，此类影响越显著)，还会由于子批数过多而增加管控难度。根据批量划分策略的不同，有等量分批(将任务划分为均等批量的传输/生产子批，且同类任务在各道工序上的划分方案相同)和非等量分批两种方式，后者还可以进一步分为一致子批(任务各子批的批量可以不同，但同类任务在各道工序上的划分方案仍需相同)和可变子批(任务的划分方案可灵活变化且各道工序不必相同)两类[9]。文献[17]表明相对于可变分批策略，等量分批策略为实践中最直接、最容易实现的方式，其能节省拆分设置成本和计算工作量，有利于平衡工作负荷和提高机器利用率，文献[10-12]针对装配作业车间的研究也支持了该结论，因此本文仅聚焦于更为实用的等量分批策略，并基于该策略对加工零件/组装部件进行批量划分，具体考虑以下5种策略：

(1)策略Ⅰ(基准策略1) 不对任一类零部件进行分批，即同类零部件进行整批加工和传输，而且同一类部件要在其所有直属零件/子部件齐套之后才能开工，该策略用于与其他分批策略进行性能对比。

(2)策略Ⅱ(基准策略2) 对所有零部件进行随机等量分批。该策略理论上能够获得全局最优解，是结合零件加工与部件装配两个阶段进行统一考量的一类策略。为了对比分析，本文考虑以下3类分批策略，以找出不同环境下分批优化的方向，使搜索空间可预测，从而提升求解效率。

(3)策略Ⅲ 仅对所有零件进行随机等量分批，不对任一类部件进行分批，该策略用以测试在零件加工阶段进行分批对生产性能的影响。在该策略下，任一类部件组装都要等其直属的所有零件子批完成后才能开工。

(4)策略Ⅳ 不对任一类零件进行分批，而对所有部件进行随机等量分批，该策略用以测试在部件组装阶段进行分批对生产体性能的影响。在该策略下，任一类部件子批的组装都要等其直属的所有零件类全局齐套后才能开工。

(5)策略Ⅴ 为协同复杂性导向策略，是基于订单整体协同性而提出的策略，即在调度时考虑订单之间产品BOM结构复杂程度的不同与订单内部零部件类之间工时工序数的差异，给不同的订单产品与产品内不同零部件以不同的分批优先级，来使订单整体具有较好的协同性；本文具体以产品的装配层级、装配关联工件的种类数、零部件形成不同路径的关键性3个维度构造策略Ⅴ，因为装配层级越高，装配关联工件数越多，零部件形成路径的关键性越高，对其分批在实现订单整体协同性上可能具有更大的优化空间，所以优先对高层级多工件类的产品及其关键路径上的零部件进行分批，而低层级少工件类的产品及其非关键路径上的工件则以较低优先级进行分批或不进行分批，具体操作可见实验部分。

2.2 基于可行域的改进型遗传算法

分批调度问题求解算法主要包括分步优化和集成优化两类，分步优化策略将复杂的分批调度问题分解为生产批量优化和子批调度优化两个问题分别加以求解，本质上属于局部优化方法；集成优化策略将生产批量和生产顺序统一编码，通过优化算法同时确定所有决策变量[18]。考虑到集成优化法能够进行全局优化，本文将构建一类基于可行域的改进型遗传算法，根据不同分批策略产生各零部件子批的批量，同时确定各零件/部件子批在加工机器/装配单元的生产顺序，算法中初始种群的生产方式、交叉和变异算子设计都考虑了零部件批量划分时带来的分层耦合约束的动态性，可以确保进化过程中染色体的合法性，即算法在可行域内进行搜索。算法总体流程如图2所示。

2.2.1 编码方式

以集成优化策略对染色体进行两段式编码，染色体前半段为根据不同分批策略产生的分批方案，该段染色体基因位数与工件种类数n相同，记录每类工件所分的批次数量；染色体后半段为满足分层耦合约束的子批调度方案，基因位数为所有工件的子批批次数量与工序数乘积之和，编码方式为x-y型，其中x表示工件种类，y表示x类工件的第y个子批，并以x-y出现的频数表示其工序数量。以图3染色体片段为例，预先对工件种类进行编号，并在染色体的分批序列编码段中按照编号顺序记录每类工件的分批批数。第1类工件分为2批，第2类工件分为1批(即该类工件不分批)，1-1表示第1类工件的第1个子批，1-2表示第1类工件的第2个子批，2-1表示第2类工件的第1个子批，在子批调度编码序列中1-1，1-2，2-1分别出现了两次，表示每个子批都有两道工序。

2.2.2 初始种群生成方式的设计

以图4所示的产品结构说明初始种群染色体生成方式，过程如图5所示。假设工件1～5的需求数量均为12且每类工件的工序数均为1，工件1～5的分批批数依次为3，3，4，2，1。在染色体的分批方案基因段依次记录工件分批批数即可，而在工序排列基因段先随机生成零件1～3共10个子批，每个子批各一道工序的10个基因位，然后顺序遍历染色体基因位，找到工件1与工件2子批满足部件4子批批量开工需求的最晚完工位置，并在该位置后插入工件4的子批基因位，因为零件1和零件2都分为3个子批，每批批量为4，部件4分为2个子批，每批批量为6，所以部件4第1个子批开工需要零件1和零件2各有两个子批完工才能满足批量需求，即4-1可插入1-3之后的任意基因位，此处特定插入1-3之后第1个基因位；部件4第2个子批开工要在零件1和零件2各剩余子批完工(即各自3个子批都完工)后，即4-2需插入1-2之后，也特定插入1-2之后第1个基因位。最后根据零件3将部件4的子批基因位插入部件5的子批基因位，同理将5-1插入3-3基因位之后，至此生成一条完整的染色体。

工序在染色体中出现的先后顺序代表工序安排开工时间的早晚，此时分层耦合约束在染色体中的具体体现为，各部件子批的装配工序基因位在其直属工件相应子批的基因位之后。

2.2.3 改进型交叉算子的设计

为了使交叉后的子代仍然具有合法性，需要使交叉后的各个部件子批仍能满足其装配开工批量的需求，即参与交叉互换的基因需要使零部件之间的分层耦合约束仍能得到满足。为此，本文提出一种将装配关联的零部件类进行统一交叉的方式，即本文的交叉算子的设计如下：

随机选取一个节点上的部件类I*，I*及约束其装配的所有子孙节点上的工件类构成的工件类集合为U，将U中的所有工件类(即以I*为根节点的子树上的所有工件类)对应的工序基因位统一进行交叉互换，若I*不在产品总装层，则基因交叉过程中仍需满足交叉后其上一层部件的装配约束。在父代1与父代2中按从左到右的顺序抽出U中所含工件类对应的基因位得到集合X1和X2，并在各父代找出部件I*直接父节点上的Y*部件各子批首道工序的开工基因位，在X1和X2内将I*的各子批完工基因位分段插入子代，并能够满足Y*各子批装配批量。如图4所示的产品结构，若选中部件4，则将部件4与零件1和零件2的工序基因位一起进行交叉。基因交叉过程如图6所示，对于子代1，部件4的上层部件5的批数为1即未分批，则部件5开工需部件4的3个子批都完工，此时将X2中基因依次插入5-1之前的空白基因位；对于子代2，部件4和部件5均分为两批，5-1和5-2各自开工都应在相应部件4的子批完工之后，在X1中则以4-1为截点将X1分为两段，将1-1～4-1片段按顺序插入5-1之前的空白基因位，删除多余的空白基因位，将2-1～4-2片段插入5-2之前5-1之后的空白基因位，空白基因位不够则将后续基因附着于最后一个空白基因位。若I*代表产品总装层，则将该产品所有零部件的基因位进行统一交换，交叉过程中不用考虑交换基因的层级约束，只需将X1和X2中基因依次填入子代空白基因位即可。

2.2.4 改进型变异算子的设计

为了满足分层耦合约束，变异算子设计如下：

步骤1在p种产品中随机选取一种，并在染色体调度序列段中找出该产品所有零部件的基因位。

步骤2找出该产品所有部件所有子批的首道工序并附上标识。

步骤3附上标识的基因位将该产品整条染色体的基因序列分割为若干个子片段，在每个子片段内将基因反转得到变异后的子代。

具体的变异操作如图7所示，因为该染色体只包含图4所示的一种产品的编码信息，且各类工件的工序数量均为1，所以只需标识部件4和部件5的首道装配工序基因位，染色体的分批方案段基因不进行任何操作，为4-1，4-2，5-1，4-3，5-2加上标识后将调度基因序列划分成多个子片段，将子片段内基因反转的实质是在满足分层耦合约束的前提下，对其零件的加工基因位进行了分段反转。

2.2.5 选择策略

基于种群的适应度函数采用轮盘赌方法选出相应的后代，每个个体被选中的概率与其适应度成正比，一般步骤如下：

(4)产生[0,1]之间的随机数r，若0≤r≤Q1，则选中P1；若Qi-1≤r≤Qi，则选中Pi。

3 仿真实验

3.1 仿真参数与实验设计

本文以图8所示的产品BOM结构为实验案例，根据前文3类典型产品结构的定义，将图8a～图8c产品结构归为Flat型，图8d～图8f产品结构归为Tall型，图8g～图8i产品结构归为Complex型。

本文的多层级装配作业车间由6个加工机器(a=6)和3个装配单元(b=3)构成，每台加工机器/装配单元包含不同的加工/装配工艺，每种BOM结构对应的产品需求数量服从离散均匀分布[4,10]，每道加工/装配工序所需时间服从离散均匀分布[1,5]，工序准备时间与加工/装配时间成比例，仿真参数设定总结如表1所示。

表1 仿真模型参数设定

续表1

本文实验设计如下：

(1)基于可行域搜索算法的基础性能验证，将本文算法与文献[7-8]同为基于可行域搜索的改进型遗传算法在任务不分批的条件下进行对比，以验证本文算法在处理此类含静态分层耦合约束调度问题时的基础性能。

(2)基于上述3类代表不同复杂程度的产品结构，探究加工/装配两阶段4种分批策略(策略Ⅰ～策略Ⅳ)在这3种典型结构产品下的性能表现及随不同梯度准备时间的变化趋势，即通过比较4种分批策略在Flat型、Tall型、Complex型(每种产品类型下各含3种BOM结构)产品结构下的性能，分析其在3种典型产品结构下的适应性，并根据不同准备时间(t=0.2，t=0.5，t=1.0)分析各分批策略的变化情况。

(3)分批的导向性实验。随着任务规模的增大，算法的搜索效率和质量不可避免地会下降，为使最优分批方案的搜索具有可操作性，探究更具方向性指导的分批策略，在p=9时即对9种BOM结构的产品进行统一分批调度，分析比较较大订单规模下策略Ⅱ(随机搜索策略)和策略Ⅴ(协同复杂性导向策略)的求解效率和质量，以探究更大规模生产任务下分批的方向性。

为评价本文不同分批策略下的调度性能，以工件最大完工时间为优化目标，以装配等待时间、工作中心稼动率、准备时间、算法运行时间等为观测指标。具体评价指标与计算公式如表2所示。

表2 性能评价指标

本文的遗传参数设置如下：种群大小为200；最大遗传代数为60代；交叉概率为0.8；变异概率为0.05；代沟为0.9。本文数据基于MATLAB 2016b,在相同环境下对每次实验重复运行30次取均值得到。

3.2 验证算法的基础性能

本文算法与文献[7-8]算法都是针对多层级AJSP的可行域搜索算法，但文献[7-8]算法用于求解不考虑加工/装配任务分批生产的情况，各层级零部件之间的分层耦合约束为静态，其算法的交叉、变异操作也考虑了这种静态约束；若在该调度问题中考虑加工/装配任务的分批生产，则由于子批允许分批生产和调度，各子批装配任务开工并不需要等其直属工件所有批次全部完成，只要等其直属工件若干个能满足其批量需求的子批完工即可开始，各层级零部件子批任务之间的分层耦合约束呈现高度动态性。因此，本文以处理静态分层耦合约束的可行域方法为基础，构建能够应对独立分批带来的动态分层耦合约束的求解算法。鉴于本文算法与文献[7-8]算法的适用范围不同，后者只适用于解决不考虑分批的多层级AJSP，为本文所研究问题(即允许分批问题)的一个特例，因此本文在任务整批生产的条件下对算法进行对比，以验证本文算法在不考虑任务分批调度环境下的基础性能。对算法分别进行30次独立实验，统计各自的进化性能，如表3所示。本文以图8所示的BOM结构为实验案例，其中Flat表示对图8a～图8c结构产品进行统一调度，Tall表示对图8d～图8f结构产品进行统一调度，Complex表示对图8g～图8i结构产品进行统一调度，以30次独立实验最优解的平均值、最优值、最差值、标准差和CPU耗时进行统计。

表3 算法30次独立实验结果的比较

由表3可见，与文献[7-8]算法相比，本文算法基于可行域的邻域构建和搜索策略在3类实验案例调度中的性能表现相当，即在不考虑任务分批的情况下，本文算法在处理包含静态分层耦合约束的调度问题中也具有较好的适应性，求解效率与求解质量都能得到保证。因此，本文基于算法的可行域进行搜索，重点探究不同分批策略对不同产品结构调度的影响，以及大规模任务下具有一定导向型分批策略的性能表现。

3.3 分批策略对不同产品结构类型效果的分析实验

为探究4种策略在3种典型产品结构下以及不同准备时间设置下的性能表现，采用上述目标函数、5个性能观测指标、3种准备时间的设置、3种产品结构类型，共进行3×4×3=36组实验。该阶段算法搜索效率不是研究重点，因此不对t0进行统计说明。

表4所示为Flat型产品结构的实验结果，可知：

表4 Flat类型实验结果

(1)准备时间梯度较低时(t=0.2，0.5),策略Ⅲ优于策略Ⅰ，对加工阶段进行分批能够提高加工中心稼动率，缩短工件之间的装配等待时间，从而缩短生成周期；当准备时间设置较高时(t=1.0)，策略Ⅲ劣于策略Ⅰ，此时分批会使准备时间大幅上升，从而降低加工中心的稼动率，使生产周期延长。

(2)策略Ⅳ劣于策略Ⅰ。由于Flat型产品结构只包含单层装配层级，装配任务数远少于加工任务数，若仅对部件进行分批，则部件的各个子批在同一时刻竞争有限的装配资源，不仅不能提升装配中心的稼动率，反而会增加部件子批之间的准备时间。

(3)准备时间梯度设置较低(t=0.2，t=0.5)时，策略Ⅱ表现最优，因为零件分批能使部件子批的装配工序提前进行，部件子批之间不需要在同一时刻竞争有限的装配资源，所以有效提高了工作中心稼动率。然而随着准备时间设置的增大，分批使子批之间的准备时间增大，从而延长了生产周期，因此策略Ⅱ劣于策略Ⅰ。

表5所示为Tall类型产品的实验结果，可知：

表5 Tall类型实验结果

续表5

续表5

(1)策略Ⅲ和策略Ⅳ均优于策略Ⅰ。对于具有高装配层级且每层级装配关联工件类较少的Tall型产品结构，零件加工进度影响部件装配进度，每一低层级部件装配进度也影响高层级部件装配进度，对零/部件分批均能使更高层级部件的装配进度提前，有效提升加工与装配中心的稼动率；而且此时每一装配层级的任务齐套性约束都严重影响后续高层级装配任务的开工时间，对装配阶段每一层级的部件进行批量划分均可使后续高层级部件装配提前开工而加速生产进程，其分批优化空间大于零件加工阶段，因此策略Ⅳ优于策略Ⅲ。

(2)策略Ⅱ下的生产周期表现最优，因其综合零件加工与部件装配两阶段分批收益，每一层级部件都不需要在同一时刻竞争有限的装配资源，子批任务能够获得较好的流动性，从而极大缩短任务间的装配等待时间，明显提高工作中心稼动率。

(3)随着准备时间设置梯度的升高，分批使加工/装配两阶段工件子批之间的准备时间大幅度上升，其在缩短生产周期上发挥的效力有所减弱。

表6所示为Complex类型产品的实验结果，可知：

表6 Complex类型实验结果

(1)对于含有较高装配层级且每层级下装配关联工件类较多的Complex类结构的产品，对零部件分批均能使较小的子批以更好的流动性实现更灵活的进度协同，从而缩短装配等待时间，提高工作中心稼动率，并缩短生产周期。

(2)当准备时间比例设置较低(t=0.2，t=0.5)时，在加工与装配阶段进行分批均能缩短生产周期，于是策略Ⅲ和策略Ⅳ均优于策略Ⅰ；而且在加工阶段分批能促进装配阶段分批调度的效果，因此策略Ⅱ表现最优；当准备时间比例设置较高时(t=1.0)，因为Complex型产品结构所含工件类较多，所以分批会大幅增加零部件子批间的准备时间，工作中心稼动率下降，导致任一阶段分批都不能为生产周期带来收益，因此策略Ⅲ和策略Ⅳ均劣于策略Ⅰ，同时策略Ⅱ因两阶段都产生大量准备时间而表现最差。

3.4 随机搜索策略与协同复杂性导向策略的对比实验

本阶段实验为探究多层级装配作业车间下分批的方向性，以解决订单规模增大导致最优分批方案存在搜索空间大、求解效率低的问题。基于策略Ⅴ提出的具体实验步骤如下：

步骤1以p个待交付产品每种产品的最高装配层级ki层(i=1，2，…，p)为第一优先级，由高到低进行排序，并以产品下属工件种类数为第二优先级，由多到少进行排序，假定产品排序后为J1，J2，…，Jp。

步骤2找出产品的关键路径，假设一产品下的各类零部件从零件加工层到产品总装层形成q条路径，计算各条路径中所含零部件的总加工时长Tj和工序总数Uj(j=1，2，…，p)，记q条路径中的工时最大值为Tmax，工序最大值为Umax，则每条路径的关键性

(14)

式中CRj值最大的路径即为关键路径。

步骤3对每类产品关键路径上的工件按顺序进行累加分批调度，即第1次调度仅对J2中关键路径上的工件类等量分批，J1其余工件类及其余产品所含工件类均不分批；第2次调度在第1次的基础上再对J2产品关键路径上的工件类等量分批；第p次调度对所有产品(J1，J2，…，Jp)关键路径上的工件等量分批，其余工件不分批。

由前一阶段实验可知，随着准备时间比例的增大，分批效力逐渐下降，当准备时间设置为t=1.0时，分批在本文实验设置中不能给调度性能带来正向收益，因此用准备时间设置中间值(t=0.5)对图8a～图8i结构产品(p=9)进行统一调度，采用策略Ⅴ共进行9组实验(实验编号为1～9)，并与全域随机搜索策略Ⅱ(策略Ⅱ时3种产品结构的调度性能最优)的实验结果(实验编号为10)进行对比。该阶段的探究重点为算法搜索效率和求解质量，实验终止条件为收敛200代，并采用订单生产周期、算法运行时间作为观测指标，以每组实验重复运行30次的均值取整进行说明。

如图9所示，协同复杂性导向策略Ⅴ在搜索质量和效率上优于随机搜索策略Ⅱ。在策略Ⅴ的9组实验下，生产周期变化曲线呈明显的先下降后上升的趋势，搜索时间也随分批任务数的增多呈稳步上升趋势，获得的最优调度结果为1 240 h，耗时290 s，而策略Ⅱ的调度结果为1 320 h，耗时542 s。在较大订单规模下对所有工件类进行完全随机搜索分批，调度结果和算法搜索效率均表现较差，不能满足实际生产的需求，而策略Ⅴ以一定的导向性选择产品和产品中具体的工件类进行优先分批，有效地缩小了搜索范围，保证了求解质量和效率。图10所示为所给的策略Ⅱ和策略Ⅴ(实验编号为3)下30次实验中最优值的收敛曲线，可见策略Ⅴ以更快的收敛速度获得了更优的解。

4 结束语

在多层级装配作业车间中，分层耦合约束导致可行解所构成的可行域范围小，批量划分的随机性使可行域的动态变化程度更高，问题的求解更复杂。本文提出改进型遗传算法对初始种群生成方式和交叉变异算子进行设计，使问题的搜索过程始终保持合法与可行，验证了算法的有效性，并基于可行域搜索进行了以下两方面研究：

(1)加工/装配两阶段的4种分批策略对3种典型产品结构适应性的研究 在产品的零件加工与部件装配两阶段分别考虑分批，提出4种分批策略并探究其不同产品结构下的性能表现，以及不同准备时间设置下的变化趋势。实验结果表明，对每一层级工件进行分批都能使其以更好的流动性满足后续高层级装配任务的齐套性需求，从而优化调度结果；在调度时对具有更高装配层级和更多装配关联工件类结构的产品进行批量划分，能够通过更灵活的任务间进度协同来缩短生产周期；随着准备时间设置比例的增加，批量划分的子批之间会产生大量的准备时间，使工作中心的稼动率下降，从而减弱分批效力，甚至产生负收益。

(2)随机搜索策略与协同复杂性导向策略的求解效果对比研究 随着订单规模的增大，完全随机分批会增大搜索空间，降低算法的搜索效率和质量，本文提出一种基于任务协同性的分批策略，使批量划分时能更有针对性地选择产品以及产品中的具体工件类。实验结果表明，批量划分时优先选择高装配层级、多工件类的产品及其关键路径上的工件，能够使任务之间有更好的协同性，使最优分批调度方案的搜索更具方向性。

针对本文的不足，未来将从以下两个方面进行研究：①从更多维度区别产品和工件类的分批优先级，以使分批更具可操作性，如工件的需求数量、工件的种类(零/部件)；②在以交货期、生产成本等为优化目标的多目标调度模型中考虑分批调度，使分批方案更符合实际生产。