智能制造系统中柔性车间调度的一种有效局部搜索算法

张俊杰 ,  吕志鹏 ,  丁俊文 ,  苏宙行 ,  李新宇 ,  高亮

Engineering ›› 2025, Vol. 50 ›› Issue (7) : 117 -127.

PDF (2281KB)
Engineering ›› 2025, Vol. 50 ›› Issue (7) : 117 -127. DOI: 10.1016/j.eng.2024.07.022
研究论文

智能制造系统中柔性车间调度的一种有效局部搜索算法

作者信息 +

An Effective Local Search Algorithm for Flexible Job Shop Scheduling in Intelligent Manufacturing Systems

Author information +
文章历史 +
PDF (2335K)

摘要

柔性作业车间调度问题（flexible job shop scheduling problem, FJSP）作为最经典的调度问题之一，在现代智能制造系统中得到了广泛应用。然而，现有文献中解决FJSP的大多数元启发式方法都是基于种群的进化算法，这些算法复杂且耗时。本文提出了一种快速有效的基于单解的局部搜索算法，其引入一种创新的自适应加权局部搜索（adaptive weighting-based local search, AWLS）来求解FJSP。自适应加权技术为每个工序分配权重，并在搜索过程中自适应地更新这些权重。AWLS结合禁忌搜索策略和自适应加权技术，有效平滑搜索空间的地形，增强算法搜索的多样性。在313个经典基准算例上的计算实验表明，尽管AWLS算法简单，但在解的质量和计算效率方面与最先进的算法相比极具竞争力。具体而言，AWLS在33个算例上改进了文献中之前的最优结果，其余算例除一个外均达到已有最优解。FJSP是一类强非确定性多项式（NP）难问题，近半个世纪以来被广泛研究。在这些经典算例上进行突破是一项艰巨的任务。然而，AWLS仍在8个具有挑战性的算例上实现突破，这些算例之前的最佳纪录是由最先进的元启发式算法和知名的工业求解器所保持。

Abstract

As one of the most classical scheduling problems, flexible job shop scheduling problems (FJSP) find widespread applications in modern intelligent manufacturing systems. However, the majority of meta-heuristic methods for solving FJSP in the literature are population-based evolutionary algorithms, which are complex and time-consuming. In this paper, we propose a fast effective single-solution based local search algorithm with an innovative adaptive weighting-based local search (AWLS) technique for solving FJSP. The adaptive weighting technique assigns weights to each operation and adaptively updates them during the exploration. AWLS integrates a Tabu Search strategy and the adaptive weighting technique to smooth the landscape of the search space and enhance the exploration diversity. Computational experiments on 313 well-known benchmark instances demonstrate that AWLS is highly competitive with state-of-the-art algorithms in terms of both solution quality and computational efficiency, despite of its simplicity. Specifically, AWLS improves the previous best-known results in the literature on 33 instances and match the best-known results on the remaining ones except for only one under the same time limit of up to 300 s. As a strongly non-deterministic polynomia (NP)-hard problem which has been extensively studied for nearly half a century, breaking the records on these classic instances is an arduous task. Nevertheless, AWLS establishes new records on 8 challenging instances whose previous best records were established by a state-of-the-art meta-heuristic algorithm and a famous industrial solver.

关键词

车间调度 / 自适应加权技术 / 智能制造系统

Key words

Job shop scheduling / Adaptive weighting technique / Intelligent manufacturing systems

引用本文

引用格式 ▾
张俊杰,吕志鹏,丁俊文,苏宙行,李新宇,高亮. 智能制造系统中柔性车间调度的一种有效局部搜索算法[J]. 工程（英文）, 2025, 50(7): 117-127 DOI:10.1016/j.eng.2024.07.022

登录浏览全文

4963

注册一个新账户 忘记密码

1 引言

制造业和信息技术的持续进步，使生产格局朝着“多品种、小批量、短周期以及最小化库存”的范式转变[1‒2]。传统的制造系统和控制方法已难以满足新时代的需求。随着德国“工业4.0”和中国“中国制造2025”等国家战略的提出，新一轮工业革命和转型浪潮正在涌现[3]。为提升制造系统的整体能力，需要在灵活性、信息化、数字化和智能化等多个维度进行改进[4]。在这种制造系统中，智能制造已成为推动下一代工业革命的关键技术。

车间调度问题（job shop scheduling problem, JSP）是现代智能制造系统中的一个焦点问题[5]。它代表了运行管理中的一个基本调度挑战，JSP的核心在于为一组给定的工件在特定机器上安排加工顺序，以实现总完成时间或总生产周期的最小化。作为JSP的扩展，柔性作业车间调度问题（flexible job shop scheduling problem, FJSP）是一个更具挑战性的非确定性多项式（NP）难问题，在智能制造中有众多应用[6]。与JSP不同，FJSP为每个工序分配一组特定的候选机器，这些机器的处理时间可能不同。FJSP的优化目标是通过最小化总体作业完成时间来提高制造系统内的运行效率和生产率。

