考虑工时可变的飞机总装资源配置与作业调度

鲍中凯，裘柯钧，陈 璐

(上海交通大学 工业工程与管理系，上海 200240)

0 引言

飞机总装是飞机制造过程的最后阶段，其主要任务是在整架飞机上安装各种功能装置和系统并进行测试验证。飞机总装阶段涉及大量串行工序，且以手工操作为主，其劳动量约占整个飞机制造劳动量的8%～20%，装配周期约占整个飞机制造周期的25%～40%[1]。然而，在国内，飞机移动式装配生产技术的应用尚未成熟，同时也亟需对总装配线进行合理规划，以适应大规模批产的需求。飞机总装资源配置与作业调度是实现总装生产线合理规划的重要手段之一，其指在生产资源的支持下，通过为各项工序分配资源、安排时间，使得装配工序有序进行的同时，实现成本或时间等指标的最优化。

文献中相关研究主要集中于“飞机装配”这一泛化对象。飞机装配资源配置与作业调度问题常被抽象为一种资源受限项目调度问题(Resource Constrained Project Scheduling Problem, RCPSP)[2]及其变体,包括资源投入问题(Resource Investment Problem, RIP)[3]与资源水平问题[4]等。RCPSP是指将有限资源分配给项目中的各项作业，使得项目总工期最小。RIP则是在RCPSP的基础上考虑工期固定与总资源量可变，并以资源投入成本最小化为目标。在这些基本问题中，有学者还考虑了一些额外因素，如陆志强等[5]在RIP中允许作业可拆分；LU等[6]在RIP中引入了项目分割与资源时间窗的概念；初梓豪等[7]在RCPSP中考虑活动重叠与多模式特征；朱宏伟等[8]在RCPSP中引入了排班约束；CHAKRABORTTY等[9]则研究了作业时间不确定的RCPSP。此外，部分学者依据实际飞机生产线的不同特征，将飞机装配资源配置与作业调度问题抽象为其他不同类型的问题。URGO[10]针对生产资源不确定的飞机装配生产线，将其抽象为一种无等待置换流水车间问题，以最小化生产周期内未完成的工作量。BIELE等[11]针对一种包含并行混流装配线的飞机制造过程，建立了综合考虑成本与时间目标的混合整数规划模型，有效解决了作业分配与排序、时间安排以及人员分配等多个问题。FANG等[12]针对具有多阶段工作站的飞机装配线，通过合理安排作业时间与各阶段工作站工人分配，实现工作站生产周期最小与工作负荷平衡。在优化方法方面，常用求解方法主要可以分为精确算法与启发式方法，其中精确算法主要是分支定界算法及其变体[10,13-14]等;启发式方法凭借自身高效、操作简单以及受模型限制较小的特点，得到了更广泛的应用，包括启发式规则[15]、蚁群算法[16]、差分进化算法[17]、遗传算法(Genetic Algorithm, GA)[18]以及混合算法[19]、自适应技术[20]等改进算法。

飞机总装以手工操作为主的特点使得工序工时受人员分配量的影响较大，在不超出空间上限时，人员数越多，则工时越短。然而，目前考虑工时可变的相关研究还较少。多模式项目调度问题[21]通过定义“模式”这一概念，允许工序具有多种工时和资源需求的组合；XIONG等[22]采用资源比例系数表示各资源对工序的贡献度，建立了工时与所分配资源量的线性函数关系，但都并不能体现飞机总装问题的特点。

本文将飞机总装资源配置与作业调度抽象为RIP，并引入工时可变的因素，最终问题为考虑工时可变的资源投入问题(RIP considering Variable Processing Time, RIP-VPT)。传统RIP中所有工序的工时与人员需求是固定的，只需要协调各工序的开始时间以最小化资源投入总量。RIP-VPT中每个工序工时可变，即具有多种不同的人员分配量，而人员分配的选择直接影响资源投入总量。因此，RIP-VPT的求解是时间与人员分配的协同决策过程，在协调各工序开始时间的同时，还需要考虑各工序参与人员数量的分配。时间与人数之间存在较强的耦合约束关系，且所有工序的人员分配组合方式随着工序数量的增大呈指数型增长，使得问题的求解难度较大，传统的精确算法难以在有限的时间内得到实际问题的最优解，直接采用启发式方法也易出现早熟收敛。在优化算法中嵌入知识是一种应对复杂问题的有效手段[23]，如NASIRI等[24]在作业车间问题中采用数据挖掘方法，从问题实例中挖掘出近似最优解中作业属性与作业顺序之间存在的规则，并将其作为知识应用于初始种群改进；裴小兵等[25]在零等待流水车间调度问题中采用关联规则挖掘优势个体的“优势块”并将其作为知识直接复制到染色体中。

