作业车间调度的邻域单次搜索人工蜂群算法

张开元, 杨火根, 夏小云, 庄鹤林, 陈泽丰

PDF(1904 KB)
欢迎访问制造业自动化官方网站!
PDF(1904 KB)
制造业自动化 ›› 2024, Vol. 46 ›› Issue (9) : 95-103. DOI: 10.3969/j.issn.1009-0134.2024.09.014
计算机算法

作业车间调度的邻域单次搜索人工蜂群算法

作者信息 +

A Single Neighborhood Search Artificial Bee Colony Algorithm for Job Shop Scheduling

Author information +
History +

摘要

为了减少算法求解作业车间调度问题(Job Shop Scheduling Problem,JSP)时的无效重复搜索,以提高算法性能,提出一种邻域单次搜索人工蜂群算法(Single Neighborhood Search Artificial Bee Colony Algorithm,SNSABC)。在工序加工优先级的编码方式上结合JSP本身的特性设计邻域搜索策略,该策略采用了交换算子和路径重连算子配合搜索的方式。每次交换算子选择未被搜索过的位置搜索,在交换过程中跳过不能改变最大完工时间和已经做过的工序交换。若没有搜索到更优解,将搜索的位置标为已搜索。若搜索到更优解,将更优解进行路径重连。根据邻域搜索策略改进侦查蜂阶段,淘汰所有关键工序位置搜索完毕的解,用淘汰的解和种群中剩余的解分别交叉寻找更优解。在人工蜂群算法中加入所提策略,算法搜索效率和求解质量得到明显提升,能够快速搜索到可接受解,在大部分算例可以收敛到已知最优解。相比于对比算法,邻域单次搜索人工蜂群算法求得的最优解和均值具有更短的完工时间。实验结果表明所提策略有效提高了算法的性能。

关键词

作业车间调度 ; 人工蜂群算法 ; 邻域搜索策略 ; 关键路径 ; 路径重连

基金

国家自然科学基金(62206313)
浙江省公益技术应用研究计划(LGG19F030010)

引用本文

导出引用
张开元 , 杨火根 , 夏小云 , 庄鹤林 , 陈泽丰. 作业车间调度的邻域单次搜索人工蜂群算法[J].制造业自动化, 2024, 46(9): 95-103. https://doi.org/10.3969/j.issn.1009-0134.2024.09.014
ZHANG Kai-yuan , YANG Huo-gen , XIA Xiao-yun , ZHUANG He-lin , CHEN Ze-feng. A Single Neighborhood Search Artificial Bee Colony Algorithm for Job Shop Scheduling[J]. Manufacturing Automation, 2024, 46(9): 95-103. https://doi.org/10.3969/j.issn.1009-0134.2024.09.014

0 引言

作业车间调度(Job Shop Scheduling Problem,JSP)是经典的NP-hard约束组合优化问题1。由于JSP应用广泛,其高效求解算法的研究一直是相关领域的重要课题。2015年国务院发布了《中国制造2025》,阐明智能制造是主攻方向2。因此如何利用人工智能技术提出高效的生产调度算法具有重要的现实意义3
根据JSP问题的性质进行针对性优化已被证明能提升启发式算法的求解效果。SHARMA N等提出了由啤酒泡沫现象启发改进的人工蜂群算法,在JSP问题上取得了优秀的实验效果4。RAMESHKUMAR K和RAJENDRAN C提出了离散粒子群算法,将粒子群算法在连续问题中全局最优解和个体历史最优解的权重系数引入离散粒子群算法5。SIMPLICIO V M等提出了采用局部搜索策略和多交叉算子的改进遗传算法,开发了一种新的多交叉算子6。DING Junwen等人提出以禁忌搜索和路径重连相结合的方式解决柔性作业车间调度问题7。ASADZADEH L设计了结合局部搜索技术的遗传算法8和动态迁移策略的并行人工蜂群算法9,都在JSP上取得了良好的性能。赵诗奎提出了一种强化搜索的多工序联动邻域结构,可以更为充分的利用原有工序块相邻空闲时间和移动工序形成的空闲时间10。此外,还提出一种路径重连和禁忌搜索混合算法,结合JSP领域知识设计路径重连,分别将正向无延迟调度解和反向无延迟调度解作为路径重连的导向解,提升算法了的求解效率11。薛玲玲提出了基于块邻域结构的遗传算法,解决了邻域构建中邻域的冗余问题12
现有的启发式算法求解JSP问题大都没有避免重复的邻域搜索。例如,算子邻域搜索时交换了解中两个工序的位置,但没有产生新的更优解。下次算子邻域搜索还有可能再次交换上次被选中的两个工序的位置,产生重复无效搜索。过多的无效搜索不仅浪费计算资源还严重影响了算法的求解效率。因此,本文提出了结合JSP问题性质的无重复搜索算子,以提高算法的求解效率。人工蜂群算法(Artificial Bee Colony,ABC)由于具有强大的邻域搜索能力,在组合优化问题中得到了广泛的应用,适合JSP的搜索4。但是传统ABC算法在解决复杂组合优化问题时存在收敛速度较慢、开采能力不足等问题。本文算法根据JSP的特点融合已有基于关键路径的块邻域结构搜索方法对ABC进行进一步改进,提高算法的求解效率。最后,将本文提出的算法与其他现有算法在基准算例上进行对比,验证算法的有效性。

