﻿ 考虑物料配送的飞机移动生产线调度问题优化<sup>*</sup>
 文章快速检索 高级检索

Optimization of aircraft moving assembly line scheduling problem considering material delivery
HU Xinming, LU Zhiqiang
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Received: 2016-12-12; Accepted: 2017-01-20; Published online: 2017-03-08 09:29
Foundation item: National Natural Science Foundation of China (61473211, 71171130)
Corresponding author. LU Zhiqiang, E-mail: zhiqianglu@tongji.edu.cn
Abstract: This paper abstracted the scheduling of assembly process as a resource-constrained project scheduling problem in the background of aircraft moving assembly line, and decisions about material delivery and the storage of line-side material were introduced considering the capabilities, constraints and other practical factors. An integrating mathematical model with the objective of minimizing the makespan was established. A heuristic algorithm was proposed based on genetic algorithm framework, combining with solution generation algorithm and local optimization search algorithm. With the global searching advantages of genetic algorithm, a joint decision of start time, material delivery time and material storage position in line-side space for each job was made taking into account job sequence, resource constraints, delivery capability, line-side space and other factors through SCRDS algorithm. On this basis, a local optimization algorithm aiming at adjusting line-side material positions between two jobs was proposed to re-optimize the start time and material delivery time of jobs, which decreases the project duration further. Numerical experiments were carried out by using a standard example library and the results proved the validity of the model and algorithm.
Key words: aircraft moving assembly line     material delivery     genetic algorithm     SCRDS algorithm     local optimization

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

1) 飞机装配作业项目包含n项作业，J={1, 2, …, n}，任意jJ的执行工期为tj，开始时间为TjS，完成时间TjF=TjS+tjPj表示作业j的紧前作业集合，任意作业在其紧前作业全部完成后才能执行。增加作业0和作业n+1表示虚作业，虚作业执行时间为0，且不占用任何资源。

2) 可更新资源为R={1, 2, …, K}，任意时刻第k种资源总量为Rk，单位时间内作业j消耗资源k的数量用rjk表示。

3) 将时间离散化，时间集合为D={1, 2, …, z}，z表示所有作业操作时间总和，任意dD表示离散的时间节点。

4) 将飞机上的作业空间离散化，如图 1所示，对于任意一架飞机，以飞机机尾作为零参考点，ψ表示飞机的长度。飞机上的作业空间集合为Γ={1, 2, …, ψ}，任意ljΓ表示作业j在飞机上的固定装配位置。

 图 1 飞机移动生产线作业装配点及物料摆放位置示意图 Fig. 1 Schematic of positions of assembly and material storage on aircraft moving assembly line

5) 假定飞机移动生产线的移动速度为V，作业j在移动生产线上的装配位置和物料摆放位置可通过图 1表示。离散化的线边空间集合为L={1, 2, …, ω}，lL。对于任意一架飞机，图中状态A表示飞机进入移动生产线的起始位置。在时刻TjS飞机移动到状态B位置时作业j开始装配，经过tj时间段飞机移动到状态D所示位置时作业j装配完成。作业j开始执行到完成时间段内飞机在移动生产线上移动距离的中间位置，即状态C所示位置，定义该位置作业j的装配点所对应的线边空间位置为该作业所需物料的中心摆放位置ljm，用图中黑色部分表示。任意ljmLljm=「lj+VTjS+Vtj/2 表示向上取整。

6) 线边空间的分配以将任意作业装配所需物料存放在距离装配中心位置较近区域为基本原则，可允许物料占用ljm左右两侧各m个单位的线边空间，用图 1中阴影部分表示。

