160 31,,, (makespan). π = {π 1, π 2,, π n }, p πi,j C πi,j π i j, PFSP [1] : min : C max (π), (1) C max (π) C πi,j, i = 2, 3,, n; j = 2, 3,, m, C π1,1

Size: px

Start display at page:

Download "160 31,,, (makespan). π = {π 1, π 2,, π n }, p πi,j C πi,j π i j, PFSP [1] : min : C max (π), (1) C max (π) C πi,j, i = 2, 3,, n; j = 2, 3,, m, C π1,1"

赛匾施
5 years ago
Views:

1 DOI: /CTA Control Theory & Applications Vol. 31 No. 2 Feb. 2014,, (, ) :,. 4 :., ;, ;, ;,.,,.,. : ; ; ; : TP18 : A A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem ZHENG Xiao-long, WANG Ling, WANG Sheng-yao (Department of Automation, Tsinghua University, Beijing , China) Abstract: To solve the permutation flow-shop scheduling problem (PFSP), we propose a novel hybrid discrete fruit fly optimization algorithm (HDFOA). Each generation of evolution in the algorithm contains four search stages: smell-based search, vision-based search, co-evolutionary search and annealing procedure. In the smell-based search stage, an insertion operator is adopted to produce neighbors. In the vision-based search stage, the individuals are replaced by their best neighbors. In the co-evolutionary search stage, the guiding individuals are produced based on the differential information among fruit flies. In the annealing procedure, the best guiding fruit flies are accepted according to certain acceptance probabilities for updating the population. Moreover, the effect from parameter setting is analyzed by using the experiment design method, and a combination of suitable parameter values is determined. Finally, simulation results and comparisons based on the benchmark testing sets demonstrate the effectiveness and robustness of the proposed algorithm. Key words: permutation flow-shop scheduling; discrete fruit fly optimization algorithm; co-evolution; hybrid algorithm 1 (Introduction) (permutation flow-shop scheduling problem, PFSP) [1], NP-hard [2],. PFSP. [3],.,,., PFSP, [4] [5] [6 8] [9] [10] [11]. (fruit fly optimization algorithm, FOA) [12].,,., FOA [12] [13] [14] [15]., FOA. PFSP (hybrid discrete FOA, HDFOA).,,.,,. 2 (Problem statement) PFSP [1] : n m,,. : ; : wangling@tsinghua.edu.cn; Tel.: : (2013CB329503); ( ).

2 160 31,,, (makespan). π = {π 1, π 2,, π n }, p πi,j C πi,j π i j, PFSP [1] : min : C max (π), (1) C max (π) C πi,j, i = 2, 3,, n; j = 2, 3,, m, C π1,1 = p π1,1, s.t. C πi,1 =C πi 1,1+ p πi,1, i=2, 3,, n, C π1,j =C π1,j 1+ p π1,j, j =2, 3,, m, C πi,j =max{c πi 1,j, C πi,j 1}+p πi,j, i = 2, 3,, n; j = 2, 3,, m, C max (π). 3 (FOA) (2).,,,. [12] : NP ,. 5., ;, 2. 4 PFSP HDFOA(HDFOA for PFSP) HDFOA FOA:, ;, PFSP, NAWAZ-ENSCORE-HAM(NEH) [16] ;, ;,,. 4.1 (Encoding), HDFOA n,.. 4, (2, 1, 4, 3) 2, 1 4, (Population initialization), 10% NEH [16], 90%. 4.3 (Smell and vision-based search) FOA. PFSP, [4]., HDFOA insert(r, k), r k, 1. 1 insert(r, k) Fig. 1 Insert operator insert(r, k), r, makespan k.,, SN.,., HDFOA : : Procedure FOR i = 1 to NP // Ff i FOR j = 1 to SN // nff j r; insert(r, k ) nff j ; END FOR BnFf; Ff i BnFf; END FOR 4.4 (Co-evolution scheme),,,,.,,. Ff i, Ff r1 Ff r2, Ff i F Ff r1, Ff r2,. : Ff i = Ff i F (Ff r1 Ff r2 ), (3) (3) : 1 F Ff r1, Ff r2 : i = F (Ff r1 Ff r2 )