1 作业车间调度模型

1.1 作业车间调度问题描述

JSP可以描述为 n个工件 {Jii=1,2,...,n} m台机器 {Mj  j=1,2,...,m}上加工,每个工件在不同机器上的加工时间已知,且一个工件加工过程中进入机器的先后顺序确定13。假设工件和机器从零时刻开始加工,忽略工件在不同机器之间的转运时间14。加工过程需满足以下约束条件14:1)同一工件任何时刻最多在一台机器上加工,同一机器任何时刻最多加工一个工件;2)工序一旦投入机器加工便不能停止;3)工件的上一道工序加工完成才能加工下一道工序;4)机器只有加工完当前工序才能加工下一道工序。JSP通常以最大完工时间 Cmax最小化为优化目标,目标函数为13表1所示为一个 2×2的JSP实例。
Cmax=min(maxi=1n(Ci))
(1)
其中 Ci为工件 Ji的完工时间, Cmax为所有完工时间的最大值。
表1 2×2JSP实例
工件 工序 加工机器及时间
M1 M2
J1 O11 3
O12 2
J2 O21 2
O22 3
表1所示工件 J1有两道工序分别为 O11 O12,根据约束条件只有在工序 O11加工完后才能加工工序 O12。工序 O11在机器 M1上加工,加工时间为3。工序 O12在机器 M2上加工,加工时间为2。工件 J2同理。

1.2 编码方式

基于工序加工优先级的编码方式可以保证邻域搜索中产生的新解符合约束,因此本文采用该编码方式。以表1中的问题为例,假设一个解为 1221,解如表2所示。
表2 解和其中对应的工序
解编码 1 2 2 1
工序 O11 O21 O22 O12
工件号在解中的位置代表对应工序的加工顺序。其中,解中出现的第一个1表示工件1的第一道工序 O11,解中出现的第二个1表示工件1的第二道工序 O12。以此类推,上述解对应的加工顺序为工件1的第一道工序 O11、工件2的第一道工序 O21、工件2的第二道工序 O22、工件1的第二道工序 O12

1.3 解码方式

作业车间调度问题在解码的过程中通常首先确定各个工序的加工顺序,将工序按顺序加工得到一个调度及甘特图。主要的解码方式有半主动调度、主动调度、全主动调度、无延迟调度11。1.2章节中的解 1221根据表1生成的半主动调度和主动调度分别如图1中(a)和图1中(b)所示。
图1 调度甘特图

Full size|PPT slide

图1(a)半主动调度根据解中工序的加工顺序得到;主动调度在半主动调度基础上,不影响其他工序完工时间的情况下,对工序左移来实现。如图1(a)中的工序 O12向前移动不影响其他工序的完工时间,左移工序 O12图1(b);同理,全主动调度是在主动调度基础上,不影响其他工序完工时间的情况下,对工序右移来实现。不同调度之间的关系如图2所示15
图2 不同调度间关系图

