考虑协作度的双人异步并行拆卸序列规划

贾宝惠，任 帅，卢 翔

（中国民航大学航空工程学院，天津 300300）

1 引言

后勤保障分析国际程序规范（S3000L）明确要求产品在设计阶段应考虑在运营阶段和报废阶段的拆卸，这要求在技术出版物中必须有相关拆卸流程，进行拆卸序列规划（Disassembly Sequence Planning，简称DSP）设计阶段有助于提高产品维修性且可对技术出版物进行有效验证；运营阶段或报废阶段可有效提高工作人员效率，降低维修成本。

DSP通过产品零部件的约束关系得到合理的拆卸顺序，以达到“最佳目标”，此目标可为拆卸成本最小、拆卸收益最大、对环境污染最小等。DSP问题随着产品规模增长，拆卸序列将爆炸式增长，求解难度大。因此，大量学者开展算法研究，提高求解效率，例如蚁群算法［1］，人工蜂群算法［2］、遗传蝙蝠算法［3］但仅可进行单人DSP。工程实践中，经常会遇到大型复杂产品，例如飞机的拆解，一般需要几十人甚至几百人共同进行工作，因此多人并行DSP 问题日益重要。文献［4］提出了基于模糊粗糙集的并行DSP，可快速获得近似最优解。文献［5］探讨和确定操作者最佳数目，并提出异步并行DSP。文献［6］建立可变序列矩阵搭建了串行与并行拆卸的桥梁。但上研究均是单个部件只能被单个执行者进行拆卸，未考虑执行者之间的协作关系。文献［7］提出了多人协作的并行DSP数学模型，但不能实现异步并行，需约束多人若要协作完成某操作时，必须同时开始，同时结束，而不能实现一人先开始，另一人中途加入。

综上，因此，现有的多人DSP并未考虑到协作效率，且由于优先约束关系的存在，有人员闲置的情况，不能真正实现异步并行，使得协作效率较低。基于此，这里提出协作度概念，建立数学模型，实现两人尽量少间歇或无间歇地异步并行拆卸序列提高拆卸效率，降低人力成本。

2 双人协作异步并行DSP

2.1 拆卸优先图

这里所涉及DSP是完全拆卸，其目标函数为拆卸时间最短，选用较简单的拆卸优先图进行表达，如图1所示。

图1 拆卸优先图Fig.1 Disassembly Priority Diagram

A、B、C、D、E、F分别表示该产品的组成构件，有向箭头代表约束关系，表示各部件优先约束关系，如F→A表示在拆卸A之前，必须先拆卸F，F为A的优先操作。不同于前人研究的表达，这里所采用的拆解优先图使用分层表达，A为第0层，B、C为第一层，D为第二层，E作为第三层，F为第四层，通过分层表达便于对序列的“合规化处理”“，合规化处理”即为对随机序列进行处理使其满足优先约束。

DSP为离散组合优化问题，基于拆卸优先图模型，可将此问题描述为：

产品可拆卸单元为N个，每次仅能拆卸其中一个，所求序列应该满足拆卸优先关系，并且每个顶点都须遍历且只能遍历一次。A-F按1～6进行排列，拆卸优先矩阵R，如式（1）所示。

式中：Rrc—矩阵R的第r行第c列的数值4 即为拆卸优先矩阵层数。通过搜索优先矩阵可以将随机序列进行合规化处理，合规化处理流程图，如图2所示。

图2 合规化处理流程图Fig.2 Flow Chart of Compliance Processing

2.2 建模准备

DSP中无法避免出现操作者存在闲置时间，例如某产品拆卸序列如下：操作者1：123；操作者2：45。若零件4受零件1的优先约束，则在操作者2拆卸零件1时，操作者1将被闲置。若有足够的空间可容许两个人同时拆卸零件1，既可以节省二人的体力，也可有效减少工作总时间。因此下面提出异步并行协作，解决此问题。

协作是指两人一起完成操作，可分为同步并行与异步并行，同步并行是指两操作者同时开始和同时结束对同一零件的操作；异步并行是指在一人开始某零件的拆卸工作之后，另一人可以加入此人的拆卸工作中。然而两人同时进行一个操作时其完成时间不一定为原操作时间的一半，因此在建立模型时需考虑二者协作效率对模型的影响，在此引入变量“协作度-εi”，是两人在同时进行某零部件拆卸时的协作效率，影响两人同时进行同一零部件的拆卸时间=ti×εi。i为零件号，ti为零件拆卸时间，为零件在两人协作下的拆卸的时间。

协作度主要影响因素有拆卸容纳人数、零件体积、零件质量、连接件数量、是否可用工装等。其值数据，如表1～表3所示。

表1 搬运重物受重量影响量化标准Tab.1 Quantitative Criteria for Removal Rod Parts Affected by Weight

