李思瀚，莫超雄，刘建军，陈庆新，毛 宁

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

近年来，许多单机装备供应商为迎合市场需要，转型为提供自动化生产线的定制研发、客户现场总装和售后运维的服务型企业，帮助客户实现更高效、更可靠和更低成本的整线配置和运维。自动化生产线是集成了机电液气等多模块的复杂产品，其在客户地现场进行的总装过程组织和管控均较复杂。一方面，为有效利用装配组资源，需要合理调配多个装配组在多个客户地之间往返执行装配。另一方面，由于装配作业的先决条件是物料齐套，而实际齐套时间和期望齐套时间有一定偏差，这种时间偏差不确定性增加了企业总装作业调度的难度。

当前，装配调度的主攻方向为自动化装配[1-4]，而通过手工装配完成结构复杂的产品装配的场景尚不多见[5-6]。文献[7]依据Petri网原理提出控制关键装配工序的调度方法，用以规范手工装配复杂产品的工艺流程；也有一些研究考虑了复杂产品装配过程的生产管控问题，比如航空发动机的装配场景，胡跃洋等[8]在构建装配流程中引入工作流的机制，万峰等[9]提出基于启发式规则的装配调度算法，伍伟民等[10]提出基于无线射频识别和流程的装配物料管控，叶剑辉等[11]提出基于日作业计划的车间现场数据管理模型实现对装配现场精细化监控。文献[12]提出通过集成生产计划与调度的优化模型解决考虑随机返工的定点装配车间的调度问题。文献[13] 提出改进型离散磷虾调度算法来优化复杂产品的最小装配工期。这些调度方法大多假定物料适时齐套，但整线定制下的总装环节需要面对齐套时间不确定问题，且装配组往来不同客户地需要较长时间，所以其调度模型关键是对不确定性进行前摄性考虑，降低装配组的停工待料时长和无效差旅。

前摄性调度通过预先考虑未来可能发生的不确定性干扰因素影响，制定稳健性较强的基准计划，常用的实现方式是在相邻任务结束时刻和开始时刻之间插入合适的缓冲时间间隔，以提升调度方案的鲁棒性。目前，前摄性调度研究主要应用于受不确定性因素影响较大的场景，如受限资源项目调度、船舶调度、应急救援调度等场景。崔南方等[14]为解决多目标鲁棒性优化问题，提出了基于STC (starting time criticality)分散缓冲原理的优化算法。为得到多种救援模式下，计划鲁棒性最大和救援时间最小的前摄性调度计划，何正文等[15]构建了多目标调度模型来求解。而针对不确定性救援活动工期的调度场景，王艳婷等[16]通过前摄性调度模型得到鲁棒性最大的调度计划。张振毓等[17]在已知船舶到达时间概率分布的背景下，通过在多目标遗传算法加入抽样仿真的方法，研究了通过前摄性调度来解决码头岸边岸桥资源分配的问题。

综上可知，前摄性调度在装配作业场景的应用研究较少。为解决多地总装作业过程的问题，本文将考虑整线定制环境下装配物料的不确定性齐套时间，建立同时优化质量鲁棒性和解鲁棒性双目标的多地总装作业前摄性调度模型，并构建结合了抽样仿真技术的改进非支配排序遗传NSGA-Ⅱ求解算法。

1 数学模型

1.1 整线定制企业装配作业流程及特点

整线定制企业的装配环节如图1所示，主要分为备料和客户地总装2个阶段，特点如下。

图1 多地总装作业示意图Figure 1 Schematic diagram of multi-location final-assembly operation

1) 以工作流方式驱动装配生产。在自动化生产线的总装环节，其工艺流程分为传动、控制、执行、辅助等多种装配类别的任务，各个任务之间又有逻辑约束。文献[18]详细介绍了制定此类装配工作流的方法。

2) 以手工装配为主。整线定制产线以装配组为单位，在客户地的固定位置，通过手工装配方式完成产品的总装。定制产线服务商通常有多个由不同工种人员组成的装配组，对不同的装配任务有不同的熟练度。在实际生产中，为了有效利用装配组资源，需要装配小组在客户地之间调配，并行完成多个客户的总装作业任务。

