﻿ 飞机移动生产线物料配送与空箱回收集成建模
 文章快速检索
 同济大学学报(自然科学版)  2019, Vol. 47 Issue (1): 136-142.  DOI: 10.11908/j.issn.0253-374x.2019.01.018 0

### 引用本文

LU Zhiqiang, ZENG Jun. Integrated Modeling of Material Delivery and Container Pickup Problem for Aircraft Moving Assembly Line[J]. Journal of Tongji University (Natural Science), 2019, 47(1): 136-142. DOI: 10.11908/j.issn.0253-374x.2019.01.018

### 文章历史

Integrated Modeling of Material Delivery and Container Pickup Problem for Aircraft Moving Assembly Line
LU Zhiqiang , ZENG Jun
College of Mechanical Engineering, Tongji University, Shanghai 201804, China
Abstract: To solve the material supply problem for aircraft moving assembly line, an integrated model was formulated to make decisions of material delivery and container pickup, and the scheduling method was proposed to solve the model. On the basis of the material-batching and vehicle scheduling problems, decisions on the pickup of line-side containers were introduced. An integrating mathematical model with the objective of minimizing the number of deliveries was established and a heuristic algorithm based on genetic algorithm was proposed. Due to the global searching advantage of genetic algorithm, an improved heuristic algorithm was introduced to make a joint decision on three variables of the batching of job's material and container, and delivery time, which took into account of the capacity of the delivery and line-side storage, and combined with the local search algorithm for re-optimization. Results of the numerical experiments proved the model and algorithms.
Key words: aircraft moving assembly line    material delivery    container pickup    genetic algorithm

1 问题描述及数学模型 1.1 问题描述

 图 1 飞机移动生产线物料供应模式 Fig.1 Schematic of material supply mode for aircraft moving assembly line

(1) 飞机移动装配项目包含n项作业，J={1, 2, …, n}.任意jJ的执行工期为tj，开始时间为Tjs, 完成时间Tjf=Tjs+tj.装配作业所需物料的供应包含两类任务，即送料任务和回收任务.j'∈α={1, 2, …, n}表示送料任务集合，包含n项任务，表示将作业j'∈J所需物料配送至相应的线边空间.j"∈β={n+1, n+2, …, 2n}表示回收任务集合，包含n项任务，表示将作业(j"-n)∈J的空箱回收至仓库.

(2) 将时间离散化，时间集合为T={1, 2, …, ϑ}，ϑ表示计划期时长，任意tT表示离散的时间节点.

(3) 线边存储区域是工位旁用于暂存提前送达的料箱和未及时回收的空箱的区域，将线边存储区域离散为单位线边空间，lL={1, 2, …, w}表示单位线边空间位置集合，且l的最大容量为Cmax.假设作业j的物料的线边暂存位置为ljljL.任意线边单元l被分配暂存的作业集合为ΩlΩlJ.对任意线边位置e, fLΩeΩf=ϕ.

(4) 作业j所需的物料量为mj，由多载量小车配送至相应的线边空间.某项作业所需的所有物料由一辆小车一次性完成配送，且一辆小车每次可配送多个作业所需的物料，小车的最大容量为Dmax.为了保证作业j的正常进行，其物料的配送完成时间TjdTjs.作业结束后空箱可以被回收，即空箱的开始回收时间TjcTjf.因此作业j占用线边空间的时间为料箱送达线边空间的时刻至空箱被小车回收完成的时刻.任意作业的所有空箱由一辆小车一次性完成回收，且一辆小车一次可回收多个作业的空箱.

(5) 物料配送与空箱的回收采用milkrun的方式.R表示小车出行次数集合，kR={1, 2, …, r}.小车从仓库出发，沿着给定路径行驶并在相应的线边单元对物料箱或空箱进行装卸，然后返回.小车从仓库到线边空间l的行车时间为tl，小车卸载料箱和回收空箱的时间分别为tun, tc.假设作业j的物料配送完成时间为料箱卸载完成的时间.

1.2 数学模型

(1) 决策变量：τk为整数变量，表示第k次出行的发车时刻；Zjk为0，1变量，当其为1时表示作业j所需物料在第k次出行时配送，否则为0；Yjk为0，1变量，当其为1时表示作业j的空箱在第k次出行时回收，否则为0.