其中，m—搬运物体质量；L—搬运杆件的长度；j—连接件数量。表1确定了各搬运重物受重量影响的量化标准边界，若两人同时进行较轻物体的搬运工作，则时间搬运时间不会变化；若使用工装，则需要准备和撤回工装的操作，因此协作度会有所增大；随着物体重量的提升，单人搬运的困难程度继续增大，协作度随之减小。同理，表2确定了搬运杆件的长度对协作度的影响；表3确定了连接件数量对协作度的影响，若连接件仅为1，则协作度为1，随着连接件数量增多，连接件可由两个人同时进行连接件的拆卸，协作度可确定为（0.5～0.6），若使用工装，协作度将有所减小。以上3个表格提出了协作度的量化方法，根据工人经验进行确定。

表2 搬运杆件受长度影响量化标准Tab.2 Quantitative Criteria for Removal Rod Parts Affected by Length

表3 协作度受紧固件数量影响量化标准Tab.3 Quantitative Criteria for Number of Fasteners

组合任务可以将搬运任务的协作度与拆卸任务协作度进行加权平均，权重考虑工作时间占比。

2.3 模型的数学描述

cti：无协作的零件拆卸开始时间；

sti：无协作的零件拆卸结束时间；

cti’：协作下的零件拆卸开始时间；

sti’：协作下的零件拆卸结束时间；

AS(i)：i的优先约束零件，可从拆卸优先矩阵中获取；

此模型的拆卸目标函数如下：

拆卸优先约束如下：

某零件i由单人拆卸，则有：

若零件i的拆卸工作由2人同时开始进行，则有：

假设操作者1操作序列为m1，m3，操作者2的操作序列为m2，m2是m3的拆卸优先约束，且stm1

式（2）～式（7）从数学上对模型进行了描述。

3 遗传-粒子群混合优化算法

3.1 算子编码、解码及适应度函数

将采取双链结构编码，包含2个子序列。令v={v1，v2}表示双链拆卸序列。其中v1={s1，…，sj，…，sN}为操作序列，sj表示操作，n=1，2，…，N；v2={q1，…，qn，…，qN}，qn表示v1链中的第n个操作由第qn操作者操作，qn=1，2，…，Q。q1=1，Q为操作者人数，则表示s1操作由操作者1完成。

首先通过1.1节中的方法对v1序列进行“合规化处理”保证序列满足优先约束。

为计算适应度值，设计适用的解码方案，流程，如图3所示。

图3 解码流程图Fig.3 Decoding Flowchart

图中：B—操作分配矩阵，例如B=［1，3，5；2，6，0］，说明操作者1进行1、3、5操作，操作者2进行2、6操作；find函数功能：找到向量Y中所有大于零元素的位置；ct、st—操作开始时间与结束时间矩阵，1*N；t—操作时间矩阵，1*N，各操作在单人操作下所需时间；为矩阵B的列数；F—零件的优先约束向量；q—第q个操作者。

步骤一：根据双链染色体建立矩阵B；

步骤二：ct=st=0，建立操作时间矩阵t；

步骤三：判断操作者q拆卸的第i个零件是否被约束于别的零件。则比较操作者q的第i-1个零件的结束时间与其所有优先零件的结束时间，最大者为i的开始时间，i=1则将第i-1个零件结束时间视为0；否，将其开始时间设定为前一零件的结束时间；

步骤四：计算上述零件拆卸结束时间，并更新约束矩阵，使该操作不再作为其他零件的约束零件；

步骤五：q=q+1；

步骤六：当q达到总人数时，i+1；

步骤七：重复步骤三至步骤六，当i>b时，返回步骤一；

步骤八：重复步骤三至步骤七N次。

至此，已求出所有零件在不考虑异步并行情况下的拆卸开始及结束时间。然而，这并没实现异步并行，求解考虑协作度的异步并行DSP，需对以上结果进行处理，步骤如下：

步骤一：查找序列中是否存在操作者具有闲置时间；

步骤二：确定此段闲置时间另一操作者所拆卸零件；

步骤三：计算二人协作下所节省的实际。

步骤四：更新，并重复以上步骤。

在算法中实现，流程参照图，如图4所示。

图4 考虑协作处理流程图Fig.4 Processing Flowchart Considered Collaboration

所求st中最大值即为最后一个拆卸零件的结束时间，也是适应度函数。图中：Q—人数为2；k、l—操作者的第k、l个操作；K、L—各操作者的操作个数；ts—协作操作节省的时间；Ts—协作操作节省的总时间；ε—协作度；ct、st—操作开始时间与结束时间矩阵；ct’、st’—协作下操作开始时间与结束时间矩阵，1*N。

3.2 遗传-粒子群混合算法

粒子群算法（PSO）：

粒子群算法多适用于连续组合优化问题［8］，通过PSO 求解DSP这种离散问题，需通过以下方法将其进行对应。

在产品模型基础上，产生多个粒子，每个粒子由1-N的自然数组成，N为可拆卸零件个数，即可构成一个粒子群。