因此，本文将建立RIP-VPT数学模型，并基于GA框架，设计适用于RIP-VPT的编码方式，一种不可行工期修复方法，以及一种包含统计概率知识提取、聚集与分散两条重启操作的工时优选策略，从动态优化过程产生的精英解中挖掘表征较优工时/人员分配与时间安排的概率知识，并将其周期性地应用于种群的重启中，改进后续优化的人员分配与时间安排，以得到成本更低的飞机总装资源配置与作业调度方案。

1 问题定义与建模

1.1 问题描述与假设

RIP-VPT是指在资源约束、空间约束、工期约束及优先级约束等多重约束条件下，以班次作为生产组织形式，通过为所有工序合理分配人员并安排时间，实现人员投入成本的最优化。其中工序是飞机总装过程的基本操作步骤，如飞机顶起、左侧发动机安装等。

如图1所示为RIP-VPT问题的示意图，展示了工序0～工序6的串、并行工作方式。其他假设如下：各任务组的工人不能参与其他任务组的工作；若工序在班次结束时仍未完成，允许工序跨班次执行；工序一旦开工不能中断。

1.2 可变工时表达

飞机总装包括功能装置和系统的安装与测试验证等多种不同类型的工序以及驾驶舱、整流罩、货舱等多种不同的部段，因此，RIP-VPT中每个工序的工作空间容纳能力不同，并且其工时受人员分配量的影响程度不同。本文将工序工时定义为所分配人员数量的线性函数，如式(1)和式(2)所示。

(1)

(2)

1.3 数学模型

基于1.1节与1.2节给出RIP-VPT的数学模型。

(1)决策变量

wj为整型变量，表示工序j的人员分配量；

(2)中间变量

xjd为0-1整型变量，工序j在时间d执行时取1，否则取0。

(3)目标函数为人员投入成本最小

(3)

式中Ur为任务组r的总人数，等于该任务组在任意连续3个班次的人数之和的最大值，

(4)

式中Fgr为任务组r在班次g中的人数，等于该任务组在该班次所有时刻的人数的最大值，

(5)

(4)约束条件

1)工时约束。

(6)

2)优先级关系约束。

(7)

飞机总装工序之间存在严格的优先级顺序，工序j必须在其所有紧前工序完工后才能开工。

3)工期约束。

T-ΔTmax≤Ta≤T；

(8)

(9)

允许实际工期(最后一道工序的结束时间)相比规定工期最多提前ΔTmax(ΔTmax>0)完工。

4)工序实际开始时间和结束时间。

工序j的实际开始时间：

(10)

(11)

工序j的实际结束时间：

(12)

(13)

该约束解释了xjd与实际开始与结束时间的关系，通过式(6)、式(12)与式(13)可以保证工序一旦开工就不会中断。

6)资源约束。

(14)

7)空间约束。

(15)

8)班次数量与工期的关系。

(16)

9)变量可行域。

xjd∈{0,1}；

(17)

(18)

2 集成工时优选策略的改进GA算法

RIP-VPT中人员分配方式直接影响资源投入总量，然而工时/人员分配组合众多，使得工时/人员分配方式的选择成为问题求解的重点与难点之一。鉴于此，本文提出一种集成工时优选策略的改进GA算法(improved GA Integrated with Selection Strategy of operation time, GAISS)，方法框架如图2所示。设计了一种适用于RIP-VPT时间安排与人员分配协同决策的编码方式与交叉变异机制；针对决策过程中常出现违反工期约束的染色体，提出一种不可行工期修复方法；针对人员分配方式的选择问题，提出工时优选策略，从优化过程中实时更新的精英解中提取表征较优工时/人员分配与时间安排的统计概率知识，并基于概率知识对种群执行聚集操作与分散操作，实现种群重启，指导后续优化的人员分配与时间安排，降低问题求解难度，提升优化质量。