7) 飞机装配作业j所需的物料主要包括4类：形状不规则、数量少的大型结构件，需求量大、体积小的通用标准件，体积中等、数量多的装配件和复杂昂贵的系统件。大型结构件由于线边空间容量不足，采用标准料架直接进行配送；通用标准件(如装配所需的螺母等紧固件)由于需求量较高且体积小，通常在各工位线边单独划定存放区域，通过定期补货的方式配送；因此本文重点考虑装配件和系统件2类物料的配送与存放。装配件和系统件均使用标准料箱由小车配送至线边空间，并在装配作业结束后以统一回收空料箱的方式进行供应，配送完成时间TjDTjS，配送提前期tjppmax，物料占用线边空间时长为TjO=TjF-TjD。作业j对物料的需求为vj

8) 每个单位线边空间容量为Su，假定任意时刻物料综合配送能力的上限为Dmax，记项目总工期为T

1) xjd。0, 1变量，当其为1时表示作业j在时刻d开始执行，否则为0。

2) yjd。0, 1变量，当其为1时表示作业j所需物料在时刻d完成配送，否则为0。

3) vjdl。非负整数变量，表示作业j在时刻d在线边空间l存放的料箱数量，取值范围为{0, 1, 2，…，Su}。

1.2 数学模型

AMALSP-CMD的数学模型如下：

 (1)
 (2)
 (3)
 (4)
 (5)
 (6)
 (7)
 (8)
 (9)
 (10)
 (11)
 (12)
 (13)
 (14)
 (15)

2 算法设计

2.1 遗传算法框架

 图 2 染色体初始化示意图 Fig. 2 Schematic of chromosome initialization

 图 3 遗传算法框架 Fig. 3 Genetic algorithm framework
2.2 基于作业顺序列表的解生成算法

2.3 基于物料摆放位置调整的局部优化搜索算法

 图 4 基于物料摆放位置调整的局部优化搜索机理 Fig. 4 Local optimization search mechanism based on material position adjustment

1) [ljm-m, ljm+m]∩[lim-m, lim+m]且iPj，表示作业i与作业j的物料线边摆放空间重叠，且作业i不是作业j的紧前作业。

2) TjS＞max{TPjF}，表示作业j被延期执行。

3) TiS′TjS′TiF′，表示若不存在延期，作业i和作业j之间可以存在时间上的重叠，有并行执行的可能。

4) 当TiS′t≤max{TiF′, TjF′}，Sleft[lim-m, lim+m]-SujmSleft[lim-m, lim+m]∩Sleft[ljm-m, ljm+m]，表示可以通过调整部分作业i的物料摆放位置使得作业j的物料能够在不拖期的情况下有足够的空间存放。

1) 对于作业1~i-1，其开始和结束时间不受影响。

2) 对于作业i与作业j之间的作业，由于只移动了作业i和作业j的物料，对其他作业的物料摆放没有任何改变，不会影响其开始和完成时间。

3) 对于作业j+1~n，由于TjF′TjF，因此Tj+1F′Tj+1F, …, TnF′TnF，使得总工期必定不会增加。

3 数值实验

3.1 与CPLEX结果对比

 作业规模 算例 Dur/TCPU GAP/% CPLEX THBG 10 1 16/0.58 16/0.54 0.00 2 23/1.43 23/0.53 0.00 3 13/1.61 13/0.53 0.00 4 34/2.77 34/0.52 0.00 5 20/1.11 20/0.50 0.00 6 31/0.93 31/0.54 0.00 7 20/0.92 20/0.52 0.00 8 22/1.87 22/0.52 0.00 9 22/0.58 22/0.49 0.00 10 20/1.05 20/0.51 0.00 平均值 22.1/1.29 22.1/0.52 0.00 20 1 24/66.67 24/0.83 0.00 2 24/6.14 24/0.83 0.00 3 33/126.88 35/0.83 5.71 4 36/23.06 36/0.84 0.00 5 24/13.29 24/0.83 0.00 6 18/3.63 18/0.85 0.00 7 24/21.36 24/0.84 0.00 8 27/7.28 27/0.82 0.00 9 22/3.58 22/0.83 0.00 10 22/17.50 23/0.85 4.35 平均值 25.4/28.94 25.7/0.84 1.01 30 1 43/810 43/1.52 0.00 2 53/677 53/1.54 0.00 3 37/3 478 37/1.46 0.00 4 41/9 478 42/1.58 2.44 5 46/25 007 47/1.49 2.17 6 42/3 811 42/1.71 0.00 7 61/14 967 62/1.48 1.64 8 LB=52/- 57/1.47 9.62* 9 LB=51/- 57/1.48 11.76* 10 61/32 927 61/1.50 0.00 平均值 48/11 394 50.1/1.52 0.78 注：CPLEX栏中数据，如16/0.58表示CPLEX求得的精确解和CPU时间，LB=52/-表示CPLEX在可接受时间(36 000 s)内无法求出问题可行解，记录其低界值LB=52；THBG栏中数据，如16/0.54表示THBG算法得到的解和CPU时间；GAP栏中“*”表示CPLEX得不到可行解时用低界计算GAP值。