Full size|PPT slide

半主动调度包含主动调度,主动调度包含全主动调度,且最优解必在全主动调度集中。由于全主动调度能够缩小解空间且包含最优解,因此本文使用全主动解码方式计算解的完工时间。本文使用了文献[11]中的无延迟调度方法,无延迟调度通过移动部分工序实现了全部工序某侧的可用空闲时间为0。下文中用到的正向无延迟调度是将解做主动调度,然后根据主动调度后的工序优先级和工序完工时间做无延迟调度得到11。反向无延迟调度是在主动调度后反转工序的加工优先级、加工机器、加工时间,再根据工序优先级和工序完工时间做无延迟调度11

1.4 关键路径和关键工序块

一个可行调度中工序间无时间间隔的最长路径称为关键路径,关键路径上的工序为关键工序16。同一台机器上,最大序列的紧密相邻关键工序组成一个关键工序块(至少2个工序)17。从前往后,处于块首的第一个工序为块首工序,处于块尾的最后一个工序为块尾工序,位于块首工序和块尾工序之间的工序称为块内工序17。本文采用文献[16]和文献[17]中的方法查找关键路径和关键路径中的关键工序块。此外由JSP本身的性质可知17:1)交换任意相邻的非关键工序不能减小最大完工时间。2)交换关键工序块内的相邻工序不能减小最大完工时间。关键路径的长度决定着一个解的最大完工时间,因此算子对基于工序顺序编码的解做各种操作的本质就是引导关键工序对机器上的空闲时间进行利用,从而减少关键路径的长度减少最大完工时间。

2 邻域单次搜索人工蜂群算法求解JSP

2.1 ABC

人工蜂群算法是一个由蜂群行为启发的算法,于2005年由Karaboga为优化函数问题而提出18。人工蜂群算法主要由4部分组成:蜜源、雇佣蜂、跟随蜂、侦查蜂。每个蜜源对应问题的一个解,通过解的适应值大小评价一个解的优劣程度。每个雇佣蜂对应一个蜜源,并向跟随蜂分享蜜源信息。跟随蜂依据雇佣蜂分享的蜜源信息概率选择蜜源搜索,蜜源越好选择的概率越大。侦查蜂搜索新的蜜源。
ABC算法的主要步骤如下19
1)初始化种群,并计算每个个体的适应值。设种群规模为 NP,问题维度为 D。单个蜜源表示为 Xi=(xi1,xi2,,xiD),其中 i=1,2,,NP。通过式(2)产生 NP个蜜源完成种群的初始化。
xij=xjmin+rand×(xjmax-xjmin)
(2)
其中, j 1,2,3,,D中的随机数。 xjmax xjmin分别表示解空间在第 j维的上界和下界。 rand为0到1之间服从均匀分布的随机数。
在最小值优化问题中每个蜜源的适应值计算如式(3)所示:
fiti=11+fi,fi01+fi,fi<0
(3)
其中, fiti为蜜源的适应值,适应值越大蜜源越优秀。 fi为蜜源 i的目标函数值。
2)雇佣蜂阶段每个雇佣蜂对其对应的蜜源进行邻域搜索,对蜜源进行贪婪更新。新的蜜源 Yi=(yi1,yi2,,yiD)式(4)产生。
yij=xij+φij×(xij-xkj)
(4)
其中, φij-1,1 k{1,2,,NP},且 ki。每次蜜源更新一个维度的值,然后计算 Yi的适应值。若 Yi的适应值比 Xi更大,则 Yi替换 Xi
3)跟随蜂阶段跟随蜂依据概率随机选择蜜源进行邻域搜索并进行贪婪更新。每个蜜源的选择概率 Pi计算如式(5)所示:
Pi=fitii=1NPfiti
(5)
其中, Pi为蜜源 Xi的选择概率,当 Xi被选中按式(4)进行邻域搜索。
4)侦查蜂阶段淘汰适应值难以提升的蜜源,对应雇佣蜂转化为侦查蜂,随机搜索寻找一个新的蜜源。即将一定迭代次数没有更新的蜜源移出种群,由式(2)产生新的蜜源加入种群。
由上可知,邻域搜索是ABC的核心。后文将根据1.4节(关键路径和关键工序块)所述问题体系设计邻域搜索算子,给出求解的具体细节和改进策略。