2.1 GA应用于RIP-VPT

文献[22]采用包含资源总量列表、资源分配量列表与作业列表的三层编码方式解决考虑多种随机因素的RIP，然而，这种编码方式需要在每次迭代时检查资源总量约束是否被满足，且决策变量较多，在一定程度上增加了优化的复杂度。因此，本文提出了一种包含人员分配量列表与延时时间列表的双层实数编码方式，其中延时时间列表可以增加优化的可变动性[8]。

(2)交叉与变异

随机选择父代中的两条染色体，采用双点交叉产生两条子代染色体(如图3)，实现染色体进化。

从染色体中均匀选择一定数目的工序，并针对不同列表采用不同的变异机制对选中的工序相关变量进行变异。对于人员分配量列表，各工序在由资源约束与空间约束确定的人员分配上下限内随机选择不同的值以实现变异，示意图如图4所示；对于延时列表，设置变异步长对工序延时进行随机增减以实现变异，如式(19)和式(20)所示：

(19)

(20)

其中：lt为变异步长；round为四舍五入取整函数；rand(0,1)为0-1内的均匀随机数。

③聚类分析。经过对各个数据包进行科学的剖析探究，遵照某种规律、特征将其分成不同的组别，不同的小组之间有不同的特征，对这些组内数据进行聚类分析，能够识别出数据的分布特点以及疏密状况，将具有不同特性的数据关系反映出来。

(3)适应度评价与个体选择

计算每个染色体对应人员投入成本。采用二元竞赛的选择机制[26]，通过对比选择两条染色体中的更优者进入下一代，直至下一代染色体数目达到种群规模。

2.2 工时优选策略

本文提出了一种工时优选策略，通过从具有较低成本的精英解集中提取关于工时的统计概率知识，实现工时优选，并将该知识应用于针对较劣解的重启操作，改进后续优化方向，降低RIP-VPT求解的复杂性。

2.2.1 基于统计概率知识的工时优选

从算法优化过程产生的精英解中获得知识载体，从知识载体中提取统计概率，将统计概率作为知识的表示方式。

定义2精英解。创建历史最优解存档，选择历史最优的M1个染色体与当代最优的M2个染色体进入候选精英解池，再从候选精英解池中进一步筛选出最优的M3个染色体作为最终的精英解。

定义3知识载体。工序工时的选择本质上就是人员分配量的选择。此外，最终方案是由人员分配量与工序的延时时间共同决定的，同时考虑到延时时间取值变化范围较大，且大量计算实验表明最终方案中大部分工序是不产生延时的，因此将工序的人员分配量与表征是否不延时的0-1逻辑变量作为知识载体。

按式(21)得到精英解在知识载体各变量上选择某个具体取值的统计概率：

(21)

式中：P为概率；x为知识载体中的某个变量；val为x的某个取值；Nx=val为在变量x上取val的精英解个数；Ntotal为精英解总个数。

图5与图6分别展示了统计概率知识创建的过程(Ntotal=5)，精英解越倾向于选择某个取值，则对应取值的概率越大，例如0.8是指存在80%的精英解选择了对应取值。最终得到各工序人员分配量选择的概率向量及非延时概率，基于这种概率知识实现对较优人员分配/工时组合方式以及延时状态的优选。

2.2.2 基于工时优选的重启操作

上述统计概率知识总结了精英解在选择人员分配/工时，以及判断工序是否延时方面的历史经验，基于此将该知识应用于两条重启操作。为适应动态优化过程，需要周期性更新概率知识与执行重启操作。此外，选择当代最差的一半染色体作为重启对象。

(1)重启操作1——聚集操作

基于概率大小生成新染色体替换所有重启对象，从而产生部分聚集在精英解附近的新解，增强对优选区域中人员分配与延时方案的勘探能力。

如图7所示为针对人员分配的聚集操作，各工序基于人员分配概率向量建立轮盘，采用轮盘赌生成新染色体的各工序人员分配量。其中轮盘中的数值为选择不大于对应人员分配量的概率。例如，对于工序2，给定一个随机数，当随机数处于[0，0.2]时，选择第1种人员分配量；当随机数处于(0.2，0.6]时，选择第2种人员分配量；当随机数处于(0.6，1]时，选择第3种人员分配量。