如文献[7]所示，基于种群的进化算法在为FJSP生成高质量解决方案方面已展现出其有效性。然而，这些算法面临的一个重大挑战是管理庞大的种群以及在整个搜索过程中保持多样性，这可能会变得极其耗时。解决这一问题通常需要创新的策略，以在有效平衡探索与开发的同时，高效优化调度问题[8]。因此，本文提出了一种基于单解的局部搜索算法，该算法在当前文献中鲜有研究。基于单解的算法比基于种群的进化算法更高效，因为它们无需管理庞大的种群，也不涉及种群中个体的交叉和变异操作。然而，基于单解的算法的搜索多样性通常不如基于种群的进化算法。为了解决这一问题，我们引入了一种新的自适应加权技术，该技术可以尽可能避免在相同搜索空间中重复搜索，并提高搜索多样性。

本文以下部分的结构为：第2节综述了相关文献；第3节描述了所提出的自适应加权局部搜索（adaptive weighting-based local search, AWLS）算法；第4节将AWLS与最先进算法进行了比较分析；第5节则讨论了AWLS算法关键组成部分的优势；第6节对全文进行总结。

2 文献综述

在解决FJSP方面，广泛使用的主要算法有两类：精确算法和元启发式算法。精确算法依赖于数学建模方法，如拉格朗日松弛法和混合整数线性规划（ILP）。元启发式算法包括启发式和元启发式策略，如基于规则的启发式方法、局部搜索方法、遗传算法等。这些算法通过有效探索搜索解空间来获得近似解。此外，人工智能（AI）技术也被应用于管理复杂的生产调度难题，包括JSP和FJSP [9‒10]。然而，基于AI的算法仍处于起步阶段，而精确算法和元启发式算法因其成熟度和有效性，仍然是解决此类复杂调度问题的主流手段。

大多数使用精确算法解决FJSP的方法都基于ILP。Sawik [11]设计了一个多级ILP模型，用于建模经典FJSP。Gomes等[12]引入了一种新颖的针对离散部件制造业的ILP模型。该模型考虑了并行机器、有限缓冲区以及最小换型影响等因素，有效解决了调度领域的实际挑战。通过利用商业混合整数线性规划（MILP）软件（美国IBM公司），该模型为现实场景提供了高质量的解决方案，展示了该方法在解决作业JSP中的竞争力。Elazeem等[13]从对偶优化角度出发，构建了FJSP原问题的对偶问题，并提出通过原-对偶解之间的差距来评估解的质量。此外，Gomes等[14]还引入了一种专门针对多目标FJSP的新型MILP模型。与典型的柔性作业车间调度模型不同，该方法考虑了作业可以重新进入同一台机器的场景。Yin等[15]阐述了一个新型数学模型，显著降低了车间运行过程中的能源效率和环境影响。Kaplanoğlu [16]提出了一种基于目标导向的创新算法，简化了FJSP的编码结构。具体而言，通过采用面向目标的设计，FJSP的解决方案可以使用单一编码方案进行编码，而不是现有文献中常见的复杂双字符串方案。然而，由于NP难度的计算挑战，当将精确算法应用于大规模生产调度问题时，其性能通常面临严重瓶颈[17]。

大多数用于解决FJSP的元启发式算法都涉及基于种群的算法。Pezzella等[18]提出了一种创新的初始化方法和交叉算子，以增强种群的多样性。Gao等[19]同时优化了两个工序，以进一步细化移动单个工序的局部最优解。他们的遗传算法发现了38个新的更优解。Zhang等[20]将粒子群优化（PSO）和禁忌搜索（TS）策略相结合，以解决FJSP。局部搜索有效地识别了质量更高的局部最优解，而全局搜索则防止陷入局部最优解。PSO将局部搜索方案与全局搜索相结合，以提高搜索效率。Zhou等[21]开发了一种有效的解码策略和混合初始化方法来解决FJSP。他们引入了一种新的种群更新策略，以在搜索过程中保持搜索和多样化之间的平衡。González等[22]确定了一种新的邻域结构和相异性度量方法，以有效解决FJSP。通过对FJSP的基准实例进行实验验证，他们提出的算法优于现有方法。Palacios等[23]提出了一种新的方法，将遗传算法和启发式种子相结合，以求解模糊FJSP。他们的算法通过将遗传算法与TS策略相结合，展现出具有竞争力的性能。Li和Gao [24]提出了一种混合算法，融合了遗传算法的全局探索能力和TS的局部开发能力。这种方法通过策略性编码方法、遗传算子和邻域结构，在各种基准实例中取得了出色的性能。Kemmoé-Tchomté等[25]通过将贪婪随机自适应搜索过程（GRASP）的多样化与多层级进化局部搜索的集约化相结合，改进了增强型贪婪随机自适应搜索过程（GRASP）。他们的算法能够在125个基准实例上获得已知的最佳解。Caldeira和Gnanavelbabu [26]融合了改进的初始化、局部搜索和接受准则，以克服局部最优解并提高解的质量。

