为了满足客户多样化、个性化的需求，汽车制造商广泛地采用混流生产线进行装配作业. 以多品种、小批量为特色的混流生产模式使得装配线所需零部件的种类和数目显著增加，因而准时化物料供应调度逐步成为整车企业亟待解决的关键问题^[1]. 据此可知，进行汽车装配线的物料供应调度研究对提高生产线的装配效率具有重要意义.

近年来，许多国内外学者对汽车装配线的物料供应问题进行了较深入的研究，研究内容主要集中在循环配送问题和单点配送问题两个方面^[2]. 循环配送问题可以描述为配送设备依照固定的行车线路进行周期性的装配线物料供应活动，以设备装载能力为约束决策每次配送过程中各类物料的数目. 这一方面的研究相对较成熟，Emde等^[3]提出多项式时间算法，用于求解以优化线边库存为目标的循环配送问题；Fathi等^[4]构建循环配送问题的多目标模型，以优化线边库存和配送次数. 单点配送问题可以描述为配送设备以多批次、小批量的模式进行装配线物料供应活动，且每次配送活动仅涉及一个工位. 单点配送问题的研究相对较少，Boysen等^[5]研究基于单个设备的汽车装配线单点配送问题，建立动态规划算法和启发式算法，以优化装配线的库存. Boysen等^[6]系统地阐述了不同类型单点配送问题，给出各类问题的复杂度证明. 以上文献仅考虑单个设备的单点配送问题，实际的汽车装配线物料供应往往涉及到多个设备的联合配送调度. Luo等^[7-8]研究多设备协作配送的调度问题，但优化指标为配送设备的最大完工时间、配置数目和等待时间等，未考虑生产线的库存状况.

汽车装配线的物料供应调度问题为复杂的组合优化问题，在大规模情形下，难以利用精确算法进行求解；因此，群智能算法成为解决这一难题的重要手段，目前应用于这一领域的算法包括蚁群算法、粒子群算法和遗传算法等. 教-学优化算法是Rao等^[9]受教师与学生之间学习过程的启发而提出的一种新型的群智能算法. 与上述算法相比，教-学优化算法具有收敛速度快、控制参数少等优点，并且该算法在神经网络训练、资源项目调度等方面已经获得了成功应用. 标准TLBO算法采用实数编码方式，无法直接应用于离散问题的求解；此外，算法在迭代后期易陷入局部最优，全局搜索能力和深度寻优能力有待进一步的开发.

本文针对多个设备的联合配送问题进行建模，考虑各型号设备配送速度的差异性，构建以优化线边库存为目标的汽车装配线物料供应调度模型. 基于标准TLBO算法的框架和调度问题的性质，在编码与解码方法、强化算法的全局搜索能力和增强算法的深度寻优能力3个方面进行重新设计，构建混合教-学求解算法；利用仿真测试，验证了调度算法的有效性.

1 数学建模 1.1 问题描述

在汽车装配车间，在制品依次流经各个工位进行装配作业，装配线所需零部件在物料超市进行分拣和装箱，各个料箱内装有一定数目的同类物料，并由多台不同型号的配送设备完成物料的上线作业，图 1给出汽车装配线物料供应的示意图.

为了清晰地描述汽车装配线的物料供应问题，给出如下基本假设. 1)作业车间采用装配线节拍时间，作为系统的基本时间单位；2)为了简化建模过程，假定每个工位负责装配一类物料，据此可以实现物料类型和工位的一一对应关系；3)各个料箱中的物料类型及数目已知；4)每次配送作业包含一个料箱，配送过程不可中断，各个设备在到达当前配送任务的目标工位后立刻返回物料超市，并开始后续的配送任务；5)各类型配送设备从超市到所有工位间的行驶时间为定值，由于装卸作业时间较短，忽略不计；6)各个工位在初始阶段的库存量已知；7)装配线的投产排序结果已知，因而各工位的需求为已知量；8)各工位不允许发生缺货.

为了有效地控制线边库存，实现装配线的准时化物料供应，构建的调度问题包含以下2个子问题：1)料箱分配问题，即确定各个设备所负责配送的料箱集合；2)料箱排序问题，即确定每个配送设备的料箱配送次序.

1.2 数学模型

目标函数为最小化规划期内所有工位的最大加权库存，如下：

${\rm{min }}\,\,Z(\sigma ) = \mathop {\max }\limits_{s = 1, \cdots ,w;t = 1, \cdots ,T} \{ {\omega _s} {L_{s,t}}\}. $