针对延时时间的聚集操作，首先按照非延时概率大小选择是否延时。若不延时，则新染色体对应工序的延时为0；否则，从精英解对应工序中选择一个延时时间作为新染色体的延时时间。

(2)重启操作2——分散操作

为了避免直接采用聚集操作导致种群多样性下降，同时增强算法的全局搜索能力，在聚集操作的基础上选择部分重启对象执行分散操作。

针对人员分配量，基于文献[27]的对立学习思想，选择染色体中的部分工序按照式(22)执行分散操作，采用式(23)对可能由式(22)产生的不可行人员分配量进行修正。通过对立学习，可以扩大算法的搜索范围。

(22)

(23)

2.3 可行化策略

优化过程中可能出现违反工期约束的染色体，因此提出了两条可行化策略。

2.3.1 惩罚函数法

(24)

其中：P1为违反工期约束的罚函数，α1为罚因子，β1为罚指数。

2.3.2 不可行工期修复

采用惩罚函数法可以去除不可行解，但是无法避免不可行解的产生，从而可能降低算法优化效率。因此，本文提出一种不可行工期修复方法以保证优化过程中的所有染色体都处于可行域内，具体步骤如下;

步骤1将连接开始与结束工序的所有路径中工时与延时时长之和的最大者作为关键路径(若有多条，从中任选一条)。

步骤2由关键路径确定当前染色体的实际工期。

步骤3调整关键路径时刻表。

最后计算调整后关键路径上所有工序的实际开始与结束时间。

3 优化结果分析

3.1 算例生成

某客机总装制造厂采用移动式装配生产线，包含3个工位以及动力燃油组、环控组、航电组等多个任务组，每个工位又包含两个模块，分别负责不同的装配任务。由于飞机总装具有严格的串并行执行顺序，各任务组所负责工序分布在不同工位/模块中，不同工位/模块对任务组的需求也是不同的。本文以一个工位模块的装配过程为例，由于文献中没有RIP-VPT的基准算例，按表1所示规则随机生成多种不同工序数量的算例。

表1 算例生成规则

此外，规定工期的生成方法：在不考虑任何延时的情况下，各工序取最少人员分配量即最长工时，并计算关键路径长度T′。选择不小于T′、距离T′最近且能被8整除的工期作为规定工期。

3.2 实验设置

将不集成工时优选策略且采用惩罚函数法的GA记为GA1，将不集成工时优选策略且采用不可行工期修复的GA记为GA2，通过对比GAISS与Gurobi求解器、GA1、GA2的优化结果，验证GAISS的有效性。其中每个算法均运行10次，Gurobi版本为V9.0.3。GA种群规模为50，交叉概率取0.9，变异概率取0.4。GAISS中的重启周期为每隔100代。针对工序为6与8的算例、工序为10的算例、工序在30以上的算例，最大迭代步数分别为100、200与800。在工序为6和8的所有算例中，GAISS的重启操作不会被触发，优化性能等同于GA2，故不再运行。

评价指标如式(25)～式(27)所示，其中SGAISS、SGA1、SGA2分别为GAISS、GA1与GA2的平均优化结果，SGurobi为Gurobi优化结果。G1～G3为GAISS相对其他各方法的相对偏差；针对工序为6和8的算例，将SGA2代入SGAISS。G1～G3若为负，其绝对值则是优化质量的相对提升比例。

(25)

(26)

(27)

此外，采用Python 3.7编写算法程序，计算机处理器为Intel(R) Core(TM) i7-5500U CPU @ 2.40 GHz 2.39 GHz，内存为8 G。

3.3 算法对比分析

6～10工序数量的小规模算例优化结果如表2所示，其中Tc为CPU计算时间。可以看出，Gurobi能在较短的时间内得到最优解，验证了本文模型的正确性。对于6与8工序，GA2也能在较短的时间内给出大多数算例的最优解，最大相对偏差仅为1.25%；与GA1相比，GA2在多个算例上更优，优化质量提升了0.40%～6.90%，验证了不可行工期修复方法能有效提升算法对可行域的搜索效率。对于10工序，GAISS在3个算例上得到了最优解；由于规模较小，搜索空间有限，GAISS与GA2的优化质量几乎相同，只在1个算例中提升了0.92%；与GA1相比，GAISS将优化质量提升了1.40%～3.88%，再次验证了不可行工期修复方法的有效性。

