Dynamic scheduling for aircraft mobile production line considering material supply interference
-
摘要:
针对飞机装配过程中出现的物料供应延期干扰问题，对飞机移动生产线装配作业调度进行了研究。通过对物料供应信息的动态分析，将反应调度决策划分为固定决策和不同场景下的预测决策，并建立了物料供应干扰环境下的动态调度框架。在滚动决策点，以最小化与模板装配计划的偏差及工期的加权和期望值为目标函数，建立了二阶段近似优化模型。针对模型的决策逻辑，设计了以两阶段禁忌搜索算法为框架的启发式算法，求解滚动决策点的优化问题。不同规模下的数值实验表明，所提出的动态调度方法能够有效利用不断更新的物料供应信息，获得接近后验精确解的调度结果，且相比于传统的调度方法，所提方法能更有效地应对物料供应干扰。
Abstract:To solve the problem of material supply delay during the assembly process of aircraft, the assembly operation scheduling problem of aircraft mobile production line is studied. Through the dynamic analysis of material supply information, reactive scheduling decisions were divided into fixed decisions and predictive decisions in different scenarios, and a dynamic scheduling framework in the environment of material supply interference was established. At each rolling decision point, a two-stage approximate optimization model was established with the objective function of minimizing the expected weighted sum of the deviation from the template plan and the makespan. On the basis of the decision logic of the model, a two-stage tabu search based heuristic was designed to solve the optimization problem of each rolling decision point. Numerical experiments with different scales indicate that the proposed dynamic scheduling method can effectively utilize the constantly updated material supply information to obtain scheduling results which is close to the posterior exact solution, and compared to the traditional scheduling strategies, the proposed method can more effectively deal with the interference of material supply.
-
Key words:
- aircraft mobile production line /
- material supply /
- uncertainty /
- dynamic scheduling /
- rolling decision
-
图 1 飞机移动生产线装配工位布局图
Figure 1. Assembly station layout of aircraft mobile production line
图 9 不同干扰次数下的方法性能对比
Figure 9. Performance comparison of methods under different interference times
图 10 不同工期权重下的方法性能对比
Figure 10. Performance comparison of methods under different duration weights
图 13 单阶段决策方法调度结果(Z=310)
Figure 13. Scheduling results of single stage decision method(Z=310)
图 14 期望场景方法调度结果(Z=307.5)
Figure 14. Scheduling results of expectation scenario method(Z=307.5)
图 16 前摄-反应方法调度结果(Z=309.5)
Figure 16. Scheduling results of proactive-reactive method(Z=309.5)
表 1 参数与决策变量
Table 1. Parameters and decision variables
参数 定义 J 作业集合 n 作业数量 j∈[0, 1, …, n, n+1] 作业序号 K 可更新资源集合 k∈K 资源种类编号 T 时间集合 t∈T 时间编号 pj 作业j的执行工期 Pj 作业j的紧前作业集合 rjk 作业j对第k种资源的需求量 Rk 第k种资源总量 sj0 作业j的模板计划开始时间 Aj0 作业j的物料计划到达时间 d 作业的物料配送提前期 决策变量 定义 sj 整数变量, 作业j的开始时间 xjt 0/1变量, 作业j在时刻t开始取1, 否则取0 
下载: 导出CSV
表 2 修正的参数与决策变量
Table 2. Modified parameters and decision variables
参数 定义 q∈[0, 1, …, ε] 干扰编号, 0代表无干扰, ε为干扰总数 Tq 第q次干扰发生时刻 JF, JD, JP 3类作业集合 sR, j(j∈JF) JF类作业j的实际开始时间 ω1, ω2 ω1为与模板装配计划偏差的单位时间成本权重, ω2为工期的单位时间成本权重, 且满足ω1+ω2=1 Θ 物料到达场景集合 N 场景数量 θ∈Θ 场景编号 Aj, θ 场景θ下, 作业j的物料到达时间 决策变量 定义 sj, θ 整数变量, 场景θ下, 作业j的开始时间 xjt, θ 0/1变量, 场景θ下, 作业j在时刻t开始取1, 否则取0
下载: 导出CSV
表 3 基于后验信息的实验结果
Table 3. Experiment results based on posterior information
V 算例 实验1 实验2 实验3 Z t/min Z t/min G Z t/min G 20 1 260.0 0 260.0 0.1 0 287.0 0.1 10.4 2 304.5 0.1 304.5 0 0 304.5 0 0 3 300.0 0 300.0 0.1 0 304.5 0 1.5 4 242.0 0 245.0 0.1 1.2 261.5 0 8.1 5 281.0 0 281.0 0.1 0 287.0 0.1 2.1 6 264.5 0.1 264.5 0.1 0 267.0 0 0.9 7 328.0 0 356.0 0.1 8.5 356.5 0.1 8.7 8 358.5 0.3 358.5 0.1 0 360.0 0 0.4 9 232.0 0.1 232.0 0.1 0 243.0 0.1 4.7 10 346.5 0.4 362.0 0.1 4.5 370.5 0.1 6.9 均值 291.7 0.1 296.4 0.1 1.4 304.2 0.1 4.4 30 1 315.5 0.6 315.5 0.2 0 315.5 0.2 0 2 262.5 0.7 300.0 0.2 14.3 300.0 0.1 14.3 3 344.0 0.6 369.5 0.3 7.4 369.5 0.2 7.4 4 353.5 0.6 353.5 0.1 0 353.5 0.1 0 5 250.5 0.9 250.5 0.4 0 250.5 0.2 0 6 249.0 0.7 256.0 0.3 2.8 256.0 0.3 2.8 7 398.5 1.4 398.5 0.8 0 406.0 0.6 1.9 8 261.0 0.7 261.0 0.4 0 261.0 0.1 0 9 448.5 1.8 448.5 0.6 0 448.5 0.4 0 10 383.0 1.1 394.5 0.5 3.0 416.5 0.3 8.7 均值 326.6 0.9 334.8 0.4 2.8 337.7 0.3 3.5 60 1 543.5 126 543.5 4.6 0 544.0 3.3 0.1 2 538.5 42 541.0 3.8 0.5 541.0 2.9 0.5 3 815.0 137 848.0 4.7 4.0 903.5 3.3 10.9 4 667.5 92 667.5 3.5 0 682.0 2.1 2.2 5* 803.5 180 803.5 4.6 0 835.0 3.4 3.9 6 547.0 38 552.0 3.1 0.9 567.0 2.9 3.7 7 440.5 30 458.0 3.7 4.0 458.0 2.8 4.0 8* 665.5 180 750.0 3.0 12.7 756.0 2.8 13.6 9 506.0 142 506.0 4.7 0 522.0 4.1 3.2 10 587.0 83 618.5 3.7 5.4 618.5 2.4 5.4 均值 611.4 105 628.8 3.9 2.8 642.7 3.0 4.8
下载: 导出CSV
表 4 小规模算例实验结果
Table 4. Experiment results of small-scale example
V 算例 实验4 实验5 实验6 实验7 实验8 Z GAP1 Z GAP2 Z GAP3 Z GAP4 Z GAP5 20 1 260.0 0 260.0 0 260.0 0 307.5 18.3 265.0 1.9 2 309.5 1.6 310.5 0.3 310.5 0.3 358.5 15.8 313.5 1.3 3 300.0 0 300.5 0.2 304.5 1.5 363.5 21.2 324.5 8.2 4 262.0 8.3 262.0 0 266.5 1.7 356.5 36.1 271.5 3.6 5 281.0 0 284.0 1.1 281.0 0 357.0 27.0 299.0 6.4 6 271.0 2.5 275.5 1.7 268.5 -0.9 390.0 43.9 285.5 5.4 7 356.0 8.5 361.0 1.4 356.0 0 369.5 3.8 368.0 3.4 8 366.5 2.2 366.5 0 364.5 -0.5 419.0 14.3 378.5 3.3 9 234.5 1.1 234.5 0 241.5 3.0 356.0 51.8 243.0 3.6 10 364.0 5.1 365.0 0.3 370.0 1.6 392.5 7.8 370.0 1.6 均值 300.5 2.9 302.0 0.5 302.3 0.7 367.0 24.0 311.9 3.9 30 1 315.5 0 319.0 1.1 315.5 0 317.5 0.6 315.5 0 2 302.5 15.2 303.5 0.3 307.5 1.7 331.0 9.4 323.0 6.8 3 369.5 7.4 370.0 0.1 369.5 0 378.5 2.4 370.0 0 4 353.5 0 355.0 0.4 356.5 0.8 353.5 0 358.5 1.4 5 259.0 3.4 260.5 0.6 260.5 0.6 314.5 21.4 279.5 7.9 6 257.5 3.4 260.0 1.0 256.0 -0.6 268.0 4.1 264.0 2.5 7 402.5 1.0 405.0 0.6 407.0 1.1 418.5 4.0 410.5 2.0 8 261.0 0 261.0 0 261.0 0 261.0 0 261.0 0 9 448.5 0 451.0 0.6 457.5 2.0 487.5 8.7 467.5 4.2 10 401.5 4.8 408.5 1.7 420.0 4.6 483.5 20.4 442.5 10.2 均值 337.1 3.5 339.4 0.6 341.1 1.0 361.4 7.1 349.2 3.5 60 1 543.5 0 548.0 0.9 549.5 1.1 558.0 2.8 555.5 2.2 2 542.5 0.7 547.5 0.9 538.5 -0.7 547.0 0.8 546.5 0.7 3 852.5 4.6 875.5 2.7 913.5 7.3 974.5 14.3 941.0 10.4 4 674.5 1.0 678.0 0.5 676.5 0.3 780.5 15.7 702.0 4.1 5* 810.5 0.9 824.5 1.7 824.5 1.7 827.5 2.1 827.0 2.0 6 558.0 2.0 565.5 1.3 552.0 -1.1 633.0 13.4 573.5 2.8 7 465.5 5.7 472.5 1.5 504.5 8.4 522.0 12.1 495.5 6.4 8* 722.5 8.6 730.0 1.0 750.0 3.8 857.5 18.7 765.5 6.0 9 511.0 1.0 515.0 0.8 548.5 7.3 548.5 7.3 529.0 3.5 10 622.5 6.0 631.5 1.4 635.5 2.1 631.5 1.4 632.5 1.6 均值 630.3 3.1 638.8 1.3 649.3 3.0 688.0 8.9 656.8 4.0
下载: 导出CSV
表 5 大规模算例实验结果
Table 5. Experiment results of large-scale example
V 算例 后验结果 实验4 实验5 实验6 实验7 实验8 Z Z GAP1 Z GAP2 Z GAP3 Z GAP4 Z GAP5 90 1 652.5 668.5 2.5 702.5 5.1 802.5 20.0 859.5 28.6 739.0 10.5 2 654.0 674.5 3.1 691.5 2.5 918.0 36.1 962.5 42.7 849.5 25.9 3 918.0 930.0 1.3 949.0 2.0 1 155.5 24.2 1 016.5 9.3 1 005.0 8.1 4 891.0 921.0 3.4 965.0 4.8 1 162.5 26.2 1 104.5 19.9 993.5 7.9 5 702.5 774.0 10.2 796.5 2.9 952.5 23.1 962.5 24.4 871.5 12.6 6 776.5 808.0 4.1 814.5 0.8 776.5 -3.9 914.0 13.1 867.5 7.4 7 652.5 715.0 9.6 715.0 0 728.0 1.8 864.0 20.8 782.5 9.4 8 823.5 843.5 2.4 850.5 0.8 843.5 0 1 281.0 51.9 922.5 9.4 9 988.0 1 002.0 1.4 1 032.5 3.0 1 063.0 6.1 1 071.0 6.9 1 071.0 6.9 10 946.0 959.0 1.4 967.5 0.9 974.0 1.6 1 124.0 17.2 1 008.5 5.2 均值 800.5 829.6 3.9 848.5 2.3 937.6 13.5 1 016.0 23.5 911.1 10.3 120 1 1 224.5 1 269.5 3.7 1 335.5 5.2 1 582.5 24.7 1 684.0 32.7 1 405.5 10.7 2 1 239.5 1 279.0 3.2 1 343.0 5.0 1 520.5 18.9 1 678.0 31.2 1 414.5 10.6 3 1 228.0 1 275.0 3.8 1 339.5 5.1 2 283.0 79.1 1 626.0 27.5 1 471.0 15.4 4 1 247.0 1 314.0 5.4 1 374.0 4.6 1 380.0 5.0 1 548.0 17.8 1 445.0 10.0 5 1 035.5 1 057.5 2.1 1 134.0 7.2 1 691.5 60.0 1 476.0 39.6 1 267.0 19.8 6 1 086.5 1 208.0 11.2 1 263.5 4.6 1 281.0 6.0 1 743.0 44.3 1 363.5 12.9 7 855.0 904.5 5.8 945.0 4.5 1 117.5 23.5 1 395.0 54.2 1 073.5 18.7 8 965 968.0 0.3 983.0 1.5 1 003.0 3.6 1 003.5 3.7 1 003.0 3.6 9 1 282 1 370.5 6.9 1 413.0 3.1 1 433.5 4.6 1 735.5 26.6 1 510.5 10.2 10 1 270 1 302.0 2.5 1 392.5 7.0 1 539.0 18.2 1 756.5 34.9 1 496.5 14.9 均值 1 143.3 1 194.8 4.5 1 252.3 4.8 1 483.2 24.4 1 564.6 31.3 1 345.0 12.7
下载: 导出CSV
表 6 尾翼装配工位模板装配计划
Table 6. Template assembly plan of tail assembly station
作业编号 开始时间 装配工时 物料计划到达时间 资源占用 紧后作业 AO15001 0 0 [0,0,0,0] 2,3,4 AO15002 0 12 0 [2,1,1,2] 7,8 AO15003 0 12 0 [2,1,1,2] 5,6,11 AO15004 0 14 0 [2,2,1,2] 10 AO15005 12 24 6 [3,2,1,2] 9 AO15006 12 52 0 [5,2,1,5] 8 AO15007 12 8 2 [2,2,1,5] 11,12 AO15008 132 21 126 [2,2,1,4] 18 AO15009 92 60 77 [4,3,1,5] 17 AO15010 14 48 7 [4,2,1,2] 13 AO15011 20 18 12 [6,4,1,5] 14,16,19 AO15012 132 48 117 [4,2,1,2] 16,18 AO15013 64 13 47 [4,3,1,4] 15 AO15014 64 28 48 [6,4,1,5] 15 AO15015 92 40 85 [6,4,1,5] 20 AO15016 180 16 175 [5,2,1,5] 21 AO15017 152 35 146 [6,4,1,5] 20 AO15018 187 14 180 [5,4,1,2] 20 AO15019 38 10 30 [2,1,1,2] 22 AO15020 201 32 196 [2,1,1,2] 21,22 AO15021 233 25 226 [2,1,1,2] 23 AO15022 233 11 228 [2,1,1,2] 23 AO15023 258 0 [0,0,0,0] 注:紧后作业一栏为简写, 如2表示作业编号为AO15002的作业。
下载: 导出CSV
-
[1] LU H, LIU X, PANG W, et al.Modeling and simulation of aircraft assembly line based on quest[J].Advanced Materials Research, 2012, 569:666-669. doi: 10.4028/www.scientific.net/AMR.569.666 [2] 郑倩, 奚立峰.飞机移动生产线作业调度问题的启发式算法[J].工业工程与管理, 2015, 20(2):116-121. doi: 10.3969/j.issn.1007-5429.2015.02.018ZHENG Q, XI L F.Heuristics for aircraft moving assembly line scheduling problem[J].Industrial Engineering & Management, 2015, 20(2):116-121(in Chinese). doi: 10.3969/j.issn.1007-5429.2015.02.018 [3] SHAN S, HU Z, LIU Z, et al.An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly[J].Information Technology and Management, 2017, 18(1):41-53. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=13d8a8b65447bbcc029253ff0d4b06b7 [4] 胡鑫铭, 陆志强.考虑物料配送的飞机移动生产线调度问题优化[J].北京航空航天大学学报, 2017, 44(12):2573-2582. doi: 10.13700/j.bh.1001-5965.2016.0932HU X M, LU Z Q.Optimization of aircraft moving assembly line scheduling problem considering material delivery[J].Journal of Beijing University of Aeronautics and Astronautics, 2017, 44(12):2573-2582(in Chinese). doi: 10.13700/j.bh.1001-5965.2016.0932 [5] BANERJEE A G, YUND W, YANG D, et al.A hybrid statistical method for accurate prediction of supplier delivery times of aircraft engine parts[C]//Proceedings of the ASME 2015 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference.New York: ASME, 2015: 286-295. [6] CHTOUROU H, HAOUARI M.A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J].Computers & Industrial Engineering, 2008, 55(1):183-194. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=4863e0a701273ff451d9559340169f83 [7] VAN DE VONDER S, DEMEULEMEESTER E, HERROELEN W.Proactive heuristic procedures for robust project scheduling:An experimental analysis[J].European Journal of Operational Research, 2008, 189(3):723-733. doi: 10.1016/j.ejor.2006.10.061 [8] CHAKRABORTTY R K, SARKER R A, ESSAM D L.Resource constrained project scheduling with uncertain activity durations[J].Computers & Industrial Engineering, 2017, 112:537-550. http://cn.bing.com/academic/profile?id=754b797bcb890b46fb5e1459f044b49b&encoded=0&v=paper_preview&mkt=zh-cn [9] BRUNI M E, DI PUGLIA PUGLIESE L, BERALDI P, et al.An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations[J].Omega, 2016, 71:66-84. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=58e737ec8a6fdb31140a727ea6aab951 [10] LAMBRECHTS O, DEMEULEMEESTER E, HERROELEN W.Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities[J].Journal of Scheduling, 2008, 11(2):121-136. doi: 10.1007/s10951-007-0021-0 [11] MA Z Q, DEMEULEMEESTER E, HE Z W, et al.A computational experiment to explore better robustness measures for project scheduling under two types of uncertain environments[J].Computers & Industrial Engineering, 2019, 131:382-390. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=129c5c5f83a183a4f94b9340733befef [12] VAN DE VONDER S, BALLESTÍN F, DEMEULEMEESTER E, et al.Heuristic procedures for reactive project scheduling[J].Computers & Industrial Engineering, 2007, 52(1):11-28. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=03c8597b34f23b552774c8699d22a47f [13] CHAKRABORTTY R K, SARKER R A, ESSAM D L.Single mode resource constrained project scheduling with unreliable resources[J].Operational Research, 2018, 1:1-35. http://cn.bing.com/academic/profile?id=b361b42913e0f17f22da12514d0cc28a&encoded=0&v=paper_preview&mkt=zh-cn [14] DAVARI M, DEMEULEMEESTER E.The proactive and reactive resource-constrained project scheduling problem[J].Journal of Scheduling, 2019, 22(2):211-237. doi: 10.1007/s10951-017-0553-x [15] CHAND S, SINGH H, RAY T.Evolving heuristics for the resource constrained project scheduling problem with dynamic resource disruptions[J].Swarm and Evolutionary Computation, 2019, 44:897-912. doi: 10.1016/j.swevo.2018.09.007 [16] 陆志强, 胡鑫铭, 朱宏伟.物料供给不确定环境下的飞机移动生产线动态调度方法[J].同济大学学报(自然科学版), 2019, 47(5):723-730. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=tjdxxb201905019LU Z Q, HU X M, ZHU H W.Dynamic scheduling method for aircraft moving assembly line under uncertain supply of material[J].Journal of Tongji University (Natural Science), 2019, 47(5):723-730(in Chinese). http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=tjdxxb201905019 [17] ZHANG G M, SMILOWITZ K, ERERA A.Dynamic planning for urban drayage operations[J].Transportation Research Part E:Logistics and Transportation Review, 2011, 47(5):764-777. doi: 10.1016/j.tre.2011.02.003 [18] 韩笑乐, 许可, 陆志强.集装箱码头泊位-堆场资源的鲁棒性模板决策[J].计算机集成制造系统, 2020, 26(3):784-794.HAN X L, XU K, LU Z Q.Robust scheduling of berth and yard resource template in container terminal[J].Computer Integrat-ed Manufacturing Systems, 2020, 26(3):784-794(in Chinese). -
下载:
点击查看大图
计量
- 文章访问数: 497
- HTML全文浏览量: 83
- PDF下载量: 121
- 被引次数: 0
