留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

考虑物料供应干扰的飞机移动生产线动态调度

卢斌 陆志强

卢斌, 陆志强. 考虑物料供应干扰的飞机移动生产线动态调度[J]. 北京航空航天大学学报, 2020, 46(8): 1521-1534. doi: 10.13700/j.bh.1001-5965.2019.0500
引用本文: 卢斌, 陆志强. 考虑物料供应干扰的飞机移动生产线动态调度[J]. 北京航空航天大学学报, 2020, 46(8): 1521-1534. doi: 10.13700/j.bh.1001-5965.2019.0500
LU Bin, LU Zhiqiang. Dynamic scheduling for aircraft mobile production line considering material supply interference[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(8): 1521-1534. doi: 10.13700/j.bh.1001-5965.2019.0500(in Chinese)
Citation: LU Bin, LU Zhiqiang. Dynamic scheduling for aircraft mobile production line considering material supply interference[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(8): 1521-1534. doi: 10.13700/j.bh.1001-5965.2019.0500(in Chinese)

考虑物料供应干扰的飞机移动生产线动态调度

doi: 10.13700/j.bh.1001-5965.2019.0500
基金项目: 

国家自然科学基金 61473211

国家自然科学基金 71171130

详细信息
    作者简介:

    卢斌  男, 硕士研究生。主要研究方向:生产调度的建模与优化

    陆志强  男, 博士, 教授, 博士生导师。主要研究方向:物流与供应链建模与优化、生产工程等

    通讯作者:

    陆志强, E-mail:zhiqianglu@tongji.edu.cn

  • 中图分类号: TP29

Dynamic scheduling for aircraft mobile production line considering material supply interference

Funds: 

National Natural Science Foundation of China 61473211

National Natural Science Foundation of China 71171130

More Information
  • 摘要:

    针对飞机装配过程中出现的物料供应延期干扰问题,对飞机移动生产线装配作业调度进行了研究。通过对物料供应信息的动态分析,将反应调度决策划分为固定决策和不同场景下的预测决策,并建立了物料供应干扰环境下的动态调度框架。在滚动决策点,以最小化与模板装配计划的偏差及工期的加权和期望值为目标函数,建立了二阶段近似优化模型。针对模型的决策逻辑,设计了以两阶段禁忌搜索算法为框架的启发式算法,求解滚动决策点的优化问题。不同规模下的数值实验表明,所提出的动态调度方法能够有效利用不断更新的物料供应信息,获得接近后验精确解的调度结果,且相比于传统的调度方法,所提方法能更有效地应对物料供应干扰。

     

  • 图 1  飞机移动生产线装配工位布局图

    Figure 1.  Assembly station layout of aircraft mobile production line

    图 2  Tq时刻的甘特图

    Figure 2.  Gantt chart at Tq

    图 3  Tq+1时刻的甘特图

    Figure 3.  Gantt chart at Tq+1

    图 4  动态调度框架

    Figure 4.  Framework of dynamic scheduling

    图 5  作业列表编码拆分示意图

    Figure 5.  Schematic diagram of job list coding splitting

    图 6  TTSBH算法流程

    Figure 6.  Flowchart of TTSBH algorithm

    图 7  解码过程示例

    Figure 7.  An example of decoding process

    图 8  TTSBH算法收敛曲线

    Figure 8.  Convergence curve of TTSBH algorithm

    图 9  不同干扰次数下的方法性能对比

    Figure 9.  Performance comparison of methods under different interference times

    图 10  不同工期权重下的方法性能对比

    Figure 10.  Performance comparison of methods under different duration weights

    图 11  后验求解调度结果(Z=280.5)

    Figure 11.  Scheduling results of posteriori solution(Z=280.5)

    图 12  本文方法调度结果(Z=284.5)

    Figure 12.  Scheduling results of proposed method(Z=284.5)

    图 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)

    图 15  RS方法调度结果(Z=339)

    Figure 15.  Scheduling results of right shift method(Z=339)

    图 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 可更新资源集合
    kK 资源种类编号
    T 时间集合
    tT 时间编号
    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(jJF) 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.018

    ZHENG 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.0932

    HU 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=tjdxxb201905019

    LU 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).
  • 加载中
图(16) / 表(6)
计量
  • 文章访问数:  276
  • HTML全文浏览量:  13
  • PDF下载量:  117
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-11
  • 录用日期:  2020-02-03
  • 刊出日期:  2020-08-20

目录

    /

    返回文章
    返回
    常见问答