2.2 关键工序的交换算子

交换算子通过交换解中两个不同位置的工件号来产生新的解。交换算子策略如图3所示。
图3 交换算子流程图

Full size|PPT slide

每次算子随机选择一个未被搜索的位置 P1,将 P1对应位置标记为已搜索,另一个交换的位置 P2为解中第一个位置。交换算子执行的流程如图3。首先,若 P1 P2符合以下情况跳过此次交换:1) P1 P2为相同位置。2)解在 P1 P2位置上的工件号相同跳过这次交换。3)若 P1 P2位置上的工件号之前已经做过交换操作也跳过这次交换。然后,判断是否可以根据1.4节所述的性质跳过这次交换。若跳过本次交换则 P2向后移一个位置,并将 P2再次与 P1进行判断。若交换可以进行,判断交换后产生的新邻域解完工时间是否比原有的解更短。如果新邻域解的完工时间更短,那么将新邻域解加入种群,并结束交换算子。如果新邻域解没有加入种群,依顺序选择解中下一个位置为 P2,继续执行上述步骤。直到完工时间更短的新邻域解加入种群,或者 P2为解中的最后一个位置且完成交换操作,结束交换算子。

2.3 路径重连

路径重连是通过探索两高质量解之间的运动轨迹来生成新解的过程20。实验证明将交叉算子产生的新邻域解进行路径重连提升了算法的邻域搜索能力。本文采用文献[11]中的路径重连方法生成新邻域解。每次路径重连时从随机选取正向无延迟导向解和反向无延迟导向解中的一个作为导向解,当前解作为起始解进行路径重连11。路径重连过程如图4所示。
图4 路径重连过程

Full size|PPT slide

比较起始解和导向解中第一个位置的工件号是否相同,如果不同,从起始解中找寻与导向解中第一个位置相同的工件号,将起始解中找到的第一个相同工件号与起始解第一个位置的工件号互换,产生第一个路径解;如果起始解和导向解中第一个位置的工件号相同,比较第二个位置的工件号,以此类推20。产生第一个路径解后,将当前路径解按上述原理同导向解进行路径重连,产生多个路径解,直至路径解同导向解完全一致,结束重连过程20

2.4 交叉算子

交叉算子将两个高质量解的信息结合组成新的解。交叉策略如图5所示21
图5 交叉过程

Full size|PPT slide

选取2个解作为父代,将工件集合 Jii=1,2,...,n随机划分为两个非空工件子集合集合1和集合2。将父代1在集合1中的工件号按照在父代1中的位置放入子代1中,将父代2在集合2中的工件号按顺序放入子代1的空缺位置中。将父代2在集合1中的工件号按照在父代2中的位置放入子代2中,将父代1在集合2中的工件号按顺序放入子代1的空缺位置中。假设父代1和父代2分别为 123321312 321223113,集合1为 3,集合2为 1,2

2.5 适应值函数

根据目标函数式(1),解的适应值的参考依据为其最大完工时间,最大完工时间越小,适应值越高18。综上所述,给出适应值函数如下:
f(Ti)=1+k×Tmax-TiTmax-Tmin
(6)
Tmax为当前种群中所有的解的 Cmax的最大值, Tmin为当前种群中所有的解的 Cmax最小值, Ti为当前解的 Cmax k为一个大于0的系数,实验中设置为1.0,其值越大种群中个体的适应值差距越大。设1为适应值下限,可以保证种群中最大完工时间最大的解仍有概率被选择。比起直接使用最大完工时间的倒数作为适应值,根据上次迭代的结果以归一化方式计算适应值更能反映每个解的质量。

2.6 改进搜索策略

