高级检索

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

基于离散正弦优化算法的多目标混合零空闲置换流水车间调度

    作者简介: 赵 芮(1994-),女,重庆永川人,硕士,研究方向为生产调度。E-mail:Y30200968@mail.ecust.edu.cn;
    通讯作者: 顾幸生, xsgu@ecust.edu.cn
  • 中图分类号: TB497

Mixed No-idle Permutation Flow Shop Scheduling Problem Based on Multi-objective Discrete Sine Optimization Algorithm

    Corresponding author: GU Xingsheng, xsgu@ecust.edu.cn
  • CLC number: TB497

  • 摘要: 针对以最小化最大完工时间(makespan)和最小化最大拖期(maximum tardiness)为目标的多目标混合零空闲置换流水车间调度问题(Mixed No-idle Permutation Flow Shop Scheduling Problem, MNPFSP),提出了一种多目标离散正弦优化算法(Multi-objective Discrete Sine Optimization Algorithm, MDSOA)。首先,建立外部档案集(AS)存储Pareto解,并在每次迭代后对AS进行更新;其次,在正弦优化算法(Sine Optimization Algorithm,SOA)的基础上,引入迭代贪婪(IG)算法的破坏重构机制,重新定义了一种适用于离散调度问题的位置更新策略;最后,引入快速非支配排序和拥挤距离对种群进行筛选,在保留精英解的同时保证了解的多样性和分布性。选取Taillard Benchmark中11个不同规模的算例进行仿真实验,并将仿真结果与NSGA-II和NSGA-III算法进行比较,验证了MDSOA求解MNPFSP的有效性。
  • 图 1  基于FNDS和拥挤距离的选择策略

    Figure 1.  Selection strategy based on fast non-dominated sorting and crowding distance

    图 2  MDSOA算法流程图

    Figure 2.  Flowchart of the MDSOA

    图 3  MDSOA、NSGA-II和NSGA-III获得的Pareto前沿

    Figure 3.  Pareto front obtained by MDSOA, NSGA-II and NSGA-III algorithms

    表 1  正交设计因子水平表

    Table 1.  Factors and levels for orthogonal design

    FactorLevel 1Level 2Level 3
    ${\rm{MaxGen}}$100150300
    ${P_{{\rm{size}}}}$203050
    $\;\beta$0.10.30.5
    $K$304050
    下载: 导出CSV

    表 2  算例Ta051的正交试验结果

    Table 2.  Orthogonal test results for the instance of Ta051

    TestFactor levelsRV/%
    ${\rm{MaxGen}}$${P_{{\rm{size}}}}$$\;\beta$$K$
    1100(1)20(1)0.1(1)30(1)0.339
    2100(1)30(2)0.3(2)40(2)0.508
    3100(1)50(3)0.5(3)50(3)0.485
    4150(2)20(1)0.3(2)50(3)0.271
    5150(2)30(2)0.5(3)30(1)0.485
    6150(2)50(3)0.1(1)40(2)0.610
    7300(3)20(1)0.5(3)40(2)0.746
    8300(3)30(2)0.1(1)50(3)0.576
    9300(3)50(3)0.3(2)30(1)0.898
    k10.4350.4520.5080.565
    k20.4460.5140.5590.621
    k30.7400.6550.5540.435
    Range0.3050.2030.0510.186
    Level1243
    下载: 导出CSV

    表 3  NSGA-II和NSGA-III的参数设置

    Table 3.  Parameter settings of NSGA-II and NSGA-III algorithms

    Algorithm${\rm{MaxGen}}$${P_{{\rm{size}}}}$${P_c}$${P_m}$
    NSGA-II300500.70.4
    NSGA-III300500.50.5
    下载: 导出CSV

    表 4  ${N_{{\rm{NDS}}}}$的计算结果

    Table 4.  Computational result of${N_{{\rm{NDS}}}}$

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×515.105.4913.604.2240.000.00
    Ta011520×1012.003.699.602.8438.602.37
    Ta0211120×209.603.448.402.1515.506.05
    Ta031350×531.902.4730.204.8139.301.19
    Ta041850×1011.502.8711.503.1137.806.60
    Ta0511550×2010.703.2610.301.7913.506.68
    Ta0614100×521.006.1331.105.1940.000.00
    Ta0717100×1014.104.7217.807.3640.000.00
    Ta08110100×2011.102.6611.503.8015.406.65
    Ta0913200×1018.804.1213.106.8839.800.40
    Ta1016200×2013.903.5310.102.3417.109.47
    Average15.433.8515.204.0430.643.58
    下载: 导出CSV

    表 5  SM的计算结果

    Table 5.  Computational results of SM

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×525.1911.3318.7212.498.494.82
    Ta011520×1044.4828.6772.5893.8211.792.96
    Ta0211120×20108.61135.99133.4289.0533.5827.49
    Ta031350×514.956.3823.3911.3218.387.04
    Ta041850×1040.7427.1969.3451.3918.9710.81
    Ta0511550×20195.52186.81108.1978.2132.3324.06
    Ta0614100×513.629.3411.247.8714.764.47
    Ta0717100×1099.05123.54126.3274.9341.1736.82
    Ta08110100×2054.8739.26114.82117.7730.5620.46
    Ta0913200×1034.8917.1970.5772.9340.3646.85
    Ta1016200×2050.6850.3587.1497.1258.7236.16
    Average62.0557.8275.9864.2628.1020.18
    下载: 导出CSV

    表 6  $D{I_{\rm{R}}}$的计算结果

    Table 6.  Computational results of $D{I_{\rm{R}}}$

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×50.230.060.210.070.050.05
    Ta011520×100.300.090.430.090.060.03
    Ta0211120×200.430.120.490.150.040.02
    Ta031350×50.130.030.140.030.010.01
    Ta041850×100.900.081.170.160.100.10
    Ta0511550×200.980.161.350.170.080.06
    Ta0614100×50.270.120.440.230.010.01
    Ta0717100×101.890.652.530.590.040.07
    Ta08110100×201.540.242.020.270.080.05
    Ta0913200×102.200.442.990.590.020.03
    Ta1016200×203.530.454.470.470.230.12
    Average1.130.221.480.260.070.05
    下载: 导出CSV

    表 7  IGD的计算结果

    Table 7.  Computational results of IGD

    ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
    AvgSDAvgSDAvgSD
    Ta001220×50.4212.840.4112.660.1813.39
    Ta011520×100.6115.240.9123.030.1810.05
    Ta0211120×201.2626.821.4837.630.438.17
    Ta031350×50.4912.290.7412.990.3127.76
    Ta041850×102.2624.622.8525.800.5716.28
    Ta0511550×204.3884.315.9493.221.4648.85
    Ta0614100×51.3578.951.92106.120.0710.90
    Ta0717100×103.0157.944.4652.410.6251.69
    Ta08110100×207.65110.929.74107.001.5739.99
    Ta0913200×105.3872.217.07144.190.3043.67
    Ta1016200×2012.22123.8315.38156.131.1047.91
    Average3.5556.364.6370.110.6228.97
    下载: 导出CSV
  • [1] 刘翱, 冯骁毅, 邓旭东, 等. 求解零空闲置换流水车间调度问题的离散烟花算法[J]. 系统工程理论与实践, 2018, 38(11): 2874-2884.
    [2] PAN Q K, WANG L. No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(7/8): 796-807.
    [3] PAN Q K, RUIZ R. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem[J]. Omega, 2014, 44(2): 41-50.
    [4] 张晓霞, 吕云虹. 一种求解混合零空闲置换流水车间调度禁忌分布估计算法[J]. 计算机应用与软件, 2017, 34(1): 270-274, 292.
    [5] CHENG C Y, YING K C, CHEN H H, et al. Minimising makespan in distributed mixed no-idle flowshops[J]. International Journal of Production Research, 2019, 57(1): 48-60. doi: 10.1080/00207543.2018.1457812
    [6] ROSSI F L, NAGANO M S. Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion[J]. Expert Systems with Applications, 2019, 125(1): 40-54.
    [7] SANTOSA B, SISWANTO N. Discrete particle swarm optimization to solve multi-objective limited-wait hybrid flow shop scheduling problem[J]. IOP Conference Series: Materials Science and Engineering, 2018, 337(1): 012006.
    [8] PAN Q K, WANG L, QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers & Operations Research, 2009, 36(8): 2498-2511.
    [9] LEI D M, ZHENG Y L. Hybrid flow shop scheduling with assembly operations and key objectives: A novel neighborhood search[J]. Applied Soft Computing, 2017, 61: 122-128. doi: 10.1016/j.asoc.2017.07.058
    [10] MURILO Z, APARECIDO C A, JOSU C. A decomposition-based kernel of Mallows models algorithm for bi- and tri-objective permutationflowshop scheduling problem[J]. Applied Soft Computing Journal, 2018, 71: 526-537. doi: 10.1016/j.asoc.2018.07.011
    [11] MESHKAT M, PARHIZGAR M. Sine optimization algorithm (SOA): A novel optimization algorithm by change update position strategy of search agent in sine cosine algorithm[C]//2017 3rd Iranian Conference on Intelligent Systems and Signal Processing (ICSPIS)[C]. Shahrood, Iran: IEEE, 2017: 11-16.
    [12] MIRJALILI S. SCA: A Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133. doi: 10.1016/j.knosys.2015.12.022
    [13] FERNANDEZ-VIAGAS V, FRAMINAN J M. A beam-search-based constructive heuristic for the PFSP to minimise total flowtime[J]. Computers and Operations Research, 2017, 81: 167-177. doi: 10.1016/j.cor.2016.12.020
    [14] JOLAI F, ASEFI H, RABIEE M, et al. Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem[J]. Scientia Iranica, 2013, 20(3): 861-872.
    [15] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017
    [16] MIRJALILI S, LEWIS A. Novel performance metrics for robust multi-objective optimization algorithms[J]. Swarm and Evolutionary Computation, 2015, 21: 1-23. doi: 10.1016/j.swevo.2014.10.005
    [17] DEB K, AGARWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000: 849-858.
    [18] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285. doi: 10.1016/0377-2217(93)90182-M
    [19] MINELLA G, RUIZ R, CIAVOTTA M. Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems[J]. Computers & Operations Research, 2011, 38(11): 1521-1533.
    [20] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach: Part I. Solving problems with box constraints[J]. IEEE transactions on evolutionary computation, 2014, 18(4): 577-601. doi: 10.1109/TEVC.2013.2281535
    [21] RIQUELME N, LÜCKEN C V, BARAN B. Performance metrics in multi-objective optimization[C]//Latin American Computing Conference (CLEI). Arequipa, Peru: IEEE, 2015: 286-296.
    [22] QIAN B, WANG L, HUANG D X, et al. An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2009, 33(10): 2960-2971.
  • 加载中
