混合粒子群与VNS优化机械设备分配与调度问题

智能系统与应用18（2023）200206混合粒子群算法与VNS求解机器共享安排下的机器分配与调度问题Kongkidakhon Worasana，Kanchana Sethananb，*，Rapeepan Pitakaso c，Thitipong Jamrus b，Karn Moonsrid，Paulina Golinska-Dawson ea泰国孔敬大学工商管理和会计学院，孔敬40002b泰国孔敬大学工程学院工业工程系工业系统建模研究组，邮编：40002c乌汶大学工程学院工业工程系物流优化元分析实验室，乌汶，泰国d泰国洛坤府洛坤府洛坤大学工程学院物流工程系e波兹南理工大学工程管理学院，2 Jacka Ryanwskiego Str.，波兹南60-965，波兰A R T I C L EI N FO保留字：资源共享系统排程工具约束阻塞约束机器限制A B S T R A C T本文提出了混合粒子群优化算法和变邻域搜索算法（PSO-VNS）来解决机械设备的分配和调度问题，以帮助种植户扩大生产水平，满足不断增长的需求和利益，提高盈利能力。该问题可以表述为机器设备分配与调度问题（MEASP），它是一类特殊的混合流水车间调度问题（HFS），具有序列相关的准备时间、机器合格性、机器分组、阻塞、工具约束和时间窗|S DST，rcrc，阻塞，工具，Tw|C max）。本研究的目的是最大限度地减少甘蔗种植的总完成时间。提出了一种混合线性规划（MILP）模型来处理小规模问题。采用混合粒子群算法和变邻域搜索算法（PSO-VNS）求解大规模问题。在粒子群优化算法中引入了两个新的速度更新公式和一个新的位置更新公式，并提出了四种邻域策略。实验结果表明，由于新提出的速度和位置更新公式在寻找最优解方面的有效性，所有PSO-VNS方法的性能都优于传统PSO方法，PSO-VNS-6方法的计算时间平均比原始PSO减少58.43%，解的质量平均提高11.71%。1. 介绍甘蔗和制糖业是泰国主要的农业加工业之一，每年收入超过80亿美元，占农业GDP的21%或食品工业GDP的48%（泰国银行，2018年）。从1991年到2022年，泰国糖和相关产品的出口额为11755.93百万美元。目前，泰国农业部门的第三大出口产品，仅次于橡胶和大米，糖是世界上第二大出口产品（美国农业部外国农业服务，2022年）。因此，制糖业是种植园主（约40万户家庭）的就业和创收来源（农业部EX张力，2020年）。根据二零一八年至二零二二年的数据，由于以糖为原料的行业扩张，糖消费量呈逐年上升趋势（USDA，二零二二年）。因此，在此期间对糖的需求持续增加。然而，泰国的制糖业目前正经历着更高的生产成本，包括甘蔗种植和运输成本，以及从入境到出境物流的供应链（Patil，2017）。为了降低这些成本，已经进行了各种研究（参见Neungmatcha et al. 2013，Sethanan和Neungmatcha 2016，Ahmed和Alam 2015）。通过对甘蔗种植供应链成本的分析，发现甘蔗种植供应链的成本包括收割（35%）、整地（21%）、种植（16%）、除草（10%）、施肥（20%）、施肥（20%）、施肥（20%）、施肥（20%）和施肥（20%）。* 通讯作者。电子邮件地址：skanch@kku.ac.th（K.Sethanan）。https://doi.org/10.1016/j.iswa.2023.200206接收日期：2021年12月31日;接收日期：2022年7月12日;接受日期：2023年2月16日在线预订2023年2667-3053/© 2023作者。由Elsevier Ltd.发布。这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表智能系统及其应用杂志主页：www.journals.elsevier.com/intelligent-systems-with-applicationsK. Worasan等人智能系统与应用18（2023）2002062施用（10%）和灌溉（8%）（Dharmawardene，2006年）。甘蔗整地的成本几乎占甘蔗种植总成本的40%。因此，一些研究人员通过开发土壤 制 备 设 备 来 研 究 土 壤 制 备 （ Danok&McCarl ， 1978;BirthalParthasarathy，2002&;Stoof Richards，2015&）。在与甘蔗整地有关的研究中，Monjezi et al. （2015）研究了土地整理和种植，以及使用图形评估和审查技术的甘蔗生产调度操作。然而，有效的甘蔗土壤准备工具的分配和安排可以帮助降低成本，也可以根据农民的需求为他们服务。通常，土壤制备需要各种操作，并且每种操作都需要几种设备类型，以便为植物生长提供最佳环境条件。对于甘蔗田的准备，它是根据地区条件进行的。在这项研究中，考虑了6种操作：操作1：使用动力耙疏松土壤并减少和保持土壤水分，操作2：使用五柄松土器在底土压实中犁，帮助水很好地渗透底土，操作3：使用22/24圆盘耙抑制杂草并切碎老宿根，操作4：使用施肥工具将肥料放入甘蔗槽中，操作5：在甘蔗种植过程中，使用双圆盘打开土壤以尽可能保持土壤中的水分，以及操作6：甘蔗种植机（CP 95/ 100）。然而，为了准备甘蔗地，每次操作都需要拖拉机作为动力源，根据所需的操作，该拖拉机具有可以直接安装在拖拉机上或附接在拖拉机后部的设备。由于同一台拖拉机上可以安装多种类型的设备，因此需要设置时间才能将设备从一种类型切换到另一种类型。此外，有些作业需要相同类型的拖拉机，而其他的需要不同的类型。因此，操作1、4、5和6被认为是机器资格（rcrc）调度。更重要的是，开始下一次操作的时间是有限的，以获得早期根渗透和增殖的最佳土地环境。由于拖拉机和设备成本高，甘蔗种植者获得这些拖拉机和设备的机会有限。田间准备的挑战是如何帮助种植者扩大生产水平以满足不断增长的需求和兴趣，并通过机械化和其他替代方法找到提高劳动效率的方法来增加盈利能力。然而，小规模农户往往面临资金和现金流动方面的限制。考虑了农民之间共享设备的变通方式，因为机械共享使农民能够获得专业机械，从而提高生产效率并降低劳动力成本。因此，共享机器和设备导致合同农业系统中糖厂与农民之间的合作，以及大规模农民与小规模农民之间的合作。然而，养殖机械和设备的成本非常高，并不是每个农场都能负担得起。因此，资源共享至关重要。为了赶上季节，减少甘蔗田准备工作的时间成功的关键是要有耐心。 机械调度的采用增加的管理成本必须通过仔细和频繁的规划来克服（Artz Naeve，2016&），以确保目标甘蔗田在最短的完成时间内完成土地准备。因此，需要安排有效的甘蔗土壤准备，以降低成本，并根据农民的需求为他们服务在本研究中，我们考虑一个机器设备分配与调度问题。这个特殊的问题被表述为一个混合流水车间调度问题，它具有顺序相关的准备时间（SDST）、机器合格性（rcrc）、机器分组（RCRC）、阻塞、工具约束和时间窗口（HFS|S DST，rcrc，阻塞，工具，Tw|C max），目标是最小化完工时间（即，完成时间）。目前，许多研究者在传统的HFS问题的基础上，研究了各种混合流水车间模型. HFS在文献中得到了广泛的研究。它集中在考虑两个单一的问题以及多个约束，例如SDST（参见Sethanan，2001），工具配置（Worasan等人，2018; Worasan等人，2020年）、时间窗（参见Chamnanlor等人，2015年; Yan和Zhang，2015年）、机器合格性（参见Xu等人，2015年）。 2013年，Chamnanlor等人 2013，Bektur and Sarac 2019 ， Worasanet al. 2020 ， Kusoncum et al.2021，Wang et al. 2020，Valizadeh et al. 2020），阻塞约束（见Javadian等人，2010年，Ebrahimi等人， 2014），时间窗和SDST（参见Khare和Agrawal 2019，Li et al. 2021），时间窗口和阻塞约束（参见Sangsawang et al. 2015，Shao等人，2021，Aqil和Allali2021b）、时间窗和机器合格性（参见Yu等人，2020，Zhuang等人，2022）、阻塞约束和SDST（参见Meng等人，2020，Maciel等人，2022，Aqil和Allali 2021a）以及时间窗和分组约束（参见Li和Han，2020，SagKazir&Okul，2020）。在实际的HFS环境中，前面提到的作者受到各种约束和具有不同特征的问题的影响。到目前为止，很少有研究同时考虑各种约束，特别是刀具约束、模块化和机床分组。据我们所知，通过考虑工具分配、SDST、时间窗和阻塞约束，在甘蔗种植中仅进行了一些最近的研究（参见Worasan等人， 2018; Worasan等人，2020年）。由于具有SDST、机器合格性、机器分组、阻塞、工具约束和时间窗口的HFS大多是NP难的，因此很难找到最优解。因此，启发式和Meta启发式方法是潜在的替代考虑和发展。可以看出，已经采用了各种元启发式方法来解决该问题。例如，Chamnanlor et al. （2014）提出了一种基于自调整策略的混合遗传算法，用于求解带时间窗约束的可重入混合流水车间调度问题（RHFSTW）。后来，Wu et al.（2018）使用HPSO算法的六个变体来解决装配流水线调度问题，包括两个阶段和三台机器。de Siqueira等人（2018）和Peng等人（2019）也提出了PSO算法和VNS算法来解决HFS问题。后来，Mar-ichelvam（2020）开发了混合变量邻域搜索（VNS）算法与PSO算法，以解决每个阶段具有相同并行机的多阶段同年，Kong et al.（2020）提出了一种混合SFLA-VNS算法，将Shuffle Frog Leap Al-出租m（SFLA）与Variable Neighborhood Search Algorithm（VNS）相结合，以解决单机和无关并行机上具有非线性处理时间的并行可调度问题最近，李和汉（2020）开发了ABC算法来解决两种不同的机器类型，带时间窗和分组约束的HFS问题。多目标函数是最大完成时间、最大设备工作负载和所有设备的总工作负载的最小化。后来，Shao等人（2021）改进了NEH启发式算法，以解决具有时间窗口、机器资格和阻塞约束的HFS问题。本研究考察了三种不同的阻塞限制以及那些没有阻塞。最近，Zhuang等人（2022）提出了自适应大邻域搜索，以修改具有阻塞，机器资格和可分离序列依赖设置时间的HFS问题，以最小化最大完成时间。同年，Maciel et al. （2022）针对小实例开发了混合整数线性规划，针对大实例开发了混合遗传算法，以解决具有顺序依赖的准备时间和机器阻塞的HFS问题，其中每个阶段的机器与目标函数相同，以最小化完工时间。对文献的进一步回顾表明，许多技术用于处理设备分配和调度。 虽然回顾的研究已经解决了各种约束的混合流水车间调度问题的文献中，几乎没有任何研究，同时考虑现实的约束。据我们所知，还没有人试图考虑以最小化最大完工时间为目标的公式，同时考虑序列相关的准备时间，机器合格性，工件的可加工性，阻塞K. Worasan等人智能系统与应用18（2023）2002063∑∑不模型公式中使用的决策变量如下：M不ismt-你好，、约束，工具约束和时间窗口被考虑。由于为了验证粒子群算法和VNS算法的有效性，本文将粒子群算法和变邻域算法相结合，（续）Wijsmt1，如果在操作s中，在具有工具t的提出了一种基于粒子群优化的VNS算法，第一个职位0;否则。问题所在在粒子群优化算法中引入了两个新的速度更新公式和一个新的位置更新公式，最后一份工作i0smt1如果在操作s中首先在具有工具t的拖拉机m上处理田地i0;否则。并为VNS开发了四种类型的邻域策略本文的其余部分组织如下。第二给出了数学模型。在第3节中，描述了所提出的方法。第四节讨论了计算结果。最后，在第五，总结了本文的研究结论，并提出了未来的研究2. 数学公式本文研究了机器设备分配与调度问题。有m台机器（即，拖拉机）用于土地整理。每个设备或工具t可以直接安装在或附接在机器m的后部。在每个阶段（即，在土地准备的操作中，需要工具，该工具可以是与前一阶段相同的工具或不同的工具。在使用机器m和工具t的每个阶段s，从操作i变为操作j 需要依赖设置时间（SUTjismt）。在每个阶段s，不是所有的工具都能够安装或附接在机器m上。这意味着刀具t仅限于机器m来处理操作i。机器必须被分配和调度以便完成任何作业（即，字段）与特定时间（即，时间窗口是必需的）。因此，考虑了顺序相关的安装时间、机器合格性、工件可调性、阻塞约束、工具约束和时间窗口。有了。具体的问题是制定为一个混合流车间计划，0ismt1如果在操作s中最后在具有工具t的拖拉机m上处理田地i0;否则。如果字段i在操作s更改为工具类型t0时由牵引机m处理，则Y为1;否则为。目标函数最小化E（1）受C ismt=ST ismt+（P ismt. X ismt）+（Y ismt. TICismt）i，s，m，t（2）Ci，（s-1），m′，t′≤STi，s，m，m′，t，t′;s>1（3）Cmax（s-3），m≤ST间期，s，m，t;s=4（4）Cmax（s-1），m≤STismti，s，m，t;s>4（5）Cmaxs，m≥Cmaxs，m，t（6）STismt-Ci，（s-1），m，t≤TWJismtCi，s，m，t（7）我的天Xismt=Cismt-Cjsmt-SUTjismt+L。1-Wijsmt）i，j，s，m，t（8）M T乌林 问题 与 序列 依赖 设置 时代， 机资格、机器分组、分块、工具约束和时间窗口。问题的目标是最小化完工时间|S DST，rcrc，阻塞，工具，Tw|C max）。 参数和Xismt=1i，s（9）m=1t=1∑∑（Xism t. ELIsmti）=1i，s（10）如下指数m=1t=1N TXismt-LastJob0jsmt-∑ ∑Wijsmt=0j，s，m，t（11）i，j字段索引（i，j= 1，2，. . .，N）。s操作索引（即，阶段）（s= 1，2，.. 、.、S）。m，m'拖拉机索引（即，机器）（m，m. .，M）的X FirstJobi=1∑t=1∑Wt=10（12）参数∑ ∑LastJob0jsmt≤1s，m（13）N字段数T模具数量Nt，t. .，T）i0smt-j=1Ijsmt=K. Worasan等人智能系统与应用18（2023）2002064不t=1TNj=1N手术次数M拖拉机数量操作s中字段i的处理时间在拖拉机m上安装工具tSUTjismt使用拖拉机上的工具t设置从场j到场iMELIsmti用于处理操作中的字段i的拖拉机m和工具t的套件L大量TICismt转换到用于加工的牵引机上的工具t的设置时间∑ ∑FirstJobi0smt≤1s，m（14）Yismt=FirstJobi0smti，m;s&t>4（15）Cismt≤Ei，s，m，t（16）TWJ操作s中的字段iismt时间窗控制使用拖拉机m在操作s中操作字段iCismt≤极限切粒i，m，t和s=6（17）限制_裁剪和工具t整地作物种植时限FirstJobi0smt={0，1}i，s，m，t（18）LastJob0jsmt={0，1}j，s，m，t（19）决策变量Cismt在拖拉机m上操作s中的字段i的完成时间STismt在拖拉机m上操作s中的字段i的开始时间EMakespan在拖拉机上完成作业的时间sXismt1，如果田地i在操作s中在拖拉机m上用工具t处理0;否则。（下一栏）Xismt={0，1}i，s，m，t（20）Wijsmt={0，1}i，j，s，m，t（21）Yismt={0，1}i，s，m，t（22）模型中的约束条件（1）旨在最小化完工时间。约束（2）说明在拖拉机作业时田地i的完成时间t=1i=1K. Worasan等人智能系统与应用18（2023）2002065=1111.）的。）⃒⃒.）的 。）X-Xijm与工具t的关系。约束条件（3）保证在具有工具t '的牵引车m'的操作s处的场i约束（4）指示拖拉机m在操作1中完成田地的时间小于或等于拖拉机m在操作4中使用工具t开始田地i的时间。约束条件（5）提出，如果阶段s大于4，则牵引机m在当前操作s中的场的完成时间小于或等于具有工具t的牵引机m在操作s中的场i的开始时间。约束（6）提供了在当前操作s中由牵引机m完成田地的时间大于或等于在操作s中由具有工具t的牵引机m开始田地i的时间。包括约束（7）约束条件（8）与场的顺序有关;因此，在阶段s中，具有工具t的牵引机m对场i的处理时间等于当前场i的完成时间减去前一场j的完成时间。约束（9）保证字段必须由一个3.1.1. 初始种群使用0到1之间的随机实数来生成粒子（i 1，...，K）并评估所有粒子的目标函数。随机密钥最早由Bean（1994）在表示置换时提出.本文使用Norman和Bean（1997）开发的随机编码方法来解决生产问题。编码遵循选择要服务的甘蔗田的优先级确定。尺寸问题的定义是尺寸D，即粒子数K，如图1所示。图1中所示的粒子可以通过使用以下解码过程来解码以获得MEASP的结果解码过程每个粒子都是通过排列粒子每个维度中的值来解码的，这是按升序排列的。每个粒子都被分配了甘蔗田的服务序列。在第一阶段中，每台机器的第一个作业被设置为从上到下选择（{S1，M1，J7}，{S1，M2，J4}）。对于下一个作业，机器选择因子选自阶段中的前一作业的最小完成时间（{S1，M1，一次只能使用一台拖拉机，一次只能使用一个工具约束约束J21（10）保证有一台拖拉机加工田间。牵引车必须在机器合格性约束中，并且工具必须能够7，J1，J6，J8，J9}，{S1，M1，J4，J5，J2，J3，J10}）。在第二阶段，中型机器（M2）具有与第一阶段中的小型机器（M1）（{S2，M1，J7，J1，J6，J8，执行该字段。约束（11）确保，除了最后一个字段，J22由牵引车调度的田地必须紧跟着一个不同的田地。此外，约束（12）确保除了第一个字段之外，在拖拉机上调度的字段必须紧接着一个不同的字段。约束（13）和约束（14）确保拖拉机可以精确地具有第一个和最后一个字段。约束（15）示出了转换到工具t的设置时间的二进制变量。约束条件（16）确保完工时间是在拖拉机m上使用工具t的最终操作s中的场i的完成时间。约束（17）保证在具有工具t的拖拉机m上的最后操作中的田地的完成时间小于或等于作物种植的极限时间。约束（18）到约束（22）是对二进制变量的基本9}，{S2，M2，J4，J5，J2，J3，J10}）。在第三步中，再次使用小型机器，但在开始工作之前必须用新的模具更换（转换到模具的设置时间：TIC）（{S3，M1，J7，J1，J6，J8，J9}，{S3，M2，J4，J5，J2，J3，J10}）。在这项研究中，机器（拖拉机）在田地i和田地j之间行驶所花费的时间被认为是建立时间（SUT jismt），如图所示。 二、3.1.2. 速度更新从当前位置移动到下一个位置的速度是使用Eq. （23）或Eq. （24）或Eq. （25）.vi （ t+1 ） =w （ t ） vi （ t ） +cpr.xpbesti-xi （ t ） ）+cgr 。Xgbesti-xi（t））（ 23）所提出的问题将使用混合粒子群优化和可变邻域搜索（PSO-VNS）来解决，这可以解释如下。3. 该方法在本节中，PSO-VNS方法和案例研究的当前实践如下所示。3.1. 粒子群优化算法（PSO）与变邻域搜索算法（PSO-VNS）PSO-VNS是两种优秀的运动学的结合，即，v i（t+1）=w（t）v i（t）+c p r X pbesti -xi（t）+c g r X gbesti-xi（t）+Ch r（xr（t）-xi（t））v i（t+1）=w（t）v i（t）+c p u X pbesti -X i（t）+c g u X gbesti-Xi（t）+ c l u（X lbesti - X i（t））+c n u（X nbesti -Xi （t））+））+Ch r（xr（t）-xi（t））而FDR由Eq. （26页）。FDR=f（Xi）-f.Xj）;iscin=jX nbesti =Xi（t）;Xi（t）=MAX{FDR}X，lbesti=Xi（t）;Xi（t）=MAX{f（Xi（t））};i ∈P局部（二十四）（二十五）（二十六）粒子群优化（PSO）和可变邻域搜索（VNS）。PSO-VNS算法由5个步骤组成：（1）生成初始解或初始粒子集;（2）更新粒子的速度;（3）更新粒子的位置;（4）使用VNS作为PSO的局部搜索;（5）重复步骤2-4直到满足终止条件。其中Cp，Cg，Cl和Cn是单调递增函数和单调递减函数，本文给出了如下公式，其中Cp，Cl线性递减折 痕 ， 而 Cg 和 Cn 线 性 增 加 。 在 方 程 式 中 ， (27 ） - （ 3 0 ） ，C p m i n ， C g m i n ， C l m i n 和 C n m i n 分 别 是 个 人 学 习 因 子 和社 会 学 习 因 子 的 最 小 值 ， 而 C p m a x ， C g m a x ， ClmaxK. Worasan等人智能系统与应用18（2023）2002066Fig. 1. 所有算法的编码。K. Worasan等人智能系统与应用18（2023）2002067（）。（）+（（）+（.）tmax3Cp最大值-Cp最小值图二. 图1中所有算法的解码。和Cnmax分别是表1中的最大值（Chegini&Bagheri，2018; Ratnaweera等人， 2004年）。的粒子群算法，从而得到一个更好的解决方案。本文中使用的VNS基于邻域的系统性变化，（t max-t）。）tmax在下降阶段中找到局部最优值，在扰动阶段中（二摆脱局部最优（Mladenov i′c&Hansen，1997）。VNS将算法格式指定为d{P1 P2 P3 P4}。设d为Cg（t）=Cg min+tmax-tCtmaxg min- Cg max）（二十八）每个粒子的VNS算法的位置迭代设P1，P2，P3和P4代表技术检索方法的种类。设S为交换执行器，I为插入执行器。Cl（t）=CL mintmax-tCtmaxl max — Cl min ）（29）本文使用了四种VNS算法，包括SSII（AptCommand 0194;1）、ISIS（AptCommand 0194;2）、SSSI（AptCommand 0194;3）、SSIS（AptCommand 0194;4）（Pongchairerks，Cn（t）=Cn mintmax-tCtmaxn min — Cn max ）（30）2016年）。本文中VNS算法的一个例子如图所示。3.第三章。最后，在算法1中示出了所提出的方法PSO-VNS。其中tmax是预定义的最大迭代次数。Xr是新的随机粒子，并且C h定义为等式（1）。（31）.Ch（t）=Chmin+（tmax-t）（Chmin-Chmax）（31）3.1.3. 粒子的位置更新本研究的重要变量被列出并表示为：（1）位置（xi）;（2）速度（vi）;（3）迭代（t）;（4）个人最佳位置（pbesti）和（5）全局最佳解（gbesti）。在每次迭代中，每个粒子都记住给出个人解决方案的位置，只有当它找到一个给出更好解决方案的位置时才调整它。（三十二）Xpbesti（t+1）=Xi（t+1）如果f（Xi（t+1））≤f Xpbesti（t）（32）速度矢量用于指示每个粒子的运动方向。然后它调整位置以用于下一代3.2. 现行做法（CP）在这项研究中，MEASP的调度重点是最小化最大完工时间。这个问题被称为HFS|S DST，rcrc，crack，block，Tool，Tw|C max.农民受到成本上升和资源不足的影响。造成这一问题的主要原因是整地和甘蔗种植，特别是对于没有农业机械（拖拉机和配件）的中小型农场，它们依赖于与大型农场共享资源。实际上，为农民提供的土壤准备服务是以先到先得的方式提供的。本研究针对甘蔗栽培中机械利用率有限、机械需求量大的问题进行研究。因此，MEASP被认为对时间窗限制和资源有限的农民有利。本研究的目标是最大限度地减少完工时间。土壤制备过程包括6个步骤，每个步骤使用不同的工具的类型此外，拖拉机有3种尺寸;小型拖拉机（Mn）根据等式（33）.n1Xi（t+1）=Xi（t）+Vi（t+1）（33）一个新的位置更新公式的基础上的基本思想，让粒子从局部最优逃脱新的位置更新公式由方程。（34）。Xi（t+1）=Xi（t）+rvi（t+1）（34）其中r是0和1之间的随机数3.1.4. 全球最佳更新最好的粒子提供最好的目标，并且通过等式（1）被选择为全局最Cp（t）=Cpmin+K. Worasan等人智能系统与应用18（2023）2002068我我如算法2所示。佳。（35页）。Xgbest（t+1）=ar giminf.Xpbest（t））（35）在步骤1、4、5和6中使用。中型拖拉机（M2）用于步骤2，大型拖拉机（Mn）用于步骤3。土壤改良服务的延迟可能会导致压实，并可能导致另一次田间准备，从而导致更高的成本和浪费的时间损失。该问题的特点如图所示. 四、3.3. 比较算法比较算法来检查所提出的方法的性能。Worasan等人（2020）提出了混合粒子群优化和邻域策略搜索（HPSO-NSS）。该方法用于求解最大收获面积，因此我们必须修改HPSO-NSS来求解最小制作跨度以收获所有所需的面积。求解最小闭合跨度的修改版本为3.1.5. 变邻域搜索在粒子群算法中的应用可变邻域搜索被用作HPSO-NSS中采用的邻域策略有SKIS、KSIK、ISKI和RRR，S代表Swap算法，K代表k-可变移动算法，I代表插入算法，R代表随机K. Worasan等人智能系统与应用18（2023）2002069算法1图3.第三章。PSO-VNS 的 VN S 中 操作符SSII（AptCommand 0194;1）的示例。提出的方法进行了测试与30个测试实例。亲的细节变邻域策略全局局部和邻域粒子群优化算法。输入：f（X），vi（0），pbesti（0），gbesti（0），cp，cg，cl，cn，邻域策略（交换和插入），最大迭代次数（MaxIt），粒子中的位置输出：最佳解决方案开始t=0步骤1：初始化xi（t）;计算xi（t）;while（非终止条件）do对于swarm中的每个粒子xi，所提出的问题如表2所示。本研究设计了三个因素的实验，即场地、机器和阶段。所有实验重复进行三次。对于小尺寸的问题，使用Lingo V.11，并且发现运行时间小于1440 min以找到最优解，而大尺寸的问题使用Lingo V.11的运行时间大于1440 min以找到最优孤子。在小尺寸试验实例中，进行了12次试验实例（S-1至S 12）。Lingo V.11使用的计算时间在30.74到1071.81 s之间。PSO和PSO-VNS使用平均步骤2：使用c r Xx t c r X x t37.64和29.64 s，相对较好地得到了最优解。PSO-VNS-（可选）vi（t+1）=w（t）vi（t）+p（pbesti-i（））+g（gbesti-i（））;（可选）vi（t+1）=w（t）vi（t）+c pr（Xpbesti-xi（t））+c gr（Xgbesti-xi（t））+Ch r（xr（t）-xi（t））（可选）v i（t+1）=w（t）v i（t）+c p u（X pbesti -xi（t））+c p u（X gbesti -xi（t））+c l u（X lbesti - xi（t））+c n u（X nbesti -xi （t））步骤3：更新粒子位置（可选）xi（t+1）=xi（t）+vi（t+ 1）;//（可选）xi（t+1）=xi（t）+ri（t+ 1）(used当当前解决方案在200次迭代中没有改变时）步骤4：应用VNS如果当前迭代小于或等于MaxIt，Poprandi≤0.25：邻域策略的类型AptCommand 0194;10.26Poprandi0.50：邻域策略的类型AptCommand 0194;20.51≤Poprandi0.75：邻域策略的类型AptCommand 0194;3Poprandi<1：邻域策略的类型AptCommand 0194;4<<<端第五：计算xk（t）;1和2满足最优解7次。PSO-VNS-3和PSO-VNS- 4满足最优解9次。PSO-VNS - 5和PSO-VNS-6分别达到最优解10次和12次。PSO - 1到PSO - 4满足最优解5次。粒子群优化算法5和6相对而言达到最优解6次。HPSO-NSS算法10次满足最优在大尺寸测试实例中，实验用22个测试实例（L-1至L-22）进行。相同的计算时间被用作所有算法的终止条件。所提出的方法的有限计算时间设置为45分钟。所提出的方法用于所有测试实例。测试实例的详细信息如表3和表4所示。在这篇文章中，我们提出了原来的PSO和混合PSO-VNS。它们使用不同的速度和位置更新公式。PSO的详细信息和PSO-VNS方法在表4中示出。如果f（xi（t+1））≤f（pbesti（t+ 1））;不1x不1个;为了评估本文提出的启发式算法，步骤6：更新pbesti（+结束;））≤i（+））重点研究：（1）性能的建议步骤7：gbesti（t+1）=argmin{f（pbesti（t+1）），f（pbesti（t+1））}t=t+1 end;输出：最佳解gbest;端在K、S和I之间选择（Worasan等人， 2020年）。4. 计算结果4.1. 测试问题和性能测量通过使用MATLAB软件版本R2018 a对所提出的求解方法进行编码，并且在PC（Intel® Core（TM）i7-6700HQ CPU@2.80 GHz RAM（8 GBRAM））上进行实验。的K. Worasan等人智能系统与应用18（2023）20020610努莫普启发式算法（Pheu），通过将其解与最优解进行比较而获得，以及（2）从当前实践、最近的算法（即，HPSO-NSS）、修改的PSO（即，PSO-2、PSO-3、PSO-4、PSO-5和PSO-6）或传统PSO（即，PSO-1）在应用PSO和VNS算法的混合（即，PSO-VNS-1、PSO-VNS-2、PSO-VNS-3、PSO-VNS-4、PSO-VNS-5和PSO-VNS-6）（见表4）进行了评价，并如下所示：让Pheu=100×100（36）哪里Pheu=所有提出的启发式算法的性能（即，K. Worasan等人智能系统与应用18（2023）20020611=见图4。 问题的特征算法2HPSO-NSS、PSO-1、PSO-2、PSO-3、PSO-4、PSO-5、PSO-6、PSO-VNS-1、PSO-VNS-2、PSO-VNS-3、PSO-VNS-4、PSO-VNS-5和PSO-VNS-6）最优解=最优解的实例数通过数学模型拉舍所有建议的启发式产生最优解K. Worasan等人智能系统与应用18（2023）20020612索尔=表1PSO控制参数的设定。参数设置参数值粒子数最大迭代次数取决于计算时间计算时间（在大规模问题中为45分钟）记录溶液并显示在表5中。提出的方法的停止标准是5分钟的CPU时间，结果如表5所示，而表5结果的统计检验如表6所示。表5的计算结果表明，粒子群算法和矢量神经网络算法在寻找最优解方面的效率超过58.33%。Cp min、Cg min、Cl min、Cnmin，Cn minCp max、Cg max、Cl max、Cnmax，Ch max不个人和社会学习因素的最小值（0.5）个人和社会学习因素的最大值（2.5）而传统的粒子群算法的效率在41.67%~ 50%之间。显然，PSO和VNS的方法优于传统版本的PSO。使用配对t检验进行统计学检验，max预定义的最大迭代次数（500迭代）w（t）0.75让RI=Solcur-Solheu×100（37）哪里RI=Solcur和Solheu之间的相对改进（百分比）Sol cur=从当前实践算法获得的解Solheu 从所有提出的启发式算法获得的解(i.e.、HPSO-NSS、PSO-1、PSO-2、PSO-3、PSO-4、PSO-5、PSO-6、PSO-VNS- 1、PSO-VNS-2、PSO-VNS-3、PSO-VNS-4、PSO-VNS-5和PSO-VNS-6）4.2. 计算结果在本研究中，所有方法均执行5次;最佳解决方案结果见表6。可以看出，PSO-VNS-6优于所有其他提出的方法。此外，所有PSO-VNS算法都优于PSO。这意味着引入VNS可以提高PSO的效率从表7中我们可以看出，使用Eq. (25)在速度更新公式中，最优的是Eqs，与Eqs相比，其解的质量分别提高了1.53%和0.63%。（23）和（24）。使用表3建议方法的详细信息。算法详情Lingo从Lingo v.11BS在预定义时间内从Lingo v.11获得的最佳解决方案当前实践PSO原始粒子群优化问题（PSO-1，PSO-2，PSO-3，PSO-4，PSO-5，PSO-6）PSO-VNS混合PSO和VNS（PSO-VNS-1，PSO-VNS-2，PSO-VNS-3，PSO-VNS-4）在五次运行中，将是该方法的代表性溶液。首先使用Lingo v.11对小规模问题进行实验，直到产生最优解。CPU时间和表2建议问题的详细信息。HPSO-NSS4、PSO-VNS-5、PSO-VNS-6）Worasan等人提出的算法。（2020年）不。工号阶段号MC编号刀具参数设置（min）PismtSUTjismtTICismtTWJismt限制_裁剪S-15323[150，3000]【2,160】[30，50]7,200133,920S-25323[150，3000]【2,160】[30，50]7,200133,920S-35323[150，3000]【2,160】[30，50]7,200133,920S-46454[150，3000]【2,160】[30，50]7,200133,920S-56454[150，3000]【2,160】[30，50]7,200133,920S_67343[150，3000]【2,160】[30，50]7,200133,920S-77343[150，3000]【2,160】[30，50]7,200133,920S-87343[150，3000]【2,160】[30，50]7,200133,920S-910343[150，3000]【2,160】[30，50]7,200133,920S-1010343[150，3000]【2,160】[30，50]7,200133,920S-1110344[150，3000]【2,160】[30，50]7,200133,920S-1210344[150，3000]【2,160】[30，50]7,200133,920L-112363[150，3000]【2,160】[30，50]7,200133,920L-212363[150，3000]【2,160】[30，50]7,200133,920L-312363[150，3000]【2,160】[30，50]7,200133,920L-415484[150，3000]【2,160】[30，50]7,200133,920L-5204