为了解决邻域搜索中的重复无效搜索,本文使用了一种避免重复搜索的方式:为每个解定义一个搜索标识数组,数组的长度为解的长度,数组中每个关键工序对应的位置初始值置为1,其余位置值置为0。数组中元素对应位置的值为1表示对应位置未搜索,值为0表示对应位置已搜索。算子选择解中一个工序进行操作时,若产生了完工时间更短的邻域解,用更优的新解替换原来的解,并将新解的搜索标识数组初始化。若没有产生新的更优解,将算子选择工序的位置对应搜索标识数组位置中的值置为0。算子每次选择未被搜索过的位置进行搜索。搜索过程如图6所示。
图6 搜索过程

Full size|PPT slide

图6中(a)是解的初始化状态,灰色位置代表解的关键工序。选中第一个关键工序 O21与其他工序依前后顺序进行交换,若发现更优解返回更优解。图6中(b)为假设第一个关键工序搜索完毕没有发现更优解,对关键工序 O11进行交换操作,其中 O21 O11在上一轮已进行过交换,本轮不在进行重复交换。图6中(c)为假设第二个关键工序搜索完毕没有发现更优解,对关键工序 O32进行交换操作。图6中(d)为假设全部搜索结束没有发现新解,全部数组值为0,将在侦查蜂阶段被淘汰。图6中(e)为假设 O32 O22交换中发现了最优解生成新的解并初始化数组。
雇佣蜂阶段和跟随蜂阶段的算子配合搜索流程如图7所示。
图7 算子配合搜索流程图

Full size|PPT slide

对当前解使用交换算子搜索邻域解。若交换算子没有找到更优的邻域解,返回空值。若交换算子找到了更优的邻域解,则以邻域解为路径重连的起始解进行路径重连。若路径重连没有找到更好的解,将交换算子找到的解加入种群。若路径重连得到了比起始解更好的解,将路径重连得到的解加入种群。

2.7 改进侦查蜂阶段

根据邻域搜索策略改进的侦查蜂阶段流程如图8所示。
图8 侦查蜂阶段流程图

Full size|PPT slide

当关键路径的所有位置都被交换算子搜索完毕时,每个解对应的搜索标识数组的值全部为0,在侦查蜂阶段将搜索标识数组值全为0的解从种群中淘汰。当一个解在侦查蜂阶段被淘汰时,调用交叉算子使淘汰解和种群里剩余的所有解分别做一次交叉,如果得到的解最大完工时间比父代的两个解更短将得到的更优解加入种群。仅在侦查蜂阶段使用交叉算子的原因是:在雇佣蜂和跟随蜂阶段使用交叉算子,交叉算子会将侦查蜂阶段随机生成的解替换为与种群中其他解交叉后生成的解,降低了算法的全局搜索能力和种群的多样性。侦查蜂阶段淘汰的解已经过了充分的搜索,是一个邻域较优解。当种群中的解数量小于种群大小时,随机生成解直到种群中解的数量等于种群大小。

2.8 SNSABC求解JSP算法步骤

SNSABC在ABC原有的算法框架下跟据JSP问题的特性设计了新的邻域搜索算子,结合邻域搜索策略改进了算法的侦查蜂阶段,并在侦查蜂阶段引入了交叉算子。
算法:SNSABC
输入:种群大小、适应值跨度系数
输出:求得最大完工时间最短的解
1: Xi=generatingSolution()//生成初始蜜源 (xi1,xi2,,xiD)
2: while 运行时间达到上限
3: for each 雇佣蜂:
4: neighborhood_search( Xi) //邻域搜索
5: end for
6: for each 跟随蜂:
7: Xj=select()//赌盘算法选择蜜源
8: neighborhood_search( Xj) //邻域搜索
9: end for
10: for each Xi
11: if Xi标识数组的和为0
12: pop( Xi)//淘汰邻域搜索完未更新的蜜源
13: cross( Xi)//淘汰蜜源和其他蜜源做交叉
14: end if
15: end for
16: while 蜜源数量小于种群大小
17: Yi=generatingSolution()//生成新的蜜源加入种群
18: end while
19:end while
其中generatingSolution()为生成一个新的蜜源,neighborhood_search( Xi)为对蜜源 Xi进行邻域搜索,select()为赌盘算法选取蜜源,pop( Xi)为淘汰蜜源,cross( Xi)用蜜源 Xi和其他蜜源做交叉。
算法包含如下步骤:1)初始化种群。2)判断是否满足算法终止条件,满足条件则终止算法输出算法找到的最优解。3)雇佣蜂阶段:对每个解进行邻域搜索,将邻域搜索得到的新解加入种群。4)跟随蜂阶段:每个跟随蜂根据适应值的大小概率选择一个解进行邻域搜索,将邻域搜索得到的新解加入种群。5)侦查蜂阶段淘汰种群中对应搜索标识数组和为0的解,将淘汰的解与种群中剩余的解分别做一次交叉,若交叉产生了更优解加入种群。然后,判断种群中的个体是否小于种群大小,若小于种群大小随机生成新的解加入种群。6)执行步骤2。

