Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2020, Vol. 54 Issue (4): 712-721    DOI: 10.3785/j.issn.1008-973X.2020.04.010
Computer Technology, Inf ormation Engineering     
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
Download: HTML     PDF(1091KB) HTML
Export: BibTeX | EndNote (RIS)      

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)     
Received: 07 April 2019      Published: 05 April 2020
CLC:  TP 391  
  TU 723  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Xuan QIN
Zi-han FANG
Zhao-xin ZHANG
Cite this article:

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.

URL:

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


混合共生生物搜索算法求解置换流水车间调度问题

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


关键词： 置换流水车间调度,  共生生物搜索算法,  局部搜索策略,  NEH启发式算法,  混合共生生物搜索（HSOS） 
Fig.1 Hybrid SOS algorithm flow chart
Fig.2 Random+NEH initial population
Fig.3 Representation of largest rank value
构件 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
Tab.1 Example of permutation flow shop scheduling problem
组合 工作排列 完成时间
1 4-3-1-2 54
2 3-1-4-2 58
3 3-1-2-4 58
4 3-4-1-2 57
Tab.2 Calculation of different work sequences
Fig.4 2 and 4 sites execute swap mutation
Fig.5 Insert-reversed block
实验组 问题规模 最优解 实验组 问题规模 最优解
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
Tab.3 Comparison for optimization results of Carliar benchmark
实验组 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
Tab.4 Error comparison for results of Carlier benchmark
实验组 问题规模 最优解 实验组 问题规模 最优解
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 ? ? ?
Tab.5 Comparison for optimization results of Rec benchmark
实验组 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
Tab.6 Error comparison for results of Rec benchmark
Fig.6 Best relative error of scheduling result
Fig.7 Average relative error of scheduling result
Fig.8 Worst relative error of scheduling result
Fig.9 Comparison of BRE，ARE，and WRE averages of Rec benchmark
实验组 问题规模 最优解 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
Tab.7 Comparison for results of Taillard benchmark
Fig.10 Average error of Taillard benchmark
Fig.11 Percentage improvement based on HSOS for other algorithms
[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!