近年来，在计算机技术的快速发展和该领域理论研究的推动下，涌现出多种解决FJSP的竞争性算法。Ding等[8]采用了一种新的方法来计算解的距离，并将其与路径重连策略相结合，从而显著提高了解的质量。他们的算法在10个基准实例上打破了世界纪录。Fan等[27]提出了一种创新的混合算法，该算法将Jaya方法与TS相结合，通过实施独特的Jaya算子和定制的局部搜索策略，在各种基准数据集上表现出卓越的稳定性和解质量。Li等[28]提出了一种高效的双阶段进化算法，该算法由领域特定的启发式算法驱动初始种群的生成，第二阶段采用基于帕累托（Pareto）的技术来促进解的收敛。通过在包含20个实例的基准数据集上进行实验，验证了他们算法的有效性。Zhang等[9]创新性地提出了一种基于深度强化学习网络的方法来解决动态FJSP，引入了一种自适应学习技术来增强不同条件下的决策能力。Du等[10]开发了一种深度Q学习网络模型，旨在通过加权方法同时优化总生产周期和能耗，并融入起重机运输阶段等特定特征以提高性能。Xie等[29]将遗传算法的全局搜索能力与禁忌搜索的局部搜索能力相结合，以提高搜索效率。他们将一种新的邻域结构集成到禁忌搜索中，以搜索更大的邻域解空间。其算法在69个分布式柔性作业车间调度基准实例中找到了13个新的上界。Sun等[30]通过优先考虑机器工作负载平衡，并引入染色体编码、交叉算子、变异算子和局部搜索技术的创新策略，增强了一种混合遗传算法，以有效应对FJSP的挑战。Yang等[31]通过引入动态对向学习策略改进了蜻蜓算法，在Brandimate规则生成的大规模柔性作业车间调度实例上获得了高质量解。Alzaqebah等[32]提出了头脑风暴优化算法，通过新的选择方法和邻域结构增强了全局搜索能力。

3 基于自适应加权的局部搜索

为了解决FJSP问题，我们提出了一种AWLS算法。该方法结合了TS策略，以防止算法重复访问最近已探索的解或属性，并采用自适应加权技术来平滑搜索空间的地形。

算法1概述了AWLS的主要框架。首先，AWLS随机生成一个初始可行解（第1行）。这种初始化方法确保了将工序公平且无偏地分配给候选机器。当前解表示为S。然后，将找到的最佳解和上一个解设置为初始解，并初始化权重（第2行和第3行）。接下来，AWLS执行从邻域移动中选择的移动来改进当前解（第4~16行）。

具体而言，利用所提出的邻域评估方法来估计当前解的潜在移动。随后，根据估计的邻域值及其在禁忌列表中的状态，选择一个有前景的移动（第5行）。之后，通过执行有前景的移动获得一个新的当前解（第6行和第7行），同时计算新当前解的总生产周期和关键路径（第8行和第9行）。移动(o*,m,k)表示将操作o*移动到机器m上的位置k。然后，根据执行移动后的总生产周期变化，更新相应工序的权重（第10行）。最后，当新解S优于当前解S*时，S*将更新找到的最佳解（第12~14行）。

3.1 邻域评估与自适应加权技术

FJSP的解表示为文献[22]中使用的(α,π)，其中，α表示每个工序到机器的可行分配，π表示每台机器上的工序序列。在我们的AWLS中，将机器上位置的工序的可行分配表示为(o,m,k)。算法2描述了详细的邻域移动选择过程。首先基于当前解S获得关键路径cp，然后基于两个不同的邻域生成候选邻域移动。本文采用文献[33]提出的k插入邻域(Nk)来生成候选机器重新分配，而采用文献[20]提出的N7邻域来生成同一机器上的候选位置变化。接下来，AWLS尝试将关键工序重新分配到同一机器上的其他可行位置mu（第5行）。利用函数PosiEstimate()来估计非禁忌可行候选位置变化(u,mu,j)，并选择所有可行候选位置中估计总生产周期最小的位置变化（第5~11行）。同样，选择所有候选机器上所有可行位置中估计总生产周期最小的机器重新分配（第12~18行）。最后，选择并返回评估总生产周期最佳的移动（第20行）。

在经典的局部搜索中，通常选择具有最小估计总生产周期的邻域移动。然而，这种方法存在两个缺点：首先，估计总生产周期的方法不准确，因此具有最小估计总生产周期的移动可能无法达到预期结果；其次，贪婪地选择具有最小估计总生产周期的邻域移动，很容易使搜索陷入局部最优。