(2) 目标函数：

 $\min Z = \left| R \right|$ (1)

 $\sum\limits_{k = 1}^r {{Z_{jk}}} = 1,\forall j \in J$ (2)
 $\sum\limits_{k = 1}^r {{Y_{jk}}} = 1,\forall j \in J$ (3)
 ${\tau _{k + 1}} \le {\tau _{k + 1}},\forall k \in R$ (4)
 $\sum\limits_{j = 1}^n {{Z_{jk}}{m_j}} \le {D_{\max }},\forall k \in R$ (5)
 $\begin{array}{l} \sum\limits_{j = 1}^n {{Z_{jk}}{m_j}} + \sum\limits_{l' = 1}^l {\sum\limits_{{\mathit{\Omega }_{l'}}} {\left( {{Y_{jk}} - {Z_{jk}}} \right){m_j}} } \le {D_{\max }}\\ \;\;\;\;\;\;\forall k \in R,l \in L \end{array}$ (6)
 $\begin{array}{l} {\rho _{kl}} = {\tau _k} + {t_l} + \sum\limits_{l' = 1}^{l - 1} {\sum\limits_{{\mathit{\Omega }_{l'}}} {\left( {{Z_{jk}}{t_{{\rm{un}}}} + {Y_{jk}}{t_{\rm{c}}}} \right)} } ,\\ \;\;\;\;\;\;\forall k \in R,l \in L \end{array}$ (7)
 $\begin{array}{l} \sum\limits_{\begin{array}{*{20}{c}} {k' \in K}\\ {{\rho _{k'l}}{\rho _{kl}}} \end{array}} {\sum\limits_{{\mathit{\Omega }_l}} {\left( {{Z_{jk}} + {Y_{jk'}}} \right){m_j}} } \le {C_{\max }},\\ \;\;\;\;\;\;\forall k \in R,l \in L \end{array}$ (8)
 $\begin{array}{l} {\rho _{k{l_j}}} + \sum\limits_{{\mathit{\Omega }_{{l_j}}}} {{Z_{jk}}{t_{{\rm{un}}}}} \le {T_{js}} + \left( {1 - {Z_{jk}}} \right)M,\\ \;\;\;\;\;\;\forall k \in R,j \in J \end{array}$ (9)
 ${\rho _{k{l_j}}} + \sum\limits_{{\mathit{\Omega }_{{l_j}}}} {{Z_{jk}}{t_{{\rm{un}}}}} \le {Z_{jk}}{T_{jf}},\forall k \in R,j \in J$ (10)
 ${\tau _k},\forall k \in R$ (11)
 ${Z_{jk}} \in \left\{ {0,1} \right\},{Y_{jk}} \in \left\{ {0,1} \right\},\forall k \in R,j \in J$ (12)

2 算法设计

2.1 算法框架

 ${\rm{Fit}} = \frac{1}{{\left| R \right|}}\sum\limits_{k = 1}^{\left| R \right|} {{{\left( {\frac{{{D_k} + {C_k}}}{{2{D_{\max }}}}} \right)}^2}}$ (13)

 图 2 遗传算法框架 Fig.2 Genetic algorithm framework
2.2 约束转换

 图 3 调度计划甘特图 Fig.3 Gantt chart representation of schedule
2.3 启发式解码

(1) 令k=1，初始化已安排任务集合ω=Ø，未安排任务集合η={1, …, 2n}, 未安排的送料任务集合D={1, …, n}，未安排回收任务集合Ρ={n+1, …, 2n}.

(2) 初始化第k次出行已安排任务集合υk=Ø，送料任务集合Dk=Ø，回收任务集合Pk=Ø.

(3) 可选择的任务集合ωk=η.读取编码中的任务列表.

(4) 按照顺序从小到大选择序号最小的任务bωk，以任务b确定小车离开时间窗[εA, ψA].

(5) 更新D, P, Dk, Pk, υk, η=η-{b}, ω=ω+{b}, 以及小车离开各线边位置时运载的料箱数πk, l+，空箱数δk, l+，最大运载量Mk, l+.若η=Ø，转(11)，否则(6).

(6) 修正小车离开时间窗[εB, ψB].对送料任务iD，对应的小车离开时间窗[εi, ψi]，若[εi, ψi]∩[εB, ψB]≠Ø且小车离开仓库的容量Mk, 0++miDmax，同时满足对所有iυk，若[εi, ψi]∩[εB, ψB]≠Ø.则将满足条件的任务i加入任务集合ξkd.若ξkd=Ø，转(8)，否则转(7).

(7) 选择线边位置靠前的任务mξkd.更新D, Dk, υk, η, ω, Mk, 0+, 以及小车离开时间窗[εC, ψC].若D≠Ø，转(6)，否则转(8).

(8) 对iP，若[εi, ψi]∩[εC, ψC]≠Ø，且小车到达线边位置的最大运载量Mk2, lj++piDmax，同时所有iυk的时间窗满足.则将任务i加入任务集合ξkc.若ξkc=Ø，转(10)，否则转(9).

(9) 选择空箱数量多的任务zξkc.更新P, Dk, υk, η, ω以及小车离开各线边位置时运载的料箱数πk, l+，空箱数δk, l+，最大运载量Mk, l+.若P≠Ø，转(8)，否则转(10).

(10) 令k=k+1，若η≠Ø，转(2)，否则转(11).

(11) 检验单位线边空间容量约束，即计划期T内任意时刻所有线边空间的料箱数都不超过上限，若不满足，则k=k+ζζ为惩罚因子.

(12) 输出配送回收计划S，算法结束.

2.4 局部搜索

(1) 获取可行计划S，由一组元组(Θ, λ)∈S表示，Θ代表每次出行安排的任务集合，λ代表小车出行时间.

(2) 将|R|个任务集合Θ按照任务数由小到大排序.若$\sum\limits_{i \in {\mathit{\Theta }_1}} {{m_i}} > {D_{\max }}/2$，转(6)，否则转(3).

(3) 选取任务数少的pS，出行计划为(Θp, λp).若对任意任务iΘp，都存在qS，满足Mq, li+1-+diDmaxMq, li++piDmax.其中，di表示送料任务的物料量; pi表示回收任务的空箱量.πk, l-δk, l-分别表示到达线边位置l={1, …, w, w+1}时的运载量，πk, l+δk, l+分别表示离开线边位置l={0, 1, …, w}时的运载量.Mk, l-=maxs=1, …, l {πk, s-+δk, s-}到达线边位置l={1, …, w, w+1}的运载量的最大值.Mk, l+=maxs=l, …, w+1 {πk, s++δk, s+}表示离开线边位置l={0, 1, …, w}的运载量的最大值.否则转(6).

(4) 若所有更新的q满足时间约束，则|R|=|R|-1.

(5) 通过调整出行时间使线边空间容量约束满足，若能满足，则更新计划S，转(2)，否则转(6).

(6) 输出优化后的计划S.

3 数值实验

3.1 与CPLEX的对比

3.2 与现有文献的对比

4 总结与展望

(1) 以飞机移动生产线为实际背景，同时考虑了物料的配送及其空箱的回收问题，将这两类相互影响的决策整合到一个联合决策框架中，提出了集成决策的优化模型.

(2) 针对集成模型设计了以遗传算法为框架的启发式算法，该算法对小车的装载、调度进行了联合优化决策，通过充分利用小车运载能力优化了小车出行次数，减少了配送与回收的总成本.

(3) 通过数值实验对算法进行了验证，实验结果证明了本文提出的算法的有效性，为飞机移动生产线这类考虑空箱回收的物料配送问题研究提供了借鉴.

(4) 后续可以考虑对飞机移动生产线中线边空间物料摆放决策展开详细研究，为IMDCP-AMAL问题提供更高效的决策.

 [1] ZHENG Y, HAN D, NI Y, et al. Research and application of bottom-up route-based product data conformity inspection approach for civil aircraft[J]. International Journal of Computer Integrated Manufacturing, 2014, 27(6): 591 DOI:10.1080/0951192X.2013.834464 [2] MEI Z, LIU Y, YOUNUS M. Material delivery system for aircraft composite component manufacturing workshop[C]//Proceedings of the International Multi Conference of Engineers and Computer Scientists. Hong Kong: [s.n.], 2011: 1097-1102. [3] 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 DOI:10.1016/j.ejor.2014.09.065 [4] SOUZA M C, CARVALHO C R V, Brizon W B. Packing items to feed assembly lines[J]. European Journal of Operational Research, 2008, 184(2): 480 DOI:10.1016/j.ejor.2006.09.091 [5] CUNHA A S, SOUZA M C. Stronger upper and lower bounds for a hard batching problem to feed assembly lines[J]. Electronic Notes in Discrete Mathematics, 2008, 30: 159 DOI:10.1016/j.endm.2008.01.028 [6] 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 DOI:10.1016/j.ejor.2016.12.012 [7] BOYSEN N, BRISKORN D, EMDE S. Just-in-time vehicle scheduling with capacity constraints[J]. ⅡE Transactions, 2016, 48(2): 134 [8] GOLZ J, GUJJULA R, GVNTHER H O, et al. Part feeding at high-variant mixed-model assembly lines[J]. Flexible Services and Manufacturing Journal, 2012, 24(2): 119 DOI:10.1007/s10696-011-9116-1 [9] 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, 11(1): 809 [10] 胡鑫铭, 陆志强. 飞机移动生产线物料配送与线边存储集成优化[J]. 工程科学学报, 2018, 40(1): 108 HU Xinming, LU Zhiqiang. Integrated optimization of material delivery and line-side storage problem for aircraft moving assembly line[J]. Chinese Journal of Engineering, 2018, 40(1): 108 [11] 朱永国, 李俊杰, 刘春锋, 等. 基于正态模糊时间窗约束的飞机装配物料配送路径规划[J]. 中国机械工程, 2017, 28(21): 2534 ZHU Yongguo, LI Junjie, LIU Chunfeng, et al. Aircraft assembly material delivery path planning based on normal fuzzy time window constraints[J]. China Mechanical Engineering, 2017, 28(21): 2534 DOI:10.3969/j.issn.1004-132X.2017.21.003 [12] LI H, DEMEULEMEESTER E. A genetic algorithm for the robust resource leveling problem[J]. Journal of Scheduling, 2016, 19(1): 43 DOI:10.1007/s10951-015-0457-6 [13] BENNELL J A, LEE L S, POTTS C N. A genetic algorithm for two-dimensional bin packing with due dates[J]. International Journal of Production Economics, 2013, 145(2): 547 DOI:10.1016/j.ijpe.2013.04.040 [14] LIN Y K, CHONG C S. Fast GA-based project scheduling for computing resources allocation in a cloud manufacturing system[J]. Journal of Intelligent Manufacturing, 2017, 28(5): 1 [15] FLESZAR K, CHARALAMBOUS C. Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem[J]. European Journal of Operational Research, 2011, 210(2): 176 DOI:10.1016/j.ejor.2010.11.004