高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

离散水波优化算法求解带批处理的混合流水车间批量流调度问题

    作者简介: 王文艳(1994—),女,江苏淮安人,硕士生,研究方向为生产调度、智能算法;
    通讯作者: 徐震浩, xuzhenhao@ecust.edu.cn
  • 中图分类号: TP301

Discrete Water Wave Optimization Algorithm for Hybrid Flowshop Lot-Streaming Scheduling Problem with Batch Processing

    Corresponding author: XU Zhenhao, xuzhenhao@ecust.edu.cn ;
  • CLC number: TP301

  • 摘要: 针对实际生产系统中生产方式复杂多样的特点,研究了带批处理的混合流水车间批量流调度问题。综合考虑批处理机容量和不相关离散机加工能力,提出了一种可变分批方法,以最小化完工时间为目标建立了调度模型,并提出了一种动态连续加工策略来优化目标函数。同时提出了一种离散水波优化(DWWO)算法求解模型。结合分批特点与优化目标,设计了4种解码方式对机器选择及工件的加工顺序进行优化;利用块最优插入、交叉操作和多邻域搜索对操作算子进行改进,增强了局部搜索能力;提出了一种替换差解的操作提高算法的收敛能力。最后,采用实验设计的方法对算法的参数进行了标定;并设计了不同规模的算例,对算法的性能进行评估。实验结果表明DWWO算法能够有效解决带批处理的混合流水车间批量流调度问题。
  • 图 1  参数水平影响趋势图

    Figure 1.  Trend graphs of influence of parameters

    图 2  加工序列为$ {\pi }_{1} $时两种策略下的甘特图

    Figure 2.  Gantt charts under two strategies when the processing sequence is $ {\pi }_{1} $

    图 3  各算法求解不同规模问题的迭代曲线

    Figure 3.  Iterative curves of each algorithm for solving problems of different scales

    表 1  不同解码方案对比结果

    Table 1.  Comparison results of different decoding schemes

    nmAVG
    IIIIIIIV
    641 224.01 220.01 231.01 222.0
    71 520.41 520.01 522.01 522.0
    102 200.02 200.02 200.02 200.0
    153 025.02967.03 140.03 058.0
    1041 605.01 605.01 605.01 605.0
    72 040.82 037.02 039.22 039.4
    102 844.52 832.02 884.32 832.0
    153 688.43 652.83 714.73 712.5
    1542 280.82 278.02 277.82 277.5
    72 719.02 719.02 790.32 786.8
    103 488.83 447.03 486.03 449.0
    154 400.94 344.04 462.94 397.2
    2042 968.02 968.02 968.02 968.0
    73 378.63 378.63 378.63 378.6
    104 436.64 326.04 435.04 381.0
    155 297.25 170.05 355.45 278.4
    3545 254.05 254.05 254.05 254.0
    76 010.66 009.06 011.46 009.8
    106 874.06 847.06 937.86 861.0
    157 753.87 686.47 842.87 786.4
    5047 681.07 681.07 681.07 681.0
    78 559.98 559.68 560.08 559.6
    109 307.49 256.89 326.89 301.6
    1510 175.410 094.410 247.410 226.8
    下载: 导出CSV

    表 2  两种策略下的实验结果对比

    Table 2.  Comparison of experimental results under two strategies

    nmAVG
    With dynamic continuous processingWithout dynamic continuous processing
    641 122.01 220.0
    71 376.51 520.0
    102 021.02 200.0
    152 742.82 967.0
    1041 531.01 605.0
    71 904.02 037.0
    102 658.02 832.0
    153 337.83 652.8
    1542 192.02 278.0
    72 642.02 719.0
    103 293.03 447.0
    153 983.64 344.0
    2042 888.02 968.0
    73 308.03 378.6
    104 202.04 326.0
    154 853.05 170.0
    3545 223.05 254.0
    75 891.06 009.0
    106 715.66 847.0
    157 377.67 686.4
    5047 622.07 681.0
    78 478.28 559.6
    109 145.29 256.8
    159 787.010 094.4
    下载: 导出CSV

    表 3  DWWO,FOA,MMBO,WWO,IGA_V算法对比结果

    Table 3.  Comparison results of DWWO, FOA, MMBO, WWO and IGA_V

    nmMRPD$ \times {10}^{2} $SDRPD$ \times {10}^{2} $BRPD$ \times {10}^{2} $
    DWWOFOAMMBOWWOIGA_VDWWOFOAMMBOWWOIGA_VDWWOFOAMMBOWWOIGA_V
    64000000000000000
    70.4000000.40000000000
    10000000000000000
    150.4000000.32000000000
    104000000000000000
    700.173.711.010.3200.080.600.640.32002.570.210
    10000.4100000.810000000
    150.260.321.470.580.340.320.230.420.290.33000.660.000
    15400.240.320.320.2500.12000.22000.320.320
    7003.440.640.07000.420.450.14002.990.000
    10000.7200000.590000000
    150.043.066.224.201.830.040.460.601.070.9402.345.152.110.60
    2040.030.150.820.610.070.030.240.260.36000.070.070.070.07
    701.372.581.540.7900.460.650.410.400.391.870.910.21
    10001.930.190000.110.250001.8600
    150.413.254.595.243.310.570.920.510.131.2302.054.015.031.63
    354000000000000000
    70.10.521.11.420.810.080.1900.270.6400.251.11.020.32
    100.440.591.491.190.580.220.070.130.180.1200.551.230.970.45
    150.272.134.254.072.120.250.480.470.670.8601.373.872.890.86
    5040000.120.050000.10.0600000
    70.010.171.090.692.080.020.120.150.261.700.040.80.260.02
    100.080.460.931.320.850.060.220.10.290.4300.140.890.890.26
    150.342.43.824.442.830.250.6600.320.601.383.823.941.74
    下载: 导出CSV
  • [1] 郝尚刚, 陈华平, 李小林. 两阶段流水车间批处理机调度的聚类算法[J]. 计算机工程, 2012, 38(14): 272-275. doi: 10.3969/j.issn.1000-3428.2012.14.081
    [2] QIN M, WANG R S, SHI Z S, et al. A genetic programming-based scheduling approach for hybrid flow shop with a batch processor and waiting time constraint[J]. IEEE Transactions on Automation Science and Engineering, 2019, PP(99): 1-2.
    [3] 张煜, 容芷君, 马杰. 含批处理机和多工件族的混合流水车间问题[J]. 计算机集成制造系统, 2014, 20(2): 407-413.
    [4] LIU M, YANG X N, ZHANG J T, et al. Scheduling a tempered glass manufacturing system: a three-stage hybrid flow shop model[J]. International Journal of Production Research, 2017, 55(19/20): 181-190.
    [5] 王君妍, 王薛苑, 轩华. 带批处理机的多阶段柔性流水车间调度优化[J]. 郑州大学学报(工学版), 2017, 38(5): 86-90.
    [6] 轩华, 王君妍, 王薛苑. 初始阶段为串行批处理的FFSP改进遗传算法[J]. 控制工程, 2018, 25(8): 1415-1420.
    [7] ZHANG B, PAN Q K, GAO L, et al. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming[J]. Applied Soft Computing, 2017, 52: 14-27. doi: 10.1016/j.asoc.2016.12.021
    [8] QIN W, ZHUANG Z L, LIU Y, et al. A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly[J]. Computers & Industrial Engineering, 2019, 138: 106115.
    [9] NEJATI M, MAHDAVI I, HASSANZADEH R, et al. Multi-job lot streaming to minimize the weighted completion time in a hybrid flow shop scheduling problem with work shift constraint[J]. International Journal of Advanced Manufacturing Technology, 2014, 70(1/4): 501-514.
    [10] WANG S S, KURZ M, MASON S J, et al. Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups[J]. International Journal of Production Research, 2019, 57(22): 1-15.
    [11] ZHENG Y J. Water wave optimization: A new nature-inspired metaheuristic[J]. Computers and Operations Research, 2015, 55: 1-11. doi: 10.1016/j.cor.2014.10.008
    [12] ZHAO F Q, LIU H, ZHANG Y. A discrete Water wave optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2018, 91: 347-363. doi: 10.1016/j.eswa.2017.09.028
    [13] LAKSHMINARASIMMAN L, SIVA M, BALAMURUGAN R. Water wave optimization algorithm for solving multi-area economic dispatch problem[J]. International Journal of Computer Applications, 2017, 167(5): 19-27. doi: 10.5120/ijca2017914247
    [14] SIVA M, BALAMURUGAN R, LAKSHMINARASIMMAN L. Water wave optimization algorithm for solving thermal unit maintenance scheduling[J]. IOSR Journal of Electrical and Electronics Engineering, 2017, 12(3): 61-70. doi: 10.9790/1676-1203026170
    [15] 任彩乐. 基于候鸟优化算法的混合流水车间调度问题研究[D]. 武汉: 华中科技大学, 2019.
    [16] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9): 1917-1927.
    [17] NAWAZ M, ENSCORE J E, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega, 1983, 11(1): 91-95. doi: 10.1016/0305-0483(83)90088-9
    [18] 陈飞跃, 徐震浩, 顾幸生. 基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度[J]. 华东理工大学学报 (自然科学版), 2017, 43(3): 425-435.
    [19] 刘欢. 水波优化算法及在车间调度问题中的应用研究[D]. 兰州: 兰州理工大学, 2018.
    [20] 杜利珍, 王震, 柯善富, 等. 混合流水车间调度问题的果蝇优化算法求解[J]. 中国机械工程, 2019, 30(12): 1480-1485. doi: 10.3969/j.issn.1004-132X.2019.12.015
    [21] ZHANG B, PAN Q K, GAO L, et al. A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem[J]. Soft Computing, 2019, 23: 8101-8129. doi: 10.1007/s00500-018-3447-8
  • 加载中