3 仿真实验与分析

为了验证本文算法的性能实验采用LA数据集22、ORB数据集23。计算机的操作系统为Windows 11,CPU为i7-12700h,以Python为编程语言。为了选取本文算法的参数,对本文算法参数在LA21算例上进行正交实验,每一轮实验分别独立计算10次取平均值,其中跟随蜂数量默认为种群大小的两倍,实验结果如表3所示。根据表3中的实验结果,算法选取种群大小为80,适应值跨度系数为1.0时,算法的平均性能最好。因此,选用上述数值作为本文算法的参数。
表3 正交实验结果
实验编号 种群大小 适应值跨度系数 平均值
1 40 1 1063.0
2 40 2 1064.4
3 40 3 1063.9
4 80 1 1060.8
5 80 2 1063.5
6 80 3 1064.8
7 120 1 1076.2
8 120 2 1070.5
9 120 3 1061.7
为了验证邻域搜索策略的有效性选取LA27、LA29、LA36、LA39、LA40到LA30这5个求解较难算例进行实验,在搜索标识数组中只有关键路径对应位置值为1和所有位置全为1(交换算子将每个工序都依次和其他工序进行交换操作)的情况下分别独立计算10次,结束条件算法为迭代100代。实验结果如表4所示。表中的参数描述如下: Cmax表示使用10次测试结果得到的最优解。 AVCmax为10次测试结果的平均值。 LB表示当前已知最优解。经过实验验证,除了LA29和LA40算例搜索到的最小值相同,在其余3个算例中本文策略的最值都更优秀,并且在全部算例中采用本文策略求得的均值都更小。实验结果表明,与搜索标识数组所有的初始值置为1相比较只给关键路径对应的位置赋值为1,算法的求解效率和质量都得到了提升。
表4 邻域搜索策略对比实验
算例 全部值为1 关键路径为1
Cmax AVCmax Cmax AVCmax
LA27 1255 1261.4 1246 1259.9
LA29 1174 1184 1174 1183.6
LA36 1281 1290.4 1278 1280.7
LA39 1240 1244.3 1238 1240.7
LA40 1235 1245.6 1235 1239.3
为了验证本文适应值函数的有效性,选取LA21到LA25的5个15 ×10规模算例进行测试。每个算例分别独立计算10次比较均值,算法结束条件为算法运行迭代50代。对适应值取倒数和本文适应值函数两种情况分别进行测试。经过实验验证,本文适应值方法除了在易快速收敛到已知最优解的LA23算例外,在其余算例中得到结果均值都明显优于对最大完工时间取倒数的方式。实验结果表明,本文的适应值计算方式相比于取最大完工时间的倒数具有更高的求解效率。实验结果如表5所示。
表5 适应值对比实验
算例 适应值取倒数 本文适应值
AVCmax AVCmax
LA21 1063.8 1061.8
LA22 939.8 937
LA23 1032 1032
LA24 948.6 942.2
LA25 990.4 986.2
算法在每个ORB算例上选择10个不同的随机种子独立计算10次。实验结果如表6所示。算法在LA21~LA29和LA36~LA40共14个较难求解的算例上选择10个不同的随机种子独立计算10次。测试结果如表7所示。表6 表7中的参数描述如下: RE表示算法找到的最优解 Cmax和当前已知最优解 LB之间的相对偏差14。对14个算例的 RE求平均值为 MRE
表6 ORB数据集实验结果
算例 规模 LB Cmax AVCmax
ORB01 10 ×10 1059 1059 1059
ORB02 10 ×10 888 888 888.8
ORB03 10 ×10 1005 1005 1005
ORB04 10 ×10 1005 1005 1009.8
ORB05 10 ×10 887 887 888.2
ORB06 10 ×10 1010 1010 1012
ORB07 10 ×10 397 397 397
ORB08 10 ×10 899 899 899
ORB09 10 ×10 934 934 934
ORB10 10 ×10 944 944 944
RE=Cmax-LBLB×100%
(3)
表7 实验结果及对比
算例 规模 LB SNSABC 文献[17] 文献[5] 文献[6]
Cmax AVCmax RE Cmax RE Cmax RE Cmax RE
LA21 15 ×10 1046 1046 1052 0 1046 0 1047 0.1 1059 1.24
LA22 15 ×10 927 927 929.1 0 927 0 927 0 935 0.86
LA23 15 ×10 1032 1032 1032 0 1032 0 1032 0 1032 0
LA24 15 ×10 935 935 937.7 0 938 0.32 939 0.43 946 1.17
LA25 15 ×10 977 977 980.5 0 978 0.1 984 0.72 986 0.92
LA26 20 ×10 1218 1218 1218 0 1218 0 1218 0 1218 0
LA27 20 ×10 1235 1236 1257 0.08 1240 0.4 1236 0.08 1269 2.75
LA28 20 ×10 1216 1216 1216 0 1216 0 1225 0.74 1239 1.89
LA29 20 ×10 1152 1164 1171 1.04 1164 1.04 1164 0.71 1201 4.25
LA36 15 ×15 1268 1274 1278 0.47 1281 1.03 1279 0.87 1295 2.12
LA37 15 ×15 1397 1397 1400 0 1407 0.72 1407 0.72 1415 1.28
LA38 15 ×15 1196 1196 1204 0 1202 0.5 1219 1.92 1246 4.18
LA39 15 ×15 1233 1238 1239 0.41 1238 0.41 1246 1.05 1258 2.02
LA40 15 ×15 1222 1224 1229 0.16 1229 0.57 1229 0.57 1243 1.71
MRE 0.154 0.363 0.565 1.742
从总体角度使用 MRE评价算法的性能,将本文结果与文献[17]、文献[5]、文献[6]分别比较。由表7数据可知本文算法的 MRE为0.154,其他几篇文章的 MRE分别为0.363、0.565、1.742。实验表明,本文算法具有较强的整体性能,在大规模问题上的求解质量明显优于对比算法。SNSABC在LA40算例上求得完工时间为1224的调度甘特图如图9所示。
图9 LA40调度甘特图

