流水车间最小完工时间调度问题的遗传禁忌混合算法

沙特国王大学学报求解流水车间最小完工时间调度问题的遗传禁忌混合算法Moch Saiful Umama，Mr.，MustaMustab，Suryono Suryonoc印度尼西亚三宝垄50241，Diponegoro大学研究生院信息系统硕士课程b印度尼西亚三宝垄50275 Diponegoro大学科学与数学学院统计系c印度尼西亚三宝垄50275 Diponegoro大学物理、科学和数学系阿提奇莱因福奥文章历史记录：2021年3月31日收到2021年7月23日修订2021年8月23日接受2021年9月1日网上发售保留字：遗传算法禁忌搜索最大跨度流水车间A B S T R A C T本文将禁忌搜索与遗传算法相结合，采用一种新的基于部分反对的种群初始化技术，以最小化最大完工时间。流水作业是调度中的一个重要分支，在包括生产在内的许多学科中有着广泛的应用。它的困难使得许多研究人员开发算法来解决它，因为它被归类为NP难问题。生产调度问题的研究已经取得了一些进展，特别是进化算法.遗传算法由于其能够产生良好、快速和有效的结果来探索复杂的解空间（全局搜索）而成为最常用的进化算法来解决生产调度问题。然而，当进行容易卡在最佳局部区域中的利用（局部搜索）时，它提供无效的结果。同时，禁忌搜索具有局部搜索的优势，使遗传算法不陷入局部最优。通过将这两种算法与初始化方案相结合，得到了一种新的算法，该算法在产生更高质量的解时平衡搜索。使用120个问题实例对算法进行了测试。实验结果表明，该算法可以提高115个解决方案的120个实例比其他六个混合算法。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍所有复杂组织任务的协调和控制，包括资源分配，对于缩写：FSSP，流水车间调度问题; TS，禁忌搜索; AOA，算术优化算法; GA-TS，遗传算法禁忌搜索; GA-ISCR，插入搜索切割和修复的遗传算法; ACO，蚁群优化; CQGA，协同进化量子遗传算法; HGSA，混合遗传模拟退火; TANG，禁忌机制改进的迭代贪婪; SA，模拟退火; IG-JP，具有跳跃概率的迭代贪婪; DSOMA，离散自组织迁移算法; IG，迭代贪婪; GA，遗传算法; AE，平均误差; PI，增加百分比; ARPD，平均相对百分比偏差。*通讯作者。电子邮件地址：itgov@yandex.com（M.S.Umam），mustafid55@gmail.com（M.mustaiti），suryonosur@gmail.com（S. Suryono）。沙特国王大学负责同行审查制作和主办：Elsevier管理职能（Pinedo，2016），以尽可能快地向消费者提供产品或服务（Mustados等人，2018年）。组织的任务逐年变化，而且更加复杂。因此，生产过程中的重组应该在更短的时间内完成（Li et al.，2021年），特别是在调度上，以适应客户和市场的不同需求。流水车间调度是著名的，并被归类为NP-难优化问题（Berlin'ska和Przybylski，202 1），并开发了几种算法来克服这个问题（Lee和Loong，2019）。该领域的大多数研究人员使用进化算法（EA），更一般地，由于其优越性，自然启发的元进化算法（Greiner等人，2018年）。在元启发式算法中，大多数算法的灵感主要来自自然进化过程、群体行为和物理定律。这种基于群体的过程在执行搜索过程时采用多于一个候选解，以保持群体多样性并防止解陷入局部最优（Katoch等人， 2021年）。通过对各种文献的分析，我们可以提到一些著名的基于种群的元启发式方法来解决流水车间问题https://doi.org/10.1016/j.jksuci.2021.08.0251319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comMoch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7460是遗传算法（GA）（Yu等人，2018）、迭代贪婪（IG）（Shao等人，2017），蚁群优化算法（ACO）（Engin和Güçlü，2018），通过交换邻域序列进行禁忌搜索（Gao等人，2013），由Wei等人，2018），最近使用的搜索方法灵感来自数学运算符，称为算术优化算法（AOA），由（Abualigah等人，2021年a）。在元启发式求解方法中，GA是目前最流行的（Bisht等人，2021），这是由生物进化过程的启发，非常有用的解决搜索和优化问题，在大型和连续的搜索空间（Keskin和Engin，2021）。GA算法在解决调度问题方面表现出色，因为它能够在探索复杂的解空间时获得良好、快速和有效的结果（Piroozfard等人，2016年）。但在局部搜索能力方面存在问题-在利用局 部 最 优 区 域 时 容 易 陷 入 困 境 （ 早 期 收 敛 ） （ Amirghasemi 和Zamani，2017）。另一方面，禁忌搜索（TS）被提名为最佳局部搜索方 法 ， 旨 在 摆 脱 最 佳 局 部 ， 提 高 全 局 优 化 能 力 （ Grabowski 和Wodecki，2004）。通过混合一些算法的优点，我们可以提高基本算法的性能（Raidl等人， 2019年）。遗传算法在初始化后执行三个生物启发的算子对种群进行选择，如选择，交叉和突变（Sivanandam和Deepa，2008）。初始化生成个别的或可行的解决方案作为输入到GA使用各种方法。这是一项非常重要的任务，因为它可以对收敛速度并显著影响最终解的质量（Vlašic等人，2019年）。因此，在GA中为初始种群选择合适的技术对于实现接近最优解和减少计算时间至关重要，即，最小化制造跨度（Kazimipour等人，2013年）。随机方法最常用于初始化群体，但它会缩短收敛时间，并可能导致结果陷入局部最优（Pan等人，2014年）。为此，许多文献使用一些技巧来改进初始解。本文提出了一种混合遗传算法和TS算法的方法，通过采用部分相对基的初始化技术来最小化最大完工时间。GA作为全局搜索方案，TS用于搜索邻域或作为局部搜索方案。本文的主要贡献可以指出如下：我们提出了一种混合GA-TS算法，采用一种新的基于部分反对的种群初始化技术来解决流水车间问题。我们开发了一种新的方法，在遗传算法的初始人口产生一个可行的解决方案，称为部分反对为基础。通过120个基准问题对GA-TS进行了Taillard校正。本写作结构的其余部分遵循以下顺序：第2节简要概述了研究和使用的方法，然后是第3节，代表实验结果。然后在第4节中讨论了GA和TS算法的拟议合并，最后在第5中给出了结论和未来的工作。2. 材料和方法2.1. 相关作品本节包含两个方面，从遗传算法中用于初始化种群的各种技术开始，然后是一些元启发式算法来解决流水作业。的问题生产调度是根据顺序、如何安排加工资源和在一定标准下的操作顺序来安排发送到机器的生产任务，其目的是最小化最大完工时间（Pang等人，2020年）。Flow shop调度是一个吸引研究人员解决的问题，也是关于如何通过相同的加工过程来安排作业序列的流行调度类型之一（Belabid等人，2019年），在流车间的一些先决条件是（Komaki等人， 2019年）：1. 分离作业的工序之间没有调度规则。2. 一个作业或任务的任何操作每次只能在一个机器单元上完成。3. 对于所有作业，如果操作在前一阶段完成，则可以开始操作。4. 某台机器上的作业处理时间可以为0，并将该过程继续到下一台机器。5. 机器的顺序对所有的工件都是一样的，问题是找到机器上的工件顺序，使最大完工时间最小。6. 连续机器之间的行程时间可以忽略不计。以往的研究在流水车间调度问题的范围内留下了很大的研究空间。GA中的过程将从初始化种群开始。由于这一过程的重要性，使用了许多技术，例如准对立（Rahnamayan等人，2007）、空间变换搜索（Wang等人，2009）、基于对立（Li和Yin，2013）和线性回归（Hassanat等人， 2018年）。在解决流水作业时，由于问题更加复杂，启发式方法不再有效，因此必须使用元分析法（Lee和Loong，2019）。大多数文献集中在单个算法上，而不是模因或混合方案（Tosun等人，2020年）。模拟退火是解决流水作业的第一个元启发式算法（Osman and Potts，1989）。通过GA（Rahman等人， 2015），以及作为局部搜索优化而流行的TS（BenCheikh-Graiet等人，2020年）。由于杂交的概念提供了一个更强大的方法，通过结合两个或两个以上的算法，结合GA和TS是一个替代的解决方案，在解决流水车间。从已经混合的一些算法，特别是解决优化问题的元启发式算法，存在已经使用分散搜索机制与TS组合的GA（Glover等人，1995年）。对于最大完工时间最小化，存在与插入搜索切割和修复算法（GA-ISCR）杂交的GA（Tseng和Lin，2010）、与称为协同进化量子遗传算法（CQGA）的量子启发进化算法的GA（Deng等人，2015）和GA结合模拟退火（HGSA）（Wei等人， 2018年）。 除了遗传算法之外，还提出了各种类型的元算法来减少流水车间的最大完工时间，例如（Ding等人， 2015），其开发了使用称为禁忌机制的 可 变 邻 域 搜 索 的 局 部 搜 索 方 法 ， 具 有 改进的 迭 代 贪 婪 算 法（TMIIG），然后具有跳跃概率的迭代贪婪（IG-JP）（Tasgetiren等人，2017）和（Davendra和Bialic-Davendra，2013）在自组织迁移算法（DSOMA）的离散版本中使用了称为迁移的迭代。此外，近年来，aquila优化器（Abualigah等人，2021b），其灵感来自于Aquila在捕获用于一般优化问题的猎物时的行为过程。2.2. 所提出的方法本节描述的方法包括两个想法：第一，提出了混合GA-TS来解决流水车间问题，●●●Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7461←←←Fig. 1. 提出了GA-TS算法。第二，基于部分对立的技术来初始化表1参数整定。号参数名称值1人口规模1002最大迭代10003锦标赛规模供选择54交叉概率0.55突变概率0.16禁忌表52.2.2. 初始化填充初始种群的一个很好的技术是基于反对的（Li和Yin，2013），但是当所有的解都位于搜索空间的一侧时，并且该侧是局部最优的属性;那么这种状态将使算法在局部最优中收敛得太快。因此，这可以使用我们的部分基于反对的方法来欺骗，通过随机化一半的解决方案和另一半的解决方案，以确保所有的解决方案不会在搜索空间的一侧失败，正如我们可以从下面的伪代码中看到的那样人口有多种方法可以混合算法。在这论文中，杂交进行插入TS算法到GA过程中，探索一个局部搜索空间。下面的图1提供了所提出的GA-TS的工作流程。一般来说，开发的算法可以写成阶段，如下所示：图。二、拟议GA-TS阶段1：使用作业序列对问题进行编码阶段2：参数设置阶段3：初始化种群，这可以通过基于部分反对的阶段4：评估适应度值阶段5：是否达到最大迭代？如果达到，则进入第8否则，进入第6第6阶段：新种群阶段6.1：使用遗传算子进行繁殖（精英和锦标赛选择，两点交叉，交换变异）阶段6.2：运行TS邻域（插入，交换）阶段7：转到阶段4第8阶段：染色体解码以获得最佳解决方案2.2.1. 参数设置在探索解决方案和执行开发时，需要适当的参数调整来稳定所提出的算法;表1显示了所使用的调整后的参数for this study研究.混合GA-TS算法将停止生成时，达到最大迭代。遗传算法必须停止迭代本身也为TS，然后解码的解决方案，以显示最优的时间表。为了在可接受的计算时间内获得最佳结果，使用100的群体大小，并且最大代是1000（Yang等人，2015年）。一旦生成群体，就计算适应度值，这是最小化完工时间的目标函数。锦标赛规模从（Kölı和Yüzge，2019）从2增加到5，使用更大的锦标赛规模将产生更好的解决方案。交叉概率为0.5，以确保每个算法的例如， 2015年）。部分对置基1：随机化人群2：将溶液分为两部分3：通过将每个解S与S'进行比较，使用基于对立的方法创建位于左侧部分的半解，2.2.3. 适应度评估在创建初始种群后，通过适应度函数或目标函数进行适应度评估，本文中的目标函数是使工件的完工时间（makespan，Cmax）最小化，定义为：f/4 minCmax2.2.4. 选择染色体作为亲本选择与基于评估每个染色体的适应值来选择最佳染色体作为亲本在本研究中，使用了两种选择方法：a. 精英选择每次进行适应度评估时，具有最佳适应度值的染色体将存储为精英解决方案，因此在本研究中，最佳适应度值（即最小值）将较小或至少是常数。这项研究采用了精英方案（Rani等人， 2019年），伪代码如下。精英伪码1：群体中的P个个体集合2：OS繁殖后代3：//将P和OS中的个体组合成精英解决方案TEMP4：TEMP Merge（P，OS）5：//将最佳个体群体大小复制到P6：P←最佳复制（TEMP，P）b. 锦标赛选择锦标赛选择技术被认为对最小化问题更有效，因此本研究使用锦标赛规模5，考虑到使用更大的锦标赛规模将产生更好的解决方案（Lavinas等人， 2019年）。Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7462←←←←←≥KK最锦标赛1的伪码：P总体2：i =个体3：t锦标赛的规模，t14：最好从群体中随机选择染色体第五名：For i to t do6：从群体中选择向前染色体7：如果适应度（向前）>适应度（最佳），则第八章：最好的第九章：最好的回报2.2.5. 再生产过程通过交叉算子和变异算子，使染色体再生，获得新的染色体 本文采用两点交叉，变异采用交换方法。a. 两点交叉交叉是从选定的解决方案中组合基因以创建新的后代解决方案。通过将染色体的一部分与染色体的另一部分交换，这些任务提供了搜索空间中的解混合和收敛本文采用的方法（Vinoj和Jose，2016）如下。两点交叉1：随机2：定义两个点作为改变染色体的边界3：改变两个边界点图二. 两分交叉点。a.交换突变这项研究使用交换突变（Koohestani，2020），通过随机选择染色体上的两个位置并改变如图所示的值。3 .第三章。交换变异1：选择两个位置点的人口2：对所选位置的元素执行交换以产生后代2.2.6. 执行禁忌搜索TS已经成为本地搜索策略的第一当前邻域解中的最佳解，它不被认为是禁忌解或已被探索并存储在禁忌列表中的解（Laguna，2018）。禁忌搜索过程1：确定初始解和禁忌表的长度2：确定期望准则，在本研究中，跨度最小化3：确定终止标准;在本研究中，如果达到GA4：移动，在本研究中使用插入和交换方法5：评估解决方案，用搜索结果中不禁忌的最佳解决方案更新解决方案6：如果迭代次数最多，则停止搜索2.2.7. 染色体解码该编码方法使用了（Wang和Wang，2019）提出的Job-优先级（JP）它在所有机器上完成作业一的操作，然后在所有机器上完成下一个作业操作，依此类推。用于解码并在图表中显示的伪代码：伪码译码算法1：初始化结构图2：对于染色体中的每个基因，3：确定工作J4：从作业开始到作业J识别机器m的处理时间5：如果J是开始作业操作，则6：设置t0 = 07：其他8：将t0设置为J-1作业操作完成的时间9：如果10：结束3. 结果这一部分通过实验计算来评估所提出的混合GA-TS。使用一个1.9GHz的CPU与4 GB安装的RAM和数据集的Taillard，其中包含120个问题，GA-TS的性能调查已进行了测试十次，每个Taillard问题的情况下，分别记录最合适的解决方案。表2显示了来自比较分析的总结的实验结果，其配备有使用以下公式获得的误差平均值（AE）：AE¼1xXGATS-最佳x1001/1基 于 邻 域 搜 索 的 调 度 问 题 中 的 策 略 。 来 自 （ Deroussi 等 人 ，2012），它包括移动属性，邻域结构和禁忌列表。搜索步骤从初始解开始，然后探索解空间;因此，TS通过选择K表示实例的数量，Best表示从现有算法计算出的最佳解，GA-TS表示从所提出的算法生成的最大完工时间或解。该实验考虑六种混合算法：GA-ISCR、DSOMA、CQGA、TMIIG、IG-JP和HGSA。实验结果如下：图三. 交换变异Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7463最表2实验结果。实例大小上限GA-ISCR DSOMA CQGA TMIIG IG-JP HGSA电话：+86-21- 5555555传真：+86-21 - 55555555电话：+86-0571 - 8888888传真：+86电话：+86-021- 8888888传真：+86-021 - 8888888电话：+86-510 - 8888888传真：+86-510 - 8888888电话：+86-006- 51195 1430 1363 1481 1481电话：+86-510- 8888888传真：+86-510 - 8888888电话：021- 8888888传真：021 - 8888888电话：+86-510 - 8888888传真：+86-510 - 8888888电话：+86-010- 5100000传真：+86-010- 5100000电话：+86-010 - 8888888传真：+86-010- 8888888电话：+86-010-8888888传真：+86-010电话：+86-010 - 88888888传真：+86-010 - 88888888电话：+86-010 - 88888888传真：+86-010 - 88888888电话：+86-010-8888888传真：+86-010电话：+86-010 - 88888888传真：+86-010 - 88888888电话：+86-010 - 88888888传真：+86-010电话：+86-010-8888888传真：+86-010电话：+86-010-88888888传真：+86-010 - 88888888电话：+86-020- 8888888传真：+86-020 - 8888888电话：021 -2331 2331 1，48传真：021电话：+86-022 -2280 - 2169传真：+86-022- 2280 -电话：+86-023 - 2326 2922 2479 3013传真：+86-023电话：+86-024 - 202223 2967 2348 3001 3001电话：+86-025-2507 2361 3，06传真：+86-025电话：+86-026 -20 2226 2908 2383 2998 2988电话：+86-027 -2018888传真：+86-027电话：+86-028- 2200 2763 2328 2839 2839电话：+86-029 - 2237 2972 2363 3009传真：+86-029电话：+86-030 20 ×20 2178 2919 2323 2979 2979电话：+86-031- 5000000传真：+86-031 - 5000000电话：+86-032 -500 - 500传真：+86-032 - 500 - 500电话：+86-033 - 5000传真：+86-033 - 5000电话：+86-034 - 500- 500传真：+86-034 - 500 - 500电话：+86-035 50× 5 2863 3315 3128 3356 3356 3166 28642904 1，43电话：+86-036 50× 5 2829 3324 3166 3347 3347 3169 2907 2867 1，34电话：+86-037- 5000传真：+86-037 - 5000电话：+86-038- 5000传真：+86-038 - 5000传真：+86-038 - 5000电话：+86-039- 5000000传真：+86-039 - 5000000电话：+86-040- 5000传真：+86-040 - 5000传真：+86-040 - 5000电话：+86-041- 8888888传真：+86-041 - 8888888电话：+86-042 - 5000传真：+86-042 - 5000电话：+86-043 -5000传真：+86-043 - 5000电话：+86-044 50 ×10 3063 4480 3672 4399 4399 3656 3124 3124 1，99电话：+86-045 50 ×10 2976 4316 3633 4322 4322 3629 3129 3123 4，94电话：+86-046 50 ×10 3006 4282 3621 4289 4289 3621 3293 3188 6，05电话：+86-047 - 500000传真：+86-047 - 500000电话：+86-021- 8888888传真：+86-021 - 8888888电话：+86-049 - 500- 8888传真：+86-049 - 500 - 8888电话：050 -85555555传真：050 - 85555555电话：051- 85555555传真：051 - 85555555电话：+86-520 - 88888888传真：+86-520电话：053-5000000传真：053 - 5000000电话：+86-054-500000传真：+86-054 - 500000电话：0551-8888888传真：0551 - 8888888电话：+86-510- 8888888传真：+86-510- 8888888电话：+86-057 -500000传真：+86-057 - 500000电话：+86-058- 500000传真：+86-058 - 500000电话：+86-059- 500000传真：+86-059 - 500000电话：+86-060- 88888888传真：+86-060 - 88888888电话：+86-061-5493 6492 6151 6397 6397 6151 5536 5502电话：+86-062-5268 6353 6064 6234 6234 6022 5302 5301 0，63电话：+86-063-5175 6148 6003 6121 6121 5927 5221 5213 0，73电话：+86-064-5014 6080 5786 6026 6026 5772 5044 5041 0，54电话：+86-065-5250 6254 6021 6200 6200 5960 5358 5323 1，39电话：+86-510 - 8888888传真：+86-510 - 8888888电话：+86-067-5246 6257 6004 6247 6274 6004 5414 5320电话：+86-068 -5100000传真：+86-068 - 5100000电话：+86-069-55486443 6154 6370 6370 6123 5546 5506 1，06电话：070-5322 6441 6186 6381 6381 6159 5480 5386 1，20电话：+86-071-88888888传真：+86-071 - 88888888电话：+86-072-5349 7986 6813 7880 7880 6791 5596 5594 4，58电话：+86-073 - 88888888传真：+86-073 - 88888888电话：+86-074 -88888888传真：+86-074 - 88888888（接下页）Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7464最表2（续）实例大小上限GA-ISCR DSOMA CQGA TMIIG IG-JP HGSA电话：+86-076-5303 7823 6685 7801 7801 6666 5446 5401 1，85电话：077- 5595 7915 6827 7866 7866 6801 5679 5667 1，29电话：+86-078-5617 7939 6874 7913 7913 6874 5723 5633电话：+86-079-5871 8226 6092 8161 8161 7055 5934 5926电话：0510-8888888传真：0510 - 8888888电话：0755-8888888传真：0755 -8888888电话：+86-082-88888888传真：+86-082 - 8888888电话：+86-083- 200000传真：+86-083 - 2000000电话：+86-084 - 8888888传真：+86-084 - 8888888电话：+86-085 - 8555555传真：+86-085 - 85555555电话：+86-086 - 888886527传真：+86-086 - 888886527电话：+86-087 - 8888888传真：+86-087 - 8888888电话：+86-086 - 8888888传真：+86-086 - 88888888电话：0755 - 8888888传真：0755 - 8888888电话：+86-090 - 88888888传真：+86-090电话：+86-021 - 8888888传真：+86-021 - 88888888电话：+86-021- 8888888传真：+86-021 -电话：+86-021-8888888传真： +86-021 - 88888888电话：+86-021 - 8888888传真：+86-021 - 8888888电话：+86-021-8888888传真： +86-021 - 88888888电话：+86-021-8888888传真： +86-021 - 88888888电话：+86-021 - 88888888传真：+86-021 - 88888888电话：+86-021- 8888888传真： +86-021 - 88888888电话：+86-021- 8888888传真：+86-021-88888888电话：+86-10- 8888888传真：+86-10 -电话：+86-10- 8888888传真：+86-10 -电话：+86-510 - 8888888传真：+86-510-电话：+86-10- 8888888传真：+86-10 -电话：+86-10- 8888888传真：+86-10 -电话：+86-510-8888888传真：+86-510-电话：+86-10-8888888传真： +86-10 - 88888888电话：+86-510 - 8888888传真：+86-510-电话：+86-510 - 8888888传真：+86-510-88888888电话：+86-510 - 8888888传真：+86-510-电话：+86-10 - 8888888传真：+86-10 -电话：+86-10- 8888888传真：+86-10 -电话：+86-510- 88888888传真：+86-510 -2019 - 10- 16 00：00电话：+86-10- 8888888传真：+86-10 - 88888888电话：+86-10 - 8888888传真：+86-10 - 88888888电话：+86-10-88888888传真：+86-10 - 88888888电话：+86-510 - 8888888传真：+86-510 -电话：+86-510-8888888传真：+86-510-88888888电话：+86-10- 88888888传真：+86-10电话：+86-510- 8888888传真：+86-510-图四、使用GA-TS的调度结果Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7465××××¼××联系我们×120例如，通过输入第一个问题Taillard 20 5，这意味着该问题具有在5台机器上处理的20个作业，GA-TS算法已经生成了具有作业序列[16，8，14，5，15，7，0，17，18，13，10，12，2，3，1，4，6，9，11，19]，并要求完成时间为1，297，图四、正如我们在表2中看到的，最佳的完工时间被记录下来，其他算法的结果也在那里。4. 讨论我们使用三个标准来评估GA-TS的最大完工时间或解决方案的质量：平均误差（AE），增加的百分比（PI）和平均相对百分比偏差（ARPD）。基于第3节中给出的计算结果，第一个问题的最右边的列，即GA-TS 列，获得 GATS= 1282 和 Best= 1278 ，因此列值为（GATS从这里，AE值通过以下方式获得：1例AE¼2019-06 -25 00：00：00从图5中可以看到来自几种其他混合算法的AE比较，其中GA-TS对于Taillard flow shop数据集具有最低的AE。蓝色条是GA-TS以外的算法;橙色条是GA-TS算法。CQGA旁边的橙色是Taillard问题前90个示例的GA-TS的AE值下一个分析是增加的百分比（PI），这是一个相对变化，显示了最终数量相对于初始数量的增加量。在这种情况下，PI代表百分比图五、一些混合算法的AE比较与其他算法相比，GA-TS的最大完工时间有所增加。 在下面的公式中，CGATS表示使用GA-TS产生的最小完工时间，Cx表示由正在比较的其他算法产生的最小完工时间。例如，问题大小为20 5的CGATS为12，441，问题大小为20 5的CGAISCR为14265，则GA-TS算法相对于GA-ISCR的PI可以通过以下结果计算：PiCGAISCR-CGATSx100C服务贸易总协定Pi14265 - 12441x100146612441GA-TS算法与其他六种算法的百分比增加的比较可以总结在表3中。在200 20问题中，GA-TS算法的PI值相对于HGSA算法记录了负值，因为从表2所示的实验结果来看，该算法未能最小化三个问题：ta-103、ta-104和ta-105，这导致出现负号。当解决大小为100的问题时，可获得最佳性能20和GA-TS算法提高了解的质量，如图1所示。 六、最后一个标准是用来确定平均性能的GA-TS采用平均相对百分比偏差（ARPD），它可以被描述为平均百分比值之间的相对偏差GA-TS产生的结果与最佳值。通过将每个算法的完工时间差与已知的最佳完工时间值相加，然后乘以100，再除以10，我们得到ARPD。图7示出了GA-TS算法的ARPD具有低于7%的值，并且低于其他混合算法的ARPD。ARPD结果表明，GA-TS算法的解可以接近理论最优值，也可以称为Taillard问题的上界，越小越好。在每个问题实例的实验中，遗传算法和TS的混合被评为大多数流水车间问题的最佳结果。第一个原因是混合GA-TS算法是遗传算法和TS算法的结合。两者通过平衡求解精度和计算速度来共同工作，以输出更优的解。遗传算法使用其全局搜索方法进行探索，同时，TS使用其局部搜索方法进行开发。对于第二个原因，主要关注的是有效地解决流水车间在最小化最大完工时间位于初始人口的技术和参数设置。因此，GA-TS可以通过平衡多样化（当执行全局搜索时）和强化（当执行局部搜索时）来找到解决方案。表3GA-TS算法将GA-TS增加到GA-ISCR DSOMA CQGA TMIIG IG-JPHGSA 20× 5 14，66 9，56 18，99 18，9920× 10 24，20 7，87 27，01 26，8020× 20 26，21 3，00 29，05 27，8350× 5 17，47 10，49 18，34 18，34 11，43 0，3350× 10 36，28 15，12 36，63 36，63 14，98 2，0850× 20 48，58 9，34 48，81 48，81 9，43 1，72100× 5 18，87 13，75 17，56 17，62 13，23 0，64100× 10 18，92 39，59 39，42 20，40 0，69100× 20 65，93 22，91 65，53 65，53 22，42 1，61200× 10 44，27 27，47200× 20 72，07 27，63-500× 20 81，51 36，77Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7466图六、PI值GA-TS到另一个算法。见图7。 GA-TS的ARPD值5. 结论本研究提出一种混合遗传-TS演算法，并成功解决流水作业中最小化完工时间的问题遗传算法的三个主要遗传算子，包括选择，交叉和变异，已被采用，以解决流水车间有效，初始种群技术成为一个成功的因素。此外，TS算法引导GA算法的局部搜索120个开放问题的例子，从Taillard数据集，这是流行的研究人员，已被用来评估建议的混合GATS。我们可以说，遗传算法- TS已经获得了更好的增加，在最小化最大完工时间方面的解决方案的准确性，从进行的实验相比，其他六个混合算法。GA-TS的AE值为3.05%，PI是可变的，ARPD低于7%，也可以改善115 120例问题。本研究可借由将遗传演算法与其他局部搜寻演算法结合，为未来多目标、多约束模式下的研究提供进一步的拓展。同时，通过确定调度规则，可以实现更有效的算法。资金这项研究没有从公共、商业或非营利部门的资助机构获得任何具体的竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。引用阿布阿里加湖Diabat，A.，Mirjalili，S.，Abd Elaziz，M.，Gandomi，A.H.，2021年a 。 算 术 优 化 算 法 。 Comput. 方 法 应 用 机 械 工 程 376 ， 113609 。https://doi.org/10.1016/j.cma.2020.113609网站。阿 布 阿 里 加 湖 Yousri ， D. ， Abd Elaziz ， M. ， Ewees ， AA ， Al-qaness ， M.A.A. ，Gandomi，A.H、2021b的最后一页。Aquila Optimizer：一种新的元启发式优化算法。Comput. 工业工程157 ，107250 。https://doi.org/10.1016/j.cie.2021.107250 网站。Amirghasemi，M.，扎马尼河2017年。求解置换流水车间调度问题的一种有效的进化混合算法评价Comput.25（1），87-111。https://doi.org/10.1162/EVCO_a_00162网站。Belabid，J.，Aqil，S.，Allali，K.，2019.求解具有排列和序列独立设置时间的流水作业Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7467问题，在：2019年国际会议上Moch Saiful Umam，M.Mustaeli和S.苏尔约诺沙特国王大学学报7468优化和应用，ICOA2019。IEEE，pp.1-5.https:/