为了解决这两个问题，我们引入了一种自适应加权策略来改进传统的邻域评估方法。首先，在算法开始时，将所有工序的权重初始化为零。当执行移动工序无法改进当前解时（即导致后续评估中最大完工时间增大），则增加此工序的权重。这样，算法在后续迭代中会避免再次选择涉及该工序的邻域移动，从而规避可能导致性能下降的操作。此外，当搜索陷入局部最优解时，对未改进当前解的移动所涉及的工序进行加权，可以平滑搜索空间的地形并提高搜索效率。

假设u和v是两种不同的工序，且如图1所示，在将u移动到后面后，新的总生产周期估计为

makespanu,v=maxRu,vi+pi+Qu,vi+Zi,   ∀i∈{L1,…,Lg,v,u}

式中，pi表示工序i的加工时间。Ru,v和Qu,v使用参考文献[22]中介绍的方法进行计算。Lg 表示工序之后的第g个工序u。在公式（1）中，Zi被视为自适应附加处理时间，其值为其累积权重的一定比例，并由公式（2）定义。

Zi=max1-tirand(1, γ)×wi,0

式中，wi表示工序i的累积权重；ti表示工序i的闲置计数，即工序i最近一次成为关键工序时的局部搜索迭代次数。ti和wi分别初始化为+∞和0，并在每次迭代中进行更新（见第3.2节）。具体而言，工序i的闲置计数ti与参数γ共同决定累积权重在计算工序i的附加加工时间Zi中所占的比例。在式（2）中，rand(1,γ)表示1~ γ之间的随机整数，用于增强算法的随机性并提高搜索多样性。类似地，机器重分配的完工时间估计也可按相同方式计算。

对于图1所示的插入邻域移动，处理序列中工序的估计值计算如下：

Ru,vL1=maxRJPL1+pJPL1,RMPu+pMPu

式中，JPi和MPi分别表示工序i的作业前导工序和机器前导工序。Ri和Qi分别是从起始节点到工序i的最长路径和从工序i到结束节点的最长路径。

对于其他工序i∈{L2,…,Lg,v}：

Ru,vi=maxRJPi+pJPi,Ru,vMPi+pMPi

对于工序u：

Ru,vu=maxRJPu+pJPu,Ru,vv+pv

相应的Qu,v值计算方法如下。

Qu,vu=maxQJSu+pJSu,QMSv+pMSv

式中，JSi和MSi分别表示工序i的作业后续工序和机器后续工序i。

Qu,vv=maxQJSv+pJSv,   Qu,vu+pu

对于其他工序i∈{Lg,…,L1}

Qu,vi=maxQJSi+pJSi,Qu,vMSi+pMSi

AWLS算法从非禁忌候选动作中执行最优移动，并在禁忌期内避免执行相同的移动[34]。然而，过长的禁忌期会导致计算时间过长，并可能错过有潜力的优质解。

在AWLS中，wi记录搜索过程中工序i的累积权重，用于防止局部搜索返回到之前访问过的解。然而，直接将累积权重作为估计邻域移动时每个工序的额外处理时间，会极大地改变搜索空间的结构。因此，使用空闲计数ti来自适应地调整累积权重对邻域评估的影响。

从宏观角度来看，工序空闲次数ti的增加表明该工序在很长一段时间内并未处于关键路径上，这意味着当前解决方案与之前访问过的解决方案之间可能存在显著差异。因此，工序i的累积权重对邻域估计的影响应较小。

此外，TS通过利用禁忌表和禁忌期限，可以防止搜索重复最近访问过的解或属性。另外，自适应加权技术可以通过更平滑地自适应调整目标函数值，帮助搜索跳出局部最优。因此，它可以被视为一种长期记忆策略，以防止搜索重复访问过的解或属性。总的来说，这两种机制在跳出局部最优方面具有互补性。因此，我们的AWLS结合了禁忌搜索和自适应加权技术，以增强搜索的多样化能力。

3.2 权重更新过程

众所周知，权重更新是基于加权的算法中最核心的组成部分之一。在所提出的权重更新过程（算法3）中，AWLS通过改变累积权重和空闲计数的取值来自适应地调整搜索空间的地形，目的是平滑搜索空间的地形。具体而言，权重更新过程在第1~7行中给出，而空闲计数如何更新则在第8~21行中描述。权重和空闲计数的重置在第22~27行中给出。

如果在执行一次移动工序（第1~7行）后，当前解未得到改进，则当移动工序o*的空闲计数超过β时，其权重重置为0（第2~3行）。这表明工序o*已长时间未被移动。否则，其权重增加1（第4~5行）。

