PBS缓冲区部分车道中断的车辆应急调度研究

Research on Vehicle Emergency Scheduling with Partial Lane Interruption in PBS Buffer

摘要: 为缓解产线压力及适应订单随机性，汽车制造企业往往会在涂装车间与总装车间中设立涂装车身缓冲区(Painted Body Storage-PBS)。以最常见的线性缓冲区作为研究对象，针对其中可能出现的部分车道中断的突发情况，为提高产线的柔性，降低企业的损失，提出了一种通过遗传算法来对PBS缓冲区的出库和入库进行“自适应循环优化”的实时动态调配方法。首先，利用车身信息、位置以及出库计划将可运行的待出库车身构建模型并通过遗传算法求解。然后，根据求解出来的出库模型结果对未入库车身进行构建匹配模型，获得的多种入库模型再通过融合启发式规则的遗传算法来进行确定入库以及得到之后的出库模型，从而形成一种出入库“自适应循环优化”的应急调度方案。最后，通过案例分析验证了该方法的有效性。

Abstract: In order to alleviate the pressure on the production line and adapt to the randomness of orders, automobile manufacturers often set up Painted Body Storage (Painted Body Storage-PBS) in the paint workshop and the final assembly workshop. Taking the most common linear buffer as the re-search object, in response to the unexpected situation where some lanes may be interrupted, in order to improve the flexibility of the production line and reduce the loss of the enterprise, a real-time dynamic allocation method of “adaptive cycle optimization” for the outbound and inbound PBS buffers through genetic algorithm is proposed. First, use the body information, location, and out-bound plan to build a model of the runnable outbound body and solve it through genetic algorithm. Then, according to the solved outbound model results, a matching model is constructed for the unwarehousing body, and the obtained multiple inbound models are then determined through the genetic algorithm fused with heuristic rules to enter the warehouse and obtain the subsequent outbound model, thereby an emergency dispatching plan of “adaptive cycle optimization” for ware-house entry and exit is formed. Finally, the effectiveness of the method is verified through case analysis.

1. 引言

当前，汽车制造行业的市场愈发火热，不断增长的需求量对于车企的生产规模和运营规模的要求愈发高。车企在涂装车间和总装车间中越来越频繁地使用PBS (Painted Body Storage)缓冲区来进行生产调度，缓冲区的规模也越来越大，其中尤其以线性缓冲区的应用最为广泛。

因此，涂装缓冲区中发生突发情况以及其中的设备故障等事件的概率也会提高。同时，车企为了方便管理，往往会在同一条车道上分配相同“属性”的车身，即相同颜色的车身会在同一条车道上运行。当发生中断问题的时候，会使得涂装缓冲区中的部分属性车身无法输送至总装车间。

当某个车道因为突发情况从而导致了停止运行，那么缓冲区内的车辆出入库将会受阻，对于总装车间来说会“无事可干”，与此同时，对于涂装车间来说，它的出口将会逐渐形成大规模“拥挤”。如果事态过于严重的话，会导致强制暂停整体生产线的运行。而且，停滞的时长无法得知，造成的经济损失也是不可估量的。对于产线整体的统筹规划是需要将风险因素考虑在内的，因此，缓冲区的车辆应急调度研究是十分有必要的。

目前，对于PBS缓冲区的研究主要集中在排序和调度策略以及车漆缺陷和紧急订单所导致的应急调度，如Hottenrott等 [1] 通过车辆故障概率测序方法和领域搜索对车辆油漆缺陷、和零部件缺失问题进行了研究；Jw等 [2] 将涂装车间、涂装缓冲区、总装车间三者进行了一定的结构化，并通过元启发式算法来实现涂装车间耗材最小化和调整装配车间的零件使用；Tian等 [3] 通过小世界算法，旨在建立一种高效的数学模型，来降低加班时间和闲置时间；Günay等 [4] 开发了一个混合模型，以确定存储和检索系统重测序存储缓冲区备用车辆的最佳数量，从而提高计划序列实现比；刘俨后等 [5] 通过启发式算法解决了紧急订单优先交付和生产优先等问题，为多品种类的混装线生产提供了参考。而目前很少有学者针对缓冲区本身的结构损坏后，如何实施紧急调度的问题进行相关研究。

