Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2020, Vol. 54 Issue (4): 712-721    DOI: 10.3785/j.issn.1008-973X.2020.04.010
计算机技术、信息工程     
混合共生生物搜索算法求解置换流水车间调度问题
秦旋(),房子涵,张赵鑫
华侨大学 土木工程学院，福建 厦门 361021
Hybrid symbiotic organisms search algorithm for permutation flow shop scheduling problem
Xuan QIN(),Zi-han FANG,Zhao-xin ZHANG
College of Civil Engineering, Huaqiao University, Xiamen 361021, China
 全文: PDF(1091 KB)   HTML
摘要：

为了求解置换流水车间调度问题，提出基于共生生物搜索（SOS）算法与局部搜索策略结合的混合共生生物搜索算法. 采用最大排序值的优先规则，处理离散的搜索空间. 在初始化阶段结合NEH启发式算法以提高初始种群的质量. 在优化过程中引入交换变异来改善种群内的多样性，插入-倒转区增加算法跳出局部最优的能力；采用局部搜索策略提升算法的全局探索能力，有效避免了共生生物搜索算法易早熟、后期搜索效率低、易陷入局部最优等缺陷. 通过3个最常用、最专业的标准测试集Carlier、Rec和Taillard对算法性能进行测试. 与其他多种算法进行比较，验证了提出的混合SOS算法的优越性和稳定性.
关键词： 置换流水车间调度;  共生生物搜索算法;  局部搜索策略;  NEH启发式算法;  混合共生生物搜索（HSOS）    
Abstract:

A hybrid algorithm based on the combination of symbiotic organism search algorithm (SOS) and local search strategy was proposed in order to solve the permutation flow shop scheduling problem. The largest rank value was adopted to deal with the discrete search space of the problem. The Nawaz Enscore Ham (NEH) heuristic algorithm was combined during initialization stage to improve the quality of the initial population. The diversity within the population was improved using a swap mutation operation during the optimization stage, and the insert-reversed block operation was adopted to escape from the local optima. The local search strategy was used to enhance the ability of global search which effectively avoids the drawbacks of the symbiotic organism search algorithm such as ease of premature convergence, low convergence rate and falling into local optimum easily in the later stage. The performance of the proposed algorithm was tested by three most commonly used and professional standard test sets, Carlier, Rec and Taillard. The effectiveness and superiority of the proposed hybrid SOS algorithm was verified by comparing with other algorithms.
Key words: permutation flow shop scheduling    symbiotic organism search algorithm    local search strategy    NEH heuristic algorithm    hybrid symbiotic organisms search (HSOS)
收稿日期: 2019-04-07 出版日期: 2020-04-05
CLC:  TP 391  
基金资助: 福建省自然科学基金资助项目（2019J01050）
作者简介: 秦旋（1969—），女，教授，从事建筑业可持续发展研究. orcid.org/0000-0001-6416-0837. E-mail： hdwq@hqu.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
秦旋
房子涵
张赵鑫

引用本文:

秦旋,房子涵,张赵鑫. 混合共生生物搜索算法求解置换流水车间调度问题[J]. 浙江大学学报(工学版), 2020, 54(4): 712-721.

Xuan QIN,Zi-han FANG,Zhao-xin ZHANG. Hybrid symbiotic organisms search algorithm for permutation flow shop scheduling problem. Journal of ZheJiang University (Engineering Science), 2020, 54(4): 712-721.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2020.04.010    或    http://www.zjujournals.com/eng/CN/Y2020/V54/I4/712

