周炳海, 谭芬
同济大学 机械与能源工程学院, 上海 201804
收稿日期：2016-10-10
基金项目：国家自然科学基金资助项目(71471135)。
作者简介：周炳海(1965-)，男，浙江浦江人，同济大学教授，博士生导师。

摘要：为有效解决基于循环配送策略的汽车装配线物料配送调度问题, 进行了改进型免疫克隆选择算法的调度方法研究.首先, 建立了数学规划模型，以最小化计划期内所有工位的线边总库存为优化目标, 并提出了改进型免疫克隆选择算法.在算法设计过程中融入了模拟退火算子和邻域搜索算子，分别对克隆种群和记忆库进行操作, 以克服传统免疫克隆选择算法易陷入局部最优、搜索深度不足等缺陷.最后进行了仿真实验, 表明该算法是有效、可行的.
关键词：循环配送调度超市免疫克隆选择算法邻域搜索
Scheduling Method of Material Delivery for Automotive Assembly Lines Based on Milk-Run Delivery
ZHOU Bing-hai, TAN Fen
School of Mechanical and Energy Engineering, Tongji University, Shanghai 201804, China
Corresponding author: ZHOU Bing-hai, E-mail:bhzhou@tongji.edu.cn
Abstract: To efficiently solve the scheduling problem of material delivery for automotive assembly lines based on milk-run delivery, a scheduling method was developed by the modified immune clone selection algorithm. Firstly, a mathematical programming model was set up with an objective function of minimizing total inventory for all stations over the planning horizon. Then, a modified immune clone selection algorithm was developed to solve the proposed problem. Both the simulated annealing operator and neighborhood search operator were applied to clone population and memory vault, respectively, in the design of algorithm. It overcomes deficiencies of the traditional immune clone selection algorithm, such as tendencies to trap into local optima and limited search depth. Finally, the simulation experiments were carried out and the results indicate that the as-proposed algorithm is valid and feasible.
Key Words: milk-run deliveryschedulingsupermarketimmune clone selection algorithmneighborhood search
随着产品多样化、需求个性化等方面竞争压力的不断增加, 一些车辆制造企业已开始运用循环配送策略来实现物料多品种、小批量的准时化配送^[1].
目前, 车辆装配系统中的物料配送调度问题已引起了学者的广泛关注.Emde等^[2]构建了嵌套动态规划算法来解决物料超市中循环配送系统的路径问题以及配送次数的问题.Golz等^[3]以德国某汽车制造商为例, 研究了其路径、调度和装载问题.文献[4-5]都以最小化配送次数和线边库存为目标, 构建了多目标配送调度模型, 不同之处在于求解算法.Rao等^[6]研究了单工位物料配送调度问题, 以最小化搬运和库存持有总成本为目标.然而上述文献并没有考虑到在实际装配过程中工位线边容量是有限的, 没有考虑如何优化各个周期的线边库存.
本文在分析文献的基础上, 充分考虑装配线线边库存的容量约束, 最小化计划期内所有工位的线边总库存.
1 问题描述图 1描述了汽车装配线的循环配送系统, 由多载量小车负责对装配线的工位段S进行多批次、小批量的物料配送.物料超市布置在装配线的附近, 暂存来自中心仓库的各种零件.
图 1(Fig. 1)

图 1 汽车混流装配线循环配送系统示意图Fig.1 Schematic diagram of milk-run delivery system for automotive mixed-model assembly lines

为有效描述要研究的调度问题, 作如下基本假设:①系统选用节拍时间作为基本的时间单位; ②小车的两次配送之间不允许有空闲时间; ③物料超市和各个工位的位置、小车的行车路线和行驶距离已知; ④小车从物料超市到各个工位间的行车时间已知且包括装、卸载时间; ⑤车型的装配顺序已知, 即各工位在每周期的需求已知; ⑥所有料箱的大小统一^[2], 所以小车的容量以及零件的线边库存容量均可由料箱的个数来表示.
为方便形式化描述, 现定义符号如下.
1) 下标:
s为工位集合S中的第s个工位, s∈S;
k为小车的第k次配送, k=1, 2, …, K;
c为生产周期的标号, c=1, 2, …, C, 其中C为生产周期的总数.
2) 时间相关:
t_R为全程往返的行车时间;
t_ps为从超市至工位s的行车时间;
t_δ为超市中的物料补充时间.
3) 配送相关:
t_k为第k次配送小车从超市出发的时间;
b_ks为第k次配送中送至工位s的料箱数;
(t_k; b_k1, b_k2, …, b_k|S|)为小车的一次配送作业;
Ω={(t_k; b_k1, b_k2, …, b_k|S|)}为一个完整物料配送方案.
4) 其他符号:
d_sc为在周期c工位s的料箱需求;
A为多载量小车的容量(料箱数);
B_s为工位s的线边库存容量(料箱数);
O(c, s)为周期c工位s的累积到达料箱数;
D(c, s)为周期c工位s的累积需求料箱数;
IL(s, c)为周期c工位s的线边料箱数;
IL(s, 0)为工位s的初始线边库存.
此外, 为方便后续描述, 定义如下两个二元阶跃函数:
根据上述描述, 该问题建模如下:
目标函数:

(1)

约束如下:

(2)

(3)

(4)

(5)

其中:

(6)

(7)

(8)

式(1)为目标函数, 表示最小化计划期内所有工位的线边总库存; 式(2)表示物料配送需要满足各个工位的需求总量; 式(3)表示零件既要及时到达工位以满足装配线不允许缺货约束, 又要满足工位的线边库存容量约束; 式(4)表示小车装载能力约束; 式(5)表示小车发车时间约束, 即小车完成前一次的配送且在超市补充完物料后立刻进行下一次配送.
为了进一步深入分析问题, 针对上述构建的调度模型, 给出了相关的引理、定理.
引理1??参考文献[3], 若第k次配送完成后工位s的线边料箱数为IL_sk, 在不考虑工位的线边库存能力约束时, 第k次配送完成后线边若要不缺货应满足的最少料箱数为U_k, 则任一可行解应满足∑_s=1^|S|ILsk≥U_k, ?k=1, …, K.
定理1??若第k次配送工位s的物料需求为d_sk, 第k次配送过剩的物料需求为ED_k, 当不考虑工位的线边库存能力约束时, 总库存的下界为
证明首先明确d_sk, ED_k, U_k, IL_sk的含义:
其中U_K=0.
然后深入剖析目标函数总库存f_sum的意义.f_sum分解为两部分:每次配送后在下一次配送到达前产生的库存f₁以及提前配送产生的库存f₂.第k次配送后在第k+1次配送到达前产生的库存为是一个定值, 该库存的产生是不可避免的.因此最小化f_sum也就是最小化f₂.
, 根据引理1可以得到, 即f_sum的下界为LB(f_sum)=, 定理1得证.
定理2??若对?s∈S, 方案Ω的两次配送作业φ₁, φ₂∈{1, …, K}(φ₁ < φ₂)且?k∈{φ₁+1, …, φ₂-1}满足, 则第φ₁次配送至工位s的最少料箱数(s, 0)-∑_i=1^φ₁-1b_is.
证明??由所给的约束条件?k∈{φ₁+1, …, φ₂-1}满足可知, φ₁, φ₂是某工位s的相邻两次配送作业, 而第φ₁次配送至工位s的最少料箱数b_φ1s^min即为在第φ₂次配送到达前即时刻，使得工位s的线边库存量IL(s, )=0, 定理2得证.
2 改进型免疫克隆选择算法由文献[7]可知, 汽车混流装配线的物料配送调度问题为NP-Hard问题, 在合理时间内难以求得在较大规模情形下的精确解.为此, 本文构建了改进型免疫克隆选择算法.算法的具体步骤如下:
步骤1??编码.抗体编码为K×|S|的矩阵, K为总配送次数, |S|为工位总数.其中, 矩阵的行表示第k次配送(k=1, 2, …, K), 矩阵的列表示配送至工位s(s∈S), 第k行第s列所在元素表示第k次配送至工位s的料箱数，即b_ks.
步骤2??抗体种群的初始化.提出基于混沌的初始化方法, 给定种群规模N_pop、混沌迭代参数CI, 抗体Ω构造如下:
令i=1, j=1, 生成K×|S|个不同的随机数, 对?Δ_mnⁱ(m=1, 2, …, K; n=1, 2, …, |S|)进行混沌操作Δ_mnⁱ=sin(π·Δ_mn^i-1), 直至生成Δ_mn^CI.
, 直至生成抗体Ω.
步骤3??亲和度评价.对于抗体Ω, 其亲和度函数根据下式计算:
其中:IL(Ω)为目标函数; pena(Ω)为惩罚函数.构建局部最高、最低库存量集合Γ_max, Γ_min:
若?γ^a>B_s(γ^a∈Γ_max)或?γ^b>0(γ^b∈Γ_min), 做出惩罚, pena(Ω)=·max(γ_i^a-B_s, 0)+.其中, λ₁, λ₂分别为违反线边库存容量约束和不缺货约束的惩罚系数.
步骤4??终止条件判断.若迭代次数达到规定上限MAXGEN, 则输出结果; 否则, 进入步骤5.
步骤5??选择与克隆.选取亲和度最高的前N_c个抗体存入记忆库, 并对其进行克隆.将其按照亲和度由大到小排列, 用r表示抗体在该排序中的位置, 则每个抗体的克隆个数为(N_c-r+1), 克隆体的总数为N_c(N_c+1)/2.
步骤6??邻域搜索操作.对于记忆库中的抗体Ω_Mi, 首先找到一条“关键链”, 其对应的工位称之为“关键工位”, 记为s^*, s^*=argIL(s, c).给定记忆库中的抗体Ω_Mi, Ω←Ω_Mi, 基于求得的s^*, 在满足下列约束的情况下使得最小.
步骤7??体细胞高频突变.给定变异参数0 < M₁ < M₂, 抗体Ω变异如下:
1) 已知方案Ω, ?k=1, …, K, s∈S, 根据定理2求得第k次配送至工位s的最少料箱数b_ks^min, 若b_ks^min < 0, 则随机选取某次配送k′(k′>k), b_k′s←b_k′s+b_ks, 并将第k次配送的料箱数置为0, 即b_ks←0;若b_ks^min>A, 则前一次配送至工位s的料箱数b_{(k-1), s}←b_{(k-1), s}+rand(0, 1)·Δ, 其中Δ=min{A-∑_s=1^|S|b_{(k-1), s}, b_ks}, 构成Ω′, Ω←Ω′;
2) 若r < M₁, 转3);若M₁≤r < M₂, 转4);
3) 任选s∈S, 若?k₁, k₂∈{1, …, K}, 满足b_k2s≤A-∑_j=1^|S|b_k1j, 则b_k1s←b_k1s+b_k2s, b_k2s←0构成Ω′, Ω←Ω′, 抗体变异结束.
4) 任选s∈S, 若?k, k′∈{1, …, K}, 满足b_ks>1, 则任给b′∈{1, 2, …, b_ks-1}且b′≤A-∑_j=1^|S|b_k′j, b_ks←b_ks-b′, b_k′s←b_k′s+b′, 抗体变异结束.
步骤8??模拟退火操作.免疫克隆选择算法进化到一定程度后, 可能会达到某个局部平衡状态^[8].因此, 在算法的后期, 进行模拟退火操作, 使其跳出局部最优.
步骤9更新种群, 转至步骤3.
3 仿真实验分析3.1 实例生成参考文献[9]中的相关参数, 考虑|S|=5的物料配送调度问题, , p₁=rand(0.05, 0.2), , ?s∈{2, …, |S|}, t_δ=4, A=「(∑_s=1^|S|∑_c=1^Cd_sc)/.在计划期C内, 每个工位每个周期的物料需求为1或0, 在生成实例中, d_sc=1的概率为45%至50%.
本文所有算法在主频为2.50 GHz、内存4 GB、Intel(R) Core(TM) i5-4200M CPU的PC机上进行仿真实验, 采用Matlab(2014a)环境编程实现.
3.2 算法收敛性能分析为了验证本文构建算法的收敛性能, 分别用本文构建算法(MICSA)、标准免疫克隆选择算法(SICSA)、标准遗传算法(SGA)对实例进行求解^[10], 给出了问题规模C为60时上述三种算法的收敛曲线, 如图 2所示.由图 2可以看出, 改进型免疫克隆选择算法明显优于其他两种算法.
图 2(Fig. 2)