3) 物料齐套时间不确定。在物料准备提前期中，物料生产制造和运输等过程具有不确定性，使得物料的实际齐套时间和计划齐套时间出现偏差。

1.2 问题描述

以整线定制企业的多地总装作业过程为研究问题，假设企业待交付订单集合I(I=1,2,···,i)；每个订单对应的总装任务集合J=1,2,···,j；每个订单的总装工作流为AFi；企业中有k个可分配的装配组集合K={m1,m2,···,mk}；装配组mk对不同类总装任务的装配娴熟度为qkh∈[0.6,1]；总装任务的类别h=[1,2,3,4]分别表示控制、执行、传动、辅助；PT(i,j)表示所有装配任务对应的装配类别集合；装配组mk完成总装任务aij需要的时间为标准装配工时(tij)/装配娴熟度(qkh)。装配组在不同客户地u和v之间的往返时间为RTuv。其中，当u=v时，RTuv=0，RTuv=RTvu。根据对整线定制企业总装环节实际不确定因素分析，不确定性的物料齐套时间是导致装配计划无法准确执行的主要因素。假设总装任务物料齐套时间的概率分布服从均匀分布U(Dij-ΔDij,Dij+ΔDij)。其中，Dij为总装任务物料需求时间；ΔDij表示物料实际齐套时间和物料需求时间的最大偏差。在本问题中，装配组排班和总装任务执行次序是决策变量。此外，在总装环节假设：1) 同一装配任务只能同时由一个装配组来完成；2) 一个装配组同一时间只能完成一个装配任务；3) 同一客户地总装任务之间要考虑装配任务间的逻辑约束，不同客户地不考虑；4) 不同客户地订单优先级相同。

1.3 构建模型

为了更好地解决物料齐套时间随机变化对基准计划的影响，提高基准计划的鲁棒性，运用前摄性调度方法得到前摄性基准计划，来满足实际的装配过程中对装配计划可执行性和稳定性的要求。同时，针对物料齐套时间由不确定转为确定而导致相应计划需要做出调整的问题，设计映射函数rw将前摄性计划的决策变量调整为实际调度，构建解的鲁棒性和质量鲁棒性2个评价指标来评价前摄性计划的鲁棒性；并提出以前摄性计划解的鲁棒性和质量鲁棒性为目标的优化模型。

1.3.1 主要变量与参数符号

aij为第i个客户地订单中第j个总装任务，其中j为大于0的自然数；

mk为装配组k；

zk为前摄性计划中分配给装配组mk待完成的总装任务之和；

tij为总装任务aij的标准装配工时；

RTuv为客户地u到客户地v装配资源的准备时间;

Ddi为第i个客户地的订单交货期；

Pij为总装任务aij的紧前任务集合；

Sij为总装任务aij的紧后任务集合；

qkh为装配组mk对于装配类别h的作业娴熟度值；

φij为总装任务aij的缓冲时间长度；

Xijk为0-1变量，如果分配装配组mk完成总装任务aij，则Xijk为1，否则为0；

Yijbck为0-1变量，如果装配小组mk实施总装任务aij早于总装任务abc，则Yijbck为1，否则为0。

1.3.2 目标函数与约束

式(1)～(2)为优化模型的目标函数，其中，式(1)为最小化前摄性计划的订单平均延期间的期望值，指导质量鲁棒性；式(2)为最小化调度执行计划和前摄调度计划偏差的期望，指导解的鲁棒性；式(3)为总装任务开始与结束时间满足的时间约束，M为无穷大数；式(4)为装配组的分配需要满足的约束条件；式(5)～(8)为同一装配组分配装配任务的装配顺序约束；式(9)为同一客户地的不同装配任务间的装配顺序约束；式(10)为物料齐套时间和装配任务开始时间的约束；式(12)为装配任务的缓冲时间大小约束，抽样仿真中调度执行计划和前摄性计划需要满足的约束条件是相同的；式(13)为前摄调度计划在抽样仿真中的映射模型rm对应决策变量需要满足的约束。把式(3)替换为把 式(8)～(10)中分别替换为其他约束保持不变。