(1)

式中：Z(σ) 为方案 σ 所产生的规划期内所有工位的最大加权库存， $\sigma = \{ {\sigma _1}, \cdots ,{\sigma _k}, \cdots ,{\sigma _m}\} $ 表示调度方案，σ_k 表示设备 k 的料箱配送序列，m 为配送设备总数；w 为工位总数，T 为规划期的节拍总数，ω_s 为工位 s 处库存的权重，L_s，t 为 t 时刻工位 s 处的库存.

约束条件如下.

1) 设备 k 第 p 次配送作业过程中料箱编号表示为 ${l_k}(p)$ ，该料箱到达目标工位 ${s_{{l_k}(p)}}$ 的时间为

$\left.\begin{array}{l}{r_{{l_k}(p)}} = \left\{ {\begin{array}{*{20}{l}}{{d_{{s_{{l_k}(p)}},k}}},&{p = 1};\\{{d_{{s_{{l_k}(p)}},k}} + \displaystyle\sum\limits_{q = 1}^{p - 1} {2 {d_{{s_{{l_k}(q)}},k}}} },&{p = 2, \cdots ,{n_k}};\end{array}} \right.\\\quad\quad\quad\quad k \in \{ 1,2, \cdots ,m\} ,\;\;\;p \in \{ 1,2, \cdots ,{n_k}\} .\end{array}\!\!\!\right\}\!\!\!\!$

(2)

式中: n_k 为设备 k 的总配送次数, ${d_{{s_{{l_k}(p)}},k}}$ 为设备 k 从物料超市到工位 ${s_{{l_k}(p)}}$ 所需的行驶时间.

2) t 时刻到达工位 s 处的料箱集合 ${\varGamma _{s,t}}$ 表示为

$\left.\begin{array}{l}{\varGamma _{s,t}} = \{ i \in \{ 1,2, \cdots ,n\} |{r_i} \leqslant t,{s_i} = s\} ;\\ s \in \{ 1,2, \cdots ,w\} ,\;\;t \in \{ 1,2, \cdots ,T\} .\end{array}\right\}$

(3)

式中：n 为料箱总数，r_i 为料箱 i 到达目标工位的时间.

3) t 时刻工位 s 处库存 L_{s, t} 表示为

$\left.\begin{array}{l}{L_{s,t}} = {\alpha _s} + \displaystyle\sum\limits_{i \in {\varGamma _{s,t}}} {{a_i}} - {D_{s,t}};\\ s \in \{ 1,2, \cdots ,w\} ,\;\;t \in \{ 1,2, \cdots ,T\} .\end{array}\right\}$

(4)

式中：α_s 为工位 s 的初始库存量，a_i为料箱 i 中的物料数目，D_s，t 为工位 s 在时刻 t 的累积物料需求量.

4) 装配线各工位在规划期内不允许缺货, 即

${L_{s,t}} \geqslant 0;\;\; s \in \{ 1,2, \cdots ,w\} ,\;\;t \in \{ 1,2, \cdots ,T\} .$

(5)

为了说明这一物料配送问题，给出如下算例. 2台配送设备负责2个工位的物料配送任务，各工位的初始库存量取值为 $\alpha_1=1 $ , $\alpha_2=2 $ . 料箱总数为5，各个料箱的物料数量 a_i 和目标工位 s_i 如表 1所示. 对于设备1，配送时间参数 d_s，k 取值为 ${d_{1,1}} = 1$ ， ${d_{2,1}} = 2$ ；对于设备2，配送时间参数 d_s，k 取值为 ${d_{1,2}} = 2$ , ${d_{2,2}} = 1$ . 表 2定义了两工位各个时刻的累积物料需求量 D_s，t，两工位库存的权重设置为 ${\omega _1} = {\omega _2} = 1$ .

给定调度方案 $\sigma = \left\{ {\left\{ {5,2} \right\},\left\{ {1,3,4} \right\}} \right\}$ , 可得图 2所示的调度甘特图，各工位在规划期内的库存变化状况如图 3所示. 可知，两工位在规划期内的最大库存分别为3和4，因而 Z(σ)=4.

1.3 问题性质

依据假设可知， $\forall s \in \{ 1,2, \cdots ,w\} $ ，随着装配作业的进行，工位 s 处的库存表现为阶梯式下降趋势；在工位 s 获得物料补给时该工位的库存量出现局部峰值，在工位 s 获得物料补给的前一刻，该工位的库存出现局部谷值，据此可得性质1和2.