3.2 大规模数据算法效果对比

 作业规模 Dur GAP/% R-NMO H-TD H-SCRDS THBG R-NMO H-TD H-SCRDS 30 54.86 56.24 50.17 50.10 9.79 12.38 0.14 60 74.70 73.45 61.89 61.40 21.81 19.19 0.80 90 91.70 93.65 76.03 75.00 22.80 23.78 1.37 120 137.30 156.05 111.53 108.90 26.48 41.75 2.42 480 395.48 393.37 305.24 296.37 33.44 32.73 2.99 1 200 981.50 1 033.62 739.00 709.44 38.35 45.70 4.17

 图 5 不同算法计算工期结果比较 Fig. 5 Comparison of durations of different algorithms

1) 本文设计的SCRDS算法相比于物料不能占用两侧线边空间的规则对项目工期结果有很大的优化，SCRDS算法对飞机移动生产线边空间进行了有效的分配与利用，提高了线边空间的使用效率。在项目作业规模为30时，相比于R-NMO规则所得结果的优化比例为9.79%，当项目的作业规模为60、90和120时，优化比例分别为21.81%、22.80%和26.48%，均超过20%，作业规模为1 200时，平均优化比例可以达到38.35%。

2) THBG算法在各个规模的问题上得到的结果都优于H-TD算法得到的结果。当作业规模为1 200时，THBG算法相比H-TD算法得到的结果优化比例均值达到了45.70%，说明将AMALSP-CMD问题中的资源、物料配送能力等约束综合考虑对装配计划进行决策相比传统的两阶段调度方法具有优势。

3) 问题规模较小时，局部优化算法效果不明显，只有少数项目可以实现工期优化。随着问题规模的增大，局部优化算法效果逐渐变好。当问题规模为1 200时，平均优化比例超过4%。由于SCRDS算法对线边空间的利用率已经很高，在作业规模较小时，很难找到满足条件的作业通过微调物料摆放位置使其提前执行，因此该局部优化算法针对大规模算例效果较好。

4 结论

1) 以飞机移动生产线为实际背景，将其抽象为资源受限项目调度问题，并引入了物料配送能力约束和线边空间物料存放的约束，对AMALSP-CMD问题建立了相应的数学模型

2) 针对物料的JIT配送策略及线边空间物料的摆放设计了以遗传算法为框架的启发式算法，提高了线边空间利用率，减少了因物料存放空间不足无法配送导致的作业延期，优化了项目总工期。

