局部搜索策略对流水线车间调度问题的影响：混合优化算法研究

沙特国王大学学报局部搜索策略对Flow-shop调度AbdülkadirGümü，sçüa，soul，SerkanKayab，MehmetEminTenekecic，I_zzettinHakanKaraçizmelib，I_ brahim Berkan Aydilekca土耳其南勒乌尔法哈兰大学工程系电气和电子工程系b土耳其南勒乌尔法哈兰大学工程学院工业工程系c土耳其南勒乌尔法哈兰大学工程学院计算机工程系阿提奇莱因福奥文章历史记录：2021年3月26日收到2021年7月12日修订2021年7月24日接受在线预订2021年保留字：Flow-shop调度混沌映射局部搜索萤火虫算法粒子群优化A B S T R A C T流水线生产环境是工业中广泛使用的生产环境，特别是当产品和工艺的种类有限时更受欢迎。技术的不断发展和市场竞争的日益激烈迫使研究人员寻求提高效率的方法。因此，调度仍然是研究人员的一个重要研究领域。当问题的规模增加时，特别是在现实生活中，几乎不可能通过当前的计算机技术来制定一个可行的解决方案。在这种情况下，解决方案通常使用启发式或元启发式方法来开发。然而，这些方法的性能可能会根据问题或建议的解决方案的组成部分而有所研究了局部搜索策略对萤火虫-粒子群混合优化算法求解性能的影响。我们使用了四种不同的求解方法：三重局部搜索策略，包括插入，交换和反演，这是在早期研究中经常使用的，以及这三种策略中的每一种的单独使用。在本研究中，使用插入、交换、倒置和三重策略计算的平均相对差值分别为3.03、1.27、2.54和1.20。由于进行了分析，以比较在Taillard的流水车间调度问题中获得的解决方案的结果，发现使用三重策略获得了更好的结果这些发现可作为今后研究的参考版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着计算机技术的发展，优化方法在许多学科中的应用越来越多作为这种发展的结果，已经提出了许多不同的优化方法，并且已经获得了解决不同问题的成功结果（Gupta等人，2018; Turgut，2020; Zhang等人，2021年）。作为主要问题之一，流水车间调度在工业中常见（Wang等人，*通讯作者。电子邮件地址：agumuscu@harran.edu.tr（A。 Gümü，sçü）. 沙特国王大学负责同行审查。制作和主办：Elsevier2020年）。考虑到这些问题的规模，显然应该使用Meta启发式方法.随机性是元算法所固有的，就像在其他一些优化方法中一样。它造成了在优化过程中在解空间中的搜索陷入局部最小值的可能性。在最近为解决该问题而进行的优化研究中，混沌优化方法已被频繁地用于消除搜索中可能的常规循环（Kaveh等人，2021年）。例如，Aydilek等人提出了一种新的混沌混合萤火虫粒子群算法（Aydilek等人，2019）通过混沌映射改进混合萤火虫和粒子群算法。此外，一些局部搜索方法已被开发和杂交使用优化，以达到更好的解决问题的结果。局部搜索方法和元启发式方法采用不同的策略。最常用的局部搜索方法是交换、插入和反转。局部搜索方法是流水车间调度问题中的一种常用方法。此外，MetaHeuristichttps://doi.org/10.1016/j.jksuci.2021.07.0171319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comA. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报6433方法与混沌映射一起用于改进搜索空间的扫描。此外，混沌元启发式方法，连同局部搜索方法，可以使用不同的策略。这项研究集中于两个主要目标。这些都是为了确定什么样的改进局部搜索方法提供流水车间调度问题，并观察不同的局部搜索组合的效果。为此，在Taillard流水车间调度问题中，研究了局部搜索策略（包括交换、插入、求逆和三重策略）对混沌混合萤火虫粒子群算法的影响本研究的结果可以显着有助于前瞻性的研究，旨在解决优化问题，以及流水车间和其他调度问题，通过使用启发式和元启发式方法，以扩大知识，如何使用局部搜索方法。本文的其余部分组织如下：第二部分提供了文献中早期研究的概述。第三章讨论了本研究所采用的方法和算法。第四章详细阐述了利用局部搜索算法进行的实验在研究中获得的结果在第5节中的局部搜索方法的效果方面提出和讨论。最后一节阐述了本研究的贡献。2. 文献综述在优化问题中，元启发式方法用于在短时间内获得最优或接近最优的结果。尽管这些方法很难保证最优解，但它们是具有实现接近最优结果的高概率的算法。另一方面，局部搜索算法采用策略来进一步开发使用元启发式方法获得的解决方案（Aydilek等人， 2019年）。迄今为止，研究人员已经开发了混合算法，通过调整局部搜索算法的Meta启发式方法，而不是使用传统的元启发式或局部搜索算法来解决调度问题。除了消除解决方法遇到的重要问题（即，它被困在局部最小值），这些混合算法也使得在全局空间中搜索解成为可能。文献综述首先集中在研究调查不同的调度问题，其中使用局部搜索算法，然后继续讨论研究流水车间调度问题。SI_R（2019）提出了一种基于最短路径解决了具有变速活动的单机调度问题，特别关注总完成时间。本研究在以最短加工时间为准则的作业排程的每一步，利用局部搜 寻 中 的 交 换 策 略 ， 发 展 其 求 解 方 法 。 Kaya 和 Karaçizmeli（2018）提出了一种局部搜索算法来解决具有多目的序列相关设置时间和公共截止日期的并行机调度问题。他们观察到，该算法取得了更好的结果比经典的调度规则和蚁群算法的基础上，通过解决问题，其中的平均完成时间和最大完工时间的标准得到解决的帕累托最优结果Özçelik和Saraelik（2011）提出了一种启发式局部搜索算法来解决同样的问题，以最小化完工时间和总拖期。作者使用局部搜索来改进使用经典调度规则获得的初始解Kaya（2014）在粒子群优化算法中加入局部搜索策略，提出了两种求解多目标柔性作业车间调度问题的算法（集成算法和分层算法）在另一项研究，Kay和Favorig Zulalalaleet（2018）提出了局部搜索算法与元启发式算法的混合来解决相同的问题。为了解决同时取货和送货的动态车辆路径问题，Aydo g du 和Özyörük（2020）提出了一个数学模型和一个启发式算法，该算法采用随机迭代局部搜索和可变邻域下降搜索。 为了解决时间窗车辆路径问题，Küçükaydın（2019）提出了两种基于列生成的启发式算法（一种使用迭代局部搜索元算法，另一种使用可变邻域搜索元算法）。Küçükaydın评估了算法在小型和大型问题集上的性能，并观察到它们在短时间内产生了更多可行的解决方案。 为了解决动态车辆路径问题，Demirt a，s和Özdemir（2017）提出了一种结合粒子群优化算法和局部搜索的混合算法。研究人员观察到，使用文献中提供的测试问题和现实生活中的问题进行测试的算法提供了良好的结果。为了解决伙伴约束的车道覆盖问题，Kuyzu（2020）提出了一种混合遗传算法，该算法由遗传算法、局部搜索和大规模邻域搜索方法的组合Baykovich和I_，sleyen（2007）提出了一种快速有效的迭代局部搜索算法来求解对称旅行商问题问题.与传统的迭代局部搜索算法不同，Baykovich和Ileyen试图通过在算法中使用四种不同的局部搜索算法来提高解的性能。Rithm。在另一项研究中，Karabulut（2016）提出了一种进化策略算法来解决非对称旅行商问题。作者在算法中引入了局部搜索，以改进算法的解.Karagül（2014）通过结合cuckoo和局部搜索算法来解决旅行商问题，并将其用于解决现实生活中的问题。为了解决多维背包问题，PALA（2020）提出了一种混合遗传算法，该算法使用局部搜索来改进初始种群。Özsoydan（2018）提出了一种粒子群优化算法，该算法通过对0-1问题空间的局部搜索来增强。Türkbey（2002）提出了一种使用局部搜索的模因算法来解决二次分配问题。在算法中，作者利用Eshelman过程提出了一种新的交叉算子，以增加解的多样性为了解决二次分配问题，Jesus和Öztürk（2016）提出了一种混合算法，他们通过结合遗传算法和局部算法获得。局部搜索是一种常用的算法，用于改进流水车间调度问题的解，提高解的质量。本部分详细阐述了局部搜索算法在流水车间调度问题求解中的应用研究，这也是本文研究的重点。为了解决流水车间调度问题，重点关注最大完工时间，Benavides和Ritt（2016）提出了建设性和迭代局部搜索算法;Cui等人。（2016）提出了一种使用局部搜索和遗传算法创建的混合算法，用于同一问题的可用性约束解决方案。 Wang等人（2017）介绍了Nawaz-Enscore-Ham（NEH）算法和布谷鸟搜索算法，他们采用了两种不同的策略。Liu等人（2007）提出了一种混合算法，该算法通过将模因和粒子群优化算法与局部搜索相结合而产生。Li和Yin（2012）提出了一种蜂群算法，特别关注总流动时间，他们采用了四种突变策略;即交换，插入，倒置和相邻交换。Li和Yin（2013）提出了一种混合布谷鸟搜索算法，A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报6434我我我我1我我2我我采用快速局部搜索策略。Benavides和Ritt（2015）提出了一种基于邻域结构的局部搜索算法来解决相同的问题，以最小化完工时间。为了最小化总流动时间，Reeves和Yamada（1998）开发了一种混合算法，他们将局部搜索和遗传算法混合在一起。作为多目标流水车间调度问题的解决方案，Framinan和Leisten（2008）引入了基于贪婪局部搜索方法的启发式算法;Yagmahan和Yenisey（2010）提出了一种蚁群算法，他们适应了局部搜索;JosefGeiger（2011）提出了一种基于Pareto的迭代局部搜索算法，包括可变邻域搜索和迭代局部搜索，以提供一种专注于最小化完工时间和总延误的解决方案。Arroyo和Armentano（2005）提出了一种遗传算法和局部搜索算法相结合的混合算法。 Wu等人（2018）通过使用遗传和可变局部搜索算法的组合创建了一种混合算法，以解决具有可变加工时间的多用途灵活流水车间调度问题。为了最小化分布式置换流水车间调度问题中的总流程时间，Pan等人（2019）提出了4种方法：离散蜂群、分散搜索、迭代局部搜索和迭代贪婪算法。建议的方法包括先进的和有效的搜索能力，可能会逃脱局部最优的战略。为了解决同样的问题，以最大完工时间为重点，Gao和Chen（2011 b）提出了一种混合遗传算法，其中他们集成了一种先进的局部搜索算法。Tseng和Lin（2010）提出了一种基于局部搜索和遗传算法的混合算法来解决无等待流水车间调度问题，同样关注最大完工时间。Czogalla和Fink（2009）介绍了一种算法，他们通过混合局部搜索和粒子群优化算法来解决相同的问题，并最大限度地减少延误。Ruiz et al.（2019）通过采用具有局部搜索的迭代贪婪算法改进了Flow-shop排序问题的解决方案。 Kaya等人（2021）使用混沌混合萤火虫和微粒群优化，并使用局部搜索的改进版本来解决流水车间调度问题。 Amirghasemi（2021）提出了一种有效的随机算法，该算法将大型邻域分解技术嵌入到可变邻域搜索中以解决相同的问题。Dodu和Anc au（2020）提出了一种禁忌搜索算法，该算法与局部搜索相结合，具有在整个解空间中进行密集搜索的特点。研究人员最近转向混合方法，而不是经典的启发式/元启发式方法，以解决调度问题 Benavides 和Ritt （2015）;Dodu 和Anc au（2020）;Wang et al. （2020年）。相关文献的回顾表明，研究人员往往更喜欢局部搜索，因为它不仅易于应用，但它也产生有效的混合算法的结果。此外，很明显，研究人员随机选择本地搜索算子。他们通常不解释为什么他们选择一个特定的本地搜索运算符，他们在他们的算法中使用在文献中，没有研究中，局部搜索算子产生更有效的结果，特别是在流水车间调度问题。为了弥补文献中的这一空白，本研究调度问题是不可能通过传统的数学方法解决的。从文献中的数据清楚地表明，元启发式算法在解决这些问题更有效。在流水车间调度问题中，假设n个工件可以在m台机器上完成。在不改变机器顺序的情况下，优化了机器上待处理的工件的顺序。根据目标函数的排序问题可以分为三大类。这些目标函数基于完工时间、交货时间和机器使用成本。基于完工时间的目标函数，可显示最大完工时间、平均完工时间、加权完工时间总和、最大流水时间、平均流水在求解调度问题时最常用的目标函数是最大完工时间。最大完成时间（Cmax）是指最后一个作业离开系统的完成时间。最小化Cmax，也称为最大完工时间，使得有可能有最高的机器利用率，并在到期日内完成工作。在一个n件m机流水作业调度问题中，工件的完工时间用下面的公式计算。在等式（1-4）中pij表示第i个工件在第j台机器上的处理时间，Ci表示总的完成时间。Cmax是指等式5中的完工时间。C11 = p111Ci; 1= C i- 1; 1+ pi12C1; j= C 1; j- 1+ p 1j<$3C i; j= max f C i-1; j; C i; j-1g + p i ji = 2，. ，n，j = 2，. ，m 4基于等式（1），使用等式（2）定义最大完成时间。Cmax = Cn;m5测试集包括在literature中获得的最低Cmax值和在放松条件下可能的最低Cmax值3.2.混沌萤火虫-粒子群混合优化算法Aydilek 提 出 的 混 合 萤 火 虫 和 粒 子 群 优 化 （ HFPSO ）（Aydilek，2018）算法是通过结合萤火虫算法（FA）和粒子群优化（PSO）创建的。综合运用这些方法的优点，可以得到更好的结果PSO是一种元启发式算法，在每次迭代中改变位置以找到最佳解。如等式（6）和（7）所示，每个粒子的速度（v）和位置（x）值在每次迭代时更新。它是个人（pbest）和全球最佳（gbest）影响此更改的值vk1 ¼ w：vk c1：rand k：.pbestk-xkc2：randk：gbestk-xk6解决方案的方式3. 材料和方法在等式（6）中，c1、c2、rand1、rand2是范围从0到1的随机值。c1和c2加速度;w是惯性重量。xk1¼xkvk1ð7Þ3.1. Flow-shop调度问题流水车间调度是工业界科学研究的前沿问题之一然而，高维流水车间我我我在计算新的速度值之后，如等式（7）所示计算粒子的新位置值。xk=1表示新位置，而xk表示前一个位置。研究了局部搜索算子对性能的影响，A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报6435.Σ我我我0i;jJ我我J我我0我最后一个作业完成时，Cmax值是最常用的：我由于速度参数及其保持最佳值的能力，PSO算法执行非常成功和快速由于这一特点，它已经在文献中作为一种有效的方法在全球搜索中享有的普及它快速移动到目标并快速扫描解空间然而，由于在寻找绝对最小值时的振荡，它可能导致因此，它的剥削性仍然较弱。FA算法是HFPSO算法的另一个组成部分，是一种模仿萤火虫（FF）的元启发式算法。为了实现其目标，FF在每次迭代中运行到最亮的FF。灯光的强度是根据亮度和距离计算的。Rithm算法与CHFPSO算法相比，CHFPSO-LS算法的工作量要大得多。在该算法中，每当g最佳值被改进时，将运行局部搜索块。此块重复每次迭代中作业数量的平方。这被计算为Hkωn2;取决于作业数n和迭代次数k。算法中的随机变量由均匀分布的随机函数确定。这些变量根据特定函数的初始值而变化。另一方面，混沌映射的工作原理与随机结构类似，但初始值的微小变化会完全改变分布。然而，最佳值可以通过以下公式计算：更有效地扫描整个搜索空间Xt1¼XtBe-cr2.Xt-Xtasð8Þ最初，随机识别FF的初始位置使用等式（8）来计算下一次迭代中Xt= 1的新位置。等式（8）中所示的Xt和Xt表示两个3.3. 局部搜索方法局部搜索方法可以应用于所产生的解集，以提高求解方法在调度中的成功率不同的FFsi是随机变量的向量，a是随机性参数该算法试图找到最佳递归计算每个新位置的解与PSO不同，FA缺乏保持速度参数和先前最佳值的能力。因此，它可以根据当地条件确定最合适的解决方案。因此，它确保了成功的开发。然而，它实现全局结果比PSO慢。HFPSO算法结合了FA和PSO算法的搜索能力所使用的方法将根据混合算法中适应度函数的改进而不同只要gbest值在算法中没有改变，就使用PSO，但是如果gbest值提高，就使用FA方法也就是说，该算法结合了粒子群算法的成功，由于其快速搜索功能的全局解决方案和FA等式（9）用于计算每个粒子的适应度函数中的全局最佳值是否有改善如果在迭代中有一个粒子的值比gbest更成功，则使用萤火虫算法;否则，使用PSO算法8真;如果粒 子数≤gbestt-1我问题这些方法的使用大大有助于许多优化方法。在本研究中使用了图1所示的交换、插入和倒置策略。在交换策略的实验中，两个不同的工作相互换位。另一方面，通过改变作业的位置和在不同作业之间添加作业来应用插入策略。另外，对于两个指定工件之间的所有工件，以相反的顺序应用反转策略。所应用的局部搜索策略的细节在图1中提供。在这项研究中，局部搜索分别使用插入，反转和交换操作和所有三个一起进行。4. 实验研究实验结果是通过同时使用两个共24核的Intel Xeon E5-2670 v3处理器获得的算法1示出了该方法的局部搜索部分的伪代码。局部搜索以最佳全局值作为输入，首先执行插入;然后在与循环数量相同的并行子循环中，根据作业数量，使用24个处理器内核执行插入、交换和反转fi; t。Σð9Þ（n×（n-1）/24），与解决方案的改进程度一致弱助词t>gbestt-1等式（10）和（11）用于计算新的位置。粒子的作用（Xit1）和速度（Vit1）值在我们的研究中，Taillard创建的测试集被用来解决Flow-shop scheduling problemsTaillard（1993）.以尾巴为例猪油问题在附录A中给出有120个问题，用于不同工作和机器的测试集这些问题由12个不同类别的10个不同的问题集组成Equa-Xt 1XtBe-cr2.Xt-gbestt-1asð10Þ第五，目标函数。表示为Vit1Xit 1-Xitemp11CHFPSO方法在时间复杂度方面并不比经典方法好，并且在每次迭代中使用两种方法中的一种。该方法通过利用两种不同方法的优点，实现了更成功的结果。当所提出的CHFPSO-LS算法的工作性能调度问题中的目标函数的最小化Cmax，也称为makespan，使得高-测试机器利用率，并在最后期限内完成工作全局最佳解决方案在每个周期中跨内核同步。如果作为输入提供的全局最佳解值作为局部搜索的结果得到改善，则算法提供获得的新的全局最佳值作为输出。图1.一、局部搜索策略的说明我i;j我A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报64362×2-算法1.局部搜索算法的伪代码N =作业数操作数= 31：s0 =全局最佳到0.4，并根据迭代次数进行更改。最大速度和加速度值优选分别为0.06708和1.49445。 对于萤火虫算法，Alpha（a），Beta取（B0）、Gamma（c）和随机化参数（e）值分别为0.2，2，1和[-0.5，+0.5]参见图 2、所有粒子都在全局中处理搜索阶段贯穿于相关迭代。结束时2：随机分配为n，k [1，n]，n-k4：循环= 15：while循环迭代限制（n（n-1））do（并行24核）6：p = 17：当p个操作完成时8：随机分配为n，k [1，D]，n-k9：if（p = 1 and insertion_enabled）s2 =insertion（s1，n，k） end if10：if（p = 2 and swap_enabled）s2 = swap（s1，n，k）end if11：if（p = 3 and inversion_enabled）s2 =inversion（s1，n，k） end if12：如果fitness（s2），fitness（s1）更好，则13：p = 114：s1 = s2第15章：其他16：p = p +117：如果结束第18章：结束十九日：loop = loop +1二十：end while第二十一章：如果fitness（s1），fitness（s0）更好，则二十二：全局最佳= s1二十三：end if平均相对差异（ARD）用于比较测试方法[19]。在等式（12）中，Ccal表示Cmax的计算值，CUB表示相关Taillard问题的最佳已知解或上限值。 .C校准品-CUB校准品×100迭代，在局部搜索阶段，通过密集计算获得最佳粒子值。如果在局部搜索结束时获得的最佳值优于输入的最佳值，则它将作为新的最佳值输出并用于下一次迭代。5. 结果从实验中获得的ARD平均值见表2。在大多数问题类型中，使用三重策略获得虽然三重策略的总体平均ARD为1.20，但最接近的互换策略为1.27在倒置策略中为2.54，在插入策略中为3.03图3示出了跨问题使用不同局部搜索策略获得的ARD。使用插入和倒置策略获得的结果更高。很明显，三重策略和互换策略通常会获得较低的ARD。虽然三元组和交换策略的结果相对相似，但三元组策略在大多数问题类型中的结果较低，特别是在较大的问题中。为了检验三重策略是否在统计学上优于其他策略，首先进行Friedman检验，然后进行Wilcoxon符号秩检验。试验结果见表3。根据Friedman检验的结果，使用三重策略获得最低平均秩值该方法的平均互换策略的平均秩值为1.63，与三元策略的秩值非常接近。进行Wilcoxon符号秩检验以检查方法之间的差异是否具有统计学显著性。测试表明，三重策略比基于平均ARDs的倒置和插入策略更成功，ARD¼CUB12毫米拟定方法中使用的参数见表1。在这项研究中，常用的参数值，并在以前的研究中使用粒子群和萤火虫算法。蜂群的规模是100，变量（D）的值由工作数量决定。迭代次数为1000，变量范围在1000到1000之间。对于线性减小的惯性权重，初始值从0.9表1建议方法的参数。一般群规模100D.工作数量迭代次数1000变量下限1000变量上限+1000PSO线性递减惯性权重（w）wmax = 0.9，Wmin = 0.4最大速度系数0.06708加速度系数c1，c2 1.49445FA α（a）0.2β（B0）2γ（c）1随机化器参数（e）[-0.5，+0.5]图二. 该方法的全局和局部搜索的控制A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报6437表2所有策略中的抗逆转录病毒药物。TaillardNXM插入交换逆三重战略01020x50,270,002,710,0002020x101.951.071.131.0703020x203.900.552.160.4604050x50.140.000.000.0005050x103.202.352.842.5406050x204.793.385.803.81070100x50.380.110.380.11080100x101.350.991.010.62090100x206.892.614.492.27100200x102.780.491.100.09110200x206.912.615.782.30120500x203.741.063.121.07总体平均3.031.272.541.20图三.所有问题类型的ARD。表3统计分析的结果。表4误差分析的结果。水平弗里德曼平均秩Wilcoxonp值水平MaeMAPERMSE三重1.46–三重82.501.17128.43交换1.630.44交换90.501.24135.68反演3.130.00反演196.922.45324.94插入3.790.00插入250.832.89401.02交换策略和三重策略之间的差异在统计学上不显著。误差分析结果见表4。平均绝对误差（MAE）、平均绝对百分比误差（MAPE）和均方根误差（RMSE）是性能分析中常用的误差分析指标。接近零的值表示这些指标的结果更好。在我们的研究中，使用三重策略获得了所有三个指标的最低值。图图4显示了三重策略和互换策略的平均ARD之间的差异。这两种方法在第10、20、40和70个问题中得到了最著名的结果。因此，未发现两种方法之间除了这些问题，三重策略在其中五个问题上取得了更好的结果，交换策略在其中三个问题上取得了更好的结果特别是在第70题以后的较大题中，两种策略的差异有利于三重策略。表5显示了通过单独使用三种策略和组合使用三种策略（三重策略），使用CHFPSO方法解决Taillard问题的处理时间。计算过程使用两个英特尔至强E5-2670 v3处理器（共24个内核）所有四种策略的处理时间相对相似。数据表明，方法在处理时间方面彼此没有差异创建主效应和交互作用图，以了解因子及其交互作用对结果的影响由于使用三重策略获得了最低ARD值，因此在这些效应中使用了该策略的结果 图图5显示了作业和机器数量的主效应图。在就业数量方面，ARD值没有趋势然而，随着机器数量的增加，ARD值也会增加。图6显示了工件数和机器因子数之间的相互作用。在五机问题中有一个水平的过程。在10台和20台机器的问题中，随着工件数量从20增加到50，ARD值增加，A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报6438见图4。 按问题类型划分的交换和三重局部搜索策略的ARD值之间的差异。表5跨策略的CPU持续时间（秒）。TaillardNXM插入交换逆三重战略01020x559461858457602020x1055559053957803020x2056460553658204050x570074269673205050x1073275672071806050x20758763746714070100x59819971,020960080100x101,0109981,0551,002090100x201,0271,0561,0991,098100200x102,2262,3142,3272,273110200x202,5182,5522,5702,609120500x2017,39317,39417,80517,714总体平均2,4212,4492,4212,4632,01,51,00,50,02050 100200500510 20图五、作业数（n）和机器数（m）的主效应图nMARD值A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报64394321020 50100n200500见图6。 作业数（n）和机器数（m）的交互作用图。也然而，当作业数超过50时，ARD值减小。六、6. 结论本文研究了如何在使用CHFPSO算法求解流水车间调度问题时确定局部搜索策略。采用交换、插入、求逆以及这三种局部搜索策略的组合等4种局部搜索策略，对Taillard提出的12种不同的Flow-shop调度问题进行了局部搜索策略的影响测试。当采用插入、交换、倒置和三重策略进行局部搜索时，ARD值分别为3.03、1.27、2.54、1.20。首先，计算了四种不同局部搜索策略下的ARD，并对结果进行了比较。研究的主要结论是：在用混沌元启发式方法求解流水车间调度问题时，应采用三元策略或交换策略虽然没有发现统计学上的显着差异之间的交换策略和三重策略的解决方案的质量，有四个原因有利于三重策略。1. 这些方法的处理时间非常相似。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。确认该研究得到了土耳其科学技术研究委员会（TUBITAK）的支持，项目编号为118E355。本文的数值计算部分是在Harran大学高性能计算实验室进行的。作者感谢TUBITAK和Harran HPC的所有支持。附录ATaillard问题集其中一个Taillard流水车间调度问题如下所示。在给定的问题中，在10台不同的机器上处理20个不同的作业的时间被写入。问题集里有12个不同大小的120道题给出的例子是最小的问题.对于Taillard问题集中最大的问题，工作时间是20台机器上的500个工作。2. 三重策略在更高数量的问题组3. 三重策略在较大的问题中产生更好的结果就业数量数量的机器上界下界4. 解决方案的多样性随着三重战略而增加此外，本研究还考察了四种有针对性的局部搜索策略的加工时间。研究结果表明，这些策略在处理时间方面没有太大差异。在这项研究中，CHFPSO方法的性能进行了测试，特别关注置换流水车间调度问题，这是基本的，经典版本的流水车间调度问题。前瞻性研究可以解决其他流水车间调度问题.前瞻性研究还可以调查局部搜索方法对不同元搜索方法的影响。此外，可以使用非混沌元启发式方法进行实验，以观察混沌映射对局部搜索方法的影响。20 10 1582 1448处理时间：74 21 58 4 21 28 58 83 31 61 94 44 97 94 66 6 37 22 99 8328 3 27 61 34 76 64 87 54 98 76 41 70 43 42 79 88 15 49 7289 52 56 13 7 32 32 98 46 60 23 87 7 36 26 85 7 34 36 4860 88 26 58 76 98 29 47 79 26 19 48 95 78 77 90 24 10 85 5554 66 12 57 70 82 99 84 16 41 23 11 68 58 30 5 5 39 58 3192 11 54 97 57 53 65 77 51 36 53 19 54 86 40 56 79 74 24 39 8 88 72 27 22 50 2 49 82 93 96 43 13 60 11 37 91 84 674 18 25 28 95 51 84 18 6 90 69 61 57 5 75 4 38 28 4 8025 15 91 49 56 10 62 70 76 99 58 83 84 64 74 14 18 48 96 8615 84 8 30 95 79 9 91 76 26 42 66 70 91 67 3 98 4 71 62M51020ARD值A. Gümü，sçu，S. Kaya，M.E. Tenekeci等人沙特国王大学学报6440引用Amirghasemi，M.，2021年一种求解置换流水车间调度问题的有效分解随机算法算法。14（4），112. https://doi.org/10.3390/a14040112网站。Arroyo，José Elias Claudio，Armentano，Vinícius Amaral，2005.多目标流水车间调度问题的遗传局部搜索。EUR. J.操作员Res. 167（3），717-738。Aydilek，I_.，2018年萤火虫和粒子群混合优化算法计 算 量 大 的 数 值 问 题 。 应 用 软 件 计 算 66 ， 232-249 。https://doi.org/10.1016/j.asoc.2018.02.025网站。Aydilek，I_.，Tenekeci，E.，Karaçizmeli，I_.，Kaya，S.， Gümüs，çu，A.，2019年。HibritAtes，博采格AlgoritmasınınKaotikHaritalarileI_yiles，tirilmesiRetrievedfrom Harran ÜniversitesiMühendislik Dergisi 4（2），69 -78 https：//dergipark.org.tr/en/pub/humder/issue/47643/560803网站。BurakAydogdu ， Bahar Özyörük ， 2020 ，“”Dinamik e s，zamanliteratopla da g ıtararotalama probleminin çözümüiçin matematiksel model ve sezgisel yakla s ，<$m：Rassal iteratif yerel arama de g i，s ken ko m，s u in i，s algoritması'"，Gazi Üniversistesi Mühendislik Mimarlık Fakültesi Dergisi，Ankara，Türkiye，pp. 563-580“. doi：10.17341/gazimmfd.490179Baykoki，U.S. F.、 &L，S leyen，S. K. （2007年）。SI_METRI_KGEZGI_N满足MI_I_TI_NETKI_N问题B1_ R TEKRARLI YEREL ARAMA B1_ TMASI.（土耳其文）。Teknoloji，10（2），99Benavides，A.J.，Ritt，M.，2015年。置换和非置换流水车间中最小化总完工时间的迭代局部搜索算法。ICAPS，34- 41.Benavides，A.J.，Ritt，M.，2016.非置换流水车间最小化完工时间的两个简单有效算法。Comput.操作。Res. 66，160- 169.崔，W. W.，吕志，Zhou，B.，（1991年），中国地质大学，Li，C.，汉，X.，2016.带不可用约束的非变异Flow Shop调度问题的混合遗传算法。国际计算机积分制造商：1-18Czogalla，J.，芬克·A 2009.无等待流水车间调度问题的进化算法的设计和分析，服务业的元分析，经济学与数学系统讲义624：99-126。Dodu CE ， Ancau M. 一 种 求 解 置 换 流 水 车 间 调 度 问 题 的 禁 忌 搜 索 方 法 。 StudiaUniversitatis Babes-Bolyai ， Informatica. 2020;65 （ 1 ） ： 104-115 。 doi ：10.24193/subbi.2020.1.08。ERDEMDE MI_RTAS，Y.， ÖZDEMI_R，E.，2017年。 D i_nam i_kAraqisRotalamaProblemler i_I_i_nYeni_Bi_r özüm Öneri_si_. Suleyman Demirel大学经济学系。 管理Sci. 22（3），807-823。Framinan，Jose M.，Leisten，Rainer，2008.具完工时间与完工时间准则之多目标迭代贪婪搜寻于流水作业排程。 OR Spectrum 30（4），787-804.高，J.，&陈河，巴西-地（2011年b）。基于NEH的分布式置换流水车间调度问题的启发式算法。技术报告SRE-10-1014。大连海事大学信息科学与技术学院，辽宁大连116026。古普塔，P.，Mehlawat，M.，Mahajan，D.，2018年基于数据挖掘分析的最优冗余下 软 构 件 评 价