性质1 　已知调度方案 σ，对应的目标函数可以转化为 ${\rm{min }}\,Z(\sigma ) = \mathop {\max }_{{i \in \{ 1,2, \cdots ,n\} } }\{ {\omega _{{s_i}}} {L_{{s_i},t_i^1}}\} $ . 其中，t_i¹ 表示库存局部峰值时刻，以 $\left\lceil {} \right\rceil $ 表示向上取整，t_i¹ 计算如下:

$t_i^1 = \left\{ {\begin{array}{*{20}{l}} {\min \left\{ {{r_i},T} \right\}},&{\;{r_i} = \left\lceil {{r_i}} \right\rceil }; \\ {\min \left\{ {\left\lceil {{r_i}} \right\rceil ,T} \right\}},&{{\text{其他}}} .\end{array}} \right.$

性质2  已知方案 σ，构建集合 ${H} = \{ t_i^2|i \in $ $ \{ 1,2, \cdots ,n\} \} $ ，变量 t_i² 表示库存局部谷值时刻，计算公式为

$t_i^2 = \left\{ {\begin{array}{*{20}{l}} {\min \,\{ {r_i} - 1,T\} },&{\;{r_i} = \left\lfloor {{r_i}} \right\rfloor } ;\\ {\min\, \{ \left\lfloor {{r_i}} \right\rfloor ,T\} },&{{\text{其他}}} .\end{array}} \right.$

式中： $\left\lfloor {} \right\rfloor $ 表示向下取整. 若 $\exists i \in \{ 1,2, \cdots ,n\} $ ，有 $ {L_{{s_i},t_i^2}} <$ $ 0$ 成立，则 σ 违反了不缺货约束，视为不可行解.

性质1可以用于简化目标函数的计算，性质2可以用于确定调度方案的可行性. 在后续求解算法的构造部分，将以上2条性质应用于适应度计算和剪枝算法设计，以增强算法的有效性.

2 标准TLBO算法

TLBO算法隶属于群智能优化算法. 该算法以老师表示当前种群的最优解个体，以学生表示当前种群中的剩余个体，算法进化过程包括教学阶段和学习阶段2个方面. TLBO算法的流程归纳如下.

1）初始化算法和问题的相关参数，包括种群规模 P、变量的维度 D、变量各维度的取值 $[x_d^{\rm l},x_d^{\rm u}]$ $(d \in \{ 1,2, \cdots ,D\} )$ 、算法终止条件等.

2）构建初始种群并计算适应度. 以rand（0，1）表示[0，1]之间的随机数，个体的初始化公式为

${x_d} = x_d^{\rm l} + {\rm rand}(0,1) \left(x_d^{\rm u} - x_d^{\rm l}\right).$

3）教学阶段. 求解当前群体每一维的平均值 ${\bar x_d}$ ，进而得到平均个体 ${{\bar x}}{\rm{ = [}}{\bar x_1},{\bar x_2}, \cdots ,{\bar x_d}, \cdots ,{\bar x_D}{\rm{]}}$ . 针对当前种群中的每个个体 x^old，借助 ${{\bar x}}$ 生成新的个体 x^new，若 x ^new的适应度优于 x^old, 则用 x^new 取代 x^old. 新个体 x^new 的更新公式为

${{ x}^{\rm{new}}} = {{ x}^{\rm{old}}} + {\rm{rand}}(0,1) \left({{ x}^{\rm b}} - \tau { {\bar x}}\right).$

式中：x^b 为当前种群的最优解，教学因子 $\tau \in \{ 1,2\} $ .

4）学习阶段. 针对当前种群中的每个个体 x^old，随机选择另一个体 x^r，利用学习公式进行种群的第2次更新. 以最小化问题为例，更新公式为

${{ x}^{\rm{new}}} = \left\{ {\begin{aligned}& {{{ x}^{\rm{old}}} + {\bf{rand}}{^{ D}} \left({{ x}^{\rm r}} - {{ x}^{\rm{old}}}\right)}, \quad\quad{\;f\left({{ x}^{\rm r}}\right)< f\left({{ x}^{\rm{old}}}\right)}; \\ & {{{ x}^{\rm{old}}} + {\bf{rand}}{^{D}} \left({{ x}^{\rm{old}}} - {{ x}^{\rm r}}\right)},\quad\quad{{\text{其他}}} .\end{aligned}} \right.$

式中：f 为目标函数值，rand^D 为 1×D 随机数矩阵，各维度取值为[0，1].

5）迭代终止条件判断. 若算法满足终止条件，则迭代结束；否则，循环运行3）、4）.

3 HTLBO算法

结合问题的性质构建HTLBO求解算法，算法的核心思想包括：1)构建特定的编码与解码方法，使得标准TLBO算法能够适用于求解离散问题；2)提出局部搜索流程，用于强化算法的全局开发能力；3)结合束搜索技术，构建融合问题特性的剪枝算法，以强化算法的深度寻优能力.