3) 通过数值实验对算法进行了验证，结果证明了本文算法的有效性，与传统两阶段决策算法相比，将物料配送及其在线边空间的存放与装配中的资源等约束进行综合考虑，具有较高的理论与实际意义。

 [1] CHALESHTARTI A S, SHADROKH S. Branch and bound algorithms for resource constrained project scheduling problem subject to cumulative resources[C]//International Conference on Information Management, Innovation Management and Industrial Engineering.Piscataway, NJ:IEEE Press, 2011:147-152. [2] BERTHOLD T, HEINZ S, LVBBECKE M E, et al.A constraint integer programming approach for resource-constrained project scheduling[M]//LODI A, MILANO M, TOTH P.Integration of AI and OR techniques in constraint programming for combinatorial optimization problems.Berlin:Springer, 2010:313-317. [3] BLAZEWICZ J, LENSTRA J K, KAN A H G R. Scheduling subject to resource constraints:Classification and complexity[J]. Discrete Applied Mathematics, 1983, 5 (1): 11–24. DOI:10.1016/0166-218X(83)90012-4 [4] TORMOS P, LOVA A. An efficient multi-pass heuristic for project scheduling with constrained resources[J]. International Journal of Production Research, 2003, 41 (5): 1071–1086. DOI:10.1080/0020754021000033904 [5] BUKATA L, ŠǓCHA P, HANZÁLEK Z. Solving the resource constrained project scheduling problem using the parallel Tabu search designed for the CUDA platform[J]. Journal of Parallel & Distributed Computing, 2014, 77 (11): 58–68. [6] BOULEIMEN K, LECOCQ H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operational Research, 2003, 149 (2): 268–281. DOI:10.1016/S0377-2217(02)00761-0 [7] ALCARAZ J, MAROTO C. A robust genetic algorithm for resource allocation in project scheduling[J]. Annals of Operations Research, 2013, 102 (1): 83–109. [8] HARTMANN S. A self-adapting genetic algorithm for project scheduling under resource constraints[J]. Naval Research Logistics, 2002, 49 (5): 433–448. DOI:10.1002/(ISSN)1520-6750 [9] MERKLE D, MIDDENDORF M, SCHMECK H. Ant colony optimization for resource-constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (4): 333–346. DOI:10.1109/TEVC.2002.802450 [10] KUMAR N, VIDYARTHI D P. A model for resource-constrained project scheduling using adaptive PSO[J]. Soft Computing, 2015, 20 (4): 1565–1580. [11] 王琰, 陆志强. 基于多重约束的飞机移动装配线作业调度优化[J]. 工业工程与管理, 2011, 16 (6): 115–120. WANG Y, LU Z Q. Job scheduling optimization of aircraft moving assembly line under multiple constraints[J]. Industrial Engineering & Management, 2011, 16 (6): 115–120. (in Chinese) [12] 郑倩, 奚立峰. 飞机移动生产线作业调度问题的启发式算法[J]. 工业工程与管理, 2015, 20 (2): 116–121. ZHENG Q, XI L F. Heuristics for aircraft moving assembly line scheduling problem[J]. Industrial Engineering & Management, 2015, 20 (2): 116–121. (in Chinese) [13] 葛茂根, 刘明周, 钱芳, 等. 基于JIT的多目标总装准时物料配送方法研究[J]. 中国机械工程, 2011, 22 (23): 2834–2838. GE M G, LIU M Z, QIAN F, et al. Research on multi-objective method on main assembly material delivery based on JIT[J]. China Mechanical Engineering, 2011, 22 (23): 2834–2838. (in Chinese) [14] 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–812. [15] 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): 1–16. [16] KHAYAT G E, LANGEVIN A, RIOPEL D. Integrated production and material handling scheduling using mathematical programming and constraint programming[J]. European Journal of Operational Research, 2006, 175 (3): 1818–1832. DOI:10.1016/j.ejor.2005.02.077 [17] AGUIRRE A M, MÉNDEZ C A, CASTRO P M. A hybrid scheduling approach for automated flowshops with material handling and time constraints[J]. International Journal of Production Research, 2014, 52 (9): 2788–2806. DOI:10.1080/00207543.2014.885664

#### 文章信息

HU Xinming, LU Zhiqiang

Optimization of aircraft moving assembly line scheduling problem considering material delivery

Journal of Beijing University of Aeronautics and Astronsutics, 2017, 43(12): 2573-2582
http://dx.doi.org/10.13700/j.bh.1001-5965.2016.0932