2 算法设计

在不确定环境下多地总装作业前摄性调度问题的数学建模中，优化目标相互矛盾、决策变量较多、解空间比较大，传统的数学规划方法很难得到最优的Pareto解集。此外，多目标近似算法，如最具代表性的NSGA-II算法很难对不确定性问题下的适应度进行评价，直接求解不确定性问题也比较困难。因此，基于问题的特点提出改进型非支配排序遗传算法(non-dominated sorting genetic algorithm NSGA-Ⅱ)，将遗传算法和抽样仿真思想相结合，如图2所示。采用将缓冲时间φ插入前摄性计划中的方法。首先运用全局搜索决定装配任务排序、装配组的分配和缓冲时间的分配；其次利用前摄性算法对染色体进行解码；然后结合物料齐套时间的抽样仿真信息，对前摄性调度的执行进行仿真，计算鲁棒性指标，并对前摄性计划进行评价；最后通过多次迭代，得到最优前摄性计划集合。具体步骤如下。

图2 改进的非支配排序NSGA-II算法流程图Figure 2 Improved NSGA-II algorithm flow chart for nondominant sorting

步骤1生成种群的初始化版本，令λ=0。

步骤2染色体解码。将染色体编码转换为装配任务的决策变量：优先次序、装配组分配和缓冲时间，并基于装配任务间的逻辑约束得到可行的考虑缓冲时间的前摄性调度计划。

步骤3生成w组仿真案例。基于实际物料齐套时间满足的概率分布模型和装配任务对应物料的需求时间，随机生成w组物料齐套时刻算例。

步骤6当λ＞λmax，当代种群在目标空间形成的最优Pareto解集，即为所求的最优前摄性调度集合，反之执行步骤7。

步骤7锦标赛选择。染色体种群非支配排序后，随机将两条染色体分为一组，总共分为N/2组，在每一组中选择染色体非支配排序后层级较小的染色体，如果一组中染色体非支配排序层级相同，则再比较染色体的拥挤距离，拥挤距离小的染色体被选中，依此类推，将N/2组选择出来的染色体，重新组成一个新的种群。

步骤8交叉。在锦标赛选择被保留下来的N/2个染色体种群中，根据设定的交叉率p，随机筛选出2c条待交叉的染色体，两两组队完成交叉操作，替换原种群中交叉前的染色体。

步骤9变异。在经过步骤8更新后的种群中，通过设定变异率筛选出待变异染色体，然后进行变异操作，生成新一代子种群

步骤10精英选择。将子代和父代种群合并，并对合并后的种群重新进行非支配排序，选择其中非支配层级中最小的染色体，组成新一代种群，另λ=λ+1。

步骤11去重机制。筛选出的新一代种群中，的染色体集合，如果集合不为空，则对集合中的个体进行变异操作后重新执行步骤2，否则直接执行步骤2。

2.1 染色体编码

遗传算法中将调度解编译为算法语言的过程称为染色体编码。在整线定制企业多地总装作业的前摄性调度问题中，首先要确定装配总装任务的顺序；其次要确定合适的装配组去完成装配任务；最后还需预估合适的缓冲时间。因此，本文将染色体分为3段：1) 装配顺序段，决定总装任务的装配顺序；2) 装配组段，决定装配组的任务安排；3) 缓冲时间段，决定每个总装任务预留的缓冲时间大小，且不同段对应不同的编码规则。

2.1.1 装配顺序段编码规则

装配顺序段对应的染色体总基因数和所有待总装任务数相等。假设所有客户地总装任务之和为l，则这部分染色体基因P=[P1,P2,···,Pl]。其中，客户地i的订单需要完成ni个装配任务，[i,j]为客户地i订单中第j个总装任务。同时为了用一维染色体区分不同总装任务，引入自然数索引与装配任务[i,j]一一对应。设l=7，i=2，n1=4，n2=3，自然数与总装任务的对应关系如表1所示。

