多不可用约束的单机排序问题的改进的可变邻域搜索法

þ可在www.sciencedirect.com上在线获取计算设计与工程学报4（2017）46www.elsevier.com/locate/jcde多不可用约束的单机排序问题：数学模型和改进的变邻域搜索法Maziar Yazdania，n，Seyed Mohammad Khalilia，Mahla Babagolzadehb，Fariborz Jolaia，1a伊朗德黑兰德黑兰大学工程学院工业工程学院b伊朗马什哈德Ferdowsi大学工业工程系接收日期：2016年1月22日;接收日期：2016年7月5日;接受日期：2016年8月9日2016年10月3日在线发布摘要本研究针对多个不可用期与不同交货期之排程问题目标是使工件的最大提前时间和最大拖期时间之为了精确地优化问题，提出了一个数学模型。然而，由于所考虑的问题的大型实例的计算困难，改进的可变邻域搜索（VNS）被开发。在基本的VNS算法中，搜索到全局最优解或近全局最优解的过程是完全随机的，这是该算法的弱点之一。为了解决这个弱点，VNS算法与知识模块相结合。在VNS中，知识模块提取好解的知识并保存在内存中，在搜索过程中将其反馈给算法计算结果表明，该算法是有效的.&2016 计 算 设 计 与 工 程 学 会 。 出 版 社 ： Elsevier 这 是 一 个 在 CC BY-NC- ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：单机调度;可用性约束;变邻域搜索;知识模块1. 介绍通常在调度问题中，假设机器在计划范围内连续可用然而，这种假设在许多实际情况下可能并不正确。例如，由于维护活动[1]、工具更换[2]或故障，机器可能在计划范围内不可用由于机器需要预防性和治疗性维护[3]，操作员需要休息，磨损的部件需要更换。管理者不仅越来越多地面临由于资源的暂时不可用而造成的成本，而且他们还经常关心有关平衡的n通讯作者。传真号码：98 21 88013102。电子邮件地址：Maziyar. ut.ac.ir（M. Yazdani），M.ut.ac.ir（S.M. Khalili），Mahla_golzade@yahoo.com（M.Babagolzadeh）。第1页fjolai.ut.ac.ir由计算设计与工程学会负责进行同行评审。资源的不可获得性和生产。目前，机器不可用性的计算已成为一个很有前途的研究领域。例如，在航空业，定期维护使生产时间减少了约15%[4]。Low等人[5]提到了与航空航天工业相关的两种应用，其中微型钻孔工具需要定期更换，并且机器在此期间不能使用。他们强调了该问题在实际制造环境中的广泛适用性，如计算机中心，数控机床和IC测试行业。Rapine等人[6]考虑了需要辅助资源干预的自动化机器的情况（即，移走工作或添加化学品的操作员），其不可用性阻塞机器。因此，管理人员必须有效地调度他们的机器，以最大限度地提高他们的利润，同时避免计划维护和计划生产之间的冲突。本文研究了具有多个不可用期和不同交货期的http://dx.doi.org/10.1016/j.jcde.2016.08.0012288-4300/2016计算设计与工程学会。&出版社：Elsevier这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4647目标是使工件的最大提前时间和最大拖期之和最小的日期。证明了该问题是强NP-困难的，为了精确优化该问题此外，相对于这个问题的高复杂性，元启发式算法被提出来获得所考虑的问题的最优或接近最优的解决方案。可变邻域搜索（VNS）是Mladenovic[7]首次提出的一种求解复杂组合优化问题的超启发式算法。VNS算法通过系统地改变邻域结构，能够避免局部最优。因此，在过去的十年中，它已被用于解决广泛的复杂优化问题，如图着色[8]，生成树[9]和车间调度[10]。然而，应该提到的是，VNS和其他Meta启发式算法有一些弱点。例如，他们通过利用目标函数或拟合来指导他们的优化算法[11]。这些算法的运算符的随机性是它们的另一个弱点[12]。为了克服这个缺点，最近的研究[13-本文将VNS算法与知识模块相结合，提出了一种基于知识的变邻域搜索算法。本文的结构如下。在下一节中，简要回顾了相关文献。第3节提出了所考虑的问题的数学公式。在第4节中，我们描述了所提出的算法。第5节报告了实验设计。最后一部分是结论和未来的研究方向.2. 文献综述如前所述，本文研究了以工件最大提前期和最大拖期之和最小为目标函数的多不可用期单机排序问题因此，相关文献提供了三个独立的，但复杂的流：单机调度问题的不可用性约束，机器调度问题的重点是最大提前和拖期的工件，和最近的应用VNS在调度问题。2.1. 带不可用性约束的单机排序问题Schmidt[18]对具有不可用性约束的调度规划的文献进行了全面的回顾。Angel-Bello等人[19]提出了一种混合整数规划模型，用于解决具有可用性约束和序列相关设置成本的调度问题。此外，他们提出了一个有效的不等式和一个有 效 的 启 发 式 方 法 ， 以 减 少 计 算 时 间 。 Rustogi 和Strusevich[20]考虑了具有广义位置恶化效应和机器维护的单机问题，其中做出关于可能的作业的顺序和维修活动的数量，以尽量减少总的完工时间。Zammori等人[21]专注于单机调度问题，其中作业和维护任务被联合考虑以找到最优调度。旺和刘[22]提出了一种单机生产调度和预防性维护（PM）的集成优化模型Yin等人[23]考虑了单机上独立且同时可用的作业的调度问题，其中机器具有固定的维护活动。Xu等人[24]考虑了一个维修时间与工作量相关的单机排序问题，目标是最小化总完工时间。Cui等人[25]解决了为具有故障不确定性的单机找到稳健的生产和维护计划的问题，其中生产和维护活动都占用了机器的能力，而生产消耗了机器的可靠性，维护恢复了其可靠性。Luo等人[26]考虑了在单机上调度维护活动和作业的问题，其中维护活动必须在给定的截止日期之前开始，并且维护持续时间随着其开始时间而增加。Hfaiedh等人[27]研究了在固定时间间隔内机器不可用的单机排序问题中，工件不可调度情况下的最大交货时间最小化问题Bai等人[28]研究了一个单机松弛交货期分配（通常称为SLK）调度问题，该问题具有恶化的工件和一个速率修改活动，其中恶化效应表现为工件的加工时间是其序列中开始时间的函数。Vahedi-Nouri等人。[29]考虑了一个具有学习效应和多个可用性约束的单机调度问题，该问题使总完成时间最小化。Li和Zhao[30]研究了具有固定不可用时间间隔的单机排序问题，其中工件的加工时间是其开始时间的线性增函数，每个工件都有一个释放日期。Kacem等人。[31]考虑了具有不可用性约束的单机上早期作业加权数的最大化。他们处理了可起诉和不可起诉的案件。Gu等[32]研究了两个具有新的老化效应的单机排序问题，该老化效应由机器的加工速度决定，在整个排序期内，机器需要进行一次可选的维修，维修的持续时间取决于在它之前的机器的长度。Liu等[33]研究了一个具有周期性维修的单机排序问题，其中目标是最小化拖期工件的数量。Wang[34]提出了一个双目标优化模型，用于解决单机环境下的生产调度和预防性维护问题，该问题具有序列相关的设置时间，而在设置时间内，预防性维护活动应该同时进行。这两个目标是最小化工件的总期望完工时间和最小化期望完工时间的最大值48M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）46机器故障与此同时Chen等人[35]考虑了具有操作员不可用期的单机排序问题。假定的操作员不可用期是作业既不能开始也不能完成的开放时间间隔。Fan等人[36]研究了在单机上生产和交货的集成调度问题，其中由于机器的可用性约束，加工中的他们假设当机器再次可用时，中断的作业可以恢复或重新开始处理。马什卡尼和莫斯利希[37]提出了一种新的定义，称为双峰可用性的单机Nian和Mao[38]针对单机调度问题提出了三种恶化效应模型，同时考虑了作业拒绝、恶化效应和恶化的多维护活动。他们假设，每台机器可能会受到几个维护活动的调度范围内，维护的持续时间取决于其运行时间。Hsu[39]探索了具有老化效应和可选维护活动分配的单机调度。假设工件本研究决定是否及何时将维修作业纳入作业序列，维修作业持续时间为多久，以及如何排程以最小化完工时间。2.2. 最大提前/拖期和排序问题Amin-Nayeri和Moslehi[40]是最早研究如何在单机调度问 题 中 最 小 化 最 大 提 前 和 拖 期 之 和 的 人 。 Tavakkoli-Moghovi等人。[41]通过考虑空闲插入算法研究了相同的目标函数。他们使用各种规模的问题来评估所建议的算法的效率，并提出了与公共截止日期的特殊情况相关的最佳值。之后，Tavakkoli-Moghovi等人[42]应用分支定界算法来解决单机排序问题，以获得目标函数试图最小化最大提前 和拖 期 的 最优 作 业序 列 。 后来 在 另一 篇 论 文中 ，Tavakkoli-Moghovsky和Vasei[43]使用模拟退火和分支定界算法来解决单机调度问题。结果表明，本文提出的模拟退火算法比分枝定界法具有更小的误差和更少的计算时间。Moslehi等人[44]提出了一种具有适当上下界的分枝定界方法来求解两台机器流水车间的调度问题。此外，他们提出了一些有效的引理，以提高算法的效率。在该序列中，将分支定界方法扩展到不相等释放时间的单机排序问题[45]。在后来的工作中，Moslehi等人。[46]通过考虑有用的上界和下界以及新的优势规则，为该问题开发了一种分支定界算法。Nekoie-mehr和Moslehi[47]除了三个优势规则外，还为序列相关设置时间的问题开发了一个有效的下限和上限。Mahnam等人。[48]提出了一种有效的分支和界限，以解决具有不等释放时间和空闲插入的调度问题。此外，他们还提出了两种元启发式算法，即遗传算法和粒子群优化算法，用于大作业规模，所获得的结果表明，所提出的遗传算法更有效。最近，Benmansour等人[49]提出了单机调度问题的混合整数线性模型。他们分两种情况研究这个问题。在第一种情况下，他们认为机器总是可用的，而在第二种情况下，考虑了机器与定期维护相关的2.3. 调度问题在过去的十年中，用元启发式算法解决复杂的优化问题已经受到研究人员的关注[50，51]。变邻域搜索算法是一种元启发式算法，它被广泛地应用于求解各种组合优化和全局优化问题。此外，该算法提供了一个构建算法的框架，该框架应用了邻域变化的思想，以避免局部最小值的陷阱[52]。回顾文献表明，VNS是一种常见的解决方法在调度问题。例如，Liao和Chen[53]提出了一种混合元启发式算法，该算法在VNS中使用禁忌搜索来最小化单机环境中的总加权提前和拖期基尔利克和奥古兹[54]提出了一种通用的VNS算法，用于求解单机排序问题中具有序列相关调整时间的加权Liu和Zhou[55]详细阐述了一种混合元启发式算法，称为基于置换的和谐- VNS，用于解决单机提前/拖期调度问题，其中公共交货期提前指定并作为对进度的限制Arroyo等人[56] 应用VNS算法求解了具有不同交货期窗口和不同安装时间的单机排序问题。他们同时考虑了多个目标，包括最小化总加权提前/拖后和最小化总排队时间。王和唐[57] 提出了一种基于种群的VNS算法来解决单机排序问题 ， 目 标 是 最 小 化 总 加 权 拖 期 。 最 近 ， Laalaoui 和M'Hallah [4]解决了一个单机调度问题，其中工件加权，机器在一个或多个维护期间不可用，并且所有工件共享一个共同的到期日。他们提出了一种基于VNS的启发式算法，其中包含两种机制（链表数据结构和动态阈值接受标准），以加速其向最优解的收敛。M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4649XXXXXXXXXXXXX X.ΣJJXRXX（十）3. 问题描述和模型制定本节将介绍正在研究的问题。在一台机器上可以处理n个工件。机器在整个调度范围内不能连续地用于处理，并且它具有多个固定和预定义的不可用期。Mj是第j个不可用期。如果将任何两个连续的不可用期间之间的作业视为一个批，则可以将计划视为由不可用期间分隔的作业批。该问题的目标是找到一个时间表，使最大提前和拖期的总和最小。本文提出的设想如下：wrA连续辅助变量用于线性化模型。zr用于线性化模型的二进制辅助变量现在，我们介绍模型：最小z 最大工作温度最大工作温度S.T.nk1xirb<$1;8i<$1; 2;r<$1b< $1nk1xirb<$1;8r<$1; 2;1b 1● 处理作业时不会出现错误，也不会抢占作业是不允许的。● 一台机器一次只能处理一项工作xirbpirSb-Fbi¼1r¼ 1-1;8b¼ 1; 2;● 设置时间包括在处理时间内。无无无无无无无● 这个问题中的所有数据都是确定性的。● 作业之间没有优先关系● 两次连续维护活动Xi¼1r¼ 1IRB rM~xi¼1r¼ 1IR- 1B-1 ：;8b¼ 2;.; k1 5它们是相同的。财产1. 问题1j nr_aj ETmax是强NP难的。证据1. 假设在特殊情况下，所有的任务都有一个共同的到期日，并且到期日等于零。因此，最小化最大提前和最大拖期之和成为最小化使-跨度。最小化多不可用条件nk1c½r]Zc½r-1]xirbpi;8r¼1;2;1b 1nk1c½r]Zxirb：piFb-1;8r¼1;2;1b1周期和不可分解的工作（1 nr_pm Cmax）[58]，是强NP-难的。显然，最小化最大提前和最大拖期之和也是强NP困难k1c½r]1b 1k1[xirb~piMaxc½r];1b 1xirb~Fb-1）;开发模型中使用的符号如下：8r¼1; 2;...;nnXc½r]~xirbrSb;8i<$1;2;指数r1nk1i工作索引，i 1/4，t-e¼X Xc~x-d;8i¼ 1; 2;...; n= 10r位置索引，r1/4，b批次索引，b1/4. k 1/4。我我r<$1b< $1半r]国际铁路局参数N在零时需要处理的作业数pi作业i的处理时间。K不可用期间数。di工作到期日i.Sb第b个不可用时段的开始时间Fb 第b个不可用时段的结束时间M一个非常大的数字。决策变量c½r]位置r中计划的作业的完成时间。xirb一个二进制变量，如果作业i按顺序安排在位置r和批次b，则等于1，否则为0。ei工作的早期性i.Emax作业的最大提前量ti工作延误i.Tmax工件的最大拖期yirb如果将作业i的完成时间放在批次b的位置r（用于线性化模型的辅助变量）。nn50M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）46EmaxZei;8i¼ 1; 2;TmaxZti;8i¼ 1; 2;xirbAf0; 1g;i 1; 2;b<$1; 2;c½r]Z0;r<$1;：;n=14eiZ0;i¼ 1;tiZ0;i¼ 1;目标函数（1）使工件的最大提前和拖期之和最小。约束（2）确保每个作业必须被精确地调度到一个批次和一个位置。约束条件（3）确保只有一个作业可以被调度到位置r。每个批次的处理时间受约束条件（4）的限制。约束（5）规定，如果没有作业被定位到一个批次中，则没有作业可以被放置到下一个批次中。M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4651XXXX作业的完成时间由约束（6）约束（10）根据每个工件的完成时间来确定其延迟或提前。约束（11）和（12）分别计算所有作业的最大提前和最大拖期约束（13）我们还假设C[0]和F0为零。所提出的模型是一个非线性混合整数规划模型，其非线性来源于约束条件（8）、（9）和（10）。由于求解非线性数学模型的复杂性，我们提出以下约束。为了去除约束（8）中的非线性项，我们定义：nk1ti-ei<$yirb-di;8i<$1; 2;...; n25r<$1b< $1最终的模型包括（1）最终的模型是一个线性混合整数规划模型，可以通过通用的商业软件包，如GAMS精确求解。然而，由于该问题的NP-难性质，最终的线性规划模型很难在大的情况下解决。因此，开发适当的求解算法来解决大情况下的问题是必不可少的，这将在wr¼.[c½r-1]Xk1xirbpi！-.Xnk1xi rb：.piFb-1！;下一节。1b 11b14. 提出的算法方法8b¼1; 2;其中wr是一个无符号变量。那么我们应该有：wrM~1-zrZ0;8r1;2;wrrM~zr;8r<$1;2;类似地，为了去除约束（9）和（10）中的非线性项，我们定义：yirb<$xirb~p i;8i<$1; 2;那么我们应该有：yirb-M~（1-xirb）c/r];8i<$1; 2;yirbM~1-xirbZc/r];8i/1;2;b<$1; 2;yirbrM~xirb;8i1;2;r<$1; 2;因此，约束（9）和（10）将分别重写为（24）和（25）可变邻域搜索从一个初始解开始，通过一个多嵌套的循环来操纵它，其中核心的一个通过两个主要功能来改变和探索，即所谓的“摇动”和“局部搜索”。外部循环扮演刷新器的角色，重复内部循环，而内部循环执行主要搜索。局部搜索通过局部邻域搜索改进的解决方案，而shake通过切换到另一个局部邻域来分散解决方案。只要内部循环不断改进解决方案，它就会迭代。一旦内部循环完成，外部循环将重复，直到满足终止条件（见图1）。由于邻域结构（NS）在VNS中起着关键作用，因此应该非常严格地选择它以实现有效的VNS。在这里，我们试图提出几个邻域结构，以最快和最简单的方式生成不同的解决方案。建议的邻域结构如下所示。在算法中增加了知识模块，提高了基本VNS的效率。4.1. 解表示青年国际关系委员会rSb;8i<$1;2;ð24Þ一个好的解决方案表示应该是简单的，减少冗余，显示一个准确的解决方案的问题，并允许算法有效地工作 图2示出n52M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）46Fig. 1. 基本VNS的步骤。M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4653作业数为10的问题的解决方案表示的示例。4.2. 知识模块基于知识的优化方法将知识搜索模块和启发式搜索模块集成在一起，第一个模块的任务是从解中获取必要的信息并将其反馈给搜索模块，第二个模块的任务是在广阔的解空间中搜索并找到好的解。在算法中植入知识模块的想法是保留以前解决方案的特征，并将其应用于寻找更合适的解决方案。4.2.1. 存储器存储器阵列的示例如图3所示。内存的所有行都由零值初始化。在搜索中，知识模块识别哪些解是迄今为止获得的最佳解。这些知识存储在内存中，并在搜索过程中返回到VNS，并引导它在包含更好解决方案的空间中搜索。如果找到新的和改进的解决方案，将更新内存。VNS和存储器之间的这种事务继续进行，直到满足停止条件。内存初始化及其更新将在接下来的两节中介绍。4.2.1.1. 内存初始化。在开始时，没有任何知识，内存中的所有块都设置为0.当随机生成初始解并将其视为最佳解时，此解将完全复制到内存中，其余块将设置为0。图4表示针对所考虑的问题的初始化存储器。图二. 示例解决方案表示。图三. 记忆的样本4.2.1.2. 更新记忆。在通过所获得的最佳解进行局部搜索之后更新存储器。图5示出了更新存储器的示例。如果内存已满，通过搜索过程找到新的改进解，则用改进解替换内存中存在的最差解。然而，如果存储器具有空容量，则改进的解决方案位于空行中如图所示，前两个数组与更新前的Memory相关，第三个数组是通过局部搜索获得的改进解，因此内存中存在的较差解被第三个数组替换以更新Memory。4.3. 邻域结构邻域结构，试图将当前解转换为它的一个邻居，以产生新的解决方案，使用以前的。在我们的算法中检查了许多结构，并通过它们选择最佳邻域结构。在本研究中，六个邻域结构LN1至LN6用于局部搜索，三个邻域结构SN1至SN3用于振动过程。其中两个邻域结构是基于知识的，并使用内存来生成新的解决方案。这些程序的详细情况见下文。4.3.1. 邻域结构LN1在这个过程中，我们寻找的可能性改善的目标函数，通过交换职位。两个工作是随机选择的，然后交换（见图。6）。4.3.2. 邻域结构LN2在这个过程中，一个工作是随机删除，然后重新定位到另一个随机选择的位置（见图）。 7）。图五. 一个内存更新的例子。见图6。 LN1的程序。见图4。 内存初始化的示例见图7。 LN2的程序。54M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）46ðÞ半]¼联系我们4.3.3. 邻域结构LN3三个工作是随机选择的，然后他们的位置相互随机改变（见图）。 8）。4.3.4. 邻域结构LN4选择最早的作业，然后与另一个随机选择的作业交换（见图）。 9）。4.3.5. 邻域结构LN5选择拖期最长的作业，然后与另一个随机选择的作业交换（见图1）。 10）。4.3.6. 邻域结构LN6LN 6生成相邻解的步骤如下（见图1）。 11）：步骤1：从内存中随机选择一个作业。步骤2：从当前解决方案中删除选定的作业第3步：将第一步中选择的作业插入当前解决方案中内存的第4步：在第2步中获得的空位置填充当前解决方案中没有见图8。 LN3的程序。25361091847见图9。 LN4的程序。见图10。 LN5的程序。4.3.7. 邻域结构SN1SN 1生成邻居解的步骤如下（见图1）。 12）：步骤1：创建空模板，并随机初始化为0和1。步骤2：将当前解中与二进制字符串中“1”的位置相对应的块复制第3步：随机完成剩余的空块位置。4.3.8. SN2邻域结构本小节使用基于对立的学习（OBL）概念切换到搜索空间的另一部分。基于对立的学习（OBL）的基本概念首先由Tizhoosh在2005年提出作为强化学习的机器智能方案[59]，在很短的时间内，它已被用于增强软计算方法，如人工神经网络[60在很短的时间内，一些其他类型的基于对立的学习被应用到不同的科学领域近年来，OBS已被证明是一种有效的方法，以提高各种元启发式优化方法。所取得的实证结果表明，在广泛的学习和优化领域的反对的概念表现良好。OBL已被用于提高各种元启发式算法的成功率，如蚁群优化[67，68]，模拟退火[69]，和声搜索[70]，基于地理的优化[71]，差分进化[72对这些算法以及其他基于对立的作品的全面回顾可以在[79]中找到。相反，每个变量的量定义为从搜索空间中心到解的镜像点，如下所示[80]。定义1. 如果Xx1;x2;1;2;...; d，它的相对点 Xx1;x2;定义如下（见图13）：x ia ib我x i;i1; 2;据作者所知，大多数关于基于对立学习的论文都是针对连续域问题的最近，人们逐渐意识到，基于对立的学习也可以被修改为用于用于解决离散问题，包括旅行推销员见图11。 LN6的程序。见图12。 SN1的程序。M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4655¼OO222第二图13岁在定义域[a，b]中定义的相对点问题.显然，主要问题是如何定义和评估离散域中的相反数[79]。例如，在某些问题（如TSP）中，试图通过颠倒顺序来利用对立概念确实是一种浪费的尝试。Ergezer等人[71]，定义相反的路径为：定义2. 设n是图中的节点数，P[1，2.n顺时针方向相反的路径PCW如下：见图14。 SN2的程序。PCW<$h1;1n;2;2n;根据上面的等式，如果n是奇数，则不能使用相反的点。如果n是奇数，则在原路径的末端增加一个辅助节点，然后用上式计算出候选解的顺时针相反路径，最后去掉从相反路径末端开始增加的数。根据上述事实，SN2的过程示意性地如下：（图1） 十四、4.3.9. SN3邻域结构SN 3生成邻居解的步骤如下（见图1）。 15）：步骤1：从记忆中选择一个序列步骤2：创建空模板，并为每个单元格分配随机生成的数字0和1步骤3：将步骤1中选择的序列中对应于二进制串中“1”的位置的块复制步骤4：从当前解中删除已经从内存中选择的块，这样就避免了新字符串中块步骤5：通过保留其块序列，用步骤4中剩余的未删除块完成剩余的空块位置。4.4. 强化阶段强化是在当前解决方案中搜索，以构建更接近最优的更好解决方案。所提出的可变邻域搜索使用一个简单的过程作为其强化子算法。在强化阶段，算法交换前两个相邻作业的位置，并评估新序列的拟合值如果新序列的适合度值通过该交换得到改善，则算法接受该交换并重新启动交换子过程。然而，如果这种交换不能改善解的目标函数，则两个作业将移回其原始状态图15. SN3的程序。图16. 强化阶段的结构。位置和交换将应用于接下来的两个相邻作业。强化阶段提供如下：（图。第十六章）4.5. 该算法所提出的VNS算法的结构如图所示。 十七岁建议的VNS是由震动和本地搜索程序。在第一步，确定所需的摇动、局部搜索程序和停止条件。接下来，通过搜索空间随机生成初始解y，然后将其视为最佳解。通过摇动过程SNk从最佳解y生成相邻解y 0。将k的初始值设置为1。在得到y0后，采用局部搜索的方法来提高解的质量. 在每次迭代中，从所有局部搜索中随机选择一个移动。每个局部搜索的选择概率与它在解决方案中做出改进的迭代次数成正比我们将这一特性应用于轮盘赌技术的算法在局部搜索之后，如果y0等于或优于y，则用局部最优y0替换当前最佳解y，然后将k设置为1，并更新存储器。否则k增加1。当k达到3时，k被重置为1。56M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）46：.P.P(AV)MaxB@i¼1CA，3图17. 建议的VNS结构。搜索过程重复N次。重复该算法直到满足停止条件。5. 实验设计和数据设置表1测试问题特征。因子水平职位数量8，10，12，15，20，50，70和100批次数量3处理时间Uniform[1，50]5.1. 数据生成每个实例每次不可用的持续时间（UN）每个实例制服[5，20]8>0Pn10.35和0.5RDD0.2、0.5和0.8随机生产 应该指出的是，基于特殊分布随机生成测试问题函数如表1所示。基本上，测试问题是从文献中采用，如假设中所述，不考虑发布日期基于表1，测试问题的大小从8到100个作业不等处理时间由[1，50][81]内的离散均匀分布生成。每个实例的可用性持续时间（AV）和不可用期（UN）是恒定的，并分别基于可用性和不可用期的Uniform [150，200]和Uniform[ 5，20]生成[81]。截止日期是另一个参数，由Uniform [dmin-λ;d<$dmax]为每个作业生成，其中到期日的相对范围RDD得到的值为0.2、0.5和0.8. 此外，TEF得到0.2、0.35和0.5的值基于上述参数生成了72个测试问题。对于每种规模的测试问题，考虑九个实例。生成实例的名称及其相关参数如表2所示。5.2. 实验结果dmin¼ 第1页-TEFβ;P回合1/1piþn1/1pi=AV转换器~联合国由于没有类似的工作还没有在文献中看到的基准考虑的问题，首先，在这一部分的论文中，所提出的数学模型是¼M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4657且λ <$P_RDD=2 π。TEF是迟到/提前，RDD是通过试验验证了所提出的数学模型的有效性58M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）46~~~~¼表2生成的问题名称及其相关参数。就业人数TEF<$0.2TEF<$0.35TEF<$0.5RDD<$0.5RDD<$0.8RDD<$0.2RDD<$0.5RDD<$0.8RDD<$0.2RDD<$0.5RDD<$0.88公司简介公司简介公司简介JG04公司简介公司简介公司简介公司简介公司简介10公司简介公司简介公司简介公司简介公司简介JG15公司简介公司简介公司简介12公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介15公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介20公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介50公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介70公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介100公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介公司简介问题最后，将该算法的求解结果与数学模型的求解结果进行了比较。应注意的是，通过GAMS优化软件精确求解所提出的数学模型。如第3节所述，在搜索过程中使用记忆模块，并在所提出的算法中开发了密集相位策略，以提高可变邻域搜索的效率。为了检查基于记忆和密集相位制作的邻域结构，我们进行了计算实验，并且在表3中介绍了所获得的结果。从该表中可以看出，考虑了四种不同的可变邻域搜索方法，即VNS I、VNS II、VNS III和VNS IV。在VNS中嵌入了基于记忆的I密集相和两个邻域结构。在VNS II中，所提出的算法在没有密集阶段的情况下运行。在VNS III和VNS IV中，都不考虑具有记忆的邻域结构。然而，在VNS IV强化阶段被认为与VNS II相似。由于停止准则会对运行时间和解的质量产生影响，我们做了一些测试，以达到良好的价值。为了获得停止条件参数的最佳值，我们利用三分之一的不同大小的实例作为测试问题，并评估它们的行为首先，为了调整内循环的停止条件，我们考虑了第四个不同的值;即，1= 2N，N，3=2N，2N，对于它，其中N是作业的数量，并且我们还使用了最大函数求值次数（3000N个目标函数求值，其中N是作业的数量）作为算法的停止条件。根据所得结果，N是内环停止准则的最佳值。此外，结果表明，2000N目标函数评估后，目标函数没有显着变化。实际上，经过2000N次迭代，算法收敛到最优解或接近最优解.因此，我们考虑了2000N作为算法的停止条件，以便在合理的时间内解决问题并获得最佳解。为了进行公平的比较，这些标准用于所有算法。建议VNS使用MATLAB编码。所有的实验都在运行在Intel Core i7处理器上，2 GHz，4 GB RAM。每个试验重复10次并记录这些试验的平均值测试问题的结果，包括目标函数和运行时间，记录在表3中。称为“%误差“的指数定 义 如下 ：%误差C-AAA是通过元启发式算法或GAMS获得的最佳值，C是通过各自的解决方法获得的10次运行值的平均值。考虑列中的“**“表示该解决方案在通过其他方法获得的其他解决方案中是最好的。此外，栏中的此外，“排名”列返回解决方案方法在其他方法中的排名如前所述，通过与GAMS中数学模型精确解的结果进行比较，验证了所提出的如表3所示，对于大多数测试问题，错误指数都很小，并且似乎可以信任所提出的元启发式算法。应该指出的是，在中等规模的测试问题（即，具有15到20个作业的实例）大型测试问题（即，实例与超过20个工作），GAMS未能获得一个解决方案在合理的时间内，元启发式算法被应用到得到的解决方案，可以相信是接近最优。如表3所示，基于平均误差的最佳性能算法是VNS I，平均误差为1.5%。其次是VNS II，平均误差为5.2%。VNS III的性能最差，平均误差为8.1%（见图）。18）。另一方面，根据所提出的算法在其他方法中的排名，VNS I在72个测试问题中的51个中具有最佳性能。第二好的是VNS II，72个测试问题中有27个。VNS IV和VNS III分别在72个测试问题中有25个和25个。最后，基于所实现的结果，可以推断，基于记忆的密集阶段和特别是局部搜索可以提高所提出的算法的性能。可变邻域搜索显著。6. 结论本文研究了工件具有不同交货期，机器具有不同交货期的单机排序问题。M. Yazdani等人/Journal of Computational Design and Engineering 4（2017）4659表3GAMS与VNS模型求解结果的比较GAMSVNS IVNS IIVNS IIIVNS IV一不R%E一不R%E一不R%E一不R%E一不R%E公司简介170人**4.410.0%170人**2.30410.0%170人**2.66410.0%170人**2.49910.00%170人**2.48210.0%公司简介212**9.310.0%212**2.35210.0%212**2.33610.0%212**2.39710.00%212**2.49910.0%公司简介100人**2.910.0%100人**2.17510.0%100人**2.110.0%100人**2.43110.00%100人**2.39710.0%JG04191**610.0%191**2.28810.0%191**2.25610.0%191**2.46510.00%191**2.44810.0%公司简介85岁**0.810.0%85岁 **2.28810.0%85岁 **2.1610.0%85岁 **2.43110.00%85岁 **2.5510.0%公司简介28日**0.210.0%28日 **2.23510.0%28日 **2.2510.0%28日 **2.41410.00%28日 **2.49910.0%公司简介176人**8.910.0%176人**2.27210.0%176人**2.17510.0%176人**2.53310.00%176人**2.39710.0%公司简介152**4.710.0%152**2.38410.0%152**2.20510.0%152**2.39710.00%152**2.5510.0%公司简介62个国家 **1.810.0%62个国家 **2.20510.0%62个国家 **2.1910.0%62个国家 **2.3810.00%62个国家 **2.46510.0%公司简介257**29.310.0%257**2.8410.0%257**2.77410.0%257**2.98210.00%257**3.08710.0%公司简介153名**2.210.0%153名**2.75510.0%153名**2.83110.0%153名**2.96110.00%153名**2.98210.0%公司简介123**12.810.0%123**2.79310.0%123**2.81210.0%123**3.1510.00%123**2.98210.0%公司简介175人**24.510.0%175人**2.9810.0%175人**2.83110.0