图(3)表(3)
计量
  • 文章访问数:  416
  • HTML全文浏览量:  210
  • PDF下载量:  2
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-08-31
  • 网络出版日期:  2020-12-16

离散水波优化算法求解带批处理的混合流水车间批量流调度问题

    作者简介:王文艳(1994—),女,江苏淮安人,硕士生,研究方向为生产调度、智能算法
    通讯作者: 徐震浩, xuzhenhao@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237

摘要: 针对实际生产系统中生产方式复杂多样的特点,研究了带批处理的混合流水车间批量流调度问题。综合考虑批处理机容量和不相关离散机加工能力,提出了一种可变分批方法,以最小化完工时间为目标建立了调度模型,并提出了一种动态连续加工策略来优化目标函数。同时提出了一种离散水波优化(DWWO)算法求解模型。结合分批特点与优化目标,设计了4种解码方式对机器选择及工件的加工顺序进行优化;利用块最优插入、交叉操作和多邻域搜索对操作算子进行改进,增强了局部搜索能力;提出了一种替换差解的操作提高算法的收敛能力。最后,采用实验设计的方法对算法的参数进行了标定;并设计了不同规模的算例,对算法的性能进行评估。实验结果表明DWWO算法能够有效解决带批处理的混合流水车间批量流调度问题。