图 2 收敛性能分析Fig.2 Analysis of convergence performance

3.3 算法有效性验证为验证所构建算法的有效性, 用算法求得的结果与下界(lower bound, LB)的百分比偏差(percentage deviation, PD)^[11]作为算法的评价指标, PD值能够较好地反映算法的有效性, 其值越小, 表明算法越有效.PD定义如下:
分别用上述三种算法对实例进行求解, 目标函数取20次实验的平均值(取整), 对比结果如表 1所示.由表 1可知, 当问题规模C=70时SGA对应的PD值达到69.94%, 这表明该问题没有寻得可行解, 后续用‘—’表示该种情况.可以看出随着问题规模C的扩大, MICSA寻优能力明显要高于另外两种标准算法, 优化结果的PD值始终保持在15%以内, 表明了该算法的有效性.
表 1(Table 1)

表 1 各类算法在不同问题规模下与下界的对比结果Table 1 Comparison of experimental results between various metaheuristics and the lower bound 问题规模C 下界LB MICSA SICSA SGA ILsum PD/% ILsum PD/% ILsum PD/% 10 40 40 0 40 0 40 0 20 89 89 0 89 0 92 3.37 30 140 148 5.71 151 7.86 155 10.71 40 177 189 6.78 190 7.34 199 12.43 50 219 232 5.94 242 10.50 256 16.90 60 271 291 7.38 302 11.44 332 22.51 70 303 332 9.57 356 17.49 514 69.64 80 348 389 11.78 420 20.69 — — 90 412 468 13.60 521 26.46 — — 100 458 524 14.41 606 32.31 — —

