高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ

基于头脑风暴算法的多处理机组合生产批量调度问题

王全武 徐震浩 顾幸生

王全武, 徐震浩, 顾幸生. 基于头脑风暴算法的多处理机组合生产批量调度问题[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20210427005
引用本文: 王全武, 徐震浩, 顾幸生. 基于头脑风暴算法的多处理机组合生产批量调度问题[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20210427005
WANG Quanwu, XU Zhenhao, GU Xingsheng. Multi-Processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20210427005
Citation: WANG Quanwu, XU Zhenhao, GU Xingsheng. Multi-Processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20210427005

基于头脑风暴算法的多处理机组合生产批量调度问题

doi: 10.14135/j.cnki.1006-3080.20210427005
基金项目: 国家自然科学基金(61573144,61673175,61603139)
详细信息
    作者简介:

    王全武(1996—),男,辽宁大连人,硕士生,主要研究方向为生产计划与调度。E-mail:Y30190752@mail.ecust.edu.cn

    通讯作者:

    徐震浩,E-mail:xuzhenhao@ecust.edu.cn

  • 中图分类号: TP301

Multi-Processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm

  • 摘要: 在生产调度领域中,受生产工艺等诸多因素的影响,往往每个生产过程都需要多台机器的同时参与加工。同时,待加工的工件数量较多,需要将每种类型的工件进行批量处理,以缩短生产周期。因此,本文在作业车间环境下,根据每个加工过程所参与机器的负荷,采用可变分批方案,提出了非混排多处理机组合生产批量调度模型,并结合头脑风暴算法,求解出最短加工时间。提出了一种改进的头脑风暴算法,引入贪婪思想与动态讨论机制,讨论次数随着算法的迭代而自适应变化,将全局搜索与局部搜索相结合,加强了算法的搜索能力。实验结果表明,改进的头脑风暴算法与基本的头脑风暴算法相比,求解效率更高,收敛速度更快。

     

  • 图  1  引入贪婪思想的BSO算法流程图

    Figure  1.  Flow chart of BSOGT

    图  2  逆序交叉重组操作

    Figure  2.  Reverse precedence operation crossover

    图  3  环变异操作

    Figure  3.  Ring mutation operation

    图  4  多处理机组合生产的甘特图

    Figure  4.  Gantt chart of MCBSP

    图  5  残差正态概率分布图

    Figure  5.  Externally studentized residuals

    图  6  模型预测值和实际值

    Figure  6.  Predicted vs actual

    图  7  不同算法的收敛曲线

    Figure  7.  Convergences of different algorithms

    表  1  工件加工的信息

    Table  1.   Information of job processing

    Job$ {O}_{1} $$ {O}_{2} $$ {O}_{3} $$ {O}_{4} $
    $ BH $$PT_m$$T_m$$J_m$$PT_m$$T_m$$J_m$$PT_m$$T_m$$J_m$$PT_m$$T_m$$J_m$
    115[7,5][20,24][4,5]9183[6,8][14,8][1,2]586
    215513661257162983
    315[5,7][19,25][2,1]6136[8,6][15,14][4,5]7113
    415516561628103766
    51561065142[6,5][7,13][5,4]763
    61582335142[6,3][9,12][5,4]5133
    下载: 导出CSV

    表  2  机器的最大负荷

    Table  2.   Maximum loads of the machines

    MachinePmax
    M19
    M29
    M36
    M49
    M56
    M613
    下载: 导出CSV

    表  3  不同规模算例工序总数统计表

    Table  3.   Statistical table of the total process for different scale calculation examples

    $ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $$ m $$\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}\;\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\;\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}$$\mathrm{P}\mathrm{i}\mathrm{e}\mathrm{c}\mathrm{e}$$\mathrm{T}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}\;\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}$
    $ 6\times 4 $6(1,10)(5,25)15$ 360 $
    $ 6\times 7 $11(1,10)(5,25)15$ 630 $
    $ 6\times 10 $17(1,10)(5,25)15$ 900 $
    $ 6\times 15 $27(1,10)(5,25)15$1\;350$
    $ 10\times 4 $6(1,10)(5,25)15$ 600 $
    $ 10\times 7 $11(1,10)(5,25)15$1\;050$
    $ 10\times 10 $17(1,10)(5,25)15$1\;500$
    $ 10\times 15 $27(1,10)(5,25)15$2\;250$
    $ 15\times 4 $6(1,10)(5,25)15$ 900 $
    $ 15\times 7 $11(1,10)(5,25)15$1\;575$
    $ 15\times 10 $17(1,10)(5,25)15$2\;250$
    $ 15\times 15 $27(1,10)(5,25)15$3\;375$
    $ 20\times 4 $6(1,10)(5,25)15$1\;200$
    $ 20\times 7 $11(1,10)(5,25)15$2\;100$
    $ 20\times 10 $17(1,10)(5,25)15$3\;000$
    $ 20\times 15 $27(1,10)(5,25)15$4\;500$
    $ 35\times 4 $6(1,10)(5,25)15$2\;100$
    $ 35\times 7 $11(1,10)(5,25)15$3\;675$
    $ 35\times 10 $17(1,10)(5,25)15$5\;250$
    $ 35\times 15 $27(1,10)(5,25)15$7\;875$
    $ 50\times 15 $29(1,10)(5,25)15$11\;250$
    下载: 导出CSV

    表  4  AVG的二次多项式模型的方差分析

    Table  4.   ANOVA of quadratic polynomial model for AVG

    VSMSFDSSP
    Model50913.2295.440.0180 (significant)
    $ \mathrm{A} $-population size882.0010.850.3875
    $ \mathrm{B} $-num of captain2686.4412.590.1519
    $ \mathrm{C} $-Relativity mutation length39846.65138.350.0004
    $ AB $10.8910.0100.9213
    $ AC $65.6110.0630.8088
    $ BC $829.4410.800.4013
    $ {A}^{2} $141.1510.140.7233
    $ {B}^{2} $111.2410.110.7531
    $ {C}^{2} $6092.8115.860.0460
    Residual7273.127
    Misfit term3807.7131.470.3505 (not significant)
    Error3465.414
    Sum58186.3416
    下载: 导出CSV

    表  5  初始种群质量分析

    Table  5.   Quality of initial individual

    $ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $AVG
    $ \mathrm{R}\mathrm{G} $$ \mathrm{O}\mathrm{B}\mathrm{L} $$ \mathrm{I}\mathrm{E}\mathrm{G} $
    $ 6\times 4 $1908.911721.851704.77
    $ 6\times 7 $2430.72201.462105.11
    $ 6\times 10 $3185.912888.432716.01
    $ 6\times 15 $4901.844416.574110.76
    $ 10\times 4 $2718.272417.852305.98
    $ 10\times 7 $3594.043319.463015.6
    $ 10\times 10 $4416.34151.553270.18
    $ 10\times 15 $6559.626027.685344.48
    $ 15\times 4 $3526.843241.393064.36
    $ 15\times 7 $4798.784485.384038.49
    $ 15\times 10 $6178.455751.015074.35
    $ 15\times 15 $8299.257781.186744.10
    $ 20\times 4 $3672.64002.24182.2
    $ 20\times 7 $5119.85346.65437.8
    $ 20\times 10 $6591.26959.66896
    $ 20\times 15 $8936.49081.59198.8
    $ 35\times 4 $6621.86948.66713.6
    $ 35\times 7 $8613.488378681
    $ 35\times 10 $10874.611249.811047
    $ 35\times 15 $13597.613840.614017.6
    $ 50\times 15 $27477.5226332.1521065.63
    下载: 导出CSV

    表  6  不同分批方式的对比

    Table  6.   Comparison of different batch modes

    $ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $
    $ \mathrm{m}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n} $$ \mathrm{A}\mathrm{M}\mathrm{V}\mathrm{R} $
    $ \mathrm{V}\mathrm{M} $$ \mathrm{C}\mathrm{M} $$ \mathrm{V}\mathrm{M} $$ \mathrm{C}\mathrm{M} $
    $ 6\times 4 $151115510.750.72
    $ 6\times 7 $149914450.790.83
    $ 6\times 10 $193820820.850.78
    $ 6\times 15 $295425410.810.73
    $ 10\times 4 $150219410.880.74
    $ 10\times 7 $220223410.890.81
    $ 10\times 10 $270429840.910.85
    $ 10\times 15 $388837990.790.72
    $ 15\times 4 $232128710.730.70
    $ 15\times 7 $307025770.840.80
    $ 15\times 10 $406247370.760.68
    $ 15\times 15 $549454390.780.71
    $ 50\times 15 $18962218450.680.59
    下载: 导出CSV

    表  7  算法性能对比表

    Table  7.   Performance comparison of algorithms

    $ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $
    ${\rm{RPD}}$${\rm{ WRE }}$${\rm{ BRE }}$
    $ \mathrm{B}\mathrm{S}\mathrm{O}\mathrm{G}\mathrm{T} $$ \mathrm{I}\mathrm{C}\mathrm{A} $$ \mathrm{M}\mathrm{A} $$ \mathrm{B}\mathrm{S}\mathrm{O} $$ \mathrm{B}\mathrm{S}\mathrm{O}\mathrm{G}\mathrm{T} $$ \mathrm{I}\mathrm{C}\mathrm{A} $$ \mathrm{M}\mathrm{A} $$ \mathrm{B}\mathrm{S}\mathrm{O} $$ \mathrm{B}\mathrm{S}\mathrm{O}\mathrm{G}\mathrm{T} $$ \mathrm{I}\mathrm{C}\mathrm{A} $$ \mathrm{M}\mathrm{A} $$ \mathrm{B}\mathrm{S}\mathrm{O} $
    $ 6\times 4 $000000000000
    $ 6\times 7 $00.190.270.3200.350.250.7100.180.530.85
    $ 6\times 10 $002.581.681.413.045.424.660.930.423.914.88
    $ 6\times 15 $04.636.0510.351.932.813.515.622.513.253.823.45
    $ 10\times 4 $03.793.138.322.122.235.294.441.853.524.142.95
    $ 10\times 7 $0.7701.286.131.952.823.502.732.463.706.893.55
    $ 10\times 10 $03.924.622.741.062.393.523.341.392.643.796.88
    $ 10\times 15 $06.535.929.883.1412.486.633.404.615.525.423.30
    $ 15\times 4 $00.953.352.871.471.763.743.791.291.541.532.67
    $ 15\times 7 $04.664.654.821.403.283.516.151.432.532.702.68
    $ 15\times 10 $0.402.3606.122.524.155.749.333.183.767.292.53
    $ 15\times 15 $02.473.724.751.164.345.333.851.043.473.502.97
    $ 20\times 4 $01.6320.270.881.331.195.053.931.050.883.281.67
    $ 20\times 7 $00.3220.262.331.211.533.601.721.281.922.682.62
    $ 20\times 10 $1.5506.563.111.632.105.642.541.892.405.642.54
    $ 20\times 15 $8.2203.744.211.641.553.467.521.342.053.483.44
    $ 35\times 4 $5.76025.357.500.841.621.551.901.023.643.080.97
    $ 35\times 7 $5.06010.415.691.661.757.342.842.752.465.181.61
    $ 35\times 10 $7.88015.506.603.822.142.611.103.763.021.601.52
    $ 35\times 15 $7.5506.410.861.563.182.255.603.341.682.404.36
    $ 50\times 15 $02.577.757.023.395.814.094.002.114.772.972.83
    下载: 导出CSV
  • [1] REITER S. A system for managing job-shop production[J]. The Journal of Business, 1966, 39(3): 371-393. doi: 10.1086/294867
    [2] REITER S, RICE D B. Discrete optimizing solution procedures for linear and nonlinear integer programming problems[J]. Management Science, 1966, 12(11): 829-850. doi: 10.1287/mnsc.12.11.829
    [3] HUANG R, YU T. An effective ant colony optimization algorithm for multi-objective jobshop scheduling with equal-size lot-splitting[J]. Applied Soft Computing, 2017, 57: 642- 656. doi: 10.1016/j.asoc.2017.04.062
    [4] ANDRZEJ B, FRANK W. Flexible job shop scheduling with lot streaming and sublot size optimization[J]. International Journal of Production Research 2018, 56(19): 6391-6411.
    [5] JUAN M N. Production scheduling and lot streaming at flexible job-shops environments using constraint programming[J]. Computer & Industrial Engineering, 2019, 136: 252-264.
    [6] DROZDOWSKI M. Scheduling multiprocessor tasks — An overview[J]. European Journal of Operational Research, 1996, 94(2): 215-230. doi: 10.1016/0377-2217(96)00123-3
    [7] JIANG E D, WANG L, WANG J J. Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks[J]. Tsinghua Science and Technology, 2021, 26(5): 646-663. doi: 10.26599/TST.2021.9010007
    [8] CHEN J, LEE C Y. General multiprocessor task scheduling[J]. Naval Research Logistics, 1999, 46(1): 72-74.
    [9] 吕媛媛, 樊坤, 瞿华, 等. 多目标粒子群算法求解混合多处理机任务作业车间调度问题研究[J]. 小型微型计算机系统, 2021: 1-8. doi: 10.3969/j.issn.1000-1220.2021.01.001
    [10] LIU X F, LI W D. Approximation algorithms for the multiprocessor scheduling with submodular penalties[J]. Optimization Letters, 2021: 1-16.
    [11] MOGHADDAM M E, BONYADI M R. An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem[J]. International Journal of Parallel Programming, 2012, 40(2): 225-257. doi: 10.1007/s10766-011-0179-0
    [12] SHI Y. Brain storm optimization algorithm[C]// International Conference in Swarm Intelligence. Chongqing, China: DBLP, 2011: 303-309.
    [13] 曹国刚, 朱信玉, 陈颖, 等. 基于改进头脑风暴优化算法的医学图像配准方法[J]. 数据采集与处理, 2020, 35(4): 730-738.
    [14] 李怡敏, 王宝珠, 刘翠响, 等. DBBSO算法在低空航线规划中的应用[J]. 现代电子技术, 2019, 42(22): 108-112.
    [15] 李捷, 张远春, 汪龙, 任佳, 等. 基于纵向变异头脑风暴算法的短期水火发电调度[J]. 电工材料, 2019(4): 28-32.
    [16] 张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004(23): 83-87.
    [17] 陈祥, 朱传军, 张超勇. 基于文化基因算法的开放车间调度问题研究[J]. 工业工程, 2018, 21(6): 16-22.
    [18] 徐震浩, 王程, 顾幸生. 基于DICA的存储受限流水车间调度[J]. 华东理工大学学报(自然科学版), 2018, 44(4): 563-572.
  • 加载中
图(7) / 表(7)
计量
  • 文章访问数:  79
  • HTML全文浏览量:  26
  • PDF下载量:  7
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-04-27
  • 网络出版日期:  2021-07-28

目录

    /

    返回文章
    返回