然后，将更新相应工序的空闲计数。一方面，当当前解不如上一个解时，根据γ和θ更新被移动工序的空闲计数（第8~13行）。与权重更新类似，如果被移动工序的空闲计数超过γ，则将其空闲计数减少到γ（第10行）。否则，每次将其空闲计数减少θ（第12行）。然后，除关键工序和被移动工序之外的其他工序的空闲计数均加一（第14~15行），而关键工序的空闲计数保持不变。在后一种情况下，它保持累积权重对搜索的影响，并防止算法重复最近访问的解或属性。另一方面，当当前解优于上一个解时，所有工序的空闲计数均加一，从而减少权重对搜索的影响（第18~20行）。

当获得新的最优解时，所有工序的权重和空闲计数分别重置为+∞和0（第22~27行）。在这种情况下，Z(o)等于零，估计的总生产周期变为先前研究中使用的原始估计值。换言之，加权机制被暂时禁用。如果获得了新的最优解，则意味着AWLS可能会探索新的区域。因此，先前搜索区域中使用的权重可能不适用于新的区域，需要重置权重和空闲计数。

一般来说，当搜索陷入停滞状态时，会增大已移动工序的累积权重，同时减少关键工序的空闲计数（第5行和第9~13行），这可以平滑搜索空间的地形并提高搜索效率。相反，当可以改进总生产周期时，所有工序的空闲计数会增加，工序累积权重对搜索的影响会减小（第18~20行）。最后，一旦发现新的最优解，所有工序的累积权重和空闲计数都会重置（第23~26行）。

4 结果与比较

4.1 实验实例与参数设置

AWLS是用C++实现的，并在运行于Intel Xeon E5-2698处理器上的Windows操作系统执行。在进行实验之前，我们使用调参软件Geatpy（中国）来优化算法参数。Geatpy对随机选择的40个经典FJSP实例进行了参数调优，将γ、β和θ的范围分别设置为[1,200]、[1,5000]和[1,50]。在调参过程中，每个参数都使用差分进化算法，在定义范围内随机初始化一个值。根据Geatpy的结果，我们选择了γ=40、β=500和θ=5作为在本实验中表现最佳的整体性能参数（表1）。

为了评估AWLS的性能，我们在文献中常用的四个著名基准数据集上进行了实验：DPdata [35]、BCdata [36]、BRdata [6]和HUdata [37]。对于每个实例，我们执行了20次独立运行。BCdata、BRdata、DPdata和HUdata基准数据集的截止时间限制分别设置为90 s、90 s、300 s和300 s。此外，我们还提供了其与师徒进化算法（master-apprentice evolutionary, MAE）的比较结果，该算法采用了1 h的截止时间，这与MAE中使用的设置一致。

AWLS与当前最先进的元启发式算法进行了比较，包括带路径重连的散点搜索（SSPR）[22]、混合遗传标签搜索（HGTS）[23]、混合遗传算法（HA）[24]、多起点多层级进化局部搜索（GRASP-mELS）[25]、改进的Jaya算法（IJA）[26]、MAE [8]以及混合Jaya算法（HJ）[27]，据我们所知，这些算法是解决FJSP的最佳算法。在比较中，采用与MAE相同的方法，将计算时间标准化为与计算机无关的中央处理器时间（CI-CPU）。具体而言，HJ、MAE、IJA、GRASP-mELS、SSPR、HA和HGTS的速度因子分别设置为1.07、1.00、0.63、1.09、0.75、0.50和0.63，而我们算法的速度因子设置为1。遵循该领域的标准做法，使用以下指标对算法进行了比较：平均相对百分比偏差（RPD），定义为RPD=100×(g-LB)/LB，其中，g表示20次独立运行中找到的最佳解或平均总生产周期，LB表示下界。此外，基于20次独立运行计算平均运行时间（t）。

4.2 与元启发式算法的比较

表2至表5展示了本文的算法与参考算法（SSPR、HGTS、HA、GRASP-mELS、IJA、MAE和HJ）在313个基准实例上的比较结果。“Ins.”列表示实例，UB表示该实例的上界，带*标记的LB表示最优解的总生产周期。

表2详细列出了对BCdata基准数据集进行的全面比较分析以及参考元启发式算法的结果。AWLS的平均相对百分比偏差（RPD）为0.06，运行时间为17.71，均低于SSPR、GRASP-mELS和MAE。此外，AWLS的最佳值和平均值均优于HGTS和HA，分别在7个和5个实例上表现出更优的性能。HJ的最佳RPD值与AWLS相当，但计算时间却比AWLS更长。此外，AWLS在该数据集中的所有实例上均达到了下界。

在表3中，AWLS的平均值（RPD为0.58，CI-CPU为6.89）优于所有其他参考算法。这一观察结果表明，与其他参考算法相比，AWLS能够在更短的时间内获得更优的解决方案。此外，尽管AWLS的计算时间略长于HA，但其获得的最优PRD值更小。至于MAE，其计算时间几乎是AWLS的两倍，而其平均RPD却大于AWLS。