3.1 编码与解码、适应度计算

编码过程：给定料箱数 n 和配送设备总数 m，HTLBO算法采用实数编码方式，对该物料配送问题进行编码. 编码长度为 n，每一位编码的取值为[1，m+1)，编码的第 i 位对应于料箱 i.

解码过程：对编码进行取整操作，编码第 i 位的整数部分表示负责料箱 i 配送作业的设备标号，据此可以得到各配送设备的料箱集合. 针对同一配送设备上所有料箱对应的编码数值，按大小升序排列，据此可得各设备的料箱配送序列.

为了清晰地说明以上编码和解码过程，结合数学建模部分所给算例的参数设置，给出该算例一个编码 {2.1，1.9，2.7，2.3，1.3}. 对应的调度方案为 $\sigma = {\rm{\{ }}\{ 5,2\} {\rm{,}}\{ 1,4,3\} {\rm{\} }}$ ，相应的解码过程如图 4所示.

上述编码方式简洁有效，易于实现. 该编码方式未考虑装配线不缺货这一复杂约束. 此外，该约束无法通过简单的修复方法进行处理. 基于性质1和2，通过引入惩罚项来构造HTLBO算法的评价函数 f(σ)，公式如下：

$f(\sigma ) = \mathop {\max }\limits_{i \in \{ 1,2, \cdots ,n\} } \{ {\omega _{{s_i}}} {L_{{s_i},t_i^1}}\} + \beta \sum\limits_{i = 1}^n \;{\max \left\{ 0, - {L_{{s_i},t_i^2}}\right\} }. $

式中：β 为惩罚系数，取值为正.

3.2 局部搜索流程

为了强化算法的全局开发能力，构建局部搜索流程，尽可能发掘问题的优质解^[10]. 该局部搜索流程包含以下3种基本变异算子：交换、反转和插入. 3种算子的具体操作归纳如下.

1) 交换，随机选择当前解 σ 编码位置 p₁和 p₂处的编码数值并交换，生成新个体 σ'.

2) 反转，随机选择当前解 σ 编码位置 p₁~p₂处的编码数值并倒转，生成新个体 σ'.

3) 插入，随机选择当前解 σ 编码的2个位置 p₁和 p₂，将位置 p₁上的编码数值插到 p₂之前，生成新个体 σ'.

由该编码与解码方法可知，编码的第 i 位决定料箱 i 所对应配送设备的编号和料箱 i 在该设备上的配送次序. 上述3种变异算子能够使得变异部分编码所对应的料箱获得新的设备编号和配送次序. 构建的局部搜索流程融合以上3种基本算子，首先生成3种算子的随机排列 $({O_1},{O_2},{O_3})$ ，其次结合贪婪选择策略，采用如下流程搜索新的调度方案.

1）针对当前解 σ，基于算子O₁生成新解 σ'. 若 $f(\sigma ') < f(\sigma )$ , 令 $\sigma \leftarrow \sigma '$ ，并转1）；否则，转2）.

2）针对当前解 σ, 基于算子O₂生成新解 σ'. 若 $f(\sigma ') < f(\sigma )$ ，令 $\sigma \leftarrow \sigma '$ ，并转2）；否则，转3）.

3）针对当前解 σ，基于算子O₃生成新解 σ'. 若 $f(\sigma ') < f(\sigma )$ , 令 $\sigma \leftarrow \sigma '$ ，并转3）；否则，终止局部搜索流程.

3.3 剪枝算法

为了增强算法的局部挖掘能力，结合问题的性质和束搜索技术构建剪枝算法，力求提升当前种群中可行解的性能^[11]. 给出当前可行解 σ 的瓶颈工位的定义. 结合瓶颈工位的概念，定义当前解 σ 的邻域结构. 给出剪枝算法的搜索流程.