表1 总装任务与自然数对应关系Table 1 The relationship between assembly task and natural number

关于表1中的多客户地总装作业调度问题，具体的装配顺序段的编码可以表示为[1 5 2 6 3 4 7]，其中，基因5表示客户地2中的总装任务1。

2.1.2 装配组段编码规则

设所有客户地总装任务之和为l，总共有n个可分配的装配组，则装配组编码R=[R1,R2,···,Ri],i≤l，Ri∈[1,n]的整数，表示分配Ri基因位对应的装配组来完成Pi基因位对应的总装任务。假设n=4，求解表1描述的前摄性调度问题，具体的装配组段可编码为[4 1 3 3 2 1 2]。

2.1.3 缓冲时间段编码规则

设所有客户地总装任务之和为l，缓冲时间编码的总长度和总的装配任务数相等，则缓冲时间编码φ=[φ1,φ2,···,φi]，i≤l，φi∈[0,φmax]内的自然数，表示在Pi基因位对应的装配任务的计划开始时间向后延长φi时间单位。考虑齐套时间不确定对计划影响，针对表1中具体的前摄性调度问题，具体的缓冲时间段可编码为[3 0 1 2 0 2 1]。

2.2 种群初始化

提升初始化种群的适应度是提高算法的优化效率的重要方式。因此，通过已知的物料到达期望时间建立确定模型，运用智能算法最小化订单平均延期量(质量鲁棒性指标)为优化目标，得到优化后的装配顺序和装配组分配，保留装配顺序段编码和装配段编码不变，同时生成l个0～θmax的自然数组成的缓冲时间段编码，完成种群初始化。

2.3 交叉操作

交叉操作是任意取2个染色体完成部分基因的随机交换，希望通过重组现有染色体基因的方法，得到更优的基因组合。本文染色体由3段编码方式不同的基因串组成。因此，分步进行交叉操作。其中，装配顺序段基因采用部分映射杂交，装配组段和缓冲时间段编码保持和装配顺序段编码交叉位置一致，完成交叉操作。

装配顺序段的部分映射交叉过程如下。假设染色体基因串的长度为a，随机生成一个1～a的整数r1，将父代染色体在基因位r1处拆分为2部分。父代1/父代 2中1～r1基因位分别由子代 1/子代2的1～r1基因位继承。子代1中r1～a的基因位则继承父代2中剔除子代1 中1～r1已经遗传的基因后剩余的基因，按从左到右的顺序依次继承。子代2同理。假设r1=2，具体操作如图3 所示。

(2)两方签订的仓单。因为没有及时掌握到货物的信息，企业和第三方物流信息监管存在造假的可能。企业的信用记录不全面，银行很难全面把握风险，不能全面的界定其风险水平。

图3 装配顺序段编码的部分映射交叉Figure 3 The partial mapping intersection of assembly sequence segment coding

2.4 变异操作

在算法的迭代优化过程中，为了扩大算法在解空间的搜索范围，增强群体的多样性，同时避免陷入局部最优，引入变异操作。本文染色体变异操作分3部分进行。

2.4.1 装配顺序段的邻域搜索变异

将染色体多个不同基因位上的基因互换，所组成的新的染色体集合定义为领域。装配顺序段编码的邻域搜索变异。首先在装配顺序段上随机选择q个位置(q=3，选中的基因位依次是1，4和5)，如图4所示；其次根据选中位置对应基因的组合(145)得到该基因位的邻域为(415)(451) (154) (514) (541)；最后为保证变异结果的可行性，根据装配任务间装配工艺约束对领域进行筛选，得到可行解 (154)，若邻域内不存在可行解，则重新选择基因位。

图4 装配顺序编码段的邻域搜索变异Figure 4 Neighborhood search variation of assembly sequence coding segment

2.4.2 装配组和缓冲时间段编码的变异

首先，随机生成一个长度为l，取值范围为[0,1]的整数组成的集合U1，获取U1中数值为0的位置U2集合，获取变异染色体装配组编码和缓冲时间编码U2集合中对应基因位的基因，并重新生成，如图5所示。染色体分步完成变异后，对领域中所有个体进行评价，保留最优变异子代。

