{ 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 =

Transcription

1 Control Theory & Applications Vol. 29 No. 12 Dec : (2012) ,,, (, ) :,,. 3, ;,.,,.,. : ; ; ; : TP18 : A An artificial bee colony algorithm for solving hybrid flow-shop scheduling problem with unrelated parallel machines WANG Ling, ZHOU Gang, XU Ye, WANG Sheng-yao (Department of Automation, Tsinghua University, Beijing , China) Abstract: According to the characteristics of the hybrid flow-shop scheduling problem with unrelated parallel machines (HFSP UPM), we design a permutation-based method for encoding and decoding, and propose an effective artificial bee colony (ABC) algorithm. At the employed bee phase and the onlooker bee phase, three effective neighbor-search approaches are used to enrich the searching behavior; at the scout bee phase, the population is updated by using random search to enhance the diversity of population. Based on Taguchi method for experiment design (DOE), the effect from the parameter-setting is investigated and suitable parameter values are suggested. Numerical simulation based on benchmark examples and comparisons with the existing typical algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Key words: hybrid flow-shop scheduling; unrelated parallel machine; artificial bee colony; design of experiment 1 (Introduction) (hybrid flow-shop scheduling problem, HFSP) [1 2],, HFSP. HFSP,,, (nondeterministic polynomial hard, NP-hard)., HFSP. HFSP 3 : [3], ; [4], ; [5],,. HFSP [6] [7].,,.,., HFSP, (genetic algorithm, GA) [8] [9] [10] [11] [12] (artificial immune system, AIS) [13]. (artificial bee colony, ABC) [14],, [15] [16]., Pan [17], ; Li [18], ABC. (HFSP with unrelated parallel : ; : : ( , ); (2009CB320602).

2 { 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 = 1, 2,, S 1, (6). k = 1, 2,, m j, k = 1, 2,, m j+1, 2 (HFSP n x i,l s i,1,k n x i,l+1 s i,1,k, UPM) (7) 2.1 (Problem statement) i = 1, 2,, n, l = 1, 2,, n 1, HFSP UPM [5] : n k = 1, 2,, m 1, S, n x i,l1 y i,j,k e i,j,k, n, x i,l2 y i,j,k s i,j,k +(1 n x i,l2 y i,j,k )L, (8),, l 1, l 2 = 1, 2,, n, l 1 l 2,, j = 1, 2,, S, k, k = 1, 2,, m j, {,, 1, i l,. 1. x i,l = (9) 0,, { 1, i j k, y i,j,k = 0,, 1 HFSP UPM Fig. 1 An example of HFSP UPM 2.2 (Mathematical formulation) ; ; ; [19]. J i, i = 1, 2,, n; m j, j = 1, 2,, S; t i,j,k J i j k ; s i,j,k e i,j,k J i j k ; C i J i ; C max = max{c 1, C 2,, C n } ; L. HFSP UPM : min C max (1) n s.t. x i,l = 1, l = 1, 2,, n, (2) n x i,l = 1, i = 1, 2,, n, (3) l=1 m j y i,j,k = 1, k=1 (4) i = 1, 2,, n, j = 1, 2,, S, (10) : (1) ; (2) ; (3) ; (4) ; (5) ; (6) ; (7) 1 ; (8),, L. 3 (The artificial bee colony algorithm) [14].,,., P i = f i / Psize f j, : f i i j=1 ( 1/C max ), P size,.,,. Limit,,

3 12 : ABC2 [18]. C i,j 1. j = 1, C i,j 1 = 0; 3 J i max(r k, C i,j 1 ) + t i,j,k J i, J i j k ; 4 j = j + 1; HFSP UPM., 6, 1. {2, 4, 5, 1, 6, 3} 3, 14, Table 1 Processing time of problem 1 2 ABC Fig. 2 Framework of the ABC algorithm 4 HFSP UPM ABC (ABC for HFSP UPM) HFSP UPM, ABC,. 4.1 (Encoding and decoding scheme),,, 1., 6HFSP UPM, {2, 4, 5, 1, 6, 3} 1, 2, 4 5, 3.,,. HFSP UPM :.,, : 1 (j = 1),, j(j > 1),,,., [20], : 1 j = 1; 2 j J i k, k r k J i j Fig. 3 The Gantt chart of the solution 4.2 (Population initialization) ABC s i, i = 1, 2,, P size.,. 4.3 (Exploitation search operators), 3, Scheme#1, Scheme#2 Scheme#3. 3 p 1, p 2 1 p 1 p 2. Scheme#1,.

4 Scheme#2 j(j > 1),,. j, j j., 21 5, 4, 13. Scheme#3 j(j > 1),,. j, j j. Fig. 4 4 Scheme#2 Solution after using Scheme#2 4.4 (Employed bee phase) ABC, s i, s new s i, ; (Onlooker bee phase),, 4.3 3,. 4.6 (Scout bee phase) ABC, Limit,,,,. 4.7 HFSP UPM ABC (Procedure of ABC for HFSP UPM) 1, ; 2, ; 3, ; 4, ; 5? ; 2.,,.,. 5 (Simulation test and comparisons) : 1 12 [21], 3, 3, 2, 4,, 2, M1 M9. 2 [22], 3, 3, 2, 2,, 3, M1 M10. C++, 3.21 GB RAM/2.83 GHz. [21], Table 2 Processing time of instance M1 M2 M3 M4 M5 M6 M7 M8 M (Investigation of parameters setting) ABC : P size, Scheme#1 p 1, Scheme#2 p 2, Limit. 1 [23] 4. 4, 4. 50, 3000, 50 AVG. L 16 (4 4 )

5 12 : 1555, AVG Table 3 Processing time of instance M1 M2 M3 M4 M5 M6 M7 M8 M9 M Table 4 Parameter values P size p p Limit , , p 1, p 1, p 1 Scheme#11, 1. Limit, Limit = 15, Limit,.,.,, : P size = 40, p 1 = 0.5, p 2 = 0.3, Limit = Table 6 Response value P size p 1 p 2 Limit AVG Table 5 Orthogonal array and AVG values (a) P size Psize p 1 p 2 Limit AVG (b) p 1 (c) p 2

6 (d) Limit 5 Fig. 5 Response value versus factor level 5.2 (Results and comparisons) 1, ABC AIS [24] GA [21] (DE) [25], [24] AIS, 10, Table 7 Comparison with AIS, GA and DE for instance AIS 27 GA DE ABC , ABC, 23, 6., ABC 108,., ABC., 7., ABC 50.,. 7 Fig. 7 Convergence curves of the best and average values 2, ABC GA [22] DE [25], [22] GA, [25] DE 10. ABC Table 8 Comparison with AIS, GA and DE for instance GA 347 DE ABC , ABCGA DE, ABC %, ABC. 6 (Conclusions),,,,,,. HFSP ABC. (References): 6 1 Fig. 6 Gantt chart of the optimal solution [1]. [M]. :, (WANG Ling. Shop Scheduling with Genetic Algorithms [M]. Beijing: Tsinghua University Press, 2003.) [2] SALVADOR M S. A solution of a special class of flow shop scheduling problems [C] //Proceedings of the Symposium on the Theory of Scheduling and Its Applications. Berlin: Springer-Verlag, 1973: [3] ORTMANN M C, VIGNIER A, DARDILHAC D, et al. Branch and bound crossed with GA to solve hybrid flowshops [J]. European Journal of Operational Research, 1998, 107(2): [4] SOEWANDI H, ELMAGHRABY S E. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan [J]. IIE Transactions, 2003, 35(5):

7 12 : 1557 [5] FIGIELSKA E. A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flow shop with additional resources [J]. Computers & Industrial Engineering, 2009, 56(1): [6],. HFS [J]., 2006, 21(4): (XUAN Hua, TANG Lixin. Lagrangian relaxation algorithm for realtime hybrid flow-shop scheduling with no-wait in process [J]. Control and Decision, 2006, 21(4): ) [7] RIANE F, ARTIBA A, ELMAGHRABY S E. Sequencing a hybrid two-stage flow shop with dedicated machines [J]. International Journal of Production Research, 2002, 40(17): [8] XIAO W, HAO P, ZHANG S, et al. Hybrid flow shop scheduling using genetic algorithms [C] //Proceedings of the 3rd World Congress on Intelligent Control and Automation. Shanghai: IEEE, 2000: [9] LOW C. Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines [J]. Computers & Operations Research, 2005, 32(8): [10] WANG X, TANG L. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers [J]. Computers & Operations Research, 2008, 36(3): [11] ALAYKYRAN K, ENGIN O, DOYEN A. Using ant colony optimization to solve hybrid flow shop scheduling problems [J]. International Journal of Advanced Manufacturing Technology, 2007, 35(5/6): [12] TSENG C T, LIAO C J. A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks [J]. International Journal of Production Research, 2008, 46(17): [13] ENGIN O, DOYEN A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system [J]. Future Generation Computer Systems, 2004, 20(6): [14] KARABOGA D. An idea based on honey bee swarm for numerical optimization [EB/OL]. Turkey: Computer Engineering Department, Erciyes University, [15] KARABOGA D, AKAY B. Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems [J]. Foundations of Fuzzy Logic and Soft Computing, 2007, 4529(1): [16] ZHANG C S, OUYANG D T, NING J X. An artificial bee colony approach for clustering [J]. Expert Systems with Applications, 2010, 37(7): [17] PAN Q K, TASGETIREN M F, SUGANTHAN P N, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem [J]. Information Sciences, 2010, 181(12): [18] LI J Q, PAN Q K, GAO K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems [J]. International Jounal of Advanced Manufacturing Technology, 2011, 55(1/2/3/4): [19],,,. [J]., 2011, 38(1): 1 8. (WANG Ling, ZHOU Gang, XU Ye, et al. Advances in the study on hybrid flow-shop scheduling [J]. Control and Instrument in Chemical Industry, 2011, 38(1): 1 8.) [20] BRAH S A, LUAN L L. Heuristics for scheduling in a flowshop with multiple processors [J]. European Journal of Operational Research, 1999, 113(1): [21],,. Flow-Shop [J]., 2009, 45(30): (ZHOU Huiren, TANG Wansheng, WEI Yinghui. Optimize flexible flow-shop s cheduling using genetic algorithm [J]. Computer Engineering and Applications, 2009, 45(30): ) [22],,. [J]., 2005, 27(5): (CUI Jianshuang, LI Tieke, ZHANG Wenxin. Hybrid flowshop scheduling model and its genetic algorithm [J]. Journal of University of Science and Technology Beijing, 2005, 27(5): ) [23] MONTGOMERY D C. Design and Analysis of Experiments [M]. Arizona: John Wiley & Sons, [24] LIU F, ZHANG X P, ZOU F X, et al. Immune clonal selection algorithm for hybrid flow-shop scheduling problem [C] //Proceedings of Chinese Control and Decision Conference. Guilin: IEEE, 2009: [25] XU Y, WANG L. Differential evolution algorithm for hybrid flowshop scheduling problem [J]. Journal of Systems Engineering and Electronics, 2011, 22(5): : (1972 ),,,,, wangling@tsinghua.edu.cn; (1987 ),,,, g-zhou09@mails.tsinghua.edu.cn; (1987 ),,,, xuye05@mails.tsinghua.edu.cn; (1988 ),,,, wangshengyao@tsinghua.org.cn.