给定可行解 σ，定义 Z(σ) 所在工位为 ŝ，ŝ 处的最大库存为 L_ŝ^max，变量 ŝ 和 L_ŝ^max 计算如下:

$\hat s = \arg \mathop {\max }\limits_{s = 1,2, \cdots ,S} \{ {\omega _s} \cdot \max \{ {L_{s,t}}|t \in \{ 1,2, \cdots ,T\} \} \} ,$

$L_{\hat s}^{\max } = \max\, \{ {L_{\hat s,t}}|t \in \{ {r_i}|i \in {B_{\hat s}}\} \}. $

据此可知，解 σ 中工位 ŝ 处的物料供应作业成为制约当前准时化物料供应调度的瓶颈. 定义工位 ŝ 为瓶颈工位，控制并改善瓶颈工位 ŝ 处的物料供应调度，有助于提高当前解 σ 的性能.

令 B_ŝ 表示目标工位为 ŝ 的料箱所构成的集合，基于瓶颈工位的概念，定义当前可行解 σ 的邻域结构为： $\forall i \in \{ 1,2, \cdots ,n\} $ . 若 ${s_i} \ne \hat s$ ，则保持料箱 i 在解 σ 中的位置不变；重新安排 σ 中目标工位为 ŝ 的 $|{B_{\hat s}}{\rm{|}}$ 个料箱的配送作业，以此生成新的解 σ'. 借助数学建模部分所给的算例，说明这一邻域结构. 给定解 $\sigma = \{ \{ 5,2\} ,\{ 1,3,4\} \} $ ，依据算例的参数设置和各工位库存状况(见图 3)可知， $\hat s = 2$ ， $L_{\hat s}^{\max } = 4$ ， ${B_2} = \{ 3,4,5\} $ . 如图 5所示，将 σ 中工位2接受物料供应的时刻(即料箱3、4和5到达装配线的时刻)升序排列，得到位置编号①、②和③. 维持其他料箱(料箱1和2)的调度位置不变，重新将料箱3、4和5安排在位置①~③这3处，可以获得新的调度方案 σ'. 通过合理安排 $|{B_{\hat s}}{\rm{|}}$ 个料箱的位置，能够使得瓶颈工位 ŝ 处的库存得以改善，进而提高当前解的性能.

根据问题假设可知，各类型设备的配送时间仅与料箱的目标工位相关. 新解 σ' 中工位 ŝ 接受物料更新的维持时间不变，但线边库存发生变化；其他工位料箱的到达时刻维持不变，库存随之维持与解 σ 相同的水平. 定义当前解 σ 在瓶颈工位 ŝ 处接受物料供应的时刻集合为 $ \{ {t_k}|k = $ $1,2, \cdots ,|{B_{\hat s}}|\} $ , t_k 按升序排列. 令 ${L_{\max }} = \max\, \{ {L_{\hat s,t}}|t = $ $ 1, \cdots ,{t_k}\} $ , ${L_{\min }} = $ $ \min \,\{ {L_{\hat s,t}}|t = 1, \cdots ,{t_k}\} $ , 以符号π表示 $|{B_{\hat s}}{\rm{|}}$ 个料箱的排序, 给出基于束搜索技术的剪枝算法流程.

1）令 $\pi = \phi ,k = 1$ 且 $\Pi {\rm{ = \{ }}\pi {\rm{\} }}$ , 转2）.

2） $\forall {\pi _i} \in \Pi $ , 构建集合 $\varOmega ({\pi _i}) = {B_{\hat s}}\backslash {\pi _i}$ , 转3）.

3） $\forall {\pi _i} \in \Pi {\text{，}}$ 令 $\Psi ({\pi _i}) = \{ {\pi _i} \cup {\psi _j}|{\psi _j} \in \varOmega ({\pi _i})\}. $ 若 $|\varOmega ({\pi _i})| \geqslant $ $ {l} $ , 则保留 ${l} $ 个 ${a_{{\psi _j}}}$ 最大的序列.

4） $\forall \pi{ '_p} \in \varPsi ({\pi _i})$ , 计算参数 L_max 和 L_min. 若 ${L_{\max }} < $ $ L_{s'}^{\max }$ 且 ${L_{\min }} \geqslant 0$ ，则保留 ${\pi '_p}$ ；否则，令 $\varPsi ({\pi _i}) =$ $\varPsi ({\pi _i})\backslash$ $ {\pi '_p} $ .