引起缓冲区车道中断有诸多因素，包括：机械方面的零部件磨损使得机械结构的自由度达不到原有等级从而失效，电气方面的线路负荷过大导致烧坏从而无法运行，通信方面很可能会受到环境干绕，使得生产序列指令下达不到执行器等原因，即不可能做到完美的预防。所以，为了降低事故发生后的影响力以及造成的经济损失，实现动态调度 [6] ，本文从缓冲区结构本身的特性出发，来进行相关的设计，主要是采用将生产计划分解的方法，构建出入库模型。

遗传算法因其高效、并行、全局搜索的优点，在生产调度、求解最优解问题方面有广泛应用，因此，本文拟利用遗传算法和启发式规则 [7] 来求解出最优调度结果。

2. 问题描述

汽车制造企业里应用的PBS缓冲区往往以线性缓冲区为代表，虽然它结构简单，操作方便，但是，由于它先进先出的结构特性会导致当中断发生时车辆调度有一定难度，线性缓冲区结构如图1。

Figure 1. Linear buffer

图1. 线性缓冲区

图中每条车道上每辆车身的位置排列以 $\left\{1,2,\cdots ,n-1,n\right\}$ 表示，每条车道的位置排列以 $\left\{1,2,\cdots ,m-1,m\right\}$ 表示，即每辆进入PBS缓冲区的车辆都会有一个位置编号方便统计信息如 $\left\{11,12,\cdots ,mn\right\}$，移库车道的车身位置排列按照 $\left\{L_1,L_2,\cdots ,L_n\right\}$ 分配，涂装车间输出车道的车身位置排列按照 $\left\{R_1,R_2,\cdots ,R_n\right\}$。

本文现针对当某条车道因为突发状况从而导致了停止运行的情况，制定出如何让剩余可运行车道分担中断车道的传输任务，即让中断车道的属性分散赋予到其他可运行车道里面的方法。同时通过算法将出入库的调配更加优化。

假定条件如下：

1) 缓冲区属于正常的“非拥挤”状态，有一定的空位；

2) 其中某一条车道发生故障，导致这一条车道无法进行正常的生产流程；

3) 发生故障后生产计划将在中间某一时刻无法执行，即无法提供故障车道中的相同属性车辆；

4) 移库车道之前为空。

3. 模型

遗传算法的起源可以追溯到20世纪60年代初期，它是根据自然界中生物的进化规律提出的 [8] 。模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向，最终寻找到全局最优解。

其中，种群的设立、适应度函数的建立以及选择、交叉、变异是构成该算法的核心部分 [9] 。建立出的种群质量会直接影响整体算法的运行效率。同时，交叉、变异的方法选择也会大大影响效率。

在模型建立上，将出库模型和入库模型在一个固定循环周期内进行合并得出最优模型。其数学模型如下所示：

3.1. 出库模型

出库的制定是为了能够以最小移库次数将现有的车辆尽快的移库或者是到达总装车间，减少PBS缓冲区现有的负荷。其数学模型如下：

$f\left(i\right)=\min y_i$ (1)

式中， $f\left(i\right)$ 表达每一个出库方案的最小适应度，即最少移库次数。