在表4中，AWLS展示了其最佳RPD和平均RPD，分别为0.94和1.12，均小于SSPR和HGTS的对应值。当算法的该指标值较小时，表明其求解质量更高。与SSPR和HGTS相比，AWLS能够获得更优的解。尽管与HA、GRASP-mELS、IJA和MAE相比，AWLS可能需要略多的计算时间，但它获得了最小的最佳值和平均值RPD（其值分别为0.94和1.12）。此外，在实例16a中，AWLS仅仅在300 s内将makespan从2231优化为2228，创下了新的世界纪录。

从表5中可以明显看出，与其他参考算法相比，AWLS在所有实例中均取得了更小的最佳RPD和平均RPD值，同时计算时间更短。特别是，AWLS分别在edata、rdata和vdata基准测试集的4‒5‒8、18‒19‒14和13‒8‒3实例中打破了由GRASP-mELS、SSPR和MAE建立的世界纪录。综上所述，在不超过300 s的时间限制下，AWLS在178个基准测试实例中，分别在47个、52个和33个实例中改进了SSPR、GRASP-mELS和MAE获得的最优结果。

4.3 与精确算法的比较

AWLS与最先进的精确算法[大邻域搜索（LNS）+故障导向搜索（FDS）（美国IBM公司）] [38]进行了比较，后者依赖于约束编程。LNS+FDS是约束编程优化器（constraint programming optimizer, CPO）中自动搜索机制的核心。值得注意的是，CPO已在多种调度基准测试（如JSP和FJSP）中成功进行了评估。

CPO的截止时间设置为8 h，而AWLS的截止时间设置为1 h。在总共313个实例中，AWLS在46个实例上优于CPO，在263个实例上与CPO相当，在4个实例上不如CPO。表6给出了AWLS表现出的46个改进实例的结果。

4.4 与商业求解器的比较

著名的商业求解器Quintiq在119个实例中创下了新的世界纪录[8]。然而，值得注意的是，Quintiq并未透露其算法的任何细节或取得这些结果的时间限制。

在本文对AWLS和Quintiq的比较中，实验结果表明，MAE在14个实例上优于Quintiq，在93个实例上与Quintiq结果相当，在121个实例中有14个实例不如Quintiq。AWLS获得了8项新的世界纪录，相关结果列于表7中，供后续比较。AWLS的截止时间为1 h，而Quintiq未披露其截止时间限制。

表7中，“UB Reference”列标识了建立新世界纪录的算法。标签“[Q]”“[CPO]”和“[MAE]”分别表示Quintiq方法、CPO和MAE。最后，表8对AWLS（时间限制为1 h）[39]与元启发式MAE、精确算法CPO和工业求解器Quintiq进行了全面比较。在该表中，<、=和>列分别表示AWLS取得优于、等于和劣于其他算法的实例数量。值得注意的是，AWLS与MAE获得的所有世界纪录都相匹配。

5 讨论与分析

为了评估自适应加权技术的优点，我们在BCdata基准测试中的四个最具挑战性的实例上进行了实验。通过分别在估计总生产周期时去除空闲计数[WLS, Zi=wi]的影响和停用自适应加权技术（LS，即标准TS算法），生成了AWLS的几个简化变体。此外，本研究还对我们的AWLS算法与MAE算法进行了对比实验，MAE算法目前被认为是FJSP中表现最佳的元启发式算法。本研究还测试了MAE的扩展版本（MAE_AW），其中，MAE中的LS程序被替换为使用我们的自适应加权技术的LS。所有参考算法都从相同的初始解开始，以确保公平比较。图2描绘了AWLS、WLS、LS、MAE_AW和MAE在搜索过程中总生产周期的演变趋势。每个点(x,y)表示在第x次迭代时已知最佳解的总生产周期为y。曲线周围的阴影区域表示数据的置信区间（平均值±标准差）。

从图2中可以看出，AWLS和加权局部搜索（WLS）能够快速获得更好的解，表现优于局部搜索（LS）。相比之下，WLS陷入局部最优解，在多次迭代后仍无法获得更好的解。然而，随着搜索进程的推进，AWLS始终能提高解的质量。关于MAE和MAE_AW，MAE_AW比MAE能更快地获得更好的解，这凸显了将AWLS集成到多种算法中以获得竞争性结果的有效性。AWLS比MAE_AW收敛更快，这可能由于MAE_AW是基于种群的算法，管理种群的过程耗时较长。这些发现强调了空闲计数和自适应加权技术在AWLS的有效性和效率方面都至关重要。

此外，我们对所有基准测试的结果进行了统计显著性检验（Wilcoxon符号秩检验）。表9给出了四个基准测试的p值结果。在0.05的显著性水平下，除BRdata外，AWLS与两个参考算法GRASP-mELS和SSPR在所有基准测试中均存在显著差异。此外，在BCdata、DPdata、edata和rdata上，AWLS与MAE之间存在显著差异，而在BRdata和vdata上，AWLS与MAE之间未发现存在显著差异。这可能是因为BRdata和vdata集中的大多数实例都易于求解。