图5 装配组和缓冲时间段编码的变异Figure 5 Variation in the encoding of assembly groups and buffer periods

2.5 解码及评价

2.5.1 带时间缓冲的前摄性计划算法

步骤1按照染色体装配顺序段编码基因位的顺序依次获取每个任务决策变量，基因位n对应的总装任务aij=Pn，分配的装配组为Rn，装配任务aij缓冲时间大小为φn。

步骤2总装任务aij紧前工序任务结束时间为Tij；装配组开始装配总装任务aij的时间为Sij；如果Sij＞Tij成立，则将Sij赋值给任务最早可开工时间STij，令STij=Sij，反之令STij=Tij.；其中，Sij等于装配开始装配aij前的最早结束时间Cij与装配组从客户地i到客户地j的差旅时间RTij之和。

步骤3比较总装任务aij的物料计划齐套时间Aij与总装任务aij的最早开始时间STij的大小，若STij＞Aij，则总装任务aij的开始时间不变，否则开始时间STij=Aij。

步骤4总装任务aij的标准工时为tij，装配组完成总装任务aij的作业熟练度系数为q，总装任务aij的结束时间FTij=STij+tij/q+φij。

2.5.2 右移策略

为保证前摄调度计划在抽样仿真中的可执行性，考虑实际总装环节不确定性场景会影响装配计划的执行，参考总装环节实际的执行方法，提出右移策略，装配任务aij在计划的开始时刻，受物料齐套或装配组资源约束无法开始装配，顺延任务的实际开始时间直到可开工为止。

3 算例

本文以某生产喷釉自动化生产线的企业为背景，根据企业中现有的产品种类构建装配工艺流程，验证模型和算法的有效性。图6为企业不同产品的具体装配工艺流程图。以企业一段时间周期内准备交付的6个客户地的订单为算例，每个订单具体的装配工艺流程图，分别是图6中的流程[4,2,1,3,4,2]；订单的交货期等于装配工艺流程中标准工时累加最长的工艺路径乘以松紧系数ρ。由于订单装配工艺的的复杂程度不同，本文算例的6个订单设置的松紧系数分别设为 1.6、1.4、1.7、1.5、1.6、1.4；物料预计齐套时间为公司根据订单的交期制定的装配计划中物料需求时间；可分配的装配组为 14个。

图6 装配工艺流程图Figure 6 Assembly process flow diagram

为通过数值实验校验本文所提算法，使用Matlab R2016 b软件对算法进行编程。根据前期的预实验确定多目标遗传算法的主要参数，设置种群规模N=200，算法最大迭代次数λmax=300，抽样仿真次数w=50。针对前摄性计划，通过对实际案例的实验结果来分析：1) 前摄调度计划的有效性；2) 前摄性调度在不同装配场景的适应性。

3.1 前摄调度计划的有效性分析

假设物料齐套时间偏差范围ΔDij=8，客户地间的资源准备时间RTuv=12。将本文提出的NSGA-II算法的优化方案结合右移策略下得到的仿真结果与在基于确定性的物料需求时间背景下提出的优化方法求解的优化方案在右移策略下的仿真结果(D-st)进行比较。图7中，U-st解集为NSGA-II算法得到的最优Pareto解，可以发现大部分Pareto解集在质量鲁棒性和解的鲁棒性，相较于D-st解都有更好的表现。这说明，在随机不确定性的环境中，提前考虑不确定性对决策的干扰，并通过合适的方法预防不确定性，可以有效地降低不确定性对实际决策的影响，验证算法的有效性。此外，运用多目标优化方法，可以在目标范围内得到多组优化结果，为企业装配环节的调度计划提供更多种优化方案。

图7 D-st和U-st的结果对比图Figure 7 Comparison results of D-st and U-st

3.2 前摄性调度在不同装配场景的适应性分析