English Abstract

  • 随着生产方式的不断改进,一些特殊工艺如钢铁炼制中的热处理操作、半导体芯片的预烧工序等常需要进行批处理[1]。目前,涉及批处理的混合生产方式已成为混合流水车间调度问题的一个重要研究方向,有很多学者针对带批处理的混合流水车间调度问题进行了研究。Qin等[2]考虑了机器有限等待时间,研究了同时具有批处理机和离散机的两级混合流水车间调度。张煜等[3]和Liu等[4]针对三阶段混合批处理机和非批处理机的混合流水车间问题进行了研究。王君妍等[5]和轩华等[6]在不同约束条件下,研究了中间阶段有多台批处理机、其他阶段为离散机的多阶段混合流水车间调度问题。然而,这些研究成果都是针对单个加工工件,没有考虑工件的批量性。在实际制造过程中,批量生产工件的情况普遍存在,因此,批量流调度的研究对于制造业具有重要的现实意义。

    批量流调度是将批量生产的工件划分为多个子批,并以子批为单位进行转移以减少机器闲置时间,提高生产效率。目前已有大量文献对批量流调度问题进行了研究。Zhang等[7]和Qin等[8]分别提出了改进候鸟优化算法和两阶段蚁群算法,以解决等量分批的混合流水车间批量流调度问题。Nejati等[9]研究了带有轮班约束的混合流水车间调度问题,在一致分批下采用GA算法对工件排序进行优化。Wang等[10]研究了可变分批下的混合流水车间批量流调度问题,提出一种混合线性规划模型确定了工件的划分与排序。就分批方法而言,对等量分批和一致分批的研究相对较多,可变分批因其较灵活、子批的数量和大小具有不确定性使得模型求解难度增加,因而到目前为止相关研究较少。本文将带批处理的混合流水车间问题与批量流调度问题相结合,对带批处理的混合流水车间批量流调度问题进行研究,针对批处理机与离散机不同的加工特点,提出了一种基于批处理机容量与不相关离散机加工能力的可变分批方法,能够减少分批的不确定性,降低搜索空间的维度。

    水波优化(Water Wave Optimization, WWO)[11]算法是一种针对连续优化问题的智能算法。受浅水波模型的启发,WWO算法利用传播、折射和碎浪来实现算法的搜索过程。WWO算法具有结构简单、参数少、易于实现等特点,可用于调度[12]、经济开发[13]、发电机组检修调度[14]等实际问题。本文在WWO算法的基础上,提出了一种离散水波优化(DWWO)算法来解决带批处理的混合流水车间批量流调度问题。

    • 带批处理的混合流水车间批量流调度问题可以描述为:$ n $种工件进行$ m $道工序的加工,每道工序$ k $上有$ {x}_{k}({x}_{k}\geqslant 1) $台不相关并行机,每台机器加工批量有限。其中,第$ a $($1 < a\leqslant m$)道工序为批处理工序,由单台批处理机构成,即$ {x}_{a}=1 $;其他工序为一般加工工序,工件在每道工序上具有可选机器集。一般工序上,工件根据所选离散机的加工能力划分成多个子批,子批中的工件属于同一种工件且同种工件子批批量大小相等;批处理工序上,工件根据批处理机容量分为大小相等的批处理子批,批处理子批中可包含不同种类的工件且加工时间由这一批内加工时间最长的工件决定。存在如下假设:加工阶段一致,工件在不同工序上具有各自的可选机器集,且加工时间不同;针对每道工序,同种工件的子批连续加工,即加工批之间无混排;离散机的最大加工能力已知。同一子批的工件必须连续加工;机器在操作前需要准备,其中可分离准备操作可在工件到达前完成,不可分离准备操作在工件到达之后进行,和运输时间一起包含在加工时间中。

    • $ k $$ i $:工序序号和工件序号,$ k\in \{{1,2},3, \cdots ,m\} $$ i\in \{{1,2},3, \cdots ,n\} $

      $ a $:批处理工序,($1 < a\leqslant m$);

      $ {x}_{k} $:第$ k $道工序上不相关并行机的数量($ {x}_{a} $为批处理机工序上批处理机的数量,$ {x}_{a}=1 $);

      $ {PM}_{kh} $:第$ k $道工序上第$ h $台机器最大加工能力,$ h\in \{{1,2},3, \cdots ,{x}_{k}\} $

      $ {BS}_{i} $:工件$ i $的总量;

      $ {s}_{ik} $:工件$ i $在工序k上可选机器的数量;

      $ {\phi }_{ik}=\{{\varphi }_{ik}^{1}, \cdots ,{\varphi }_{ik}^{h}, \cdots ,{\varphi }_{ik}^{{x}_{k}}\} $:工件$ i $在工序$ k $的可选机器集,若工序$ k $的第$ h $台机器为工件$ i $的可选机器,则$ {\varphi }_{ik}^{h}=1 $,否则为0;$ \sum _{h=1}^{{x}_{k}}{\varphi }_{ik}^{h}={s}_{ik} $

      $ {T}_{ik}=\{{t}_{ik}^{1}, \cdots ,{t}_{ik}^{h}, \cdots ,{t}_{ik}^{{x}_{k}}\} $:工件$ i $在工序$ k $的加工时间,若第$ h $台机器不是工件$ i $的可选机器,则$ {t}_{ik}^{h}=0 $

      $ {PT}_{ik}=\{{pt}_{ik}^{1}, \cdots ,p{t}_{ik}^{h}, \cdots ,{pt}_{ik}^{{x}_{k}}\} $:工件$ i $在工序$ k $的分离准备时间,若工序$ k $的第$ h $台机器不是工件$ i $的可选机器,则$ {pt}_{ik}^{h}=0 $

      $ BM\_pt $:批处理机可分离准备时间;

      $ {em}_{ik} $:工件$ i $在工序$ k $上选择的机器序号,$ {\varphi }_{ik}^{{em}_{ik}} $=1;

      $ {MI}_{ik}^{h} $:第$ k $道工序上第$ h $台机器加工完工件$ i $的空闲时刻;

      $ {BH}_{ik} $:工件$ i $在工序$ k $上划分的子批数;

      $ {BN}_{ikl} $:工件$ i $在工序$ k $上第$ l $个子批的批量大小 ($ {BS}_{i}=\sum _{l=1}^{{BH}_{ik}}{BN}_{ikl} $,$ l\in \{{1,2}, \cdots ,{BH}_{ik}\} $);

      $ {PTS}_{ik} $$ {PTE}_{ik} $:工件$ i $在工序$ k $的准备操作开始时间和结束时间;

      $ {M}_{ikl} $$ {P}_{ikl} $: 工件$ i $在第k道工序上第$ l $个子批的机器约束和工件约束;

      $ BM\_BH $:批处理工序的子批数量;

      $ {BM\_BN}_{{l}^{b}} $:批处理工序上第$ {l}^{b} $个子批批量($\sum \limits_{i=1}^{n} {BS}_{i}={l}^{b}\in \{{1,2}, \cdots ,BM\_BH\}$,下同);

      $ BM\_PTS $$ BM\_PTE $:批处理机准备操作开始时间和结束时间;

      $ {BM\_M}_{{l}^{b}} $$ BM\_{P}_{{l}^{b}} $:批处理机上第$ {l}^{b} $个子批的机器约束和工件约束;

      $ {NI}_{i{l}^{b}} $:批处理子批$ {l}^{b} $中工件$ i $的批量;

      $ {BT}_{i{l}^{b}} $:批处理子批$ {l}^{b} $中最先到达的工件和最后到达的工件中工件$ i $的数量;

      $ {E}_{i{l}^{b}} $:批处理子批$ {l}^{b} $中含有工件$ i $时,为1;否则,为0。

    • $ {\pi }_{k}=[{b}_{k,1},{ \cdots ,b}_{k,g}, \cdots ,{b}_{k,n}] $:第$ k $道工序上工件的加工顺序,$ k\ne a $$ {b}_{k,g}\in \left\{{1,2}, \cdots ,n\right\},g\in \{{1,2},3, \cdots ,n\} $

      $ {D}_{ikh} $:当工件$ i $在第k道工序上选择第$ h $台机器则值为1,否则值为0;

      $ {TS}_{ikl} $$ {TE}_{ikl} $:工件$ i $在工序$ k $上第$ l $个子批的加工开始时间和结束时间;

      $W=[\left({\alpha }_{1},{\beta }_{1},{\gamma }_{1}\right),\left({\alpha }_{2},{\beta }_{2},{\gamma }_{2}\right), \cdots ,\left({\alpha }_{r},{\beta }_{r},{\gamma }_{r}\right), \cdots ,\left({\alpha }_{L}, {\beta }_{L},{\gamma }_{L}\right)]$:工序$ a-1 $中按完工时间升序排列的子批序列,$ \alpha $代表子批所属工件类型,$ \beta $代表子批批量,$ \gamma $代表子批的结束加工时间,$ L=\sum \limits_{i=1}^{n}{BH}_{i(a-1)} $

      $ {BM\_TS}_{{l}^{b}} $$ {BM\_TE}_{{l}^{b}} $:批处理机上第$ {l}^{b} $个子批的加工开始时间和结束时间。

      根据上述描述和符号,采用基于批处理机容量和不相关离散机加工能力的可变分批策略,建立了具有批处理的混合流水车间批量流调度问题的模型,目标是尽量缩短完工时间:

      可行的调度方案,必须满足以下约束条件:

      (1)工件$ i $在工序$ k $阶段的子批批量:

      $ k\ne a $时,

      其中,[ ]表示取整;\表示取余。

      $ k=a $时,

      其中,inf为下确界。

      (2)工件$ i $在工序$ k (k\ne a) $上可分离准备操作的开始时间和结束时间:

      (3)工件$ i $子批$ l $在工序$ k $的加工开始时间和结束时间:

      (4)对于一般加工工序,若待加工子批是此工件第一个子批,则机器在准备操作之后即准备就绪;否则,需要等待上一个子批加工完成。

      (5)根据可变分批的特征,工件$ i $$ k\left(k\geqslant 2\right) $道工序子批$ l $中的工件可能属于上道工序中的多个子批,当子批$ l $中的全部工件到达机器时才开始加工,会造成先到达工件等待时间太长从而使makespan增加。为了缩短makespan,允许子批$ l $中先到达工件提前加工,但由于同一子批必须连续加工,因此需保证先到达工件加工完成时剩余的工件正好到达(下文用动态连续加工表述此策略),将这个时刻称为子批$ l $的转折点。

      其中:$ {l}_{s} $$ {l}_{e} $分别为工件$ i $在工序$ k $的子批$ l $中最先到达工件和最后到达工件在工序$ k-1 $中的子批号;$ {RS}_{ikl} $为子批$ l $中在转折点之前到达的工件数;Po为到达即可加工的剩余工件所属子批在工序$ k-1 $的序号,即子批$ l $中在转折点到达的工件在工序$ k-1 $的子批序号。

      (6)一般工序$ k $上机器加工完工件$ i $的空闲时刻:

      (7)批处理工序的批处理子批批量:

      (8)批处理工序的准备操作开始时间和结束时间:

      (9)批处理子批$ {l}^{b} $开始加工时间:

      (10)若当前子批是批处理机的第一个加工子批,则批处理机在准备操作之后即可工作。否则需等待批处理机完成前一子批的加工。

      (11)根据批处理机对子批中工件同时加工的特点,批处理子批$ {l}^{b} $的全部工件到达时才能开始加工。

      其中,$ {{l}^{b}}_{e} $为批处理子批$ {l}^{b} $中最后到达的工件在上道工序所属子批在W中的序号,即:

      (12)批处理子批的加工结束时间:

      其中,$ {{l}^{b}}_{s} $为批处理子批$ {l}^{b} $中最先到达的工件在上道工序所属子批在W中的序号。

    • WWO算法结构简单、参数较少,目前只用于解决连续问题。本文将WWO算法进行离散化处理并进行了改进,使其能更好地解决混合流水车间环境下的批量流调度问题。

    • 以工件在第一道工序的加工顺序为编码方案,如有6种工件,编码后产生个体$ \pi =\left[2 \; 5 \;3 \;6 \;4 \;1\right] $:在此个体中,数字代表各工件的序号,数字的排序为各工件在第一道工序上的加工顺序。为了获得切实有效的调度方案,解码时需要解决两个问题:一是各工件在后续工序的加工顺序;二是工件在每道工序的机器选择。对于工件在后续工序的加工顺序,本文根据先入先出(First In First Out,FIFO)规则,设计了两种策略:(1)子批优先,根据每种工件的第一个子批在工序$ k $的完工时间决定工件在工序$ k+1 $的加工顺序;(2)工件优先,考虑工件最后一个子批在工序$ k $的完工时间,若工件在工序$ k $上优先完工,则安排此工件在工序$ k+1 $上优先加工。针对工件在每道工序上机器的选择问题,设计了如下两种策略:

      (1) 机器机器最短完工策略$ {\rm{min}}\left( {E{P_{ikh}}} \right) $。若工件$ i $在工序$ k $上选择第$ h $台机器上加工,则机器$ h $的完工时间为

      其中,$ {Batch\_ET}_{j} $为工件$ i $在工序$ k-1 $上第$ j $个子批完成加工后立即在工序$ k $$ h $台机器上加工的完工时间。

      机器确定后,更新机器的空闲时间,即${MI}_{ik}^{h}= {EP}_{ikh}$

      (2) 机器加工均衡策略$ {\rm{min}}\left({AP}_{ikh}\right) $。确定每道工序加工机器时,在可选机器集中选择加工完工件$ i $后机器总加工时间最短的机器,并将所对应的加工时间累加到该机器的总加工时间中。

      机器确定后,更新所选机器的总工作时间,即$ {AI}_{kh}={AP}_{ikh} $

      假设$ n $种工件,解个体为$\pi =[\pi \left(1\right),\pi \left(2\right), \cdots ,\pi \left(n\right)]$,则根据上述策略可以组合成4种解码方案:(I)子批优先+机器最短完工。在第一道工序($ k $=1)上,按照加工顺序$ \pi =[\pi \left(1\right),\pi \left(2\right), \cdots ,\pi \left(n\right)] $,采用机器最短完工策略选择机器,并根据机器最大加工能力将工件分批,确定每个子批加工时段。在后续工序$(k= {2,3}, \cdots ,{{m}}{\text{且}}k\ne a)$,加工顺序$\pi {'}=[\pi {'}\left(1\right),\pi {'}\left(2\right), \cdots ,\pi {'}\left(n\right)]$是按照各工件在上一工序上第一个子批的加工结束时间升序排列生成,并采用机器最短完工选择机器,根据所选机器的最大加工能力将工件分批,确定子批加工时段。在批处理工序$ (k=a) $,各工件的子批动态到达批处理机,若已到达的工件满足批处理机容量则合成一个子批进行加工,确定子批加工时段。(II)子批优先+机器加工均衡。采用机器加工均衡策略选择机器,其他过程与方案(I)类似。(III)工件优先+机器最短完工。在后续工序,工件加工顺序按照各工件在上一工序的最后一个子批的加工结束时间升序排列生成,其他过程与方案(I)类似。(IV)工件优先+机器加工均衡。采用机器加工均衡策略选择机器,其他过程与方案(I)类似。

    • 块最优插入是从最优插入[15]发展而来的,是一种有效的局部搜索算法。作为最优插入的拓展,能够提高局部搜索能力,但若在每一次迭代中都随机产生一个长度为$ k $的块进行块最优插入,会导致个体的进化过程波动太大。本文采用基于块最优插入的传播操作,将波长$ {\lambda }_{g} $作为个体$ g $进行块最优插入时块的长度,则传播操作如下:

      Input: the current individual $ g $,the wavelength of $ g $$ {\lambda }_{g} $

      Output: individual $ {g}^{s} $

       $ g1\leftarrow $randomly select $ {\lambda }_{g} $ consecutive jobs from $ g $

       $ g{'}\leftarrow $the remaining part of $ g $

        for $ i $=1:n-$ {\lambda }_{g} $+1 do

         insert $ g_1 $ into the $ i{\rm{t}}{\rm{h}} $ position of $ g{'} $ and        calculate the objective function value $ {C}_{i} $

        if $ i $ = = 1 then

         the optimal objective function value        $ {C}^{*}\leftarrow {C}_{i} $

         the optimal position y$ \leftarrow {\rm{i}} $

         else

         if $ {C}_{i}<{C}^{*} $ then

          the optimal objective function value        $ {C}^{*}\leftarrow {C}_{i} $

          the optimal position $ y\leftarrow i $

         end if

        end if

       end for

      insert $ g_1 $ into position $ y $ to obtain the sequence $ {g}^{s} $

    • 如果个体$ g $经过多次传播均未找到更优解,且其波高$ {h}_{g} $已减为0,需要对个体$ g $执行折射操作。将个体$ g $与目前的最优个体$ {g}^{*} $进行交叉。随机在个体$ {g}^{*} $中选择长度为$ len $的连续序列$ {g}_{1}^{*} $,并将其中的数在个体$ g $中删除,个体$ g $剩余的部分用序列$ {g}_{1} $表示。根据$ {g}_{1}^{*} $$ {g}^{*} $中的位置将其放置在新个体$ {g}^{r} $中,并将$ {g}_{1} $中的数依次放置在$ {g}^{r} $的剩余位置,得到新个体$ {g}^{r} $。若折射后新个体$ {g}^{r} $的适应度值优于原个体$ g $的适应度值则$ g={g}^{r} $;否则,原个体$ g $保持不变。

    • 若个体$ g $进行传播操作后产生的个体$ {g}^{s} $优于当前最优个体$ {g}^{*} $,则对个体$ {g}^{s} $进行碎浪操作。本文结合基于反转逆序法、打乱互换法[16]的多邻域搜索对$ {g}^{s} $进行碎浪操作。碎浪操作的具体步骤如下:

      (1)随机产生一个小于P的循环次数$ r{\rm{and}} $,令$ {g}^{s{'}}={g}^{s} $,令$ i $=1。

      (2)若$ i $>$ r{\rm{and}} $,则令$ {g}^{s}={g}^{s{'}} $并输出最优的个体$ {g}^{s} $

      (3)对个体$ {g}^{s} $进行反转逆序操作,产生一个新解$ {g}_{1}^{s} $,比较新解与最优解的目标函数值。若C($ {g}_{1}^{s} $)<C($ {g}^{s{'}} $),则$ {g}^{s{'}}={g}_{1}^{s} $

      (4)对个体$ {g}^{s} $进行打乱互换操作,产生一个新解$ {g}_{1}^{s} $,比较新解与最优解的目标函数值。若C($ {g}_{1}^{s} $)<C($ {g}^{s{'}} $),则$ {g}^{s{'}}={g}_{1}^{s} $。返回步骤(2)。

    • 替换差解的操作能够在一定程度上提高种群的质量,使种群向更好的方向发展。若水波个体进行传播操作之后,新个体$ {g}^{s} $的适应度值低于原个体$ g $,并且波高$ {h}_{g} $没有减到0,那么如果新个体$ {g}^{s} $的适应度值优于当前种群中最差的解,则替换最差的解,否则丢弃个体$ {g}^{s} $

      离散水波优化算法的伪代码如下:

      Input: the size of the population NP, $ {h}_{\max} $,initialize population G=[$ {g}_{1},{g}_{2}, \cdots ,{g}_{NP} $] (generated by NEH[17]and random method),the optimal individual $ {g}^{*} $,the worst individual $ {g}^{l} $

      Output:$ {g}^{*} $

       While the terminate condition is not met do

         if $ i\leqslant NP $ then

          Update the wavelength $ {\lambda }_{{g}_{i}} $

          Propagate $ {g}_{i} $ to a new $ {g}_{i}^{{'}} $

          if $ {C}_{\max}\left({g}_{i}^{{'}}\right)<{C}_{\max}\left({g}_{i}\right) $ then

          if $ {C}_{\max}\left({g}_{i}^{{'}}\right)<{C}_{\max}\left({g}^{*}\right) $ then

           Break $ {g}_{i}^{{'}} $ and replace it with the result

           $ {g}^{*} $ = $ {g}_{i}^{{'}} $

          end if

           $ {g}_{i} $ = $ {g}_{i}^{{'}} $

          update $ {h}_{{g}_{i}} $ to $ {h}_{\max} $

         else

          $ {h}_{{g}_{i}}={h}_{{g}_{i}}-1$

            if $ {h}_{{g}_{i}}=0 $ then

            Refract $ {g}_{i}^{{'}} $ and replace it with the res        ult

              Update $ {h}_{{g}_{i}} $ to $ {h}_{\max} $

            else

          Replace inferior solution

            end if

        end if

        $ i $ =$ i+1 $

       end if

      end while

    • 目前针对考虑了批处理机容量和不相关离散机加工能力的混合流水车间批量流调度问题的研究成果较少,且没有标准算例可供参考比较,因此根据参考文献中的设置,设计了如下数据集:各工件批量随机分布在[10,30]中;一般工序阶段的机器数在[1,3]中随机产生,机器最大加工能力和加工时间分别分布在[5,15]和[4,16]中,可分离准备时间分布在[1,4]中;批处理工序随机分布在[2,m]中;批处理阶段,批处理机的加工容量和加工时间分别在[10,30]和[10,99]中随机产生,批处理机的准备时间分布在[6,15]中。此数据集由50种工件和15道工序构成,由于考虑了工件分批且工序存在不相关并行机,对于带批处理的混合流水车间批量流调度来说,数据集的规模较大且相对复杂。本文中的所有程序在Windows 10系统、Intel Corei7处理器、内存为8 GB的PC上使用MATLAB R2019a软件编写并运行。

    • 为了使算法能在较优的状态下运行,需要对参数进行合理设置[18]。设置种群规模为30,波长上界$ {\lambda }_{{\rm{m}}{\rm{a}}{\rm{x}}}=L/3 $,波长下界$ {\lambda _{{\rm{min}}}} = {\lambda _{{\rm{max}}}}/2$[19]。因算法的迭代次数$ M $、波高上限$ {h}_{{\rm{m}}{\rm{a}}{\rm{x}}} $、碎浪操作中循环次数上限$ P $和折射操作中折射长度$ {\rm{len}} $也会影响算法的运行结果,为了保证算法具有最佳的运行状态,采用正交实验法对上述4个参数进行设置。在兼顾算法性能和运行时间的情况下,本文设置为$ M=150 $$ {h}_{{\rm{m}}{\rm{a}}{\rm{x}}}=3 $$ P=15 $$ {\rm{l}}{\rm{e}}{\rm{n}}=L/5 $图1为参数水平影响趋势图,其中AVG为算法运行10次时makespan的平均值。

      图  1  参数水平影响趋势图

      Figure 1.  Trend graphs of influence of parameters

    • 为了评估不同的解码方案的性能,对2. 1节的4种解码方案进行对比。每种方案都在不同规模的算例上测试10次,结果如表1所示,较优值用粗体显示。

      nmAVG
      IIIIIIIV
      641 224.01 220.01 231.01 222.0
      71 520.41 520.01 522.01 522.0
      102 200.02 200.02 200.02 200.0
      153 025.02967.03 140.03 058.0
      1041 605.01 605.01 605.01 605.0
      72 040.82 037.02 039.22 039.4
      102 844.52 832.02 884.32 832.0
      153 688.43 652.83 714.73 712.5
      1542 280.82 278.02 277.82 277.5
      72 719.02 719.02 790.32 786.8
      103 488.83 447.03 486.03 449.0
      154 400.94 344.04 462.94 397.2
      2042 968.02 968.02 968.02 968.0
      73 378.63 378.63 378.63 378.6
      104 436.64 326.04 435.04 381.0
      155 297.25 170.05 355.45 278.4
      3545 254.05 254.05 254.05 254.0
      76 010.66 009.06 011.46 009.8
      106 874.06 847.06 937.86 861.0
      157 753.87 686.47 842.87 786.4
      5047 681.07 681.07 681.07 681.0
      78 559.98 559.68 560.08 559.6
      109 307.49 256.89 326.89 301.6
      1510 175.410 094.410 247.410 226.8

      表 1  不同解码方案对比结果

      Table 1.  Comparison results of different decoding schemes

      通过方案I与方案II、方案III与方案IV的两两对比,可以观察出针对大部分算例,方案II的AVG比方案I的值小。同样地,方案IV的AVG也优于方案III。因此,对于工件排序问题,工件优先策略比子批优先策略更适用于本文研究的问题,这是因为工件优先策略能够减小因先到达工件不足一个子批时等待的时间。另外,通过方案I与方案III、方案II与方案IV的两两对比,可以观察出针对大部分算例,方案I与方案II的结果分别优于其他两种方案。因此,对于机器选择问题,机器最短完工策略优于机器加工均衡策略,由于机器最短完工策略综合考虑机器空闲时间和子批在机器上的加工时间,相比于机器加工均衡策略只考虑机器加工总时间均衡,更能选择到合适的机器使子批在各道工序上尽快完工。综上所述,在基于批处理机容量和离散机加工能力的可变分批下,方案II的性能优于其他3种方案。因此,本文采用方案II较为适合。

    • 为测试动态连续加工策略的有效性,将其与不带动态连续加工策略的调度方案进行了比较。表2示出了两种策略下针对不同规模算例运行10次的AVG对比结果,粗体为较优值。

      nmAVG
      With dynamic continuous processingWithout dynamic continuous processing
      641 122.01 220.0
      71 376.51 520.0
      102 021.02 200.0
      152 742.82 967.0
      1041 531.01 605.0
      71 904.02 037.0
      102 658.02 832.0
      153 337.83 652.8
      1542 192.02 278.0
      72 642.02 719.0
      103 293.03 447.0
      153 983.64 344.0
      2042 888.02 968.0
      73 308.03 378.6
      104 202.04 326.0
      154 853.05 170.0
      3545 223.05 254.0
      75 891.06 009.0
      106 715.66 847.0
      157 377.67 686.4
      5047 622.07 681.0
      78 478.28 559.6
      109 145.29 256.8
      159 787.010 094.4

      表 2  两种策略下的实验结果对比

      Table 2.  Comparison of experimental results under two strategies

      表2中可以看出,针对不同规模的算例,带动态连续加工策略的方案均能取得更优的目标值。以6$ \times $4规模为例,带动态连续加工策略获得的加工序列为$ {\pi }_{1}=[{1,5},{2,3},{4,6}] $,AVG为1 122;不带动态连续加工策略获得的加工序列为$ {\pi }_{2}=[{5,6},{1,4},{3,2}] $,AVG为1 220。用两种策略分别对$ {\pi }_{1} $进行调度,对应的甘特图如图2所示,子批用白色方框表示,机器准备时间用黑色方框表示。在一般工序中,方框上的数字表示子批所属工件,方框中的数字表示子批批量;在批处理工序中,由于子批包含不同种类的工件,因此方框中的数字表示为工件-批量。白色方框下的数字表示子批的开始加工时间。

      图  2  加工序列为$ {\pi }_{1} $时两种策略下的甘特图

      Figure 2.  Gantt charts under two strategies when the processing sequence is $ {\pi }_{1} $

      图2可以看出,采用动态连续加工策略进行调度得到的目标值更优。因为采用带动态连续加工策略时, 在保证子批加工连续的情况下,子批中先到达的工件可以提前加工,减少了后续机器的等待时间,提高了生产效率。以图2(a)(b)为例,对于工序3上工件1第2个子批的加工,由于批处理子批1中包含11个工件1,因此当批处理子批1完成批处理到达工序3时,批处理子批1中工件1的其中9个工件作为其在工序3上第1个子批,另外2个工件1将放入第2个子批。采用带动态连续加工策略时,在工序3上工件1的第2个子批连续加工的情况下,先到达的这2个工件可提前加工,因此此子批比不带动态连续加工策略时的开始加工时间早了16个单位时间,由此可以验证动态连续加工策略的有效性。

    • 为了验证DWWO算法的有效性,选取不同规模的算例,并与果蝇优化算法(FOA)[20]、变邻域改进遗传算法(IGA_VNS)[16]、基本水波优化算法(WWO)[11]、候鸟优化算法(MMBO)[21]进行了对比。所有算法都具有相同的编程语言和实验环境且终止条件都为迭代150次。离散水波优化算法的参数设置如3.1节所述,其他算法的参数根据其文献确定。所有算法都运行10次,实验结果见表3。表中各项性能指标的最优值加粗显示。算法性能由相对百分比偏差平均值(MRPD)、相对百分比偏差标准差 (SDRPD)、相对百分比偏差最优值(BRPD)进行评估。计算公式如下:

      nmMRPD$ \times {10}^{2} $SDRPD$ \times {10}^{2} $BRPD$ \times {10}^{2} $
      DWWOFOAMMBOWWOIGA_VDWWOFOAMMBOWWOIGA_VDWWOFOAMMBOWWOIGA_V
      64000000000000000
      70.4000000.40000000000
      10000000000000000
      150.4000000.32000000000
      104000000000000000
      700.173.711.010.3200.080.600.640.32002.570.210
      10000.4100000.810000000
      150.260.321.470.580.340.320.230.420.290.33000.660.000
      15400.240.320.320.2500.12000.22000.320.320
      7003.440.640.07000.420.450.14002.990.000
      10000.7200000.590000000
      150.043.066.224.201.830.040.460.601.070.9402.345.152.110.60
      2040.030.150.820.610.070.030.240.260.36000.070.070.070.07
      701.372.581.540.7900.460.650.410.400.391.870.910.21
      10001.930.190000.110.250001.8600
      150.413.254.595.243.310.570.920.510.131.2302.054.015.031.63
      354000000000000000
      70.10.521.11.420.810.080.1900.270.6400.251.11.020.32
      100.440.591.491.190.580.220.070.130.180.1200.551.230.970.45
      150.272.134.254.072.120.250.480.470.670.8601.373.872.890.86
      5040000.120.050000.10.0600000
      70.010.171.090.692.080.020.120.150.261.700.040.80.260.02
      100.080.460.931.320.850.060.220.10.290.4300.140.890.890.26
      150.342.43.824.442.830.250.6600.320.601.383.823.941.74

      表 3  DWWO,FOA,MMBO,WWO,IGA_V算法对比结果

      Table 3.  Comparison results of DWWO, FOA, MMBO, WWO and IGA_V

      其中:$ {c}_{k} $表示算法第$ k $次运算的结果($ k={1,2}, \cdots ,s $);$ {c}^{*} $为所有算法得到的最优值。

      表3中可以看出,对于较小规模的算例,5种算法的结果相差不大,说明对于小规模算例,这5种算法都能取得最优值且性能较稳定;但随着规模的增加,DWWO算法的优势逐渐体现出来,针对工件数为15、20、35和50,工序数为10和15的8个较大规模的算例,DWWO算法在其中8个算例都获得了最小的MRPD和BRPD值,且在其中5个算例上获得了最小的SDRPD值,这说明了DWWO算法在求解较大规模问题时,寻优性能和稳定性相对优于其他对比算法。对于所有规模的问题,WWO算法只在其中10个较小规模的算例中取得了最小的BRPD值,而DWWO算法在24个算例中都取得了最小的BRPD值,说明DWWO算法的搜索质量相比于WWO算法有了极大的改善。

      图3示出了5种算法针对4种不同规模实例的收敛曲线。在求解不同规模的问题时,DWWO算法在第1代都具有较好的解,主要是由于DWWO算法采用了NEH方法对种群进行初始化,从而提高了初始解的质量;DWWO算法的收敛曲线在迭代前期会发生较大幅度的下降,之后会表现出逐步下降的趋势。主要是因为算法在寻优过程中采用块最优插入及多邻域搜索提高了操作算子的性能,增强了算法的局部搜索能力,使算法能够快速跳出局部最优;在每代中不断替换当前代的最差解,提升了DWWO算法解的整体质量从而加快了收敛速度,提高了全局搜索能力。但是在求解$ 50\times 15 $的算例时,DWWO算法的收敛速度却较慢,从图3(d)也可以看出,DWWO算法的收敛曲线在100代左右下降趋势才有所减缓。

      图  3  各算法求解不同规模问题的迭代曲线

      Figure 3.  Iterative curves of each algorithm for solving problems of different scales

      相对于其他算法,DWWO算法具有更好的解决带批处理的混合流水车间批量流调度问题的能力,其稳定性和收敛能力均较优,且由于DWWO算法对操作算子进行了改进并提出了一种替换差解操作,因此具有较优的局部和全局搜索能力。

    • 本文在考虑机器可分离准备时间的情况下,以最大完工时间最小化为优化目标,研究了带批处理的混合流水车间批量流调度问题:

      (1)结合实际生产中批处理机与离散机混合加工的特点,首次提出了一种可变分批方法将两种机器的加工方式相结合对工件进行分批。

      (2)针对可变分批下,工件在不同工序批量不同这一特点,提出了一种动态连续加工策略,能够减小工件的等待时间,提高生产效率。

      (3)提出了一种离散水波优化算法,采用基于工件在第一道工序上加工顺序的编码方案,并设计了4种解码方案确定后续工序工件的加工顺序及机器的选择;采用启发式算法提高种群初始解质量;利用块最优插入、交叉操作、多邻域搜索分别对基本操作进行了改进,并加入替换差解操作以协调算法的局部和全局搜索的能力,提高了算法的收敛速度。

      (4)采用实验设计方法生成随机算例,并对算法参数进行标定,测试了本文算法的性能。实验结果验证了DWWO算法求解带批处理的混合流水车间批量流调度问题的可行性和有效性。

(3)  表(3) 参考文献 (21)

目录

    /

    返回文章