6 结论

在本文中，我们提出了一种新的AWLS算法，用于解决FJSP。此自适应加权技术根据空闲计数和累积权重为每个工序分配权重，在总生产周期估计中将此权重视为额外的自适应处理时间，从而平滑搜索空间的地形。在313个公共基准实例上进行实验，结果表明，AWLS优于大多数最先进的算法。此外，AWLS刷新了8个具有挑战性的实例的世界纪录。因此，将所提出的策略集成到解决其他具有挑战性的调度问题中，是未来研究的一个方向。

参考文献

原文顺序 | 出版日期 | 本文引用
[1]

Chen B, Wan J, Shu L, Li P, Mukherjee M, Yin B. Smart factory of industry 4.0: key technologies, application case, and challenges. IEEE Access 2018;6:6505‒19. . 10.1109/access.2017.2783682
[2]

Wang B, Tao F, Fang X, Liu C, Liu Y, Freiheit T. Smart manufacturing and intelligent manufacturing: a comparative review. Engineering 2021;7 (6):738‒57. . 10.1016/j.eng.2020.07.017
[3]

Li B, Hou B, Yu W, Lu X, Yang C. Applications of artificial intelligence in intelligent manufacturing: a review. Frontiers Inf Technol Electronic Eng 2017;18(1):86‒96. . 10.1631/fitee.1601885
[4]

Yang C, Liao F, Lan S, Wang L, Shen W, Hang G. Flexible resource scheduling for software-defined cloud manufacturing with edge computing. Engineering 2023;22:60‒70. . 10.1016/j.eng.2021.08.022
[5]

Garey MR, Johnson DS, Sethi R. The complexity of flowshop and jobshop scheduling. Math Oper Res 1976;1(2):97‒196. . 10.1287/moor.1.2.117
[6]

Brandimarte P. Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 1993;41(3):157‒83. . 10.1007/bf02023073
[7]

Chaudhry IA, Khan AA. A research survey: review of flexible job shop scheduling techniques. Int Trans Oper Res 2016;23(3):551‒91. . 10.1111/itor.12199
[8]

Ding J, Lü Z, Li C, Shen L, Xu L, Glover F . et al . A two-individual based evolutionary algorithm for the flexible job shop scheduling problem. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence; 2019 Jan 27‒Feb 1; Honolulu, HI, USA. Washitong, DC: AIII Press; 2019. p. 2262‒71. . 10.1609/aaai.v33i01.33012262
[9]

Zhang Y, Zhu H, Tang D, Zhou T, Gui Y. Dynamic job shop scheduling based on deep reinforcement learning for multi-agent manufacturing systems. Robot Comput-Integr Manuf 2022;78:102412. . 10.1016/j.rcim.2022.102412
[10]

Du Y, Li J, Li C, Duan P. A reinforcement learning approach for flexible job shop scheduling problem with crane transportation and setup times. IEEE Trans Neural Netw Learn Syst 2024;35(4):5695‒709. . 10.1109/tnnls.2022.3208942
[11]

Sawik T. Modelling and scheduling of a flexible manufacturing system. Eur J Oper Res 1990;45(2‒3):177‒90.
[12]

Gomes MC, Barbosa-Póvoa AP, Novais AQ. Optimal scheduling for flexible job shop operation. Int J Prod Res 2005;43(11):2323‒53. . 10.1080/00207540412331330101
[13]

Elazeem A, Elazeem AE, Sayed M, Osman AF, Bayoumi M, Hassan A. Optimality of the flexible job shop scheduling problem. Afr J Math Comput Sci Res 2011;4 (10):321‒8.
[14]

Gomes MC, Barbosa-Póvoa AP, Novais AQ. Reactive scheduling in a make-to order flexible job shop with re-entrant process and assembly: a mathematical programming approach. Int J Prod Res 2013;51(17):5120‒41. . 10.1080/00207543.2013.793428
[15]

Yin L, Li X, Gao L, Lu C, Zhang Z. A novel mathematical model and multi objective method for the low-carbon flexible job shop scheduling problem. Sustain Comput Inform Syst 2017;13:15‒30. . 10.1016/j.suscom.2016.11.002
[16]

Kaplanoğlu V. An object-oriented approach for multi-objective flexible job shop scheduling problem. Expert Syst Appl 2016;45:71‒84. . 10.1016/j.eswa.2015.09.050
[17]

Liu Q, Li X, Gao L. Mathematical modeling and a hybrid evolutionary algorithm for process planning. J Intell Manuf 2021;32(3):781‒97. . 10.1007/s10845-020-01703-w
[18]

Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible job shop scheduling problem. Comput Oper Res 2008;35(10):3202‒12. . 10.1016/j.cor.2007.02.014
[19]

Gao J, Sun L, Gen M. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 2008;35(9):2892‒907. . 10.1016/j.cor.2007.01.001
[20]