$y_i=\{\begin{array}{ll}{y}_i=0_{{}_{{}_{}}}\hfill & j=0\hfill \\ y_i\hfill & d_{\left(x_{ij},T_{ij}\right)}=p_{j-y_{\text{i}}}\hfill \\ y_i+1\hfill & d_{\left(x_{ij},T_{ij}\right)}\ne p_{j-y_i}\hfill \end{array}$ (2)

式中， $i=1,2,\cdots ,N$ ；N表示种群数量， $j=1,2,\cdots ,M$ ；M表示出库方案中车辆的数量，d是统计缓冲区内现有的车身信息，其下标 $\left(x_{ij},T_{ij}\right)$ 分别表示哪一个车道的具体位置；p是计划中的车身信息，其下标 $j-y_i$ 是相关序列位置。该式用来判断p与d的信息是否符合，不符移库数加一。

$C_i=\{\begin{array}{ll}{C}_i=0_{{}_{{}_{}}}\hfill & j=0\hfill \\ C_i+1\hfill & d_{\left(x_{ij},T_{ij}\right)}=p_{j-y_{\text{i}}}\hfill \\ C_i\hfill & d_{\left(x_{ij},T_{ij}\right)}\ne p_{j-y_i}\hfill \end{array}$ (3)

该式与(2)的功能相反，即比较p与d的信息，如果相同那么完成计划数C加一。

$T_{ij}=\{\begin{array}{cc}{a}_{ij}=b_{ij}=c_{ij}=\mathrm{...}=0& j=0\\ a_{ij}+1& x_{ij}=1\\ b_{ij}+1& x_{ij}=2\\ c_{ij}+1& x_{ij}=3\\ ⋮& ⋮\end{array}$ (4)

其中，a_ij、b_ij、c_ij分别表示各个车道的某一辆车的序列位置。

$a_{ij}\le B_{\text{1}};b_{ij}\le B_{\text{2}};c_{ij}\le B_{\text{3}}\cdots$ (5)

上述式中， $B_{\left(1,2,\cdots ,m\right)}$ 是每条车道的现存车辆的数量。

$0\le y\le D;0\le C\le E$ (6)

式中，D是移库数量的最大值,一般设为缓冲区现存车辆总量，E生产计划数。

3.2. 入库模型

通过启发式规则加快优秀模型的建立 [9] ，入库是根据出库方案执行后可运行车道剩余的车身信息以及移库车道里的现存信息和总装计划未执行的信息相互结合从而构造一个新的模型，同时，为了保证故障修复后方便管理者继续操作，其中沿用了原有的相同车身属性放置在统一车道的规则。其数学模型如下：

$G=\{\begin{array}{cc}1& S_k=Y_{\left(1,2,\cdots ,Ln\right)}\\ 0& S_k\ne Y_{\left(1,2,\cdots ,Ln\right)}\end{array}G=\{\begin{array}{cc}1& S_k=h_{\left(1,2,\cdots ,Rn\right)}\\ 0& S_k\ne h_{\left(1,2,\cdots ,Rn\right)}\end{array}$ (7)

式中，S_k是每条车道的相关属性， $k=1,2,\cdots ,m$ ； $Y_{\left(1,2,\cdots ,Ln\right)}$ 是移库车道的相关序列上的属性信息， $h_{\left(1,2,\cdots ,Rn\right)}$ 是从涂装缓冲区过来的车身序列的相关属性信息。的相关属性信息。该式用以匹配车道属性和车身属性。

$\min \left\{B_1,B_2,\cdots ,B_m\right\}$ (8)

该式用以选择各车道中存储车辆最少的一个车道，之后用以存放未入库的车身。

4. 算法

本文采用的是一种针对突发情况的应急调度，通过遗传算法(主要工作方式如图2)，并且在实现算法的过程中通过启发式的规则来使得初始化种群进一步优化。

Figure 2. Genetic algorithm process

图2. 遗传算法流程

根据上述的相关出入库模型，现提出算法步骤如下：

1) 首先需要将收集到的实际数据转变成相应的数学表示，对通过信息收集得到的PBS缓冲区现有的各个车道的车身位置、属性信息、总装车间未完成的生产计划、从涂装车间出来和移库车道里的车身位置、属性信息，和即将进入PBS缓冲区的车身属性等信息进行数字化。

2) 初始化种群，本文是将车身属性、位置作为基本元素，同时，将PBS缓冲区中还可以正常运行的各个车道的出库顺序组成一个初始的染色体。并以此为基础构建一定规模的种群来实现算法。

3) 计算适应度值，将构建出来的种群中每一条染色体通过设定好的适应度函数计算出结果，如公式(1)所表示计算出每个方案的移库次数，并将这作为评价的参量。

4) 根据计算出来的适应度值来进行选择，选择策略使用“锦标赛策略” [10] ，该策略是可以在保持一定随机性的同时又可以选择出部分适应度好的染色体来赋予新的父系染色体，母系染色体则从种群中随机选取。

5) 根据交叉率Pc，将父系的染色体和母系的染色体进行交叉从而产生新的个体。采用两点交叉的方式来将染色体基因序列进行交叉变换，交叉点由程序随机设定如图3所示。

Figure 3. Cross-forming new chromosomes

图3. 交叉形成新染色体

6) 根据变异率Pm，当交叉过后产生新的染色体后，通过变异手段来保持种群的多样性。变异是通过连续多点变异的，当变异点随机定好后，将后面连续3个基因进行随机变异，最终诞生出新的种群如图4。这种方法在一定程度上可以提高种群在全局分布上面有很强的“生命力”，局部上有一定的收敛性。