5）更新Π, 即 $\Pi = \bigcup\nolimits_{i = 1}^{{\rm{|}}\Pi {\rm{|}}} {\varPsi ({\pi _i})} $ , 令 $k \leftarrow k + 1$ . 若 $k > |{B_{\hat s}}|$ 或 $\Pi = \phi $ , 终止搜索; 否则, 转2）.

搜索完毕后，选择Π中 L_max 最小的子序列构建新解. 剪枝算法的优化过程包含2类剪枝操作，第1类剪枝为当前子序列在工位 ŝ 处的最大库存未优于解 s 的情况，即 ${L_{\max }} \geqslant L_{s'}^{\max }$ ；第2类剪枝为 ${L_{\operatorname{m} {\rm{in}}}} < 0$ 的情况，表示工位 ŝ 处将发生缺货. 此外，参数 $l $ 用于控制剪枝算法的搜索空间. 随着问题规模的扩大，剪枝算法的搜索空间将急剧增加， $l $ 取值较大能够在一定程度上提高算法的搜索精度，但耗费的计算时间将急剧增长，因而需要合理地确定参数 $l $ .

如图 6所示，给出剪枝算法优化所给算例的示意图. 由搜索流程可得2个序列 {3，5，4} 和 {4，5，3}，对应的 L_max 分别为2和3，据此可得新的调度方案 $\sigma ' = \{ \{ 3,2\} ,\{ 1,5,4\} \} $ , 图 7给出改进解 σ' 各工位的库存状况. 瓶颈工位2处的库存状况得以改进，解 σ 的性能得以提升.

3.4 HTLBO算法流程

1）初始化算法参数和问题参数.

2）构建初始种群，计算适应度.

3）利用标准TLBO算法中教学阶段和学习阶段的邻域变换公式，更新当前种群.

4）针对当前种群中的每个解，利用局部搜索流程进行个体更新.

5）针对当前种群中的可行解，结合剪枝算法挖掘优秀解.

6）若算法满足终止条件，则终止优化流程并输出当前最优解；否则，转3）.

3.5 时间复杂度分析

分析HTLBO算法在迭代搜索过程中的相关操作的时间复杂度如下.

1）初始化每个个体的时间复杂度为 O(n).

2）对于每个个体进行解码涉及料箱分配和排序2个步骤，相应的时间复杂度分别为 O(n) 和 ${O}(m n {\log _2}n)$ .

3）利用快速排序法对P个个体进行适应度排序，所需的时间复杂度为 ${ O}(P {\log _2}P)$ .

4）教学和学习阶段的每个解更新均需耗时 O(n).

5）局部搜索中3种变异算子耗时均为 O(1).

6）剪枝算法采用广度优先的束搜索技术且搜索宽度设置为 $l $ ，因此时间复杂度为 ${ O}(n l )$ .

据此可知, HTLBO算法所需的时间复杂度相对较低, 能够有效求解中大规模调度问题.

4 实验分析 4.1 算例构建

考虑到构建的汽车装配线物料供应调度问题尚无标准测试集，为了验证算法的有效性，结合文献[5]的相关参数, 构建测试算例. 料箱数 $n \in $ $ {\rm{\{ 100,125,150,175,200\} }}$ ，配送设备数 $m \in \{ 10,15,20,25\} $ ，最大生产节拍数 T=300，工位数 $w = \left\lceil {0.01 n m} \right\rceil $ . 据此，共构建了20个测试算例，且各算例以符号(n，m)表示.

针对测试算例 (n，m)，各工位初始库存量、料箱中的物料量等相关参数设置如下.

1) 将 n 个料箱随机分配给 w 个装配工位，且保证每个工位至少分得一个料箱，据此可得各个料箱的目标工位 ${s_i}(i \in \{ 1,2, \cdots ,n\} )$ .

2) $\forall s \in \{ 1,2, \cdots ,w\} $ ，工位 s 处库存的权重 ω_s 取[1，2]上的随机数，工位 s 处初始库存 α_s 取[5，10]上的随机整数； $\forall s \in \{ 1,2, \cdots ,w\} $ ， $k \in \{ 1,2, \cdots ,m\} $ ，配送时间参数 d_s，k 取[1，5]上的随机数.

3) $\forall s \in \{ 1,2, \cdots ,w\} $ ， $t \in \{ 1,2, \cdots ,T\} $ ，需求量参数 D_s，t 按以下公式随机生成：