前人将速度取值空间定为0，1来代表至下一代粒子元素是否发生变动。但是通过此方式进行粒子的移动会导致产生不合规的粒子，需要再对粒子进行合规划处理，这里取消粒子群中速度概念。但是粒子群算法是将粒子的方向朝着更优的粒子移动，取消速度概念，但在宏观上依然是粒子群算法行为。

遗传算法（GA）：

遗传交叉算子和变异算子是遗传算法的重要操作［9-11］。在此问题的求解中若对v1链进行变异操作，则序列则需重新进行合规化处理，可能导致变异操作无效，所以对v1链只进行交叉操作。传统的交叉变异算子会导致原本合规的父代染色体得到不合规的子代染色体。因此传统的交叉算子将不适用。

（1）交叉是GA更新和探索解空间的关键操作。传统的交叉算子可能会导致序列错误，比如父代1：FEDBAC 与父代2：FECDBA在第3个点交叉则产生FECBAC与FEDDBA。

为保证基因的完整性，将使用优先选择交叉方式进行交叉［12］：生成子代掩码C1，为1-2的随机排列，②C1中第一个数字是1，子代C2第一个基因从F1的第一个基因提取，并删除F1与F2 中的该基因。③第二个数字是2，C2 提取父代2 的第一个基因，并删除F1与F2的该基因。④重复步骤可得出新染色体C2。

（2）变异算子针对v2进行，这能使在同样的v1序列下，得到不同的人员工作规划。

混合算法：

粒子群中若产生相对较优的粒子，粒子都会朝其进化，若此粒子并非全局最优，且全局最优的方向与此粒子的方向相反，则无法找到全局最优解，使得局部搜索能力较强，对求解质量要求不高时，该算法可高效求得高质量的解，但非最优解。

另外DSP是离散型数值寻优问题，且其序列有所约束，这容易导致初始种群本身就很有可能已散落在局部最优解的而导致无法寻找到全局最优解，从而得不出最优序列。

遗传算法通过变异可提高其全局搜索性，因此将遗传算法与其进行结合，可以增强其全局搜索能力，提出了GA-PSO混合的优化算法。

GA-PSO优化算法流程，如图5所示。所提的混合算法是从用遗传算法来模拟粒子群算法的角度出发，重构遗传算法交叉及变异算子。从宏观上来看，其行为是粒子群算法；从微观来看，其行为是遗传算法，从而构成GA-PSO混合算法。

图5 GA-PSO算法求解流程Fig.5 GA-PSO Algorithm Solution Process

4 实例验证及分析

以文献［13］的飞机起落架为例，以文中方法求解最优拆卸序列。飞机起落架结构复杂，包含15个零件，其伴随着大量的紧固件，在拆卸优先图中可将紧固件和其作用对象绑定，从而简化拆卸优先图，如图6所示。

图6 起落架拆卸优先图Fig.6 Priority Diagram for Landing Gear Disassembly

借鉴文献的研究成果，对各个零件的拆卸时间进行估计［14］，并根据专家经验给出各零件的拆卸协作度，零件拆卸时间及协作度，如表4所示。

表4 各零部件拆卸时间（单位：秒）Tab.4 Disassembly Time of Each Part（Unit：s）

分别通过现有方法和考虑协作度的双人异步并行DSP对起落架拆卸序列进行求解，求解结果，如表5所示。为便于观察，将结果绘制为甘特图，如图7所示。

表5 起落架拆卸方案Tab.5 Landing Gear Disassembly Scheme

图7 拆卸序列规划Fig.7 Disassembly Sequence Planning

易看出在未考虑协作度情况下，两操作者分别操作各自划分的序列，并无交叉；在考虑考虑协作度的双人异步并行拆卸序列中，对零件37和零件82进行异步并行拆卸，对零件58进行同步并行拆卸。

在操作者2完成零件22的拆卸之后，由于37零件对38零件有优先约束，因此操作者2本应在操作者1完成37零件的拆卸后再开始工作，时间闲置。考虑异步并行，操作者2加入与操作者1共同拆卸37零件。节省了操作者2的闲置时间，提高了效率。

飞机维修最主要的成本就是人力成本，对比得，前者拆卸时间为2412s，而这里所用方法拆卸时间为2349.6s，节省2.5%，这对于民航业大量的维修任务量来说，可有效地减少拆卸工作损耗时间，提高拆卸效率，降低人力成本。

另外，算法训练过程，如图8所示。种群规模为10，算法可以在15代以内收敛至最优。

图8 算法训练过程Fig.8 Algorithm Training Process

5 结论

（1）通过协作度概念的提出，建立了考虑协作度的双人异步并行DSP，模型允许操作者异步并行拆卸零件，提高了拆卸工作的灵活性，使拆卸工作更加高效。

（2）建立了适用的算法编码与解码方案，并结合遗传与粒子群算法，设计了高效的求解算法。

（3）实例验证了这里所提出双人协作异步并行DSP更加节省时间，可以为双人拆卸问题提供更加高效的方案，并且为将来实现考虑协作的多人异步并行拆卸打下了基础，对维修人员进行大型部件拆卸提供了理论依据。