作业车间调度的邻域单次搜索人工蜂群算法
张开元, 杨火根, 夏小云, 庄鹤林, 陈泽丰
作业车间调度的邻域单次搜索人工蜂群算法
A Single Neighborhood Search Artificial Bee Colony Algorithm for Job Shop Scheduling
为了减少算法求解作业车间调度问题(Job Shop Scheduling Problem,JSP)时的无效重复搜索,以提高算法性能,提出一种邻域单次搜索人工蜂群算法(Single Neighborhood Search Artificial Bee Colony Algorithm,SNSABC)。在工序加工优先级的编码方式上结合JSP本身的特性设计邻域搜索策略,该策略采用了交换算子和路径重连算子配合搜索的方式。每次交换算子选择未被搜索过的位置搜索,在交换过程中跳过不能改变最大完工时间和已经做过的工序交换。若没有搜索到更优解,将搜索的位置标为已搜索。若搜索到更优解,将更优解进行路径重连。根据邻域搜索策略改进侦查蜂阶段,淘汰所有关键工序位置搜索完毕的解,用淘汰的解和种群中剩余的解分别交叉寻找更优解。在人工蜂群算法中加入所提策略,算法搜索效率和求解质量得到明显提升,能够快速搜索到可接受解,在大部分算例可以收敛到已知最优解。相比于对比算法,邻域单次搜索人工蜂群算法求得的最优解和均值具有更短的完工时间。实验结果表明所提策略有效提高了算法的性能。
表1 |
工件 | 工序 | 加工机器及时间 | |
---|---|---|---|
| | ||
| | 3 | |
| 2 | ||
| | 2 | |
| 3 |
表2 解和其中对应的工序 |
解编码 | 1 | 2 | 2 | 1 |
---|---|---|---|---|
工序 | | | | |
算法:SNSABC |
---|
输入:种群大小、适应值跨度系数 |
输出:求得最大完工时间最短的解 |
1: |
2: while 运行时间达到上限 |
3: for each 雇佣蜂: |
4: neighborhood_search( |
5: end for |
6: for each 跟随蜂: |
7: |
8: neighborhood_search( |
9: end for |
10: for each |
11: if |
12: pop( |
13: cross( |
14: end if |
15: end for |
16: while 蜜源数量小于种群大小 |
17: |
18: end while |
19:end while |
表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 |
表4 邻域搜索策略对比实验 |
算例 | 全部值为1 | 关键路径为1 | ||
---|---|---|---|---|
| | | | |
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 |
表5 适应值对比实验 |
算例 | 适应值取倒数 | 本文适应值 |
---|---|---|
| | |
LA21 | 1063.8 | 1061.8 |
LA22 | 939.8 | 937 |
LA23 | 1032 | 1032 |
LA24 | 948.6 | 942.2 |
LA25 | 990.4 | 986.2 |
表6 ORB数据集实验结果 |
算例 | 规模 | | | |
---|---|---|---|---|
ORB01 | 10 | 1059 | 1059 | 1059 |
ORB02 | 10 | 888 | 888 | 888.8 |
ORB03 | 10 | 1005 | 1005 | 1005 |
ORB04 | 10 | 1005 | 1005 | 1009.8 |
ORB05 | 10 | 887 | 887 | 888.2 |
ORB06 | 10 | 1010 | 1010 | 1012 |
ORB07 | 10 | 397 | 397 | 397 |
ORB08 | 10 | 899 | 899 | 899 |
ORB09 | 10 | 934 | 934 | 934 |
ORB10 | 10 | 944 | 944 | 944 |
表7 实验结果及对比 |
算例 | 规模 | | SNSABC | 文献[17] | 文献[5] | 文献[6] | |||||
---|---|---|---|---|---|---|---|---|---|---|---|
| | RE | | | | | | | |||
LA21 | 15 | 1046 | 1046 | 1052 | 0 | 1046 | 0 | 1047 | 0.1 | 1059 | 1.24 |
LA22 | 15 | 927 | 927 | 929.1 | 0 | 927 | 0 | 927 | 0 | 935 | 0.86 |
LA23 | 15 | 1032 | 1032 | 1032 | 0 | 1032 | 0 | 1032 | 0 | 1032 | 0 |
LA24 | 15 | 935 | 935 | 937.7 | 0 | 938 | 0.32 | 939 | 0.43 | 946 | 1.17 |
LA25 | 15 | 977 | 977 | 980.5 | 0 | 978 | 0.1 | 984 | 0.72 | 986 | 0.92 |
LA26 | 20 | 1218 | 1218 | 1218 | 0 | 1218 | 0 | 1218 | 0 | 1218 | 0 |
LA27 | 20 | 1235 | 1236 | 1257 | 0.08 | 1240 | 0.4 | 1236 | 0.08 | 1269 | 2.75 |
LA28 | 20 | 1216 | 1216 | 1216 | 0 | 1216 | 0 | 1225 | 0.74 | 1239 | 1.89 |
LA29 | 20 | 1152 | 1164 | 1171 | 1.04 | 1164 | 1.04 | 1164 | 0.71 | 1201 | 4.25 |
LA36 | 15 | 1268 | 1274 | 1278 | 0.47 | 1281 | 1.03 | 1279 | 0.87 | 1295 | 2.12 |
LA37 | 15 | 1397 | 1397 | 1400 | 0 | 1407 | 0.72 | 1407 | 0.72 | 1415 | 1.28 |
LA38 | 15 | 1196 | 1196 | 1204 | 0 | 1202 | 0.5 | 1219 | 1.92 | 1246 | 4.18 |
LA39 | 15 | 1233 | 1238 | 1239 | 0.41 | 1238 | 0.41 | 1246 | 1.05 | 1258 | 2.02 |
LA40 | 15 | 1222 | 1224 | 1229 | 0.16 | 1229 | 0.57 | 1229 | 0.57 | 1243 | 1.71 |
| 0.154 | 0.363 | 0.565 | 1.742 |
1 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
2 |
周济.智能制造是“中国制造2025”主攻方向[J].企业观察家,2019(11):54-55.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
3 |
王凌,潘子肖.基于深度强化学习与迭代贪婪的流水车间调度优化[J].控制与决策,2021,36(11):2609-2617.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
4 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
5 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
6 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
7 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
8 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
9 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
10 |
赵诗奎,黄林,吕杰.Job shop强化多工序联动邻域结构与近似评价研究[J/OL].机械工程学报:1-14[2022-11-04].
{{custom_citation.content}}
{{custom_citation.annotation}}
|
11 |
赵诗奎. Job Shop基于无延迟调度路径重连与回溯禁忌搜索算法研究[J].机械工程学报,2021,57(14):291-303.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
12 |
薛玲玲.作业车间调度的块结构邻域搜索遗传算法[J].计算机集成制造系统,2021,27(10):2848-2857.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
13 |
赵诗奎,方水良,顾新建.作业车间调度的空闲时间邻域搜索遗传算法[J].计算机集成制造系统,2014,20(8):1930-1940.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
14 |
薛玲玲. 面向作业车间调度问题的静动态调度方法研究[D]. 北京:中国科学院大学,2021.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
15 |
张超勇. 基于自然启发式算法的作业车间调度问题理论与应用研究[D].武汉:华中科技大学,2007.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
16 |
赵诗奎,方水良.基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J].机械工程学报,2013,49(16):160-169.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
17 |
赵诗奎.基于新型邻域结构的混合算法求解作业车间调度[J].机械工程学报,2016,52(9):141-150.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
18 |
夏小云,庄鹤林,杨火根,等. 自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题[J].计算机集成制造系统,2022,28(11):3545-3557.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
19 |
熊小峰,尹雅丽,郭肇禄,等.精英区域学习的转轴人工蜂群算法[J].四川大学学报(工程科学版),2016,48(5):124-134.DOI:10.15961/j.jsuese.2016.05.018 .
{{custom_citation.content}}
{{custom_citation.annotation}}
|
20 |
孟悦,赵诗奎.融合路径重连的混合算法求解作业车间调度问题[J].机械工程师,2019(12):32-36,39.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
21 |
张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004(23):83-87.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
22 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
23 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
24 |
李薇,樊瑶驰,江巧永,等.基于教与学优化的可变卷积自编码器的医学图像分类方法[J].计算机应用,2022,42(2):592-598.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
25 |
康佳惠,邹锋,陈得宝,等.一种新的带回溯搜索的教学优化算法[J].佳木斯大学学报(自然科学版),2020,38(5):32-39.
{{custom_citation.content}}
{{custom_citation.annotation}}
|
26 |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
{{custom_ref.label}} |
{{custom_citation.content}}
{{custom_citation.annotation}}
|
/
〈 | 〉 |