Figure 4. New chromosomes formed by mutation

图4. 变异形成的新染色体

7) 开始进行迭代，迭代过程中如果满足适应度要求，输出结果，否则继续执行步骤③～⑥直到迭代结束。

5. 仿真实验

为了验证该方法的有效性，根据PBS缓冲区现存的车辆信息、未完成计划信息、移库车道里的车辆信息、从涂装缓冲区出来的车辆信息。并且结合线性缓冲区的结构来分析。

为在PBS缓冲区部分车道发生中断情况下，缓解产线压力并且完成生产计划，将采取“出库–算法–入库–算法–出库”形成一种“自适应优化循环”的方式进行调度。

假设选择四条车道，每条车道容量为10的线性缓冲区如图5进行实验。其中第四条车道发生突发情况导致整条车道发生中断(由红色标注)导致无法正常运行。同时，为了方便说明车辆相关颜色等配置，本文将相关信息进行了编码，具体如表1所示。

Figure 5. PBS buffer

图5. PBS缓冲区

Table 1. Assembly information

表1. 装配信息

首先根据现存车辆信息和生产计划如图6所示。

Figure 6. Production planning

图6. 生产计划

可以看出当生产计划进行到第八位会无法进行生产，现将生产计划拆分即Plan1：A1 A1 B2 A1 B2 C1 C1和Plan 2：D1 D2 B1 B2 C1 B1 C2 A2。

现先通过遗传算法求解Plan 1，参数设置如下：种群数量N = 200，交叉概率Pc = 0.76，变异概率Pm = 0.07，迭代次数U = 100。得出最优出库方案如下：即方案移库次数为6次，各个车道的出库顺序是1112122233333。Plan 1的任务完成。

经过一次出库后，PBS缓冲区的车辆存储情况发生了改变如图7所示，与此同时，由于在出库的时候，部分车辆会因调度计划的安排从而未进入总装车间。这部分车辆会被输送至移库车道如图8。同时涂装车间也会输送来一批新的未入库车辆如图9。

Figure 7. PBS buffer after outbound

图7. 出库后PBS缓冲区

Figure 8. Vehicle information on transfer lane after outbound

图8. 出库后移库车道车辆信息

Figure 9. Information about transport vehicles in painting workshop

图9. 涂装车间输送车辆的信息

现根据Plan 2以及上述信息实行入库算法，参数设置如下：种群数量N = 200，入库种群Z = 100，交叉概率Pc = 0.76，变异概率Pm = 0.07，迭代次数U = 100。

Figure 10. Inbound scheme information

图10. 入库方案信息

图10显示了在某一次程序运行中第38个种群是最佳入库结果，可根据表1查询相关属性得知本应进入第四车道的相关属性车辆，被分散到其余可运行车道里。同时，在此入库基础上又得出了最佳的出库方案即：最少移库次数2次，各个车道的出库顺序是3333223231 (该种群方案是将移库次数y和生产计划数E相加从而对结果进行有效部分选取得到的)。

自此，经过上述方法调度，现有生产计划全部完成，且在完成计划的同时，实现了可运行车道可以承担中断车道的传输任务的功能。

6. 结论

本文针对PBS缓冲区部分车道中断问题，提出了一种通过加入启发式规则的遗传算法来对PBS缓冲区的出库和入库进行一种“自适应循环优化”的实时动态调配方法，即通过“出库–算法–入库–算法–出库”形成一种不断优化的方式，结合实例分析，验证了该方法的有效性。该方法是可以在此突发情况下保证汽车制造企业一定的整体流通性。

本文的实例是具有一定普遍性的，而且在特殊情况下该方法也有一定的适应能力：

1) 如果在发生中断时，未执行生产计划的第一个计划，车辆就是具有中断车道里面的属性而没有可运行车道里面的属性。可以将“自适应循环优”方法进行调节，如更改为“入库–算法–出库–算法–入库”，即循环从哪里开始的问题。

2) 中断情况有可能会有两到多条车道发生故障，数量较少的话，还是可以进行调度，只不过对于算法的计算量会偏大，同时缓冲区的出库调度会比较慢，因为可运行车道的“属性负荷”会成倍加重。车道中断过多的话那么就建议整体停产维修，因为算法起的作用会比较小。

总的来说，该方法的整体适应度还是比较高的，有一定的实用性。

基金项目

国家自然科学基金项目(62003292)。