表 1 各类算法在不同问题规模下与下界的对比结果 Table 1 Comparison of experimental results between various metaheuristics and the lower bound

3.4 线边容量对工位库存水平的影响图 3给出了C=60时某工位的库存水平的阶梯图.由图可知, 线边库存的容量约束使得工位每周期的库存水平始终保持在一个较低的水平.
图 3(Fig. 3)

图 3 工位1的库存水平阶梯图Fig.3 Ladder sketch map of inventory level for station 1

4 结论1) 对考虑线边库存容量约束的汽车装配线物料配送调度问题进行了研究, 构建了以最小化计划期内所有工位的线边总库存为优化目标的数学模型;
2) 构建了改进型免疫克隆选择算法, 通过与其他启发式算法以及下界进行对比, 验证了该算法是可行的、有效的;
3) 装配工位的线边库存水平的分析算例表明线边库存的容量约束使得装配工位每周期的库存水平始终保持在一个较低的水平.
参考文献

[1]	Boysen N, Emde S, Hoeck M, et al. Part logistics in the automotive industry:decision problems, literature review and research agenda[J].European Journal of Operational Research, 2015, 242(1): 107–120.DOI:10.1016/j.ejor.2014.09.065
[2]	Emde S, Boysen N. Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines[J].European Journal of Operational Research, 2012, 217(2): 287–299.
[3]	Golz J, Gujjula R, Günther H O, et al. Part feeding at high-variant mixed-model assembly lines[J].Flexible Services and Manufacturing Journal, 2012, 24(2): 119–141.DOI:10.1007/s10696-011-9116-1
[4]	Fathi M, Rodríguez V, Alvarez M J. A novel memetic ant colony optimization-based heuristic algorithm for solving the assembly line part feeding problem[J].The International Journal of Advanced Manufacturing Technology, 2014, 75(1/2/3/4): 629–643.
[5]	Fathi M, Alvarez M J, Mehraban F H, et al. A multiobjective optimization algorithm to solve the part feeding problem in mixed-model assembly lines[J].Mathematical Problems in Engineering, 2014, 2014(1): 1–12.
[6]	Rao Y Q, Wang M C, Wang K P, et al. Scheduling a single vehicle in the just-in-time part supply for a mixed-model assembly line[J].Computers & Operations Research, 2013, 40(11): 2599–2610.
[7]	Fathi M, Rodríguez V, Fontes D B M M, et al. A modified particle swarm optimization algorithm to solve the part feeding problem at assembly lines[J].International Journal of Production Research, 2016, 54(3): 878–893.DOI:10.1080/00207543.2015.1090032
[8]	Abdollahpour S, Rezaian J. Minimizing makespan for flow shop scheduling problem with intermediate buffers by using hybrid approach of artificial immune system[J].Applied Soft Computing, 2015, 28: 44–56.DOI:10.1016/j.asoc.2014.11.022
[9]	Emde S, Gendreau M. Scheduling in-house transport vehicles to feed parts to automotive assembly lines[J].European Journal of Operational Research, 2017, 260(1): 255–267.DOI:10.1016/j.ejor.2016.12.012
[10]	周炳海, 王腾, 方腾. 考虑多约束的MOJ调度问题[J].东北大学学报(自然科学版), 2015, 36(10): 1506–1510. ( Zhou Bing-hai, Wang Teng, Fang Teng. Scheduling multiple orders per job with various constraints[J].Journal of Northeastern University(Natural Science), 2015, 36(10): 1506–1510.DOI:10.3969/j.issn.1005-3026.2015.10.030)
[11]	Singh M R, Mahapatra S S. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks[J].International Journal of Advanced Manufacturing Technology, 2012, 62(1/2/3/4): 267–277.