Full size|PPT slide

4 结论

为了减少算法求解JSP时存在的无效重复搜索,并提高算法性能,提出一种邻域单次搜索人工蜂群算法,有效的解决了算法求解JSP的重复无效搜索。
本文算法使用关键路径工序的交换和无延迟调度导向解的路径重连进行邻域搜索,路径重连的引入提升了邻域搜索得到邻域解的质量。在邻域搜索阶段利用JSP本身的信息避免无效搜索,同时使用避免重复搜索的策略。交换算子每次使用一个关键工序和其他所有工序(包括其他关键工序)交换,结合了问题本身的性质提高了邻域搜索的效率。在侦查蜂阶段,将解的淘汰条件由最大迭代次数变为解的关键路径被邻域搜索完毕。淘汰的高质量解和种群中其他解进行交叉,既保证了侦查蜂阶段新生成的解不会被交叉避免了局部最优,又保证了交叉产生解的质量。
通过在JSP基准算例上测试,验证了算法的有效性。后续的工作是进一步结合问题性质继续改进邻域搜索策略提升算法在大规模问题上的寻优速度。此外,可以设计开发更多其他智能优化算法求解JSP问题24-25,也可以将JSP问题考虑为多任务优化求解26

参考文献

1
YAZDANI M ALETI A KHALILI S M, et al. Optimizing the Sum of Maximum Earliness and Tardiness of the Job Shop Scheduling Problem[J]. Computers & Industrial Engineering2017107(5):12-24.
2
周济.智能制造是“中国制造2025”主攻方向[J].企业观察家2019(11):54-55.
3
王凌,潘子肖.基于深度强化学习与迭代贪婪的流水车间调度优化[J].控制与决策202136(11):2609-2617.
4
SHARMA N SHARMA H SHARMA A.Beer Froth Artificial Bee Colony Algorithm for Job-Shop Scheduling Problem[J]. Applied Soft Computing Journal2018,68.
5
RAMESHKUMAR K RAJENDRAN C. A Novel Discrete PSO Algorithm for Solving Job Shop Scheduling Problem to Minimize Makespan[J]. IOP Conference Series: Materials Science and Engineering2018310(1).
6
SIMPLICIO V M MORANDIN J O CONTRERAS R C. A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem.[J]. Sensors (Basel, Switzerland)202020(18).
7
DING Junwen Zhipeng LYU LI Chumin, et al. A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem[J]. Proceedings of the AAAI Conference on Artificial Intelligence2019,33.
8
ASADZADEH L. A Local Search Genetic Algorithm for the Job Shop Scheduling Problem with Intelligent Agents[J]. Computers & Industrial Engineering2015,85.
9
ASADZADEH L.A Parallel Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with a Dynamic Migration Strategy[J]. Computers & Industrial Engineering2016,102.
10
赵诗奎,黄林,吕杰.Job shop强化多工序联动邻域结构与近似评价研究[J/OL].机械工程学报:1-14[2022-11-04].
11
赵诗奎. Job Shop基于无延迟调度路径重连与回溯禁忌搜索算法研究[J].机械工程学报202157(14):291-303.
12
薛玲玲.作业车间调度的块结构邻域搜索遗传算法[J].计算机集成制造系统202127(10):2848-2857.
13
赵诗奎,方水良,顾新建.作业车间调度的空闲时间邻域搜索遗传算法[J].计算机集成制造系统201420(8):1930-1940.
14
薛玲玲. 面向作业车间调度问题的静动态调度方法研究[D]. 北京:中国科学院大学,2021.
15
张超勇. 基于自然启发式算法的作业车间调度问题理论与应用研究[D].武汉:华中科技大学,2007.
16
赵诗奎,方水良.基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J].机械工程学报201349(16):160-169.
17
赵诗奎.基于新型邻域结构的混合算法求解作业车间调度[J].机械工程学报201652(9):141-150.
18
夏小云,庄鹤林,杨火根,等. 自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题[J].计算机集成制造系统202228(11):3545-3557.
19
熊小峰,尹雅丽,郭肇禄,等.精英区域学习的转轴人工蜂群算法[J].四川大学学报(工程科学版)201648(5):124-134.DOI:10.15961/j.jsuese.2016.05.018 .
20
孟悦,赵诗奎.融合路径重连的混合算法求解作业车间调度问题[J].机械工程师2019(12):32-36,39.
21
张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程2004(23):83-87.
22
LAWRENCE S. Supplement to Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques[J]. Graduate School of Industrial Administration, Carnegie-Mellon University, 1984.
23
DAVID A WILLIAM C, et al. A Computational Study of the Job-Shop Scheduling Problem[J]. Orsa Journal on Computing1991.
24
李薇,樊瑶驰,江巧永,等.基于教与学优化的可变卷积自编码器的医学图像分类方法[J].计算机应用202242(2):592-598.
25
康佳惠,邹锋,陈得宝,等.一种新的带回溯搜索的教学优化算法[J].佳木斯大学学报(自然科学版)202038(5):32-39.
26
XU Q WANG N WANG L, et al. Multi-Task Optimization and Multi-Task Evolutionary Computation in the Past Five Years: A Brief Review. Mathematics. 20219(8): 864.
PDF(1904 KB)

50

Accesses

0

Citation

Detail

段落导航
相关文章

/