A memetic algorithm combined particle swarm optimization with simulated annealing and its application on multiprocessor scheduling problem

• Autorzy: Zhao F. , Tang J.

Warianty tytułu

PL

Algorytm memetyczny w optymalizacji szeregowania zadań w systemie wieloprocesorowym - optymalizacja PSO i algorytm symulowanego wyżarzania

• Języki publikacji: EN

Abstrakty

EN

A memetic algorithm, which combines globe search with local search strategies, is presented to deal with the multiprocessor scheduling problem(MSP). During the processes, an improved particle swarm optimization is employed to execute the globe search optimization, and the simulated annealing is adopted to improve the quality of the selected candidates based on a certain strategy. Simulations show that the proposed method performs well on the globe exploration. Experimental results based on MSP show that the algorithm achieved an efficient makespan.

PL

Przedmiotem artykułu jest algorytm memetyczny do optymalizacji szeregowania zadań w systemie wieloprocesorowym (ang. Multiprocessor Scheduling Problem), łączący w sobie strategie wyszukiwania globalnego i lokalnego. W celu optymalizacji wyszukiwania globalnego zastosowano ulepszoną metodę optymalizacji PSO (ang. Particle Swarm Optimization) oraz algorytm symulowanego wyżarzania (ang. Simulated Annealing) w celu poprawy jakości wybranych elementów.

Słowa kluczowe

EN

memetic algorithm; particle swarm optimization (PSO); simulated annealing; multiprocessor scheduling problem

PL

algorytm memetyczny; PSA; symulowane wyżarzanie; optymalizacja szeregowania zadań w systemie wieloprocesorowym

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 11a
• Strony: 292--296
• Opis fizyczny: Bibliogr. 17 poz., tab., rys.

Twórcy

autor

Zhao F.

autor

Tang J.

• Lanzhou University of Technology,

Bibliografia

• [1] Antonini, P. Ippoliti, G. Longhi, Learning control of mobile robots using a multiprocessor system, Control Engineering Practice, 11(2006), No. 14, 1279-1295
• [2] Nakata, Toshiyuki Tanabe, Norio Onozuka, etal. MULTIPROCESSOR SYSTEM FOR MODULAR CIRCUIT SIMULATION. IEEE International Conference on Computer- Aided Design: ICCAD-87 - Digest of Technical Papers. (1987), Santa Clara, CA, USA: IEEE
• [3] Garey M. R., D.S. Johnson, Computers and Intractability, New York: W. H. Freeman and Company, 1979
• [4] Piotr Switalski, Franciszek Seredynski. Generalized Extremal Optimization for Solving Multiprocessor Task Scheduling Problem, Lecture Notes in Computer Science, (2008), No. 5361, 161-169
• [5] Mohammad Reza Bonyadi, Mohsen Ebrahimi Moghaddam. A Bipartite Genetic Algorithm for Multi-processor Task Scheduling. Int J Parallel Prog, (2009), No. 37, 462-487
• [6] P Visalakshi, S N Sivanandam. Dynamic Task Scheduling with Load Balancing using Hybrid Particle Swarm Optimization, Int. J. Open Problems Compt. Math., 3(2009), No. 2, 475-488
• [7] ZHANG Chang-Sheng, SUN Ji-Gui, OUYANG Dan-Tong, ZHANG Yong-Gang, A Self-Adaptive Hybrid Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem, CHINESE JOURNAL OFCOMPUTERS, 11(2009), No. 32, 2137-2146
• [8] Pablo Moscato, Carlos Cotta, A gentle introduction to memetic algorithms. (1989), 1-60
• [9] Yew Soon Ong, Andy J. Keane, Meta-Lamarckian Learning in Memetic Algorithms, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2(2004), No. 8, 99-110
• [10] F. Choong, S. Phon-Amnuaisuk, M. Y. Alias, Metaheuristic methods in hybrid flow shop scheduling problem, Expert Systems with Applications, (2011), No. 38, 10787-10793
• [11] Ruey-Maw Chen, Der-Fang Shiau, Shih-Tang Lo, Combined Discrete Particle Swarm Optimization and Simulated Annealing for Grid Computing Scheduling Problem, (2009), 242-251
• [12] James Kennedy, Russell Eberhart, Particle Swarm Optimization, IEEE International Conference on Neural Networks, (1995), No. 4, 1942-1948
• [13] Shi Y. H., Eberhart R. C., A modified particle swarm optimizer, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, (1998), 69-73
• [14] Zhao Fuqing, T.Jianxin, Wang Jizhe, Wei Chunmiao, An Improved PSO Algorithm with Decline Disturbance Index, Journal of Computers, (2011), No. 6, 691-697
• [15] M. Nawaz, E. Enscore, I. Ham, A heuristic algorithm for the machine,n-job flow-shop sequencing problem, Omega, (1983), No. 11, 1191-1195
• [16] ZHANG Xiao-dong, LI Xiao-ping, WANG Qian, YUAN Yingchun, Hybrid particle swarm optimization algorithm for cost minimization in service-workflows with due dates, Journal on Communications, 8(2008), No. 29, 87-99
• [17] S. N. Sivanandam, P. Visalakshi, A. Bhuvaneswari, Multiprocessor Scheduling Using Hybrid Particle Swarm Optimization with Dynamically Varying Inertia, International Journal of Computer Science & Applications, 3(2007), No. 4, 95-106