留言板

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

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

考虑物料配送的飞机移动生产线调度问题优化

胡鑫铭 陆志强

胡鑫铭, 陆志强. 考虑物料配送的飞机移动生产线调度问题优化[J]. 北京航空航天大学学报, 2017, 43(12): 2573-2582. doi: 10.13700/j.bh.1001-5965.2016.0932
引用本文: 胡鑫铭, 陆志强. 考虑物料配送的飞机移动生产线调度问题优化[J]. 北京航空航天大学学报, 2017, 43(12): 2573-2582. doi: 10.13700/j.bh.1001-5965.2016.0932
HU Xinming, LU Zhiqiang. Optimization of aircraft moving assembly line scheduling problem considering material delivery[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(12): 2573-2582. doi: 10.13700/j.bh.1001-5965.2016.0932(in Chinese)
Citation: HU Xinming, LU Zhiqiang. Optimization of aircraft moving assembly line scheduling problem considering material delivery[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(12): 2573-2582. doi: 10.13700/j.bh.1001-5965.2016.0932(in Chinese)

考虑物料配送的飞机移动生产线调度问题优化

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

国家自然科学基金 61473211

国家自然科学基金 71171130

详细信息
    作者简介:

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

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

    通讯作者:

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

  • 中图分类号: TP29

Optimization of aircraft moving assembly line scheduling problem considering material delivery

Funds: 

National Natural Science Foundation of China 61473211

National Natural Science Foundation of China 71171130

More Information
  • 摘要:

    以飞机移动生产线为实际背景,将作业装配过程调度抽象为资源受限项目调度问题并进行了扩展,引入物料配送与线边存储决策,以及相关能力约束等实际因素,建立了以装配总工期最小化为目标的数学模型。针对模型,设计了一种以遗传算法为框架的启发式算法,其中结合了解生成算法和局部优化搜索算法。在遗传算法较优的全局搜索能力下,通过SCRDS算法综合作业顺序、资源约束、配送能力、线边空间等因素,联合决策作业开始时间、物料配送时间和物料在线边空间的存储位置,提出了两作业间物料摆放位置调整的局部优化搜索算法,对作业开始时间和物料配送时间进行再优化,进一步缩短了装配总工期。利用标准算例库进行了数值实验,实验结果证明了模型与算法的有效性。

     

  • 图 1  飞机移动生产线作业装配点及物料摆放位置示意图

    Figure 1.  Schematic of positions of assembly and material storage on aircraft moving assembly line

    图 2  染色体初始化示意图

    Figure 2.  Schematic of chromosome initialization

    图 3  遗传算法框架

    Figure 3.  Genetic algorithm framework

    图 4  基于物料摆放位置调整的局部优化搜索机理

    Figure 4.  Local optimization search mechanism based on material position adjustment

    图 5  不同算法计算工期结果比较

    Figure 5.  Comparison of durations of different algorithms

    表  1  小规模算例数值实验结果

    Table  1.   Numerical experiment results of small-scale examples

    作业规模 算例 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值。
    下载: 导出CSV

    表  2  不同算法工期结果和优化比例

    Table  2.   Durations and optimal proportion of different algorithms

    作业规模 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
    下载: 导出CSV
  • [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. http://www.sciencedirect.com/science/article/pii/S0743731514002226
    [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. doi: 10.1023/A:1010949931021
    [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. doi: 10.1007/s00500-015-1606-8.pdf
    [11] 王琰, 陆志强.基于多重约束的飞机移动装配线作业调度优化[J].工业工程与管理, 2011, 16(6):115-120. http://www.wenkuxiazai.com/doc/b613ef250066f5335a8121d0.html

    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). http://www.wenkuxiazai.com/doc/b613ef250066f5335a8121d0.html
    [12] 郑倩, 奚立峰.飞机移动生产线作业调度问题的启发式算法[J].工业工程与管理, 2015, 20(2):116-121. http://www.cnki.com.cn/Article/CJFDTotal-GYGC201502018.htm

    ZHENG Q, XI L F.Heuristics for aircraft moving assembly line scheduling problem[J].Industrial Engineering & Management, 2015, 20(2):116-121(in Chinese). http://www.cnki.com.cn/Article/CJFDTotal-GYGC201502018.htm
    [13] 葛茂根, 刘明周, 钱芳, 等.基于JIT的多目标总装准时物料配送方法研究[J].中国机械工程, 2011, 22(23):2834-2838. http://www.docin.com/p-516302403.html

    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). http://www.docin.com/p-516302403.html
    [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. http://connection.ebscohost.com/c/articles/100526854/multiobjective-optimization-algorithm-solve-part-feeding-problem-mixed-model-assembly-lines
    [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. doi: 10.1080/00207543.2015.1090032?journalCode=tprs20
    [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
  • 加载中
图(5) / 表(2)
计量
  • 文章访问数:  647
  • HTML全文浏览量:  124
  • PDF下载量:  456
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-12-12
  • 录用日期:  2017-01-20
  • 网络出版日期:  2017-12-20

目录

    /

    返回文章
    返回
    常见问答