3 2 : 161 { Ffr1,j Ff i,j = r2,j, rand( ) < F, 4.5 (Annealing scheme) (4) 0,, PFSP rand( ) (0, 1)., HDFOA, 2, Ff i = Ff i i Ff i,ip f (j) = Ff i,j, (5). : IP f (j) Ff i i, j. : Ff i = (π 1, π 2,, π n ), IP = (1, 2,, n), i, IP t = IP+ i. IP t, IP f = (I p1, I p2,, I pn ), I pk = j, rank 1 (j) = k.,.,,. 5. Ff i = (3, 1, 5, 4, 2), Ff r1 = (2, 4, 3, 1, 5), Ff r2 = (3, 1, 2, 5, 4), Ff r1, Ff r2 ( 1, 3, 1, 4, 1). (0, 1) 5 (0.52, 0.15, 0.22, 0.18, 0.76) F = 0.5, 0.5 i = (0, 3, 1, 4, 0). Ff i IP = (1, 2, 3, 4, 5). i, IP t = IP + i = (1, 5, 4, 0, 5)., IP f = (2, 5, 3, 1, 4), rank 1 = (4, 1, 3, 5, 2), Ff i = Ff i,rank 1 (j) = (4, 3, 5, 2, 1). 2..,, f b f w, P 0, T 0 = (f w f b )/ ln P 0.. min{1, exp( D/T g )} > rand[0, 1],. D, T g g.., T g+1 = λ T g, λ = HDFOA (Flowchart of HDFOA) PFSP HDFOA 3. 3, HDFOA 4 :. (a) i = F (Ff r1 Ff r2 ) 3 HDFOA Fig. 3 Flowchart of HDFOA (b) Ff i = Ff i i 2 Fig. 2 Generating scheme of guiding individual 4.7 (Analysis of computational complexity) HDFOA O(n 2 ). NP SN, O(NP SN n 2 ).

4 SN, O(NP SN). NP,, SN, O(SN NP n log n)., HDFOA. 5 (Simulation test and comparisons) Car Rec 29, Intel Core2(TM) Q9550(2.83 GHz), C++.,. 5.1 (Investigation of parameters setting) [10], HDFOA NP = 2n, 300., HDFOA 3 : SN F P 0. Rec17 (design of experiment, DOE) [17]. 4, 1, L 16 (4 3 ). 20, (average, AVG). 2.,, 3,, 4. 3, SN, SN, SN. P 0,, P 0. F,.,, : F = 0.9, SN = 5, P 0 = (c) P 0 4 Fig. 4 Factor level trend of the parameters 1 Table 1 Parameter values F SN P AVG Table 2 Orthogonal array and AVG values F N SN P0 AVG Table 3 Response value (a) F (b) SN F SN P

5 2 : (Results and comparisons), HDFOA PFSP (hybrid genetic algorithm, HGA) [4] OSA (Osman s simulated annealing) [5] (hybrid differential evolution, HDE) [10]., HDFOA DFOA. 20, 4 Table 4 Comparison of results 4, BRE, ARE C, SD 20. 4, HDFOA Car 100%, Rec., HDFOA,, HDE 25%. HDFOA [4 5, 10]. HDFOA DFOA HDE [10] OSA [5] HGA [4] n m c BRE ARE SD CPU/s BRE ARE SD BRE ARE SD BRE ARE SD BRE ARE SD Car Car Car Car Car Car Car Car Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec Rec , DFOA, HDFOA,.,., HDFOA HDE [10] 300, HGA [4] m n, OSA [5] 300 n (n 1).,, HDFOA [4 5]. 4, HDFOA 31.6 s, 75 20

6 s CPU., HDFOA. 5 HDFOA Rec17., HDFOA,,. 5 HDFOA Fig. 5 The convergence curve of HDFOA 6 (Conclusions) PFSP.,.,,. [18]. (References): [1]. [M]. :, (WANG Ling. Shop Scheduling with Genetic Algorithms [M]. Beijing: Tsinghua University Press, 2003.) [2] GAREY M R, JOHNSON D S, SETHY R. The complexity of flowshop and job-shop scheduling [J]. Mathematics of Operations Research, 1976, 1(2): [3] PINEDO M L. Scheduling: Theory, Algorithms, and Systems [M]. Berlin: Springer, [4] WANG L, ZHENG D Z. An effective hybrid heuristic for flow-shop scheduling [J]. International Journal Advanced Manufacturing Technology, 2003, 21(1): [5] OSMAN I H, POTTS C N. Simulated annealing for permutation flowshop scheduling [J]. Omega, 1989, 17(6): [6] NOWICKI E, SMUTNICKI C. A fast tabu search algorithm for the permutation flow-shop scheduling [J]. European Journal of Operational Research, 1996, 91(1): [7] GRABOWSKI J, WODECKI M. A very fast tabu search algorithm for the permutation flow-shop problem with makespan criterion [J]. Computers & Operations Research, 2004, 31(11): [8],,. FSP Block TS [J]., 2007, 22(3): (JIN Feng, SONG Shiji, WU Chen. Fast TS algorithm based on block properties of FSP [J]. Control and Decision, 2007, 22(3): ) [9],,,. [J]., 2009, 35(3): (ZHANG Changsheng, SUN Jigui, YANG Qingyun, et al. A hybrid algorithm for flow-shop scheduling problem [J]. Acta Automatica Sinica, 2009, 35(3): ) [10] QIAN B, WANG L, HU R, et al. A hybrid differential evolution for permutation flow-shop scheduling [J]. International Journal Advanced Manufacturing Technology, 2008, 38(7/8): [11],,. [J]., 2011, 28(10): (PAN Yuxia, PAN Quanke, LI Junqing. Shuffled frog-leaping algorithm for multi-objective no-wait flowshop scheduling [J]. Control Theory & Applications, 2011, 28(10): ) [12] PAN W T. A new fruit fly optimization algorithm: taking the financial distress model as an example [J]. Knowledge-Based Systems, 2012, 26(2): [13] LI H, GUO S, LI C, et al. A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm [J]. Knowledge-Based Systems, 2013, 37(1): [14] LIN S M. Analysis of service satisfaction in web auction logistics service using a combination of fruit fly optimization algorithm and general regression neural network [J]. Neural Computing & Applications, 2013, 22(3/4): [15] HAN J, WANG P, YANG X. Tuning of PID controller based on fruit fly optimization algorithm [C] //Proceedings of IEEE International Conference on Mechatronics and Automation. Washington: IEEE, 2012: [16] NAWAZ M, ENSCORE J, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem [J]. Omega, 1983, 11(1): [17] MONTGOMERY D C. Design and Analysis of Experiments [M]. Hoboken: John Wiley and Sons, [18],,,. [J]., 2012, 29(12): (WANG Ling, ZHOU Gang, XU Ye, et al. An artificial bee colony algorithm for solving hybrid flow-shop scheduling problem with unrelated parallel machines [J]. Control Theory & Applications, 2012, 29(12): ) : (1988 ),,,, zhengxl11@mails.tsinghua.edu.cn; (1972 ),,,,, wangling@tsinghua.edu.cn; (1988 ),,,, wangshengyao@tsinghua.org.cn.

{ machines, HFSP UPM), ei,j,k = s i,j,k + t i,j,k, i = 1, 2,, n, (5), 3 j = 1, 2,, S, k = 1, 2,, m j,, e. i,j,k s i,j+1,k,. i = 1, 2,, n, j =

{ machines, HFSP UPM), ei,j,k = s i,j,k + t i,j,k, i = 1, 2,, n, (5), 3 j = 1, 2,, S, k = 1, 2,, m j,, e. i,j,k s i,j+1,k,. i = 1, 2,, n, j = 29 12 2012 12 Control Theory & Applications Vol. 29 No. 12 Dec. 2012 : 1000 8152(2012)12 1551 07,,, (, 100084) :,,. 3, ;,.,,.,. : ; ; ; : TP18 : A An artificial bee colony algorithm for solving hybrid