为进一步了解前摄性调度在不同客户地资源准备时间的表现以及面对装配过程中不确定性逐渐变大的场景前摄性调度的适应性，设计如下实验。1) 改变项目之间的距离；2) 改变物料齐套时间变化幅度。表2和表3分别为对应场景下，优化得到的Pareto解中质量鲁棒性指标最优解与D-st解比较的实验结果。同时，设计相关指标进行辅助分析：TBT为前摄性调度计划中预留缓冲时间之和，TT为前摄性调度计划中装配组在客户地间往返次数之和；RqU为考虑不确定性的优化方法得到前摄性调度解的鲁棒性指标；RsU为质量鲁棒性指标；RqD为基于确定性环境下的优化方法得到的调度计划(后面称为确定性调度计划)的解鲁棒性指标；RsD表示质量鲁棒性指标。CRq表示前摄性计划相较于确定性调度计划解的鲁棒性指标增长率；C-Rs表示前摄性计划相较于确定性调度计划质量鲁棒性增长率。

表2 改变资源准备时间鲁棒性指标对比Table 2 Comparison of robustness index as resource preparation time changes

表3 改变物料齐套时间偏差鲁棒性指标对比Table 3 Comparison of robustness index as material nesting time deviation occurs

从表2可以看出，随着资源准备时间RTuv从 6、12、24个时间单位增加，前摄性计划相较于确定性调度计划，解的鲁棒性提升百分比从7.57%、2.06%、1.96%逐渐下降，质量鲁棒性提升百分比从6.37%、10.90%、34.71%逐渐增加。此外，受RTuv(资源准备时间)增大的影响，前摄性计划中TT(总的项目的往返次数)指标参数减少，TBT(总的缓冲时间)指标参数减少。分析可见，受资源准备时间变大的影响，在交货期一定的情况下，为保证质量鲁棒性，前摄性计划中缓冲时间的可分配量减少，前摄性计划解的鲁棒性优化空间降低；增大RTuv(资源准备时间)和装配组在客户地间往返成本，减少项目的之间的往返次数，可以让计划更有效地预防不确定性干扰，提高装配计划的稳定性，前摄性计划的质量鲁棒性显著提升，趋势如图8所示。

图8 改变RTuv鲁棒性指标提升趋势图Figure 8 Robustness index improvement trend chart

从表3的实验结果分析，在ΔD(物料齐套时间变化幅度)由4、8、12、16、20、24逐渐增大的情况下，前摄性计划相对于确定性问题下的计划，解的鲁棒性分别提升了3.57%、4.95.%、14.77%、18.00%、19.87%、21.94%，质量鲁棒性也对应提升了4.44 %、7.92%、9.36%、9.63%、14.94%、15.53%。ΔD物料齐套时间变化幅度变大，TBT指标参数变大，适当在前摄性计划中增加缓冲时间，可以更好地解决不确定性因素对前摄性计划执行造成的影响。在保证计划质量鲁棒性的同时，提升计划解鲁棒性指标，趋势如图9所示。

图9 改变ΔD鲁棒性指标提升趋势图Figure 9 Robustness index improvement trend chart

4 结论

本文研究了不确定环境下多地总装作业前摄性调度问题。以多地总装作业为背景定义了本文的研究问题，建立解的鲁棒性和质量鲁棒性的多目标优化模型；提出在前摄调度计划中加入缓冲时间的思路，借鉴抽样仿真的原理和改进型多目标遗传算法对目标问题进行求解；通过提取实际案例进行优化仿真实验。结果表明，本文所提的优化方法，在解的鲁棒性和质量鲁棒性方面都有较好表现。1) 随着客户地间资源准备时间的增加，与确定性环境下优化方法得到的调度计划相比，前摄性调度计划的质量鲁棒性表现更好。2) 在物料齐套时间不确性偏差变化的场景下，与确定性环境下优化方法得到的调度计划相比，前摄性计划有更好的抗干扰能力。

本文通过对不确定性多地总装作业问题的研究，为整线定制企业制定装配计划的制定提出了一整套完整的调度决策方法。未来的研究工作可从以下方面深入。1) 引入惩罚成本，如资源准备时间成本、拖期成本等；2) 引入更多的不确定性因素，如工时的不确定性、装配方式的不确定性等。