混合组合粒子群算法解决阻塞式车间调度问题

ðÞ¼HOS T E D B Y可在www.sciencedirect.com网站上查阅计算设计与工程学报3（2016）295www.elsevier.com/locate/jcde组合粒子群算法求解阻塞式车间调度问题Mansour Eddalya，n，Bassem Jarbouia，Patrick SiarrybaMODILS实验室，斯法克斯大学，FSEGS，route de l'aéroport km 4，斯法克斯3018，突尼斯bLiSSi，université de Paris 12，61 avenue du Général de Gaulle，94010 Créteil，France接收日期：2016年1月19日;接收日期：2016年5月8日;接受日期：2016年5月11日2016年5月17日在线发布摘要研究了带阻塞约束的车间调度问题。目标是最小化完工时间准则。我们提出了一种混合组合粒子群优化算法（HCPSO）作为解决这个问题的决议技术。在初始化时，利用不同的优先级规则。实验研究和统计分析进行选择最适合这个问题。然后，群行为进行测试，以解决组合优化问题，如约束下的排序问题。最后，将一种基于概率扰动的迭代局部搜索算法引入到粒子群优化算法中，以提高解的质量。计算结果表明，我们的方法是能够改善文献中的几个最好的已知的解决方案。事实上，120个解决方案中有76个得到了改进。此外，HCPSO优于比较方法的解决方案的质量在短时间内的要求。此外，所提出的方法的性能进行评估，根据现实世界的工业问题。&2016 年 CAD/CAM 工 程 师 协 会 。 出 版 社 ： Elsevier 这 是 一 篇 基 于 CC BY-NC-ND 许 可 证 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：调度;分块流水作业;粒子群优化算法;迭代局部搜索;最大跨度1. 介绍在过去的几年里，新的生产系统的自动化和机器人制造的出现导致了阻塞调度的几个应用领域典型的领域是化学和制药行业，其中部分完成的工作不能退出机器，而下游机器正在忙碌[1]。Grabowski和Pempera在[2]中提出了一个在生产混凝土块的建筑行业中调度客户订单的真实案例。此外，霍尔和Sriskandarajah提出，[3]对阻塞调度模型的应用进行了回顾，指出阻塞环境的产生是由于工艺本身的特点或由于机器间存储容量的不足本文研究了阻塞型车间调度问题。有一组n个作业必须在一组m台机器上以相同的顺序处理当一个作业在一台机器上完成时，该机器将被阻塞，直到下一台空闲的机器可用。Hall和Sriskandarajah[3]已经证明了这个问题对于m3是强NP完全的，其中最大完工时间Cmax是性能的度量。根据Abadi等人的研究[4]，阻塞调度问题是通过允许减慢操作来放松无等待调度问题。在最后一种变体中，每个作业都要在机器上或机器之间不间断地处理这样，如果需要，必须延迟给定机器上的作业的开始，使得操作的完成与开始n通讯作者。电子邮件地址：eddaly. gmail.com（M. Eddaly）。同行评审由CAD/CAM工程师协会负责http://dx.doi.org/10.1016/j.jcde.2016.05.0012288-4300/2016 CAD/CAM工程师协会。&出版社：Elsevier这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。296M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295X.Σfg[]]在另一台机器上的操作。因此，阻塞的并行车间可以被看作是无等待并行车间问题中限制较少的情况。一些文献研究了这两个问题之间的等价性，如Hall和Sriskandarajah[3]，Abadi等人[4]和Liu和Kozan[5]。事实上，任何解决无等待车间问题的方案都可以被认为是阻塞车间问题的上界。为了解决阻塞车间调度问题，开发了各种方法，包括分支定界算法（BB）[6事实上，Caraffa等人。[14]已经使用了阻塞和无等待车间的等价概念，通过允许减慢操作来评估GA生成的解决方案的适合性。Debora[12]提出了一种分支定界算法，其中在利用问题的阻塞性质的同时开发了一个新的下限。Grabowski和Pampera[1]提出了一种多步禁忌搜索算法，该算法在同一次迭代中执行多步，旨在引导算法朝向搜索空间中更有利的区域Wang等人[15]提出了一种混合差分进化算法。作者提出了一种新的离散作业置换编码方案此外，他们还开发了一种加速方法，以评估用于局部搜索过程的插入邻域中的完工时间。粒子群优化（PSO）算法是一类支持鸟群锁定和鱼类学校教育的基本机制的算法这项技术是由Kennedy和Eberhart在1995年开发的[16]。与其他进化算法不同，标准PSO既不使用交叉也不使用变异。该算法包括许多成功的应用程序解决离散组合优化问题[17然而，也有许多情况下，粒子群算法不适用，如阻塞车间调度问题的情况下本文从技术的角度，首次提出了用粒子群算法求解阻塞流水车间调度问题。基于生物现象的粒子群算法的主要框架用于搜索空间的全局探索。因此，PSO收敛到局部最优值的速度较慢。为了克服这个缺点，许多工作提出了混合方法，通常与局部搜索技术，用于细化搜索空间和执行局部探索。该功能使算法能够加快收敛速度，减少函数求值的次数在我们的应用程序中，迭代局部搜索（ILS）[20]被用作PSO算法的改进阶段。ILS算法是基于粒子群算法产生的解的质量，以概率的方式在文献中，混合DE算法[15]和混合分布估计算法[21]被用于解决具有阻塞的车间调度问题。另一方面，混合PSO[ 19，22]和混合GA[ 23，24]被开发用于解决无等待车间调度问题。本文件的其余部分安排如下。第2节描述了阻塞型车间调度问题。第3描述了原始PSO。第二节介绍了用于解决该问题的PSO组合版本四、第5给出了计算结果。第六是结论。2. 问题描述在一个阻塞车间调度问题中，有一组n个工件以相同的顺序在一组m台机器上被处理，而没有中间缓冲区，即。作业jA1; 2;由于在我们的情况下，最大完工时间是要最小化的标准，因此这个问题可以表示为F=blocking=Cmax[25]。设pj;k表示序列中第j个位置的作业的处理时间 1;2;表示机器k上顺序中第j个位置的工件的出发时间。参考Ronconi[13]，可以通过出发时间的递归表达式找到最大完工时间ΔCmaxΔKD½1];0<$0;D½1];k<$p½1];ik<$1;2;1/1D½j];0<$D½j-1];1j<$2;3;...; n ;D½j];k½maxD½j];k-1p½j];k;D½j-1];k1j<$2; 3;D½j];m<$D½j];m-1p½j];mj<$1;2;因此，在本发明中，Cmax<$D<$n];m-1p<$n];m3. 粒子群优化算法PSO是Kennedy和Eberhart在1995年提出的一种进化方法。这个算法构成了一个比喻方案的鸟锁定和鱼学校。M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295297.Σ¼我半]我.ΣIJ我IJI1I2在V t¼ vt; vt;的表示质点i运动的速度第三个是Pt<$pt;pt;1.;2;...; S_i，它表示在迭代点t上搜索空间中部分圆i的位置。. 第二个问题是表示第i个粒子的最佳位置，最后一个粒子是G G1;G2;群集直到第t次迭代。IJIJIJIJIJIJIJ组合状态，反之亦然。为此，我们用Yt<$t;yt;I¼i1;i2;;在8>1ifxt-1¼Gt-1;>-1ifxt-1¼pt-1;IJIJIJIJIJIJ需要注意的是，y0是通过生成算法的初始解的方式获得在PSO算法中，个体被命名为代表问题的潜在解决方案的粒子，并且群由S粒子每个粒子i可以通过n维向量来表示：第一个由Xt^xt;xt;.; x t表示ii1i2int.ttt tii1i2in在每次迭代t时，粒子i根据先前的个人最佳位置Pt-1和先前的最佳位置Pt-1来调整其速度和位置先前全局最佳位置Gt-1，通过使用以下等式：vt¼vt-1c1r1pt-1-xt-1c2r2Gt-1-xt-11xt¼xt-1vtð2Þ其中c1和c2分别表示认知学习因子和社会学习因子。r1和r2是从0; 1中的均匀分布中抽取的随机数。粒子通过势函数搜索的同时，利用粒子群算法的随机机制，避免陷入局部最优解决方案Pt和Gt。此外，需要设置控制参数VMax因为速度无法超过这个值。Vmax控制每次迭代的最大移动距离，以避免该粒子越过好的解决方案。4. 组合粒子群优化算法求解分块流水车间调度问题最初，PSO算法用于解决连续优化问题[16]。最近，在离散优化中提出了几个成功的应用，例如CPSO算法用于聚类问题[26]，车间调度问题[17]和资源受限的项目调度问题[27]。在文献[28，19]中，提出了一种离散粒子群优化算法（DPSO），分别用于求解置换型车间调度问题和无等待型车间调度问题。这些方法之间的区别主要在于，通过提出新的编码方案，将该算法从原来的连续框架转换为离散框架Tasgetiren等人[28]已经使用了一种称为最小位置值（SPV）的启发式规则来使连续粒子群优化算法适应排序问题。 在文献[19]的DPSO中，提出了一种基于离散作业置换的粒子位置更新方法。在这一节中，我们提出了一个CPSO算法来解决阻塞流水车间调度问题。4.1. 组合粒子群算法组合粒子群优化算法在粒子的定义、速度和粒子解的构造4.1.1. 粒子的定义在组合的版本中，有必要引入一个过程，允许从连续状态到连续状态的通道溶液X测试.XtXt …IJJii1i2inyt-1¼>伊季.t-1t-1T-1型ð3Þ-1或 1随机，如果xijpij;>：0otherise4.1.2. 速度速度的更新函数由以下等式给出vt<$ωvt-1c1r1d1c2r2d2;4其中d1和d2分别表示解xt-1和pt-1之间的距离以及xt-1和Gt-1因此，Eq.（4）可以写成如下：伊季国际新闻报vtωvt-1c1r1.-1-yt-1c2r2.1-yt-1μ m;105μ m代表了全球最好的位置，IJ298M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295IJIJIJ>：IJ>：IJIJIJ蒂伊1;0否则α是一个常数参数，当它取一个最小值时，可用于积分，当它取一个最大值时，可用于积分。因此，xt可以如下获得：8>Gt-1x¼-p的如果 y t¼ 1IJð8Þ一个随机数，否则CPSO算法的伪代码显示在算法（1）中。算法1. CPSO算法的伪代码。图1.一、作业按其处理时间总和的降序排序图二、作业按其处理时间总和的递增顺序排序M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295299图3.第三章。创建新序列的示例300M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295-4.2. 解表示这里使用的表示法是作业的排列排列中的作业顺序表示机器对作业的处理顺序，即，排列中的每个数字表示其位置上的作业4.3. 初始粒子为了生成S粒子的初始群，我们建议随机生成S1粒子，并对剩余的元素应用启发式算法。所使用的启发式将是Nawaz等人提出的标准NEH之一。[29]，或者修改的NEH或随机NEH。标准NEH可以描述如下：步骤1：工件按照其加工时间之和的降序排序步骤2：选择前两个作业，并评估包含它们的两个可能的时间表。对目标函数值较好的序列作进一步考虑。第三步：把第一步中给出的排列中剩下的每一个作业都放在已经安排好的作业序列中所有可能的位置上，找到最佳的标准NEH、修改后的NEH和随机NEH之间的区别发生在第一步：不是按照加工时间总和的降序对工件进行排序;在修改后的NEH情况下，它们是按照递增顺序排序的。此外，在随机NEH中，第一步是生成一个随机的作业序列。在下文中，我们分别用“NEH_dec”、“NEH_inc”和“NEH_rand”表示标准NEH、修改后的NEH和随机NEH。 关于问题的阻塞约束，应用“NEH_dec“可能会在机器上产生阻塞时间，因为机器上具有高处理时间的作业更有可能被安排在第一个位置（图1）。①的人。相反，根据所有机器上的加工时间之和，工件的递增顺序可能会出现空闲时间（图2）。因此，没有证据表明什么是最适合我们的问题的启发式，实验研究和统计分析将被执行，以选择其中之一。表1NEH_inc、NEH_dec和NEH_rand之间相对百分比偏差的比较20~ 10 1.59 1.39 1.0320~ 20 2.18 0.58 1.2420~ 50 2.23 0.34 0.3550~ 5 0.29 1.27 1.2250~ 10 0.56 1.17 0.792019 -06 - 26 0.88 1.06 0.4650~ 50 1.89 0.30 0.48100~ 5 0.10 1.21 1.27100~ 10 0.03 1.86 1.37100~ 20 0.14 1.05 0.71100~ 50 0.88 0.39 0.27200~ 5 0.00 1.28 1.06200~ 10 0.02 1.63 1.17200~ 20 0.02 1.47 0.86200~ 50 0.16 0.69 0.26500~ 5 0.00 1.06 1.09500~ 10 0.00 1.38 1.33500~ 20 0.00 1.57 1.03500~ 50 0.00 0.95 0.421000~ 5 0.00 0.96 0.961000~ 10 0.00 1.20 1.331000~ 20 0.00 1.39 1.041000~ 50 0.00 1.03 0.60平均值0.51 1.13 0.90●●●问题NEH_incNEH_decNEH_兰特20~ 5岁0.831.841.05M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295301IJ¼我ð - ÞJIJIJIJ我IJ1I42I2βf xbest选择通过三种方式之一（“NEH_dec“或“NEH_inc“或“NEH_rand”）仅生成一个解4.4. 新的作业给定Yt，通过等式（8），我们提出生成一个新的可行工件序列Xt。我们用r表示工件的位置我我在Xt中，它对应于Gt-1（如果yt<$1）或pt-1（如果yt<$1）。令pst表示n维向量，其中pst指示作业j在序列中的位置如果rZj，则位于位置r和j上的作业被交换，这种情况对应于图1中的示例中的步骤1。 三、其中j<$1，Gt-1<$4，因此r<$pst <$3，则这些位置上的作业（作业5和作业4）被交换。否则，我们将面临一个矛盾的情况下，这需要在两个不同的位置存在相同的工作，所以我们随机选择其中一个，就像在步骤5中，其中j/4 5和r/4 2。如果y t <$0，就像在步骤2中j<$2一样，那么我们试图找到位置r上的第一个作业，其索引大于或等于j，并且它不同于G t-1<$3和p t-1<$2;因此r <$3满足这个条件，作业3和5是互换的。如果不存在满足这个条件的作业，那么r= 0，因此我们保留了前一次迭代的相同序列（算法2）。算法2. 创建新作业序列的伪代码。4.5. 混合CPSO（HCPSO）为了提高算法的解质量，我们通过应用迭代局部搜索（ILS）算法[20]，为我们的CPSO提出了一种混合算法。该算法是一种基于局部搜索的算法，具有实现简单的特点。它以前的应用到困难的组合优化问题，如二次分配问题[30]，图着色[31]，车辆路径问题[32]和置换车间调度问题[33]，都是成功的。ILS算法的基本框架由两个主要部分组成：局部搜索过程和扰动。令pc=1/4，RD是ILS算法应用的计算概率，其中RD为1/4。fx当前带 宽 -fx最佳带宽，xcurrent表示所创建的作业序列，xbest表示通过算法找到的最佳解决方案我们随机抽取在0和1之间的数字如果这个数字小于或等于，那么我们将ILS算法应用于所考虑的序列概率pc表示将根据其质量受到ILS的个体局部搜索：局部搜索过程包括通过使用第一改进规则将每个作业j插入当前解的部分中的所有可能位置来进行可能的插入移动。因此，我们选择比当前解决方案更好的第一个改进邻居。然后，立即选择改进的邻居来替换当前解。置换的插入邻域中的邻域的数目是n12。根据Wang等人[15]的加速方法评估每个插入移动。这个过程是从Taillard[34]最初开发的复杂性计算的减少扩展。此外，在Nowicki和Smutnicki[35]中，加速过程用于计算禁忌搜索算法的邻域搜索中的完工时间另外，诺维茨基[36]已将相同的约简用于具有缓冲器的车间调度但是，作者没有处理零的情况302M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295ð Þ ðÞðÞðÞ不--f xbest缓冲区（阻塞情况）。因此，Wang等人[15]证明了对于阻塞的车间调度问题，所开发的加速过程可以将整个插入邻域的计算复杂度从O n3m降低到O n2m。我们重新应用这个过程，直到没有可能的改进（算法3）。算法3. 插入本地搜索的伪代码。扰动：然后，ILS算法的最后一步是扰动，包括对获得的序列执行随机移动因此，扰动后的解的质量可能会恶化，并且搜索可能会被引导远离有希望的区域。为了引导搜索最接近的有希望的区域，我们使用概率的方式接受的恶化程度。而且，以这种方式，扰动可以提供新的最佳解。该概率通过使用Boltz是一个具有恒定温度的函数。 它可以写成如下：paccep texp。 -Δλ，其中Δλ。fx摄 动 -fx最佳摄动其中f x扰动是扰动后获得的解的值由于一次局部搜索的局部最优解过程不一定是另一个相同的，在这一步中，我们执行q交换移动的工件对随机选择的考虑序列，满足概率p接受。虽然交换邻居需要更多的计算工作比插入一个，我们试图从它的探索中受益，并找到新的改进的解决方案。ILS算法将一直运行，直到达到最大迭代次数（算法4）。整个混合算法的伪代码在算法（5）中给出。表2对NEH_inc、NEH_dec和NEH_rand执行的单向Anova测试的结果（对所有生成的720个问题进行测试）。源SSDFMSF比p值组148.43274.2189.030误差1798.0921570.83总1946.522159表3LSD程序的结果（对所有生成的720个问题进行测试）。NEH_inc NEH_rand 0.49 0.39 0.30NEH_dec NEH_rand 0.14 0.23 0.33Group1Group2LB均值差异UBNEH_incNEH_dec-0.72-0.63-0.54M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295303þþ.Σ算法4. ILS算法的伪代码。算法5. HCPSO算法的伪代码。5. 计算结果我们的算法（CPSO和HCPSO）是用C语言编写的所有关于最大完工时间标准的阻塞车间调度问题的实验都在装有Intel Pentium IV的台式PC上的Windows XP中运行3.2 GHz处理器和512 MB内存。所提出的算法的性能在Taillard的实例上进行了测试，用于车间调度问题[37]，该问题由一组120个问题组成，大小为m1/45; 10和20，20; 50; 100; 200和500。5.1. 基于随机实例问题的在我们的数值研究中使用的性能指标是完工时间Δ平均值的平均相对百分比偏差：Δ平均值¼R1/1RON-Heui罗恩R~100其中Heui是我们算法的任何R1/4 10复制给出的解，RON是Ronconi提供的解P304M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295¼¼¼ð Þ¼fl1/4~¼ ¼¼200Loko PC0： 05日志0：50¼ ¼ ¼ ¼ ¼ ¼¼β见图4。 ANOVA检验图。[8]的一项建议。该算法由几个参数组成：S，α，w，c1，c2和β，其中S是整数，其余参数是连续的。因此，为了找到这些参数的良好组合，我们遵循了Akrout等人提出的程序。[38]。该过程可以被呈现为局部搜索方法，其可以通过探索每个参数的有限集合来提供参数值的良好组合在我们的例子中，值的集合是SA10; 20;为了定义参数β，我们考虑pc0.5和当前解与算法找到的最佳解之间的相对偏差RD在集合0：002; 0： 004;在数值上，例如，pc0.5和RD0.05的情况导致接受相对于由算法提供的最佳解的相对劣化到目前为止等于5%的序列，其中概率等于0.5。所以，研发在此基础上，对m ulapc/exp确定了p c。研发部参数对于CPSO，S50，α0：2，w0.75，c10.2和c20.8对于HCPSO，S20，α0比 3，w0.75，c10.8，c20.2。通过实验，我们观察到ILS算法的应用概率， 对实例的大小非常敏感随着实例的大小，较少的恶化将被接受，我们已经发现1=n是这个参数的值的一个很好的近似。对于混合算法的停止准则，我们根据实例的大小固定了一个时间界限，它等于n~m，如Wang等人[15]中的HDDE。用于比较的方法是Caraffa等人[14]提出的GA，Grabowski和Pempera[1]的TS方法以及Wang等人[15]的混合离散差分进化（HDDE）。首先，为了选择产生粒子初始布居的方法，我们比较了4.3节中描述的NEH的三个版本。因此，对于该比较研究，我们生成了720个随机范围从20个作业和5马赫到1000个作业和50马赫的台架标记问题，其中，按照文献中通常使用的排列车间调度问题的均匀分布对于m和n的每个组合，生成30个随机实例。为了实现这种比较，根据相对百分比偏差RPD RPD来评估NEH的三个版本：RPDNEH-最好的NEH100最佳NEH其中，NEH表示由“NEH_inc”、“NEH_dec“或“NEH_rand“提供的完工时间的值表1显示，在此外，为了证明这一数值结果，我们使用Tukey最小显著差异程序（LSD）进行了单向ANOVA多重比较检验，其中响应变量为RPD。LSD程序是单因素方差分析的事后检验[39]。ANOVA分析比较了几组的平均值，以检验它们具有相等平均值的假设，而不是至少有一个平均值不同的一般替代方案。在进行该检验之前，应验证三个假设，即残差的正态性、方差齐性和独立性。在我们的情况下，根据Kolgomorov-Smirnov检验检查残差的正态性。关于同方差性，使用Levene检验。最后，残差的独立性进行了研究，通过时间的残差图。单因素ANOVA分析的输出见表2。由于p值接近于零，因此至少有一个样本均值与其他样本均值显著不同。此外，表3和图4显示了LSD程序的结果。可以观察到，作业的非递减顺序产生了显著的最佳结果（在95%的置信水平下）。我们的算法（HCPSO）提供的最佳结果在表3中给出。黑体字写的数字是我们算法提供的最佳数字。结果表明，根据Wang等人的HDDE算法的最佳结果，总共改进了76个实例。[15]第10段。如表3所示，大部分改进是在大型实例中检测到因此，对于M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295305¼200¼100个作业中，30个作业中有29个得到了改进，对于n200和500，所有实例都得到了改进。除了小实例（20个作业），我们的算法能够找到HDDE算法的最佳结果（表4）。为了将CPSO与Caraffa等人的GA进行比较。[14]，我们实现了后一种算法。首先，通过将两种算法的最大迭代次数设置为等于1000次迭代来表5中给出的结果表明，CPSO在解决方案的质量方面优于GA。其次，通过设置停止准则为n~m，对两种算法进行了比较研究。表6- 9中得到的结果此外，CPSO的结果范围（Δmax与Δmin之差）小于GA，表明了该算法的鲁棒性对于HCPSO算法，可以看出，该算法在解决方案的质量方面优于所有其他解决问题的方法，同时在所有类别的实例上导致最大平均相对百分比偏差（Δmax）（表6此外，在CPSO算法中引入的杂交过程有助于其解决方案的改进此外，HCPSO算法优于ILS算法。根据这些结果，我们可以看到，CPSO没有杂交，因为它执行的搜索空间的全局搜索，不能迅速收敛到局部最优。另一方面，ILS算法可以找到很好的解决方案，因为它执行局部探索，但这个结果对该算法的初始解非常敏感。因此，ILS算法的结果具有高度可变性，这通过ILS算法的最大（Δmax）和最小（Δmin）偏差之间的结果范围来显示。因此，CPSO和ILS之间的杂交过程可以协调这些算法的主要属性，其中ILS为CPSO提供局部探索工具，后者通过为ILS提供良好的开端来提供全局此外，我们可以观察到，这种合作减少了CPSO和ILS结果的最大（Δmax）和最小（Δmin因此，混合方法可以提供更强的鲁棒性。我们的结论是，虽然CPSO和ILS算法有一个相对中等的性能，这两个算法之间的合作出现作为一个有效的算法。表10提供了每类实例的HDDE计算结果。我们观察到，对于n =100，200和500，HCPSO的Δavg值优于HDDE的Δmax值对于具有50个作业的实例，我们的算法优于HDDE表4HCPSO算法提供的最佳完工时间值实例最好实例最好实例最好实例最好tai011374tai313023tai616197tai9113,653tai021408tai323223tai626116tai9213,613tai031280tai333041tai635980tai9313,709tai041448tai343153tai645836tai9413,545tai051341tai353184tai656044tai9513,584tai061363tai363200tai665932tai9613,327tai071381tai373052tai676073tai9713,795tai081379tai383074tai685991tai9813,771tai091373tai392921tai696203tai9913,547Tai101283Tai403123Tai706248tai10013,607tai111698tai413652tai717106tai10114,946tai121833tai423517tai726803tai10215,125tai131659tai433508tai736951tai10315,223tai141535tai443670tai747212tai10415,173泰151617tai453642Tai756869tai10515,055tai161590tai463624tai766684tai10615,172tai171622tai473713tai776842tai10715,170tai181731tai483591tai786898tai10815,178tai191747tai493549tai797118tai10915,121Tai201782tai503630tai807015tai11015,165tai212436tai514517tai817856tai11136,745tai222234tai524309tai827905tai11237,034tai232479tai534279tai837871tai11336,819tai242348tai544377tai847899tai11436,947tai252435tai554285tai857901tai11536,730tai262383tai564315tai867942tai11637,090tai272390tai574329tai877998tai11736,680tai282328tai584340tai888035tai11836,988tai292363tai594322tai897965tai11936,754Tai302323Tai604427tai907968tai12037,050306M. Eddaly等人/Journal of Computational Design and Engineering 3（2016）295--------- ------------------- -- -- -- -------- ---- -表5比较GA和CPSO在相同迭代次数下的相对偏差百分比公司简介ΔmaxΔavgΔminΔmaxΔavgΔmin20~05-0.99-2.62-4.64-1.05- 1.93-2.7620~10 1.19-0.49- 2.53 0.98 0.29-0.720~ 20 2.42 1.37 0.16 2.32 1.57 0.7550~05 1.3-0.06- 1.78 0.73 0.08-0.47电话：+86-10-8888888传真：+86-10 - 8888888850~ 20 3.69 2.07 0.49 2.86 2.38 1.96100~05-1.97-3.03-4.73-2.19- 2.59-2.98100~10 1.88 0.78- 0.4 1.96 1.64 1.38100~20 1.94 0.96- 0.1 1.81 1.62 1.46200~10-1.81-2.69- 3.53 0.86 0.71 0.59200~20-0.14-0.85- 1.53 1.46 1.37 1.32500~20-2.68-3.03- 3.36 1.61 1.59 1.58平均值0.63-0.53-1.87 1.16 0.72 0.30表6以相对百分比偏差表示的20个作业实例的结果实例RON GA TSPURUM CPSO ILS HCPSOΔmaxΔavgΔminΔmaxΔavgΔminΔmaxΔavgΔminΔmaxΔavgΔmin2019 - 05 - 25 0.22 1.23 1.55 1.81 0.72 0.54 0.36 0.72 0.57 0.292019 - 10 - 15 00：00：00 00：00泰03 1294 1.55 3.17 4.56 0.08 0.62 2.11 3.09 1.08 0.82 0.23 1.08 0.62 0.23泰04 1448 1.93 3.42 4.42 0.21 0.55 1.19 1.45 0.00 0.01 0.07 0.00 0.00 0.00澳门新葡京1366 1.32 0.71 3.44 1.32 1.61 1.00 0.66 1.83 1.67 1.54 1.83 1.68 1.61电话：+86-021 - 88888888传真：+86-021 - 888888882019 - 10 - 19 00：00：00 00：002019 - 07 - 25 0.36 0.21 0.07 0.36 0.18 0.222019 - 09 - 19 1.38 3.27 4.93 1.02 2.25 2.98 3.92 0.36 0.30 0.22 0.36 0.36 0.361283 1.95 3.82 4.99 1.48 0.78 1.11 1.48 0.00 0.21 0.62 0.00 0.091.06 2.81 4.48 0.34 0.82 1.69 2.30 0.44 0.29 0.00 0.46 0.32 0.122019年12月19日，2019年12月19日，2019年12月19泰12 1897 2.21 0.75 1.00 3.22 1.11 0.18 0.79 3.37 3.37 3.37 3.33 3.27澳门新葡8455.com澳门新葡845.com泰14 1622 4.19 2.55 0.18 4.13 4.50 3.08 2.28 5.36 5.36 5.36 5.36 5.36 5.36澳门新萄京1658 1.21 0.16 2.17 1.63 1.93 1.21 0.48 2.47 2.47 2.47 2.40 1.75澳门新葡京1640 1.28 0.57 2.93 2.26 2.44 1.26 0.30 3.05 2.99 2.87 3.05 2.94 2.87澳门新葡8455.com澳门新葡845.com澳门新葡845.com澳门新葡845.com1741 1.38 2.84 4.42 0.75 0.29 0.91 1.72 0.57 0.22 0.06 0.57 0.27 0.111777 1.01 0.80 3.04 1.01 0.68 0.14 1.63 1.58 1.42 1.07 1.69 1.40 1.07泰20 1847 2.65 1.58 0.97 3.52 3.36 2.74 1.84 3.52 3.52 3.52 3.52 3.521.10 0.38 2.47 1.77 1.45 0.58 0.31 2.39 2.29 2.08 2.40 2.30 2.07澳门新濠天地2530 2.92 1.58 0.51 3.20 3.28 2.85 2.21 3.72 3.65 3.60 3.72 3.64 3.602019 - 09 - 23 0.09 2.39 1.83 0.85 0.13 2.74 2.63 2.48 2.74 2.65 2.26泰23 2560 2.46 1.23 0.20 3.01 2.54 1.46 0.82 3.16 3.13 3.01 3.16 3.14 3.01澳门金沙城中心2399 1.58 0.16 1.13 2.13 1.75 0.95 0.38 2.13 2.13 2.13泰25 2538 2.17 1.54 0.75 3.47 3.35 2.49 1.54 4.06 4.06 4.06 4.06 4.06泰26 2467 2.72 1.27 0.04 2.80 2.15 1.58 1.01 3.40 3.24 3.08 3.40 3.22 2.92泰27 2502 3.84 2.34 0.76 4.20 3.48 3.03 2.60 4.48 4.44 4.16 4.48 4.44 4.16泰28 2411 2.45 1.53 0.41 2.74 2.57 1.96 1.53 3.44 3.21 2.94 3.44 3.31 2.99澳门新葡京2421 1.57 0.24-2.44 2.40 1.28 0.55-0.62 2.40 2.40 2.40 2.40 2.40泰30 2407 1.95 1.01-1.04 3.03 2.78 2.01 1.54 3.49 3.41 3.16 3.49 3.40 3.242.38 1.20-0.46 2.94 2.50 1.77 1.09 3.30 3.23 3.10 3.30 3.24 3.08