混合头脑风暴和延迟接受爬山法求解柔性作业车间调度问题

沙特国王大学学报混合头脑风暴算法和延迟接受爬山法求解柔性作业车间调度问题Malek Alzaqebaha，b，Sana Jawarnehc，Maram Alwohaibia，b，Mutasem K.Alsmadid，放大图片作者：Ibrahim Almarashdehd.穆罕默德a伊玛目Abdulrahman Bin Faisal大学理学院数学系，P.O. Box 1982，31441，City of Dammam，沙特阿拉伯b&阿卜杜勒拉赫曼·本·费萨尔伊玛目大学基础应用科学研究中心，P.O. Box 1982，31441达曼，沙特阿拉伯c沙特阿拉伯达曼，伊玛目Abdulrahman Bin Faisal大学达曼社区学院计算机科学系d沙特阿拉伯达曼，伊玛目阿卜杜勒拉赫曼本费萨尔大学，应用研究和社区服务学院，管理信息系统系e计算机信息系统系，计算机科学和信息技术学院，伊玛目Abdulrahman Bin Faisal大学，1982年邮政信箱，沙特阿拉伯达曼阿提奇莱因福奥文章历史记录：收到2020年2020年8月14日修订2020年9月7日接受2020年9月12日网上发售保留字：头脑风暴优化算法柔性作业车间社区搜索策略延迟接受爬山A B S T R A C T头脑风暴优化算法是一种模拟人类头脑风暴过程的新型群体智能算法本文提出了BSO算法作为解决柔性作业车间调度问题（FJSSP）。为了提高BSO算法的全局搜索能力，提出了一种新的更新策略，以自适应地执行多种选择方法和邻域结构。此外，BSO算法通过对解进行聚类并在每个聚类中独立搜索，具有很好的搜索空间开拓能力，从而导致收敛速度慢。为了增强BSO算法的局部强化能力，克服BSO算法收敛速度慢的缺点，我们在BSO算法中引入了三邻域的延迟接受爬山算法（LAHC）。在FJSSP的四个著名的基准上进行了大量的计算实验，并将BSO算法与所提出的算法的性能进行了比较实验结果表明，该算法优于BSO算法。此外，所提出的方法克服了一些数据集上最著名的算法，并且在其他数据集上与这些算法相当。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍作业车间调度问题（Job-Shop Scheduling Problem，JSSP）是资源分配中的一个常见而又困难的问题，它是指在给定的时间内将各种作业分配给物理资源或机器。许多研究人员已经研究了这个问题，并提出了几个*通讯作者：应用研究和社区服务学院管理信息系统系，伊玛目Abdulrahman BinFaisal大学，P.O. Box 1982，达曼，沙特阿拉伯。电子邮件地址：maafehaid@iau.edu.sa（M. Alzaqebah），sijawarneh@iau.edu.sa（S.Jawarneh），malwohaibi@iau.edu.sa（M. Alwohaibi），mkalsmadi@iau.edu.sa（M.K.Alsmadi），iaalmarashdeh@iau.edu.sa（I.Almarashdeh），rmmohammad@iau.edu.sa（R.Mustafa A. Mohammad）。沙特国王大学负责同行审查算 法 来 解 决 它 （ Hmida 等 人 ， 2010; AitZai 和 Boudhar ， 2013;Golmakani和Namazi，2014; Ahani和Asyabani，2014）。 近年来，为响应当前的市场需求，具有柔性调度系统的制造计划已受到关注。柔性作业车间调度问题（Flexible Job-Shop Scheduling Problem，FJSSP）是传统JSSP的一种推广，即每道工序由多台机器完成，这些机器是从一个候选机器子集中选出的。然而，FJSSP被认为是更有挑战性和复杂性，因为它需要从一组机器中正确地选择机器并平衡机器的工作负载。特别是，当FJSSP被公式化为多目标问题时，其中平衡与最小化完工时间一起被并入多目标函数中（Ho等人， 2007年）。FJSSP分为两个问题。路由子问题是第一个，其中每个操作都分配给一台机器。第二个子问题是排序，它包括为分配的操作定义一个序列-从第一个https://doi.org/10.1016/j.jksuci.2020.09.0041319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comM. Alzaqebah等人沙特国王大学学报2927每台机器上都要踩一下。这一步的目的是实现一个实用的时间表，以尽量减少所需的时间来完成任务。因此，这两个子问题在解决问题时呈现出进一步的复杂性。FJSSP已经被识别为NP-困难问题（Garey等人，1976; Tay和Wibowo，2004; Genova等人， 2015年）。群智能是一种模拟生物种群/系统的集体行为的新方法这些算法具有鲁棒性强、全局搜索能力强等优点。它们适用于复杂问题的解决，因为它们的优化过程可以作为黑盒观察（Zhang等人，2017年 ） 。 常 见 的 SI 算 法 包 括 蚁 群 算 法 （ ACO ） （ Duan 等 人 ，2004）、粒子群优化（PSO）（Sengupta等人，2019），人工鱼群算 法 （ ASFA ） （ Yu 等 人 ， 2005 ） 、 Shuffled Frog LeapingAlgorithm（SFLA）（Eusuff等人， 2006）、人工蜂群（ABC）（Karaboga和Basturk，2007）、蜂群优化算法（Alzaqebah等人，最近，SI算法已经有效地应用于不同的领域，以解决困难的优化问题。例如，Dai和Zhao（2016）使用了ACO，Hashim et al.（2016）应用ABC优化无线传感器网络;Fong等人。（2015）在特征选择中使用PSO解决路径规划问题;Alzaqebah等人。（出版中）提出了自适应蜂群优化算法用于灵活的作业车间调度问题;Qin等人。（2015）使用ASFA; Alzaqebah等人。 使用Bees算法（Alzaqebah等人， 2018）用于解决车辆路径问题; Alzaqebah等人（2020）使用Moth优化算法作为特征选择问题的包装方法;在我们以前的工作中，我们使用SFLA（Zhang等人，2018年）设计局部调光算法时。许多SI算法被设计用于FJSSP求解（Zheng例如，2014年）。在过去的十年中，自然启发的智能通过在数据复杂域中进行优化而受到欢迎。对微生物和动物的合作行为如群集行为的准确表示或者说蜂群，可以在最常见的自然启发的方法中找到。鸟群和鱼群启发了粒子群优化（Shao等人， 2013; Nouiri等人，2017）和蚁群（Wang等人，2017）和人工免疫系统（Bagheri等人，Dorigo andStutzle in Dorigo and Stützle（2004）是群体行为的一个特殊例子。Wang et al.（2017）为FJSSP引入了蚁群优化算法（IACO）的改进版本。他们通过克服基本算法的两个主要限制来改进它。这就是局部最优和计算效率低。改进算法的基础是更新信息素机制所需的步骤数。作为他们的方法的结果，作者指出，一个更好的解决方案，在逻辑计算时间提供了拟议的IACO。头脑风暴优化（Brain Storming Optimization，BSO）是Shi在2011年提出的一种有前途的年轻SI算法（Shi，2011）。它模拟了人类的集体行为，即头脑风暴的过程（Cheng等，2016年）。该算法在提出后被应用于许多领域，如电力系统中设备的最佳设置和位置定位（Jordehi，2015），求解方程组（Mafteiu-Scai，2015）。设计无线传感器网络（Chen等人，2015年），滚动时域控制多无人机编队飞行（邱和段，2014年），并提出了一系列的变体，以提高BSO的性能。Zhan等人（2012）提出了一种简单的分组方法来加速算法，Zhou等人（2012）提出了修改的步长以增强其搜索能力，Yang和ShiYang等人（2015）使用混沌操作来改进个体生成策略，Yang等人（2015）采用集群间和集群内讨论合并来平衡其全局和局部搜索能力。此外，还有一些混合算法。例如Krishnanand等人（2013）将BSO与基于教学的算法混合由于BSO在许多应用中表现良好，我们使用它来解决本工作中描述的FJSSP问题。近年来，BSO被广泛应用于求解连续优化问题。然而，FJSS问题是一个离散（组合）优化问题。因此，BSO用于解决FJSS问题，它没有早熟收敛，这对解决方案的质量有直接的影响。同时，算法的效率还需要进一步提高作为一种基于种群的方法，BSO算法任何局部搜索都会导致快速收敛，但为了避免过早收敛，通过改变邻域结构来控制优化算法内的搜索进度至关重要。这有助于算法摆脱局部最优并增强其局部增强能力（Talbi，2009）。由于它专注于全局搜索，探索的好处是它增加了获得全局优化的机会。一方面，由于开发集中在局部搜索，优化提供了快速收敛。然而，另一方面，其缺点是由于过早收敛和找到全局最优值的机会减少而导致的缓慢优化和缓慢收敛速率。这些事实促使我们的BSO算法和FJSSP的局部搜索算法之间的杂交，以提高收敛行为的调查。本文下面给出了两个1. BSO与新的更新方法（BSO_US），以显示所提出的更新方法对原BSO算法的效果。2. 在新的更新策略和局部搜索LAHC（BSO_US_LAHC）的基础上，实现了BSO更新方法，并将其与局部搜索LAHC算法相结合。第二介绍了FJSSP的基本概念、形式和相关文献，第三节通过讨论参数、初始解和算法来说明所提出的方法。第四节介绍了BSO算法中参数自适应和自适应邻域搜索策略与最著名算法的比较结果。第五部分是论文的结论和未来的研究方向。2. 问题表述考虑到FJSSP的两个复杂任务，FJSSP被认为是一个NP难问题。这些是如下：（i）对机器集合的操作分配的决策;以及（ii）对每台机器上的操作排序的决策（Tay和Wibowo，2004）。FJSSP问题描述如下（Fattahi等人， 2007年）：为了安排一组N独立工作J<$fJig16i6N到一组m台机器M <$fMkg16k6m。我做的每一份工作-得到了一个ni操作序列Oi;j（1≤i≤N;1≤j≤ni），其中作业Ji的第j个操作由Oi;j表示。这个过程是一个disjunc-M. Alzaqebah等人沙特国王大学学报2928动态资源，其中每台机器可以一次执行一个任务每个操作Oi;j都可以在唯一的机器R上处理而不中断，R是从给定的子集Mi;j<$M中选择的。每个作业的不同操作（可能发生再循环）可以是由给定的机器处理对于指定的时间表，sti，j和Ci，j是操作（Oi;j）各自的开始和完成时间。每道工序的加工时间取决于机器本身。 在机器Mk上，Pi，j，k被描述为操作Oi;j的处理时间。我们的目标是制定一个具有最小可能最大完工时间（Cmax）的调度计划，Cmax表示根据预先安排的调度计划处理所有工件所需的时间（1）：一群人提供想法;一群人提供尽可能多样化的想法;以及问题的所有者（客户），他们评估想法并选择最好的一个（Zhang等人， 2011年）。图图2示出了BSO伪码，其中p替换、p一、p一中心和p两中心是0和1之间的阈值。BSO算法通过初始化种群的数量的解决方案（想法），然后，该算法是迭代处理。BSO有两个主要阶段：即聚类和更新解决方案。在聚类阶段，基于K-means算法将种群接下来，最大限度地减少CQCC和C最大值：最大温度Þ ð1Þ选择每个簇中的最佳解来替换中心MaxMax我1：：N我16j6nii;j的集群。这是BSO算法的伪代码在更新阶段，更新种群Ci是作业Ji的完成时间，它等于操作Oi，ni（作业Ji的最后一个操作）的完成 图 1是Makespan等于12时的解表示。对模型施加了以下限制：在零时，所有机器都是可访问的。在零时，所有作业都被释放。每台机器一次只能处理一个操作。一旦机器开始运行，就不能被中断。每一个作业的操作顺序没有考虑机器的设置时间和机器之间的转移时间。3. 提出了一种求解柔性作业车间调度问题的头脑风暴优化算法3.1. BSO算法头脑风暴是一个不带任何偏见或秩序地从一群人那里收集关于某个特定问题的新想法的过程。然后，这些想法被逐一评估和过滤，以选择最佳想法。头脑风暴过程的主要阶段如下（Osborn，2012）：1. 一群人聚集在一起，根据奥斯本的规则提出新的想法2. 许多客户被认为是问题的所有者，每个所有者选择解决问题的最佳想法。3. 在这个阶段，从第二步中选出的想法被用来鼓励更多的想法。一些想法是随机选择的，以鼓励更多的想法。4. 问题的所有者选择在步骤3中确定的一些最好的想法5. 重复步骤2-5，直到问题得到很好的解决。BSO算法是受人类头脑风暴过程启发而提出的一种新的群体智能算法。这一进程包括以下三个贡献者：一个促进者，鼓励Fig. 1.FJSSP解决方案表示。基于预定义的概率，以便通过使用来自四个邻域方法的方法来生成邻域(A) 选择一个随机群集，然后向/从所选群集的中心添加/删除随机(B) 选择一个随机群集，然后向/从所选群集中随机选择的解决方案添加/删除随机(C) 随机选择两个聚类，然后交换两个选定聚类中心的随机(D) 随机选择两个簇，然后从所选的两个簇中交换两个随机选择的解决方案的随机操作。当一个解被更新时，它应该根据它们的适应度值确定是否用生成的邻近解替换原始解3.2. 该算法本节主要讨论了该算法，具体内容如下：首先，通过实例说明了该算 法 的 更 新 方 法 和 邻 域 搜 索 操 作 。其 次 介 绍 了 局 部 搜 索 算 法（LAHC）的伪代码，最后说明了BSO算法与更新算法和局部搜索算法的结合。3.2.1. 建议的更新方法大多数邻域搜索操作都集中在改进单个解这一偏向于增加搜索的利用能力上，而有些邻域操作在搜索过程中不忽略利用重要性的同时也需要得到其他解的帮助来提高搜索的利用能力，因此本文提出了映射到邻域操作上的解选择策略方法，将选择策略和邻域操作的映射随机地映射到每个选择策略和邻域操作，产生4*3方法的组合（4个选择策略和3个邻域操作），这增加了BSO算法的全局和局部搜索。此外，为了实现改变邻域算子提供从局部最优值跳过，并且可以通过改变邻域算子来调整搜索空间，如Drugan和Talbi（2014）和Talbi（2009）中所述。● 溶液选择策略选择要更新的解决方案的想法来自于原始的最终BSO算法利用种群的聚类优势，避免了在相似解中搜索选择策略如下：●●●●●●M. Alzaqebah等人沙特国王大学学报2929图二、BSO算法的伪代码SM 1。选择随机聚类的中心SM 2。从随机选择的群集中选择一个随机解决方案。SM3。从两个随机聚类中选择两个中心SM4。从两个随机聚类中选择两个随机解决方案。图3表明，群体中的解决方案被聚类为两个聚类和每个聚类的中心。● 邻域搜索算子邻域搜索算子描述如下：图三. 代表人口集群。邻域N1，其中工件的选择是随机的，并且每台机器上的操作与其他机器上的操作互换而不破坏约束。如果无法更换，则不考虑更换操作图 4示出了邻域N1的示例，其中随机选择的作业是3，O3，2在时间8-9从M5移动到M2，O3，3从M3移动到M4。邻域N2，其中随机选择操作，并且考虑该操作以与另一操作交换或将其移动到新的随机和可能的位置。图5提供了邻域N2的示例，其中邻域N2将O2，1与O1，1交换，并将O1，3从M1移动到M4。邻域N3，这个邻域是基于关键路径的，至少两个关键操作的序列由同一台机器处理，称为关键路径（Jusic，1992）。关键工序的含义是指在网络的关键路径上的工序关键路径的操作通过由相同资源识别的 图图6用粗体下划线字体表示的关键路径。在N3中，最长路径（关键路径）上的操作被交换或移动到新的随机和可能的位置。图6提供了邻域N3的示例，其中最长路径包含以下操作O2，1 O2，2 O 2，3和O3，3，让随机操作是O 3，3，将操作移动到新的随机位置，让它M4次10M. Alzaqebah等人沙特国王大学学报2930见图4。 以N1为例图五. 以N2为例见图6。 以N3为例前两个邻域结构是一种聚焦策略，通过这种策略，两台特定机器上的作业（或作业集这提供了一定程度的随机探索。一些研究人员证明，当Makespan被认为是因此，组合将是（SM 1，N2），该组合将应用于所选的解决方案;再次，如果解决方案已经改进，则该组合将被插入WL，如下所示：成为目标函数。 这是因为外面的操作关键路径不影响Makespan（参见Brandimarte（1993）、Mastrolilli和Gambardella（2000）、Murovec和Šuhel（2004））。3.2.2. BSO与建议的更新方法在这里，我们解释具有如第3.2.1节中的更新方法的修改的BSO，选择方法和邻域操作被保存到两个列表（分别为SL和NL）中，如下所示：WLSM2，N3SM1，N2：n此过程将一直应用到WL变满，然后将对所选解决方案应用随机组合，请参见图7第24行。改变邻域算子选择列表（SL）列表（NL）SM1 N1SM2 N2SM3 N3SM4在每次迭代中，随机选择选择方法和邻域运算符以生成（SL和NL）的组合，然后将改进解决方案的组合保存在获胜列表（WL）中。例如，在第一次迭代中，假设随机选择方法为SM 2，随机邻域算子为N3，则组合将为（SM 2，N3）。此组合将被应用于解决方案，如果它被改进，它将被插入WL。在第二次迭代中，让随机选择方法选择策略有助于算法跳出局部最优。图7示出了具有所提出的更新策略的BSO算法的伪代码。3.2.3. 采用Late Acceptance Hill Climbing（LAHC）算法的BSOLAHC是Burke和Bykov在Burke et al.（2008）中提出的局部搜索算法。它是一个简单的局部搜索算法，依赖于后期接受爬山方法。大多数局部搜索算法，如阈值接受和模拟退火，利用冷却时间表。延迟接受的策略还采用从搜索历史导出的因此，LAHC算法通过将当前解与来自先前解之前而不是之后的较少次数的迭代的解进行比较来假定解。LAHC算法广泛用于各种应用中。这些问题包括Google机器重新分配问题（Turky等人，2016）;考试M. Alzaqebah等人沙特国王大学学报2931图7.第一次会议。具有更新策略的BSO算法的伪代码时间表（ Alzaqebah 和 Abdullah ， 2014 ），组合交互测试问题（Bazargani 等人， 2018 ）和高中课程（ Fonseca et al. ， 2016年）。LAHC被应用到一个单一的解决方案，它不断改进的该算法将每次 移 动 后 的 适 应 度 值 （ Cmax ） 存 储 在 大 小 为 （ L ） 的 列 表（Cmax=LAHClist）中。质量（Cmax）将新的解决方案与列表上的最后一个解决方案进行比较，然后接受新的改进解决方案。新的LAHC解决方案被接受取决于当前和以前的解决方案之间的比较，从第L步骤获得在验收过程之后，新解决方案的质量将被置于列表的顶部，最后一个将从列表中删除。图8呈现了LAHC的伪码。LAHC算法仅需要一个参数（即，LAHC列表大小（L））。局部搜索（LAHC）适用于每个想法。对于基本的BSO，应用只接受更好的解决方案的邻域搜索。本文还应用了更新方法（3.2.2节），将选择策略和邻域结构传递给基于WL的LAHC算法，见图3。7.第一次会议。因此，图7上的更新被应用于行24至26，如下所示：4. 实验细节4.1. FJSS的数据集使用Java对所提出的算法进行编码，并使用Intel® CoreTM i3处理器计算机和4 GB RAM来实现该算法。本研究考虑了几个问题，详细说明如下：（数据集可在http://www.idsia.ch/上获得~monaldo/fjsp.html）1. BRdata数据集有10个问题集，选自Brandimarte（Brandimarte，1993）。工作量在20到10个之间，机器在4到15个之间1.43和4.10范围的灵活性每一个操作。这些机器彼此不相似。2. BCdata数据集是Barnes和Chambers（1996）的21个问题集。考虑到通过简单地增加一些现有机器，作业车间可以变得灵活，数据是从Fisher（1963）和Lawrence（1984）通过复制机器认识到的三个最具挑战性的经典JSSP（mt10、la24和la40）中产生的。复制的机器的处理时间应该与原始机器相同。作业数量在10到15之间;机器数量在11到18之间，每个操作的灵活性在1.07到1.30之间。这些机器都是一样的.3. Edata数据集由40个问题（la 01-la 40）组成，这些问题的a. 参数整定我们进行了初步的实验，以获得最合适的值的迭代次数，并普及-M. Alzaqebah等人沙特国王大学学报2932图8.第八条。LAHC算法的伪代码见图9。mk01数据集上的BSO聚类。尺寸。我们测试了BSO算法参数的不同值。计算经验证明，以下值对于所有方法的数据集都更有效迭代次数= 200总体规模= 50根据以下方法选择聚类数（Bholowalia和Kumar，2014）。我们为LAHC使用了一些参数，如列表大小和LAHC迭代次数如下：列表大小= 500。迭代次数=作业数 * 计算机数b. 计算结果和比较BSO算法是一种有效的解聚类机制，它将解中相似的数据聚类在一起，并从同一类中的解中这种技术提供了一个全球性的搜索，同时探索人口和避免利用类似的解决方案。图9显示了mk01数据集的群体中的解决方案的聚类，以显示聚类的表1BSO在BR数据上的每种方法的性能。实例N ×m LB BSO BSO_US BSO_US_LAHCCmaxaverage Avg CPU（s）Cmaxaverage Avg CPU（s）Cmaxaverage Avg CPU（s）MK0110 ×6364141.60.814041.50.924041.21.24MK0210 ×6242828.60.852728.30.8726271.11MK0315 ×82042042043.232042043.732042047.84MK0415 ×8486566.63.406466.73.676063.37.97MK0515 ×4168175175.82.04174176.82.341731747.25MK06MK0710 ×1520 ×5331336514465.0145.62.561.856314364.5144.92.871.926114162145.28.934.74MK0820 ×105235235233.685235233.825235237.69MK0920 ×1029931131127.5730730730.7130730782.05MK1020 ×15165211211100.25208208106.34204207203.16●●●●●M. Alzaqebah等人沙特国王大学学报2933≤图9（a）用最佳解替换中心后，图9（b）用最佳解替换中心后一个随机的解决方案表1包含BRdata计算结果的概述。我们将每个算法从1到5的所有表格中。第一列和第二列分别显示问题名称和大小。第三列LB指示所建立的最佳LB粗体值表示使用所有方法找到的最佳值。带下划线的粗体值表示最优解（Cmax = LB），“-”表示数据不可用。在表1中，我们添加了每个实例的平均CPU时间（以秒为单位），平均时间在1到203秒之间。表2FJSS的BSO、BSO_US和BSO_US_LAHC的平均排名（弗里德曼算法排名BSO_US_LAHC1.349BSO_US2.050BSO2.599表3a= 0.05的Holm表秩算法pp-霍尔姆零假设1BSO_US0.00650.1175显著2BSO3.96E-40.0051显著表1显示BSO_US_LAHC算法与BSO和BSO_US算法相比产生最好的结果，其中与其他算法相比达到100%的最佳结果，然后我们得出结论，LAHC方法有助于该算法增强BSO算法的局部搜索。为了显示算法之间的差异，我们应用了Friedman检验，其中两个以上相关样本的显著性也被称为Friedman双向方差分析（Friedman，1940）。该测试用于检测多次测试尝试中的处理差异。该过程涉及将每行（或块）排列在一起，然后考虑按列排列的值。两个以上相依样本的显著性检验中的Friedman检验用于检验零假设。如表2所示，BSO_US_LAHC算法排名第一，其次是BSO_US算法，最后是BSO算法。通过Friedman检验计算的p值该值显示了实验结果之间的显著差异Holm表3显示了算法与最佳算法BSO_US_LAHC之间的显著性。该表具有以下列：第一列是算法的排名，p是p值，Holm是Holm零假设列显示了显著性检验。所有的算法都很重要。因此，平均算法结果接近最佳算法的结果因此，我们使用BSO_US_LAHC与最先进的算法进行下一次比较图10显示了原始BSO算法在Mk01、mt10c1、14a和la03数据集上的行为（从每个类别中选择一个问题）。见图10。BSO算法在Mk01、mt10c1、14a和la03数据集M. Alzaqebah等人沙特国王大学学报2934图10示出了在某些情况下，解决方案如何落入局部最优，其中即使在大量迭代之后也没有实现改进。特别是，图中的前两个图。图10显示了原始BSO算法的缓慢收敛，这清楚地暴露了执行可以帮助算法跳出局部最优的技术的需要。图图11显示了LAHC在Mk01、mt10c1、14a和la03数据集上的行为（从每个类别中选择一个问题）。 从图11我们可以观察到，LAHC通过接受最差的解决方案，帮助算法跳出局部最优。表4比较了BSO_US_LAHC方法与禁忌搜索方法的Cmax和五次运行的平均完工时间算法（TS3）（Boz_ejko等人， 2010年，遗传算法与禁忌搜索和混合元分析（GATS + HM）（Nouri等人， 2018），基于生物地理学的优化（BBO）算法（Rahmati和Zandieh，2012），禁忌搜索和粒子的多智能体系统群优化算法（MATSPSO）（Henchiri和Ennigrou，2013），一种有效的分布式粒子群优化算法（Nouiri等人，2018）和两级PSO算法（Zarrouk等人， 2019年）。从表2可以看出，在Cmax方面，BSO_US_LAHC优于所有其他方法，其中它获得了10个最佳结果中的7个，两级PSO算法获得了6个在10个最佳结果中，一个有效的分布式粒子群算法得到5个好的结果，GATS+ HM、BBO和MATSPSO得到2个好的结果。然后，BSO_US_LAHC算法仍然与最著名的结果相当。表5比较了BSO_US_LAHC方法在C max和平均完工时间方面的结果，这些结果是通过遗传算法禁忌搜索和混合元分析（GATS + HM）（ Nouriet al. ， 2018 ） 和 基 于 生 物 地 理 学 的 优 化 （ BBO ）（Rahmati和Zandieh，2012）。图十一岁 LAHC在Mk01，mt10c1，14a和la03数据集上的行为表4BSO_US_LAHC和最新方法在BR数据上的性能比较。例如N ×mLBBSO_US_LAHCTS3 2010GATS + HM 2018BBO 2012MATSPSO2013PSO 2018两级PSO2019CmaxAvgCmaxAvgCmaxAvgCmaxAvgCmaxAvgCmaxAvgCmaxAvgMK01MK0210 ×610 ×63624402641.2274029––40279340.827.84028––3927––4126––3927––MK03MK04MK0515 ×815 ×815 ×4204481682046017320463.317420465173–––2046417320465.6174.820464173–––20765174–––20765171–––20460173–––MK06MK07MK08MK09MK1010 ×1520 ×520 ×1020 ×1020 ×15331335232991656114152330720462145.252330720468144523326227–––––6514452331122267.0144.0523.0311.8224.866144523310230–––––72154523340299–––––61173523307312–––––62140523307205–––––M. Alzaqebah等人沙特国王大学学报2935表5BSO_US_LAHC和最新方法在BC数据上的性能比较。实例N× m LBBSO_US_LAHC GATS + HM 2018 BBO 2012Cmax平均Cmax平均Cmax平均电话：+86-21- 5555555传真：+86-21 - 5555555MT10xx 10×12 655 918 946.5 918 924.4 939 945.0电话：+86-21 - 5555555传真：+86-21 - 5555555电话：+86-21粤ICP备16038888号-1粤ICP备16016970号-1电话：+86-212019- 10-15 00：00：00 00：0015×12 846 939 940.5 942 953.6 967 967.0setb4xxx 15×13 846 936 940.0 949 958.6 991 991.015×12 845 930 935.5 913 941.8 978 982.0setb4xyz 15×13 838 917 925.0 926 929.8 930 930.515×11 857 914 922.5 927 936.6 959 959.015×12 857 916 923.5 938 946.8 944 950.0seti5x 15× 16 955 1221 1236.0seti5xx 15× 17 955 1213 1235.5seti5xxx 15× 18 955 1206 1241.0seti5xy 15× 17 1149 1165.0seti5xyz 15× 18 955 1140 1147.5seti5c12 15× 16 1027 1181 1204.5seti5cc 15× 17 1143 1159.0从表5中可以观察到，BSO_US_LAHC算法找到了86%的最佳已知解（14个测试实例中的12个）;其中BBO算法仅找到7%（14个测试实例中的1个），GATS + HM算法找到28%（14个测试实例中的BSO_US_LAHC算法，BBO和GATS + HM算法表6比较了BSO_US_LAHC方法在Cmax和Edata上获得的平均完工时间与遗传算法表6BSO_US_LAHC和Edata上最先进方法之间的性能比较。GATS+HM2018N1-10001994MATSLO+2008609609609655655655655550568568503503503503833833765765845845878878866866110611069609601053105311231111892892707707843857M. Alzaqebah等人沙特国王大学学报2936Nouri等人的禁忌搜索和混合元算法（GATS + HM）（2018），Ennigrou 和 Ghédira （ 2008 ） 基 于 禁 忌 搜 索 和 局 部 优 化 方 法（MATSLO+）的多智能体，以及Hurink等人的N1-1000中的禁忌搜索。（1994年）。如表6所示，可以清楚地看到，BSO_US_ LAHC优于所有其他方法，与其他算法相比，它获得了97.5%的最佳结果（20个中的19个），并且它在20个数据测试实例中的16个中获得了下限结果，然而，N1-1000算法在20个中的11个中获得了下限结果，GATS+HM算法获得了10个中的7个，其中它我们的方法的平均CPU时间（以秒为单位）大约在5到200秒之间。如果我们将BCdata和BRdata的结果与Edata中的结果进行比较，我们可以观察到BSO_US_LAHC在所有这些数据中都优于其他算法。此外，BSO_US_LAHC算法已应用于BCdata、BRdata和Edata中的所有实例，而不是与之比较的其他算法5.结论和今后的工作头脑风暴优化（Brain Storming Optimization，BSO）是一种基于种群的算法，它模拟人类头脑风暴的过程，通过收集新的想法并迭代地改进它们直到实现它们，因此，本文提出了一种混合BSO算法，以最小化柔性作业车间调度问题的最大完工时间。提出了一种新的更新策略 ， 通 过 自 适 应 地 采 用 不 同 的 选 择 和 邻 域 方 法 来 增 强 BSO 算 法（ BSO_US ） 的 全 局 搜 索 能 力 。 此 外 ， LAHC 算 法（BSO_US_LAHC）支持局部搜索能力，使算法收敛速度快，克服了原BSO算法收敛速度慢的缺点，并有助于算法跳出局部最优。结果表明，BSO_US和BSO_US_LAHC克服了基本BSO算法的不足.与文献中的其他算法进行了比较，结果表明BSO_US_LAHC算法对FJSP是有效的，并取得了相当的结果。关于未来的工作，这将是感兴趣的investi-门的BSO算法与其他优化问题的这些修改的效果，以审查和测试他们的perfor-曼斯和行为的建议算法在更广泛的域。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。确认这项工作得到了沙特阿拉伯王国伊玛目Abdulrahman Bin Faisal大学科学研究主任的支持，资助代码：2019-157-Sci。引用Hmida，A.B.，Haouari，M.，Huguet，M.J.，洛佩斯，P.，2010年。柔性作业车间调度问题的离散搜索。Comput.操作员Res. 37，2192-2201.AitZai，A.，Boudhar，M.， 2013. 求解阻塞作业车间调度问题的并行分枝定界和并行粒子群算法。 Int. J. Oper. Res. 16，14-37。戈尔马卡尼，HR，Namazi，A.，2014.带预防性维修约束的多路线作业车间调度问题的人工免疫算法。 Int. J. Oper. Res. 19，457-478.Ahani，G.，Asyabani，M.，2014.求解无等待作业车间调度问题的禁忌搜索算法。Int. J.操作员Res. 19，246-258。Ho，N.B.，泰，JC，Lai，E.- M.- K.，2007.一个有效的学习和发展灵活的作业车间调度体系结构。EUR. J. 操作员Res. 179，316-333.Garey，M.R.，约翰逊，D.S.，塞西河，1976.流水车间和作业车间调度的复杂性。数学。歌剧。Res. 1，117-129.泰，JC，Wibowo，D.，2004.一种有效的进化柔性作业车间调度的染色体表示。Evol将军Comput.确认，二一零至二二一Genova，K.，基里洛夫湖，Guliashki，V.，2015.多目标柔性作业车间调度问题求解方法综述。 赛博网 INF. 技术15，3-22。张，T.，赵，X.，An，X.，全，H