${D_{s,t}} = \left\{ {\begin{array}{*{20}{l}} {{D_{s,t}}},&{\;{\rm{rand(0,1)}} < 0.5}; \\ {{D_{s,t{\rm{ - }}1}}{\rm{ + }}1},&{{\text{其他}}} .\end{array}} \right.$

4) 工位 s 的物料需求总量为 ${D_{s,T}} - {\alpha _s}$ . 令 B_s 表示目标工位为 s 的料箱所构成的集合，将 ${D_{s,T}} - {\alpha _s}$ 个零件随机分给 ${\rm{|}}{B_s}{\rm{|}}$ 个料箱，并保证每个料箱的物料量不低于 $0.7 \left( {{{ {\left( {{D_{s,T}} - {\alpha _s}} \right)}}/{ {\left| {{B_s}} \right|}}}} \right)$ ，据此可以得到各个料箱的物料量 ${a_i}(i \in \{ 1,2, \cdots ,n\} )$ .

选用Matlab2016b平台进行编程测试，在主频为2.4 GHz、内存为4 GB、Intel(R) Core(TM) i5-2430M CPU的便携式计算机上开展仿真实验, 将运行时间 τ_max 设置为算法的终止条件.

4.2 HTLBO算法参数校验

HTLBO算法包含3个重要参数：τ_max 、剪枝算法控制参数 $l$ 和种群规模 P. 针对算例 (n，m)，令 τ_max、 $l $ 和 P 分别为 $\left\lceil {{\eta _\tau } n m} \right\rceil $ 、 $\left\lceil {{\eta _l } {\rm{|}}{B_{\hat s}}{\rm{|}}} \right\rceil $ 和 $\left\lceil {{\eta _P} n m} \right\rceil $ . 为了使得HTLBO算法达到最佳的搜索性能，需要合理确定参数 ${\eta _\tau }$ 、 ${\eta _l}$ 和 h_p 的取值. 选择算例(150，10)进行正交试验设计，每个参数设有4个水平（见表 3）. 根据正交表 L₁₆(4³) 对每组参数进行15次独立试验, 采用15次试验结果的均值 $\overline Z $ 作为响应变量，仿真结果如表 4所示.

采用直观分析法和方差分析法分析表 4的测试结果，表 5给出测试结果的极差分析，如表 6所示为测试结果的方差分析，其中显著性水平取值为0.05. 由表 5的极差分析可知，参数 $l $ 对算法的寻优性能影响最大. ${\eta _l }$ 取值过小，则将严重限制剪枝算法的搜索空间；以至于无法发挥深度搜索的能力； ${\eta _l }$ 取值过大，则将使得算法过分注重深度搜索，弱化了全局搜索能力. P 对算法的寻优性能具有重要影响. ${\eta _P}$ 过大将会破坏了群体的优良模式， ${\eta _P}$ 过小则弱化了算法每代的群体进化能力. 此外，算法运行时间参数 ${\eta _\tau }$ 需要进行合理的设置，进而确保算法能够达到最佳的优化性能. 由表 6的方差分析可知，参数 ${\eta _l }$ 和 ${\eta _P}$ 的相伴概率分别为0.006和0.014，均小于显著性水平0.05，说明这两个参数对算法的性能影响显著，契合了极差分析的结论. 综上所述，HTLBO算法的参数设置如下： ${\eta _\tau } = 0.3$ ， ${\eta _l } = 0.6$ ， ${\eta _P} = 0.04$ .

4.3 HTLBO算法性能分析

为了验证HTLBO算法的优化性能，将其与标准教-学算法(TLBO)、模拟退火算法(simulated annealing, SA)^[5]和离散粒子群算法(discrete particle swarm optimization，DPSO)^[12]的测试结果进行对比，后两者为求解同类调度问题的有效算法. 针对每个算例，各个算法均独立运行15次并对测试结果进行统计. 在算法的参数设置方面，TLBO、SA和DPSO的求解时间设置为与HTLBO相同，TLBO和DPSO的种群规模设置为与HTLBO相同，3种对比算法的其余参数采用正交实验进行校验，以此保证对比实验的公平性.