图(3)表(7)
计量
  • 文章访问数:  53
  • HTML全文浏览量:  56
  • PDF下载量:  2
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-01
  • 网络出版日期:  2021-03-24

基于离散正弦优化算法的多目标混合零空闲置换流水车间调度

    作者简介:赵 芮(1994-),女,重庆永川人,硕士,研究方向为生产调度。E-mail:Y30200968@mail.ecust.edu.cn
    通讯作者: 顾幸生, xsgu@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237

摘要: 针对以最小化最大完工时间(makespan)和最小化最大拖期(maximum tardiness)为目标的多目标混合零空闲置换流水车间调度问题(Mixed No-idle Permutation Flow Shop Scheduling Problem, MNPFSP),提出了一种多目标离散正弦优化算法(Multi-objective Discrete Sine Optimization Algorithm, MDSOA)。首先,建立外部档案集(AS)存储Pareto解,并在每次迭代后对AS进行更新;其次,在正弦优化算法(Sine Optimization Algorithm,SOA)的基础上,引入迭代贪婪(IG)算法的破坏重构机制,重新定义了一种适用于离散调度问题的位置更新策略;最后,引入快速非支配排序和拥挤距离对种群进行筛选,在保留精英解的同时保证了解的多样性和分布性。选取Taillard Benchmark中11个不同规模的算例进行仿真实验,并将仿真结果与NSGA-II和NSGA-III算法进行比较,验证了MDSOA求解MNPFSP的有效性。