图 1  HSOS算法流程图
图 2  随机+NEH初始化种群
图 3  最大排序值法的表示方法
构件 M1 M2 M3 M4 M5
J1 5 9 8 10 1
J2 9 3 10 1 8
J3 9 4 5 8 6
J4 4 8 8 7 2
表 1  置换流水车间调度例子
组合 工作排列 完成时间
1 4-3-1-2 54
2 3-1-4-2 58
3 3-1-2-4 58
4 3-4-1-2 57
表 2  不同工作序列的计算
图 4  2号位和4号位执行交换变异操作
图 5  插入-倒转区
实验组 问题规模 最优解 实验组 问题规模 最优解
Car01 11×5 7 038 Car05 10×6 7 720
Car02 13×4 7 166 Car06 8×9 8 505
Car03 12×5 7 312 Car07 7×7 6 950
Car04 14×4 8 003 Car08 8×8 8 366
表 3  Car测试集的最优解比较
实验组 BRE ARE WRE
HBA PSOVNS HBSA SOS HSOS HBA PSOVNS HBSA SOS HSOS HBA PSOVNS HBSA SOS HSOS
Car01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Car02 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Car03 0 0 0 0 0 0.397 0.420 0.06 0 0 1.190 1.189 1.19 0 0
Car04 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Car05 0 0 0 0 0 0 0.039 0 0.018 0 0 0.389 0 0.375 0
Car06 0 0 0 0 0 0 0.076 0 0.114 0 0 0.764 0 0.764 0
Car07 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Car08 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
表 4  Car测试集的计算结果误差比较
实验组 问题规模 最优解 实验组 问题规模 最优解
Rec01 20×5 1 247 Rec23 30×10 2 011
Rec03 20×5 1 109 Rec25 30×15 2 513
Rec05 20×5 1 242 Rec27 30×15 2 373
Rec07 20×10 1 566 Rec29 30×15 2 287
Rec09 20×10 1 537 Rec31 50×10 3 045
Rec11 20×10 1 431 Rec33 50×10 3 114
Rec13 20×15 1 930 Rec35 50×10 3 277
Rec15 20×15 1 950 Rec37 75×20 4 951
Rec17 20×15 1 902 Rec39 75×20 5 087
Rec19 30×10 2 093 Rec41 75×20 4 960
Rec21 30×10 2 017 ? ? ?
表 5  Rec测试集的最优解比较
实验组 BRE ARE WRE
PSOVNS MPSO DBA HGA HSOS PSOVNS MPSO DBA HGA HSOS PSOVNS MPSO DBA HGA HSOS
Rec01 0.160 0 0 0 0 0.168 0.144 0.080 0.14 0 0.321 0.160 0.160 ? 0
Rec03 0 0 0 0 0 0.158 0.189 0.081 0.09 0 0.180 0.721 0.180 ? 0
Rec05 0.242 0.242 0.242 0 0 0.249 0.249 0.242 0.29 0 0.420 0.402 0.242 ? 0
Rec07 0.702 0 0 0 0 1.095 0.986 0.575 0.69 0 1.405 1.149 1.149 ? 0
Rec09 0 0 0 0 0 0.651 0.621 0.638 0.64 0 1.366 1.691 2.407 ? 0
Rec11 0.071 0 0 0 0 1.153 0.129 1.167 1.1 0 2.656 0.978 2.655 ? 0
Rec13 1.036 0.259 0.415 0.36 0 1.790 0.839 1.461 1.68 0.273 2.643 1.502 3.782 ? 0.777
Rec15 0.769 0.051 0.154 0.56 0 1.487 0.628 1.226 1.12 0.523 2.256 1.076 2.103 ? 1.020
Rec17 0.999 0 0.368 0.95 0 2.453 1.330 1.277 2.32 1.388 3.365 2.155 2.154 ? 2.154
Rec19 1.529 0.430 0.573 0.62 0.620 2.099 1.313 0.929 1.32 1.274 2.532 2.102 2.023 ? 2.099
Rec21 1.487 1.437 1.438 1.44 1.437 1.671 1.596 1.671 1.57 1.537 2.033 1.636 2.231 ? 2.033
Rec23 1.343 0.596 0.796 0.4 0.348 2.106 1.310 1.173 0.87 1.280 2.884 2.038 2.381 ? 3.050
Rec25 2.388 0.835 1.632 1.27 0.835 3.166 2.085 2.921 2.54 2.067 3.168 3.233 3.940 ? 2.850
Rec27 1.728 1.348 1.011 1.1 0.969 2.463 1.605 1.419 1.83 1.432 3.203 2.402 2.298 ? 2.570
Rec29 1.968 1.442 1.049 1.4 0.831 3.109 1.888 2.580 2.7 2.488 4.067 2.492 3.935 ? 2.970
Rec31 2.594 1.510 2.299 0.43 0.427 3.232 2.254 3.392 1.34 0.644 4.237 2.692 4.532 ? 0.920
Rec33 0.835 0 0.610 0 0 1.007 0.645 0.728 0.78 0.565 1.477 0.834 1.734 ? 0.835
Rec35 0 0 0 0 0 0.038 0 0.037 0 0 0.092 0 0.092 ? 0
Rec37 4.383 2.101 3.373 3.75 2.565 4.949 3.537 4.872 4.9 3.001 5.736 4.039 5.979 ? 3.555
Rec39 2.850 1.553 2.280 2.2 1.828 3.371 2.426 3.851 2.79 2.222 3.951 2.830 5.347 ? 3.380
Rec41 4.173 2.641 3.810 3.64 2.388 4.867 3.684 5.095 4.92 3.350 5.585 4.052 6.532 ? 3.770
表 6  Rec测试集的计算结果误差比较
图 6  调度结果最佳相对误差
图 7  调度结果平均相对误差
图 8  调度结果最差相对误差
图 9  Rec测试集的BRE、ARE、WRE平均值比较
实验组 问题规模 最优解 HGA HSOS TMIIG DWWO NEH IIGA
Ta010 20×5 1 108 1 345.5 1 108 1 377 1 377 1 127 1 377
Ta020 20×10 1 591 2 019.3 1 601 2 051 2 051 1 656 2 051
Ta030 20×20 2 178 2 956.3 2 205 2 979 2 979 2 257 2 979
Ta040 50×5 2 782 3 341.5 2 782 3 327.2 3 336.5 2 822 3 377.2
Ta050 50×10 3 065 4 279.0 3 140 4 286.2 4 286.2 3 267 4 301
Ta060 50×20 3 756 5 963.5 3 887 5 959 5 958.8 4 036 5 982
Ta070 100×5 5 322 6 542.5 5326 6 401.6 6 427.2 5 342 6 561
Ta080 100×10 5 845 8 255.3 5 898 8 148.8 8 141 8 186 8 263.6
Ta090 100×20 6 434 10 928.8 6 650 10 817.2 10 808.5 10 794 10 944.6
Ta100 200×10 10 675 15 869.1 10 798 15 410.8 15 412.2 15 803 15 754.4
Ta110 200×20 11 288 20 587.6 11 698 19 968.6 19 946.3 20 437 20 284
Ta120 500×20 26 457 49 545.6 26 780.8 47 402.4 47 183.2 49 092 48 483.4
表 7  Taillard测试集的计算结果比较
图 10  Taillard基准测试中的平均错误率
图 11  基于HSOS对其他算法的改进百分比
1 JOHNSON S M Optimal two- and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1 (1): 61- 68
doi: 10.1002/nav.3800010110
2 NAWAZ M, JR E E E, HAM I A heuristic algorithm for the m -machine, n -job flow-shop sequencing problem[J]. Omega, 1983, 11 (1): 91- 95
doi: 10.1016/0305-0483(83)90088-9
3 MARICHELVAM M K, PRABAHARAN T, YANG X S Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan[J]. Applied Soft Computing, 2014, 19 (1): 93- 101
4 MARICHELVAM M K, TOSUN ?, GEETHA M Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time[J]. Applied Soft Computing, 2017, 55 (1): 82- 92
5 LIU Y, YIN M, GU W An effective differential evolution algorithm for permutation flow shop scheduling problem[J]. Applied Mathematics and Computation, 2014, 248 (1): 143- 159
6 PADMANABAN K P, KUMAR R S, RAJKUMAR M Minimizing makespan and total flow time in permutation flow shop scheduling problems using modified gravitational emulation local search algorithm[J]. Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture, 2018, 232 (3): 534- 545
doi: 10.1177/0954405416645775
7 TSENG L Y, LIN Y T A hybrid genetic algorithm for no-wait flowshop scheduling problem[J]. International Journal of Production Economics, 2010, 128 (1): 144- 152
doi: 10.1016/j.ijpe.2010.06.006
8 CHENG M Y, PRAYOGO D Symbiotic organisms search: a new metaheuristic optimization algorithm[J]. Computers and Structures, 2014, 139 (1): 98- 112
9 TRAN D H, CHENG M Y, PRAYOGO D A novel multiple objective symbiotic organisms search (MOSOS) for time-cost-labor utilization tradeoff problem[J]. Knowledge-Based Systems, 2016, 94: 132- 145
10 EZUGWU E S, ADEWUMI A O Discrete symbiotic organisms search algorithm for travelling salesman problem[J]. Expert Systems with Applications, 2017, 87: 70- 78
11 EZUGWU E S, ADEWUMI A O, FR?NCU M E Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem[J]. Expert Systems with Applications, 2017, 77: 189- 210
12 CHENG M Y, PRAYOGO D, TRAN D H Optimizing multiple-resources leveling in multiple projects using discrete symbiotic organisms search[J]. Journal of Computing in Civil Engineering, 2016, 30 (3): 4015036
13 PANDA A, PANI S A symbiotic organisms search algorithm with adaptive penalty function to solve multi-objective constrained optimization problems[J]. Applied Soft Computing, 2016, 46: 344- 360
14 YU V F, REDI A A N P, YANG C, et al Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem[J]. Applied Soft Computing, 2017, 52: 657- 672
15 LI X, YIN M An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure[J]. Advances in Engineering Software, 2013, 55 (8): 10- 31
16 ABDEL-BASSET M, GUNASEKARAN M, EL-SHAH-AT D, et al A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem[J]. Future Generation Computer Systems, 2018, 85 (1): 129- 145
17 CARLIER J Ordonnancements à contraintes disjonctives[J]. RAIRO - Operations Research, 2011, 12 (4): 333- 350
18 REEVES C R A genetic algorithm for flowshop sequencing[J]. Computers and Operations Research, 1995, 22 (1): 5- 13
doi: 10.1016/0305-0548(93)E0014-K
19 TAILLARD E Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64 (2): 278- 285
doi: 10.1016/0377-2217(93)90182-M
20 TOSUN ?, MARICHELVAM M K Hybrid bat algorithm for flow shop scheduling problems[J]. International Journal of Mathematics in Operational Research, 2016, 9 (1): 125- 138
doi: 10.1504/IJMOR.2016.077560
21 LIN Q, GAO L, LI X, et al A hybrid backtracking search algorithm for permutation flow-shop scheduling problem[J]. Computers and Industrial Engineering, 2015, 85 (C): 437- 446
22 TASGETIREN M F, LIANG Y C, SEVKLI M, et al A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research, 2007, 177 (3): 1930- 1947
doi: 10.1016/j.ejor.2005.12.024
23 LIU B, WANG L, JIN Y H An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Transactions on Systems Man and Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man and Cybernetics Society, 2007, 37 (1): 18- 27
doi: 10.1109/TSMCB.2006.883272
24 LUO Q, ZHOU Y, XIE J, et al. Discrete bat algorithm for optimal problem of permutation flow shop scheduling [J]. The Scientific World Journal, 2014, 2014: 1–15.
25 DING J Y, SONG S, GUPTA J N D, et al An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem[J]. Applied Soft Computing, 2015, 30 (1): 604- 613
26 ZHAO F, LIU H, ZHANG Y, et al A discrete water wave optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2017, 91 (1): 347- 363
No related articles found!