为了直观、清晰地展示测试结果，依据文献[13]对仿真结果进行如下处理. 针对各算例，令 h 表示算法( $h \in {\rm{\{ TLBO,HTLBO,SA,DPSO\} }}$ )，以符号 ${Z_{\rm w}}(h)$ 、 ${Z_{\rm a}}(h)$ 和 ${Z_{\rm b}}(h)$ 表示算法 h 在15次运行过程中所得的最优解、最劣解和均值，据此构造变量RZ_b(h)=Z_b(h)/Z_b(HTLBO)，RZ_w(h)=Z_w(h)/Z_b(HTLBO)和RZ_a(h)=Z_a(h)/Z_b(HTLBO). 变量 ${\rm{R{Z_{ b}}}}(h)$ 、 ${\rm{R{Z_{ w}}}}(h)$ 、 ${\rm{R{Z_{ a}}}}(h)$ 表示算法 h 求解结果相对于HTLBO算法所得最优结果的比值，测试结果如表 7所示. 为了说明HTLBO算法相比于其他3种算法在寻优性能方面是否具有显著差异性，采用威尔科克森符号秩检验方法对测试结果进行分析，置信水平取95%. 分别以符号 R⁺ 和 R^– 表示正、负等级的秩和，令检验统计量 $R{\rm{ = min\,\{ }}{R^{\rm{ + }}},{R^ - }{\rm{\} }}$ ，考虑算法独立运行次数为15，据此可知 R≤25，表明HTLBO算法的寻优性能显著优于对比算法，在表 7中以粗体凸显 R≤25 的情形.

由表 7可知，在与其他3种算法共计60组的对比测试中，53组算例的测试结果表明，HTLBO算法的优化结果显著优于对比算法；在剩余的7组对比测试中，HTLBO多次运行结果的均值优于对比算法. HTLBO算法相较于其他3种算法具有更强的寻优能力，能够有效地获得问题的满意解.

针对每个算例，定义变量 ${G_{\rm{wb}}} = {\rm{R{Z_w}}} - {\rm {R{Z_b}}}$ 以衡量各算法多次运行所得结果中最劣解与最优解之间的间隙，利用上述4种算法求解20组算例的 G_wb，如图 8所示. 可知，相较于其他3种对比算法，HTLBO算法在多数情况下所得的 G _wb较小，表明优化结果更稳定，具有较强的鲁棒性.

将HTLBO算法的求解结果与回溯算法^[14]的优化结果进行对比. 回溯算法隶属于最优化搜索技术，能够有效地处理含复杂约束的组合优化问题，并取得问题的精确解，且已经被成功应用于求解同类型问题，但回溯法的计算耗时受问题规模的影响较大. 针对各个算例，设定回溯算法的计算时间为5 h，即18 000 s，仿真结果表明回溯算法能够在规定的时间内求得3个算例的精确解. 如表 8所示为对HTLBO算法和回溯算法的优化效果对比. 表中，ξ为偏差；t_op为运行时间；Z(B) 为利用回溯算法所得的最优解，其中GAP_b 和 GAP_a 为HTLBO算法在15次运行过程所得最优解和均值相对于 Z(B) 的百分比偏差，即

$\begin{array}{l}{\rm{{GA{P_b}}}} = {\displaystyle\frac{{({Z_{\rm b}}({\rm{HTLBO}}) - Z(B))}}{{Z\left( B \right)}} \times 100{\text{%} } ,}\\{\rm{GA{P_a}}}={ \displaystyle\frac{{({Z_{\rm a}}({\rm{HTLBO}}) - Z(B))}}{{Z\left( B \right)}} \times 100{\text{%}} .}\end{array}$

由表 8的测试结果可知：在解的质量方面，HTLBO算法多次运行所得的最优解和均值与 Z(B) 较接近，算例(150，10)的 GAP_b 和 GAP_a 分别为0.184%和6.996%；在计算时间方面，HTLBO算法的用时远少于回溯算法，利用HTLBO算法和回溯算法求解算例(150，10)的用时分别为450和16 618 s.

以上对比测试验证了构建的HTLBO算法的有效性, 表明该算法能够获得大规模汽车装配线物料供应调度问题的满意解.

5 结　语

本文以汽车装配线物料供应调度中的多设备联合配送问题为研究对象，构建以优化线边库存为目标的准时化配送模型，提出混合教-学求解算法. 构建特定的编码与解码方法，使得标准TLBO算法能够适用于当前离散调度问题的求解；结合多种变异算子构建局部搜索流程，有效增强了算法的全局开发能力；引入优化瓶颈工位物料供应的剪枝算法，使得混合算法的深度寻优能力得以强化. 利用仿真测试与分析验证了构建的调度算法的有效性.

后续研究可以探讨这一调度问题的近似算法和最优化算法的设计以及装配线物料供应过程中包含设备故障这一随机因素的动态调度问题.