English Abstract

  • 零空闲置换流水车间调度问题(No-idle Permutation Flow Shop Scheduling Problem, NPFSP)是广泛存在于集成电路制造、玻璃纤维加工和铸造等现代工业的组合优化问题[1]。NPFSP通常要求机器都处在零空闲状态,即每台机器要不间断地加工工件[2]。然而在实际的生产过程中,往往只有部分特定的机器因设备昂贵或技术限制等受到零空闲条件的约束。混合零空闲置换流水车间调度问题(MNPFSP)是NPFSP的扩展,其要求部分机器受零空闲条件的约束,其余机器为常规机器。2014年,Pan等[3]首先提出了混合零空闲置换流水车间调度问题,并证明其为NP难问题。然而随着规模的增大,MNPFSP的复杂性呈指数增长,精确算法不再适用,因而,通过高效的智能优化算法解决MNPFSP是学术界和工业界的重要课题。

    目前,将智能优化算法应用于MNPFSP的研究并不多。Pan等[3]提出了一种改进的迭代贪婪(Iterated Greedy, IG)算法以最小化makespan。张晓霞等[4]提出了一种改进的分布估计算法(Distribution Estimation Algorithm, EDA),将禁忌搜索(Tabu Search, TS)算法引入了EDA,通过禁忌列表控制EDA的进化方向,并以最小化makespan为优化目标,对比了在7种不同零空闲情况的MNPFSP上的求解效果。Cheng等[5]基于云理论设计了一种新的IG算法对MNPFSP进行求解。Rossi等[6]开发了一种构造性启发式算法,求解以最小化总流水时间(Total Flow Time, TFT)为目标的具有序列相关准备时间的MNPFSP。

    本文针对车间生产效率和客户满意度这两个不同的生产需求,将makespan和最大拖期(maximum tardiness)作为优化目标。两者在多目标优化问题的研究中已有相关成果,如Santosa等[7]针对最小化makespan、总拖期时间和总机器空闲时间为目标的flow shop调度问题,提出了一种离散粒子群算法(Discrete Particle Swarm Optimization, DPSO)算法。Pan等[8]为解决零等待flow shop问题,提出了一种离散差分进化(Discrete Differential Evolution, DDE)算法以实现最小化makespan和最大拖期的目标,同时设计了几种加速方法提高算法效率。Lei等[9]针对以最小化总拖期时间(Total Tardiness, TTd)、最大拖期和makespan为目标的多目标混合flow shop问题,提出了一种具有全局交换功能的邻域搜索策略(Neighborhood Search with Global Exchange, NSG),通过全局交换和邻域搜索相结合的方式提高解的质量。Murilo等[10]提出了一种多目标进化算法(Multi-Objective Evolutionary Algorithm, MOEA),在分布估计算法中引入对数据排名的Mallows概率模型,解决了以makespan、总流程时间、总拖期时间为目标的多目标PFSP。

    正弦优化算法(Sine Optimization Algorithm, SOA)[11]是通过改进正余弦算法(Sine Cosine Algorithm, SCA)[12]的一种利用正弦函数对个体进行位置更新的全局优化方法。本文在SOA的基础上设计了一种多目标离散正弦优化算法(Multi-objective Discrete Sine Optimization Algorithm, MDSOA)。引入IG算法的破坏重构机制对SOA的位置更新进行了改进,并设计适用于离散调度问题的位置更新策略。构建外部档案集(AS)储存Pareto解集,通过AS选取的当前最优解与个体之间的交叉操作保留最优解的部分信息。利用快速非支配排序(FNDS)和拥挤距离筛选更新种群,以此提高种群的分布性。

    • MNPFSP可以被描述如下:$n$个工件$J = \left\{ {1,2,...,n} \right\}$按照相同的顺序在$m$台机器$M = \left\{ {1,2,...,m} \right\}$上进行加工,所有机器上工件的加工次序相同[13]。约束条件有:(1)在任意时刻,每个机器仅加工一个工件,每个工件仅在一台机器上加工;(2)在加工过程中部分机器处于零空闲状态,其余机器为置换流水车间中的常规机器,零空闲状态的机器在加工两相邻工件时不间断,即第$j$个工件在机器$i$上的开始时间必须等于第$j - 1$个工件在机器$i$上的完工时间。

      在生产过程中,最小化最大完工时间(Cmax)可以提高生产效率和机器利用率,最小化最大拖期(Tmax)可以使工厂最大程度地避免延期交货,满足客户对产品工期的要求。因此,本文将最小化最大完工时间和最大拖期作为MNPFSP的优化目标,两者之间的关系已经被证明是互相矛盾的[14]。用$\pi = $$ \left\{ {{\pi _1},{\pi _2},...,{\pi _l},...,{\pi _n}} \right\}$表示工件加工序列,用$[l]$表示排序中处于$l$的工件,即${\pi _l}$;用${p_{i,\left[ l \right]}}$表示工件${\pi _l}$在机器$i$上的加工处理时间;用${S_{i,\left[ l \right]}}$${C_{i,\left[ l \right]}}$分别表示工件${\pi _l}$在机器$i$上加工的开始时间和完成时间;${T_{[l]}}$${d_{[l]}}$分别为工件${\pi _l}$的拖期时间和交期;${a_i}$表示受零空闲条件的约束,工件${\pi _l}$在机器$i$上延迟加工的总时间,将具有零空闲状态的机器集合记为${M'} \subset M$。加工序列$\pi $的最大完工时间和最大拖期的计算公式如下[3]

      其中:式(1)计算${\pi _{\rm{1}}}$在首台机器上的开始和完成时间;式(2)计算${\pi _{\rm{1}}}$在(除首台机器外)其他各台机器上的开始和完成时间;式(3)计算每个工件在首台机器上的开始和完成时间;式(4)表示若机器2受零空闲条件的约束,则要保证各个操作之间是零空闲的,${\pi _l}$之前的工件开始时间都需右移或延迟${a_2} = \max $$ \{ {C_{1,[l]}} - {C_{2,[l - 1]}},0\}$,若机器2为常规机器,则不需要延迟加工,${a_2} = 0$;式(5)类似,工件因机器i为零空闲机器而延迟加工的时间为$\max \{ {C_{i - 1,[l]}} -({C_{i,[l - 1]}} + {a_{i - 1}}), 0\}$${a_{i - 1}}$为上游零空闲机器导致的延迟时间,因此${a_i}$为总延迟时间。式(6)和式(7)规定了工件序列$\pi $的最大完工时间和最大拖期。则优化的目标函数表示为

    • SOA是基于SCA的一种新的群智能优化算法,对SCA的位置更新策略进行了改进,仅使用正弦函数对初始候选解进行优化。相较于SCA,SOA的参数更少,算法更简便,同时收敛速度更快,精度更高[11]

      SOA使用一组随机解作为初始种群,假设在$n$维搜索空间中有${P_{{\rm{size}}}}$个个体,第$i$个个体的位置表示为

      则第$t + 1$次迭代时个体第$k$维位置分量的更新为

      其中:$x_{{\rm{rand}}}^k(t)$为第$t$次迭代时随机个体的第$k$维位置分量;$x_{{\rm{best}}}^k(t)$为第$t$次迭代时种群中最优个体的第$k$维位置分量;${\rm{MaxGen}}$为最大迭代数;$a$为常数;${r_2}$$\left[ {0,2{\text π}} \right]$之间的随机数,${r_3}$$\left[ {0,1} \right]$间的随机数。算法通过$ {r}_{1}{\text{、}}{r}_{2}{\text{、}}{r}_{3}$来平衡优化过程中的全局探索(Exploration)和局部开发(Exploitation)。迭代开始时${r_1}$较大,${r_1} \times \sin \;{r_2}$有较大的波动幅度,可以更好地进行全局探索;随着${r_1}$的减小,个体的位置变化量减小,算法进行局部开发。${r_3}$的大小决定了个体在下一次迭代位置移动的起点,当${r_3}$的取值在$[0,0.5)$时,对随机个体的位置进行修改获得下一个位置,因此可以覆盖更广的搜索区域;当${r_3}$的取值在$[0.5,1]$时,对最优个体的位置进行修改获得下一个位置,可以完成在最优个体附近的局部开发。

    • 对工件排序采用自然数编码的方法,排序的序列由一串不重复的整数表示,并且每个整数都对应一道工序,这串序列代表一个解的编码,例如解$X = \left\{ {4,1,3,6,2,5} \right\}$表示工件加工顺序为$\pi = \left\{ {4,1,3,6,} \right.\\ $$ \left. {2,5} \right\}$。初始种群均随机产生,随机的初始种群更有可能在迭代之初遍布可行域的搜索空间,提高算法的多样性。

    • 在求解多目标调度问题时,往往无法获得一个最优解,而是在相互竞争的目标中进行取舍从而获得一组Pareto解集。在MDSOA中构建一个外部档案集(AS)存储Pareto解,避免算法中的优良个体在种群迭代更新中被遗失。在种群初始化后,根据个体子目标的适应度值进行非支配排序,得到Pareto解集作为初始AS。同时在每代新种群产生后要对AS进行筛选和更新,具体方法是将当前种群X中不受AS支配的解放入AS中,并把AS中被种群X支配的解剔除出去,使AS中始终存放着算法所求的Pareto解集。AS创建及更新的伪代码如下:

      Procedure Create_AS(X)

      (1) Q = X

      (2) AS = $\emptyset$

      (3) while $Q \ne \emptyset$

      (4)  $x \in Q,\;Q = Q - x$

      (5)  x is non - dominated = true

      (6)  for each $y \in Q$

      (7)     if $x < y$ then

      (8)     $Q = Q - y$

      (9)     elseif $y < x$ then

      (10)    x is non - dominated = false; break

      (11)    endif

      (12)  endfor

      (13)  if x is non - dominated = = true then

      (14)  AS = AS $\cup$ x

      (15)  endif

      (16) endwhile

      (17) return AS

      end

      由于在求解多目标问题时可以得到大量满足约束条件的Pareto解,为了控制计算的复杂度,将外部档案集的规模限制为K。若某次更新时,AS的长度超过了K,则需要删除AS中拥挤距离更小的解,以此控制外部档案集的规模。

    • 在MDSOA中引入了IG算法的破坏重构策略来获得更优的解。在破坏(Destruction)阶段:随机选择$d$个工件从序列$\pi $中移除,移除的工件作为序列${\pi ^{\rm{R}}}$,剩余工件作为序列${\pi ^{\rm{D}}}$${\pi ^{\rm{D}}} = \pi - {\pi ^{\rm{R}}}$。在重构(Construction)阶段:将${\pi ^{\rm{R}}}$的第1个工件插入${\pi ^{\rm{D}}}$中,产生$n - d{\rm{ + 1}}$个部分解,选择最优解进入下一次迭代,再将${\pi ^{\rm{R}}}$的第2个工件插入${\pi ^{\rm{D}}}$,循环至${\pi ^{\rm{D}}}$中包含了$n$个工件。

      参数$d$使用SOA算法中的正弦函数进行更新。由于$d$为正整数,因此对函数取整,再取绝对值:

      其中:$n$为工件数;$\beta $为控制位置更新变化量大小的参数,由于$d \leqslant n$,所以$\beta $的取值范围应在$\left( {0,1} \right)$

      MDSOA中个体的位置更新公式如下:

      ${r_3}$<0.5时,利用随机个体进行位置更新,否则使用最优个体进行位置更新。位置更新策略的伪代码如下:

      Procedure Update_position(d)

      (1) ${r_3}$ = a random number in [0,1]

      (2) if ${r_3} < 0.5$ then

      (3) ${X_{{\rm{rand}}}}$ = select one solution from X randomly

      (4) $\pi = {X_{{\rm{rand}}}}$

      (5) else

      (6) $\pi = {X_{{\rm{best}}}}$

      (7) endif

      (8) ${\pi ^{\rm{R}}}$ = remove d job from $\pi $ randomly

      (9) ${\pi ^{\rm{D}}} = \pi - {\pi ^{\rm{R}}}$

      (10) for i = 1:d

      (11)  insert job ${\pi ^{\rm{R}}}$(i) into the optimal location which gives the minimum makespan in all possible positions of ${\pi ^{\rm{D}}}$

      (12) endfor

      (13) ${X_i} = \;\;{\pi ^{\rm{D}}}$

      (14) return ${X_i}$

      end

    • 在各类处理多目标问题的优化方法中,基于Pareto解的方法具有很大的优势,Deb等[15]提出的非支配排序遗传算法II(Non-dominated Sorting Genetic Algorithm II,NSGA-II)具有很好的求解效果。NSGA-II根据对种群的非支配排序和拥挤距离计算来选择下一代种群,可以在保留种群精英解的同时,保持解具有良好的分布性和收敛性。

      快速非支配排序(FNDS)的思想是根据支配关系将种群划分为若干个不同等级的Pareto前沿。在多目标搜索空间中,两个个体之间的支配关系需要针对每个目标进行比较。在这种情况下,当且仅当个体$x$的所有目标值都比个体$y$更好或相等,且至少有一个目标值优于$y$时,才有$x$支配$y$[16]

      Deb等在文献[17]中给出了拥挤距离的定义:在同等级的Pareto前沿上,与个体$i$相邻的两个个体在各子目标上的距离差之和,计算公式如下:

      其中:$P[i + 1].{f_k}$$P[i - 1].{f_k}$分别表示个体$i + 1$$i - 1$在第$k$个目标上的目标函数值。为了获得分布广而均匀的Pareto前沿,对于同一非支配等级的个体,应尽量选择拥挤距离大的个体。

      MDSOA算法引入FNDS和拥挤距离作为选择策略。其原理如图1所示。图中${X_t}$为第$t$次迭代位置更新后的种群,${Y_t}$为进行交叉操作后的种群,种群大小均为${P_{{\rm{size}}}}$${S_t} = \left\{ {{X_t},{Y_t}} \right\}$候选解集的大小为$2 \times {P_{{\rm{size}}}}$。首先对${S_t}$进行FNDS,得到不同等级的Pareto前沿${F_1},{F_2},{F_3}...$,同时计算每个解的拥挤距离并按照降序排列。按照等级由低到高的顺序将${F_i}$依次放入新种群${X_{t + 1}}$中,当某个解集${F_i}$的加入使得${X_{t + 1}}$的种群大小超过${P_{{\rm{size}}}}$时,则需要根据${F_i}$中解的拥挤距离对个体进行筛选,取前${P_{{\rm{size}}}} - \left| {{X_{t + 1}}} \right|$个个体放入${X_{t + 1}}$,剩余个体淘汰,最终形成新的种群${X_{t + 1}}$

      图  1  基于FNDS和拥挤距离的选择策略

      Figure 1.  Selection strategy based on fast non-dominated sorting and crowding distance

    • MDSOA的流程如图2所示,终止条件为满足最大迭代次数。算法首先初始化参数并随机生成初始种群,再对初始解集进行非支配排序,构建初始AS。当${r_3}$<0.5时,选择最优个体根据位置更新策略对种群进行更新,否则选择随机个体对种群进行位置更新,得到种群X。交叉策略采用的是将种群的最优解${X_{{\rm{best}}}}$作为参考,与种群中的其他解进行两点交叉,使产生的新解包含最优解的部分信息,并用新解代替当前解。将交叉操作得到的种群Y与位置更新策略得到的种群X进行非支配排序和拥挤距离计算,通过选择策略保留优解。同时更新AS和种群最优解,完成一次迭代。最终返回最优的Pareto解集。

      图  2  MDSOA算法流程图

      Figure 2.  Flowchart of the MDSOA

    • 算法基于Matlab 2017a实现,在处理器主频为2.40GHz,内存为64.0GB的PC机上运行。为了检验MDSOA求解MNPFSP的有效性,本文选取Taillard Benchmark[18]中不同问题规模的第一个算例作为测试对象,其中,规模用工件数(n)×机器数(m)表示,并将仿真结果与NSGA-II算法和NGSA-III算法进行比较。

      由MNPFSP的实际生产过程可知,一般第一台机器处于零空闲状态,最后一台机器不处于零空闲状态,并且处于零空闲状态的机器占比较小,因此,本文设置两台机器处于零空闲状态:除了第一台机器外,再随机选择一台(除最后一台机器外)机器,并用Mset表示。按算例序号的升序随机生成的Mset数据依次为$\left[ {2\;\;5\;\;11\;\;3\;\;8\;\;15\;\;4\;\;7\;\;10\;\;3\;\;6} \right]$。对于最大拖期${T_{\max }}$这个性能指标,需要规定每个工件的交期,交期的构造公式如下[19]

      其中:${P_j} = \sum\limits_{i = 1}^m {{p_{ij}}} $${\rm{random}}$是均匀分布在$\left[ {0,1} \right]$之间的随机数。

    • MDSOA有4个主要参数:最大迭代次数${\rm{MaxGen}}$、种群规模${P_{{\rm{size}}}}$、控制参数$\beta $和外部档案集长度K。为确定各个参数的取值,为每个参数设置3个不同水平,选择${L_9}({3^4})$正交试验表对参数的各种组合进行讨论,如表1所示。对于每种参数组合,算法均独立运行20次,并将仿真结果合并为该参数组合下的Pareto解集,再合并每种参数组合下的解集,最终得到该算例下的Pareto解集。将每组参数组合下Pareto解的数量占算例Pareto解集的百分比作为响应变量(Response Variable, RV),RV值越大,参数越好。正交表及算例Ta051的正交结果见表2(括号中的数值为选择的等级(Level))。

      FactorLevel 1Level 2Level 3
      ${\rm{MaxGen}}$100150300
      ${P_{{\rm{size}}}}$203050
      $\;\beta$0.10.30.5
      $K$304050

      表 1  正交设计因子水平表

      Table 1.  Factors and levels for orthogonal design

      TestFactor levelsRV/%
      ${\rm{MaxGen}}$${P_{{\rm{size}}}}$$\;\beta$$K$
      1100(1)20(1)0.1(1)30(1)0.339
      2100(1)30(2)0.3(2)40(2)0.508
      3100(1)50(3)0.5(3)50(3)0.485
      4150(2)20(1)0.3(2)50(3)0.271
      5150(2)30(2)0.5(3)30(1)0.485
      6150(2)50(3)0.1(1)40(2)0.610
      7300(3)20(1)0.5(3)40(2)0.746
      8300(3)30(2)0.1(1)50(3)0.576
      9300(3)50(3)0.3(2)30(1)0.898
      k10.4350.4520.5080.565
      k20.4460.5140.5590.621
      k30.7400.6550.5540.435
      Range0.3050.2030.0510.186
      Level1243

      表 2  算例Ta051的正交试验结果

      Table 2.  Orthogonal test results for the instance of Ta051

      表2可以看出,对算法影响较大的是${\rm{MaxGen}}$${P_{{\rm{size}}}}$。较多的迭代次数有利于种群的充分进化,合适的种群规模有利于平衡算法每次迭代的搜索广度。其次是外部档案集长度,$K$太小可能造成收敛缓慢,$K$太大可能造成早熟收敛,故$K$的取值要适中。$\;\beta $对MDSOA性能的影响较小。基于以上分析,MDSOA的参数如下:${\rm{MaxGen}} = {\rm{30}}0,{P_{{\rm{size}}}} = 50, $$ \;\beta = 0.5,K = 40$

      为验证MDSOA求解多目标MNPFSP的有效性,将其与两种典型的多目标算法NSGA-II[15]和NSGA-III[20]进行比较,其中NSGA-II和NSGA-III的交叉操作和变异操作均采用的是最常见的两点交叉和单点变异。对NSGA-II和NSGA-III的参数设置见表3

      Algorithm${\rm{MaxGen}}$${P_{{\rm{size}}}}$${P_c}$${P_m}$
      NSGA-II300500.70.4
      NSGA-III300500.50.5

      表 3  NSGA-II和NSGA-III的参数设置

      Table 3.  Parameter settings of NSGA-II and NSGA-III algorithms

    • 本文采用均匀性指标SM[21]、反世代距离IGD[21]以及非支配解的数量${N_{{\rm{NDS}}}}$[22]和距离指标$D{I_{\rm{R}}}$[22]来评价3种算法得到的Pareto解集的质量,并分别统计其平均值(Avg)和标准偏差(SD)。

      (1)SM用于度量算法求得的近似Pareto解集中每个解到其他解的最小距离的标准差,计算公式如下:

      其中,$\left| {PF} \right|$为Pareto解集中解的个数。理想情况下,Pareto解应均匀分布在解空间中,SM值越小,解集在解空间中分布越均匀。

      (2)IGD是世代距离(GD)的一种变体,它不仅可以度量算法求得的近似Pareto解集与最优Pareto解集的距离,还可以衡量解集的多样性、分布性。IGD的计算公式如下:

      其中:$P{F^*}$为最优Pareto前沿;$\left| {P{F^*}} \right|$$P{F^*}$中解的数量;${\rm{dis}}(x,PF)$$P{F^*}$中的解$x$PF之间的最小欧式距离,IGD的值越小越好。

      (3)${N_{{\rm{NDS}}}}$是指算法获得的解集中没有被参考解集支配的解的数量:

      其中:${S_h}$表示通过算法$h(h = 1,2,3)$获得的Pareto解集;${S^*} = {S_1} \cup {S_2} \cup {S_3}$,是$P{F^{\rm{*}}}$的参考解集。${N_{{\rm{NDS}}}}$的值越大,表明算法求得的近似Pareto解越多,算法性能越好。

      (4)$D{I_{\rm{R}}}$用于度量${S_h}$相对于参考解集${S^*}$的距离:

      其中${d_{xy}}$$w$维归一化目标空间中解x与参考解y之间的距离,表达式为${d_{xy}} = $$ \sqrt {{{(f_{_1}^*(y) - f_{_1}^*(x))}^2} + ... + {{(f_w^*(y) - f_w^*(x))}^2}}$。由此可知,$D{I_{\rm{R}}}$的值越小,求得的近似Pareto解集就越接近真实$P{F^*}$。由于问题的最优前沿未知,所以在用到$P{F^*}$时,用参考解集${S^*}$代替$P{F^*}$

      表4列出了3种算法支配解个数的比较结果,最优结果以黑体表示。可以看出,本文提出的MDSOA算法在11个算例中都获得了非支配解个数的最优值。虽然在算例Ta021、Ta041、Ta051、Ta081和Ta101上没有获得更小的标准偏差,但从平均结果来看,MDSOA的SD值要优于其他两个算法。因此可以说明,相较于另两种多目标优化算法,MDSOA能够找到更多的非支配解。

      ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
      AvgSDAvgSDAvgSD
      Ta001220×515.105.4913.604.2240.000.00
      Ta011520×1012.003.699.602.8438.602.37
      Ta0211120×209.603.448.402.1515.506.05
      Ta031350×531.902.4730.204.8139.301.19
      Ta041850×1011.502.8711.503.1137.806.60
      Ta0511550×2010.703.2610.301.7913.506.68
      Ta0614100×521.006.1331.105.1940.000.00
      Ta0717100×1014.104.7217.807.3640.000.00
      Ta08110100×2011.102.6611.503.8015.406.65
      Ta0913200×1018.804.1213.106.8839.800.40
      Ta1016200×2013.903.5310.102.3417.109.47
      Average15.433.8515.204.0430.643.58

      表 4  ${N_{{\rm{NDS}}}}$的计算结果

      Table 4.  Computational result of${N_{{\rm{NDS}}}}$

      表5列出了3种算法均匀性指标的比较结果。可以看出,算例Ta031、Ta061、Ta091和Ta101中较优的SM值是由NSGA-II和NGSA-III获得的,其余算例均是MDSOA获得了更优的SM值。因此,对于大部分算例,MDSOA求得的解在解空间中分布得更均匀。

      ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
      AvgSDAvgSDAvgSD
      Ta001220×525.1911.3318.7212.498.494.82
      Ta011520×1044.4828.6772.5893.8211.792.96
      Ta0211120×20108.61135.99133.4289.0533.5827.49
      Ta031350×514.956.3823.3911.3218.387.04
      Ta041850×1040.7427.1969.3451.3918.9710.81
      Ta0511550×20195.52186.81108.1978.2132.3324.06
      Ta0614100×513.629.3411.247.8714.764.47
      Ta0717100×1099.05123.54126.3274.9341.1736.82
      Ta08110100×2054.8739.26114.82117.7730.5620.46
      Ta0913200×1034.8917.1970.5772.9340.3646.85
      Ta1016200×2050.6850.3587.1497.1258.7236.16
      Average62.0557.8275.9864.2628.1020.18

      表 5  SM的计算结果

      Table 5.  Computational results of SM

      表6列出了3种算法距离指标的对比结果。可以看出,除了在算例Ta041中MDSOA求解的SD值稍逊于NSGA-II算法外,剩余算例中MDSOA都获得了更优的结果,因此MDSOA可以获得更接近真实Pareto前沿的解集。

      ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
      AvgSDAvgSDAvgSD
      Ta001220×50.230.060.210.070.050.05
      Ta011520×100.300.090.430.090.060.03
      Ta0211120×200.430.120.490.150.040.02
      Ta031350×50.130.030.140.030.010.01
      Ta041850×100.900.081.170.160.100.10
      Ta0511550×200.980.161.350.170.080.06
      Ta0614100×50.270.120.440.230.010.01
      Ta0717100×101.890.652.530.590.040.07
      Ta08110100×201.540.242.020.270.080.05
      Ta0913200×102.200.442.990.590.020.03
      Ta1016200×203.530.454.470.470.230.12
      Average1.130.221.480.260.070.05

      表 6  $D{I_{\rm{R}}}$的计算结果

      Table 6.  Computational results of $D{I_{\rm{R}}}$

      表7列出了3种算法反世代距离的比较结果。对于测试的11个算例,MDSOA求解到的 IGD值均明显小于NSGA-II和NGSA-III算法,并且随着算例的规模增大,IGD值之间的差距也逐渐增大。同时,除了算例Ta001和Ta031的SD最小值由另外两个算法获得,其余算例的SD最小值均由MDSOA算法获得。由此可见,MDSOA算法具有良好的综合性能,且随着算例的规模增大,其性能越优越。

      ProblemMsetn×mNSGA-IINSGA-IIIMDSOA
      AvgSDAvgSDAvgSD
      Ta001220×50.4212.840.4112.660.1813.39
      Ta011520×100.6115.240.9123.030.1810.05
      Ta0211120×201.2626.821.4837.630.438.17
      Ta031350×50.4912.290.7412.990.3127.76
      Ta041850×102.2624.622.8525.800.5716.28
      Ta0511550×204.3884.315.9493.221.4648.85
      Ta0614100×51.3578.951.92106.120.0710.90
      Ta0717100×103.0157.944.4652.410.6251.69
      Ta08110100×207.65110.929.74107.001.5739.99
      Ta0913200×105.3872.217.07144.190.3043.67
      Ta1016200×2012.22123.8315.38156.131.1047.91
      Average3.5556.364.6370.110.6228.97

      表 7  IGD的计算结果

      Table 7.  Computational results of IGD

      为直观地对比3种算法性能,选择部分获得最优IGD值的非支配解集绘制成Pareto前沿,如图3所示。显然在解的质量和覆盖均匀性方面,MDSOA要优于其他两个算法,并且随着问题规模逐渐增大,算法性能差距越大,MDSOA越能得到更优的Pareto解集。

      图  3  MDSOA、NSGA-II和NSGA-III获得的Pareto前沿

      Figure 3.  Pareto front obtained by MDSOA, NSGA-II and NSGA-III algorithms

      基于以上分析,可以得出,在解的数量、分布性以及收敛性上,MDSOA都显示了比NSGA-II和NGSA-III更优的算法性能,进一步表明了MDSOA算法求解MNPFSP的有效性。

    • 本文基于正弦优化算法提出了一种多目标离散正弦优化算法(MDSOA)以提高求解MNPFSP的效率和解的质量。通过在SOA位置更新策略中引入IG算法的破坏重构机制,平衡算法的全局搜索和局部搜索能力。设计交叉操作增加算法多样性,帮助算法跳出局部最优,同时,构建外部档案集,通过基于FNDS和个体拥挤距离的选择策略保留精英解。使用Taillard Benchmark算例,对比MDSOA、NSGA-II和NGSA-III在4个评价指标上的性能表现,相较于NSGA-II和NGSA-III算法,MDSOA获得的解数量更多,更接近真实Pareto前沿,分布更均匀,算法的收敛性也更好。生产调度作为一类多约束问题,求解十分困难,本文算法所针对的模型更接近实际生产过程,同时,满足生产过程中的多个生产目标的求解需要。下一步的研究将包括以下几个方面:考虑算法对其他优化目标的求解效果;在调度模型中考虑一些复杂的不确定因素,例如考虑交期窗口的情况。

(3)  表(7) 参考文献 (22)

目录

    /

    返回文章