表2 小规模算例优化结果对比

30～50工序数量的中大规模算例优化结果如表3所示，SGurobi为Gurobi求解3 600 s得到的上界，其中针对40工序的算例3未能提供可行解。GAISS在多数算例上的结果均优于Gurobi的上界，优化质量提升最大达到了58.55%，最小为3.15%，只在30工序的算例1和2与40工序的算例5中，GA-SR的结果相对较差，相对偏差在3.36%～6.12%之间。与GA2相比，GAISS在所有算例中均更优，提升了0.54%～7.38%，从而验证了工时优选策略能有效表达RIP-VPT问题精英解中存在的知识，基于工时优选的重启操作能有效增强算法搜索能力。与GA1相比，GAISS将优化结果提升了7.76%～15.62%。整体上，3种算法的计算时间处于一个量级上，其中GA1相对最短，GAISS相对最长，但是均能在13 min内计算结束。

表3 中大规模算例优化结果对比

将算法应用于具有140工序的大规模算例，对比结果如表4所示。GAISS的优化结果分别较GA2与GA1提升了8.16%和10.41%。由于该算例可行域较大，使得GAISS求解时更能发挥工时优选策略的作用，提升效果更为明显。

表4 140工序优化结果对比

从计算时间上来看，GAISS相比GA1与GA2分别增加了11.05%、3.96%。为了进一步分析优化效率，给出了如图8所示的平均优化结果迭代曲线对比。可以看出GAISS的优化效率实际上更优，在第200代左右就得到了GA1的最终解，在300代内就得到了GA2的最终解。同时，也再次验证了GAISS在求解RIP-VPT上的优越性。

3.4 不同工期对优化结果的影响

工期约束是RIP-VPT模型的重要组成部分之一，以下分析不同规定工期对优化结果的影响。

针对140工序的大规模算例，在原规定工期T的基础上产生4个新的规定工期0.8T、0.9T、1.1T、1.2T。针对各工期采用GAISS分别求解10次，平均优化结果对比如图9所示。

图9中：曲线1与曲线2分别为不同工期下的人员投入成本与平均每班次人数。可以看出，人员投入成本和平均每班次人数均随着规定工期的增大而减少。这是因为为了适应更小的工期，需要增加人员分配量以减小工序工时，以及增加“并行”执行的工序，以使得时间安排更加紧凑，从而导致较小的工期具有较大的人力资源需求；而随着工期的增大，时间安排越来越宽裕，“并行”执行的工序更可能转为“串行”执行，且对减小工序工时的需求也越来越小，从而使得较大的工期具有较小的人力资源需求。

因此，在飞机总装资源配置与作业调度中，企业需要权衡规定工期与人员投入成本之间关系，在可接受人员投入成本下规定总装工期。

4 结束语

本文面向实际飞机总装过程建立了RIP-VPT数学模型，提出了一种集成工时优选策略的改进遗传算法(GAISS)，其中设计了包含人员分配与延时时间的双层实数编码，设计了包含周期性统计概率知识提取、聚集与分散重启操作的工时优选策略，改进了算法对工时/人员分配与延时方案的选择，最后还设计了不可行工期的修复方法以保证染色体始终可行。

通过多种规模算例的优化，GAISS能将优化质量提升0.40%～15.62%，验证了GAISS求解RIP-VPT的优越性，是一种能实现飞机总装配线合理规划的有效方法。其中工时优选策略有效增强了算法搜索能力，在140工序大规模算例中取得了8.16%的提升效果，而不可行工期修复方法相比惩罚函数法也能有效提升算法优化效率。此外，通过数值实验还发现规定工期越小，人员投入成本越高，启发企业在决策时需要权衡规定工期与人员投入成本之间的关系。然而，本文假设每个工人完全相同，但是实际中每个工人的工作效率可能存在差异，因此，如何解决考虑工作效率差异的飞机总装资源配置与作业调度问题，以及工作效率差异性对优化结果的影响将是未来的重要研究方向之一。