Zhang G, Shao X, Li P, Gao L. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput Ind Eng 2009;56(4):1309‒18. . 10.1016/j.cie.2008.07.021
[21]

Zhou G, Wang L, Xu Y, Wang S. An effective artificial bee colony algorithm for multi-objective flexible job-shop scheduling problem. In: HuangDS, GanY, GuptaP, GromihaMM, editors. Advanced Intelligent Computing Theories and Applications; 2011 Aug 11‒14; Zhengzhou, China. Berlin: Springer; 2011. p. 1 8. . 10.1007/978-3-642-25944-9_1
[22]

González MA, Vela CR, Varela R. Scatter search with path relinking for the flexible job shop scheduling problem. Eur J Oper Res 2015;245(1):35‒45. . 10.1016/j.ejor.2015.02.052
[23]

Palacios JJ, González MA, Vela CR, González-Rodríguez I, Puente J. Genetic tabu search for the fuzzy flexible job shop problem. Comput Oper Res 2015;54:74‒89. . 10.1016/j.cor.2014.08.023
[24]

Li X, Gao L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int J Prod Econ 2016;174:93‒110. . 10.1016/j.ijpe.2016.01.016
[25]

Kemmoé-Tchomté S, Lamy D, Tchernev N. An effective multi-start multi-level evolutionary local search for the flexible job-shop problem. Eng Appl Artif Intell 2017;62:80‒95. . 10.1016/j.engappai.2017.04.002
[26]

Caldeira RH, Gnanavelbabu A. Solving the flexible job shop scheduling problem using an improved Jaya algorithm. Comput Ind Eng 2019;137:106064. . 10.1016/j.cie.2019.106064
[27]

Fan J, Shen W, Gao L, Zhang C, Zhang Z. A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths. J Manuf Syst 2021;60:298‒311. . 10.1016/j.jmsy.2021.05.018
[28]

Li R, Gong W, Wang L, Lu C, Jiang S. Two-stage knowledge-driven evolutionary algorithm for distributed green flexible job shop scheduling with type-2 fuzzy processing time. Swarm Evol Comput 2022;74:101139. . 10.1016/j.swevo.2022.101139
[29]

Xie J, Li X, Gao L, Gui L. A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems. J Manuf Syst 2023;71:82‒94. . 10.1016/j.jmsy.2023.09.002
[30]

Sun K, Zheng D, Song H, Cheng Z, Lang X, Yuan W, et al. Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system. Expert Syst Appl 2023;215:119359. . 10.1016/j.eswa.2022.119359
[31]

Yang D, Wu M, Li D, Xu Y, Zhou X, Yang Z. Dynamic opposite learning enhanced dragonfly algorithm for solving large-scale flexible job shop scheduling problem. Knowl-Based Syst 2022;238:107815. . 10.1016/j.knosys.2021.107815
[32]

Alzaqebah M, Jawarneh S, Alwohaibi M, Alsmadi MK, Almarashdeh I, Mohammad RMA. Hybrid brain storm optimization algorithm and late acceptance hill climbing to solve the flexible job-shop scheduling problem. J King Saud University-Comput Inf Sci 2022;34(6):2926‒37. . 10.1016/j.jksuci.2020.09.004
[33]

Mastrolilli M, Gambardella LM. Effective neighbourhood functions for the flexible job shop problem. J Sched 2000;3(1):3‒20. . 10.1002/(sici)1099-1425(200001/02)3:1<3::aid-jos32>3.3.co;2-p
[34]

Peng B, Lü Z, Cheng TCE. A tabu search/path relinking algorithm to solve the job shop scheduling problem. Comput Oper Res 2015;53:154‒64. . 10.1016/j.cor.2014.08.006
[35]

Dauzère-Pérès S, Paulli J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Oper Res 1997;70:281‒306. . 10.1023/a:1018930406487
[36]

Brandimarte P. Routing and scheduling in a flexible job shop by Tabu search. Ann Oper Res 1993;41:157‒83. . 10.1007/bf02023073
[37]

Hurink J, Jurisch B, Thole M. Tabu search for the job-shop scheduling problem with multi-purpose machines. Oper Res Spektrum 1994;15(4):205‒15. . 10.1007/bf01719451
[38]

Vilím P, Laborie P, Shaw P. Failure-directed search for constraint-based scheduling. In: MichelL, editor. Integration of AI and OR Techniques in Constraint Programming; 2015 May 18‒22; Barcelona, Spain. Berlin: Springer; 2015. p. 437‒53. . 10.1007/978-3-319-18008-3_30
[39]

Zhang J. The solution files and their corresponding Gantt charts obtained by AWLS [Internet]. 2023 [2024 Jun 28]. Available from:

AI Summary AI Mindmap
PDF (2281KB)

7118

访问

0

被引

详细
导航
相关文章

AI思维导图

/

〈 〉