Genetyczny algorytm równoległy dla pewnego permutacyjnego problemu przepływowego

• Autorzy: Bożejko W. , Wodecki M.

Warianty tytułu

EN

Parallel genetic algorithm for some permutation flow-shop problem

• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrujemy permutacyjny problem przepływowy z minimalizacją sumy czasów zakończenia zadań, w literaturze oznaczany przez F‌m‌Csum. Należy on do klasy problemów silnie NP-trudnych. Przedstawiamy algorytm równoległy jego rozwiązywania oparty na metodzie algorytmu genetycznego, w którym wykorzystano ideę zrównoleglenia opartą na migracyjnym modelu wyspowym. Wykonano wiele obliczeń na reprezentatywnej grupie przykładów zamieszczonych w pracy Taillarda. Wyniki obliczeniowe porównano z najlepszymi znanymi w literaturze. Dla algorytmu równoległego uzyskano nie tylko przyspieszenie czasu obliczeń, ale również poprawę jakości i stabilności (dyspersji) rozwiązań.

EN

In this paper we consider the permutation flow-shop sequencing problem with the objective of minimizing the sum of task's flowtime, known as F‌m‌Csum in literature. We present parallel genetic algorithm based on the island model of migration. By computer simulations on Taillard benchmarks and the best known results from literature we obtained not only acceleration of the computation's time, but better quality and stability of the results too.

Słowa kluczowe

PL

genetyczny algorytm równoległy

EN

parallel genetic algorithm

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 51--57
• Opis fizyczny: Bibliogr. 16 poz., tab.

Twórcy

autor

Bożejko W.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

autor

Wodecki M.

• Instytut Informatyki, Uniwersytet Wrocławski

Bibliografia

• [1] Belding T.C.: The distributed genetic algorithm revisited. Proceedings of the Sixth International Conference on Genetic Algorithms, Eschelman L. (Ed.), Morgan Kaufmann, 1995, 114-121
• [2] Bożejko W., Wodecki M.: Solving the flow shop problem by parallel tabu search. IEEE Computer Society 2002, PR01730 ISBN 0-7695-1730-7, 189-194
• [3] Bożejko W., Wodecki M.: Parallel algorithm for some single machine scheduling problems. Automatyka, z. 134, 2002, 81-90
• [4] Bożejko W., Wodecki M.: Permulacyjny problem przepływowy. Algorytmy równoległe symulowanego wyżarzania. Automatyka, z. 134, 2002, 90-101
• [5] Bubak M., Sowa M.: Object-oriented implementation of parallel genetic algorithms, [in:] High Performance Cluster Computing: Programming and Applications, Buyya R. (Ed.), vol. 2, Prentice Hall 1999, 331-349
• [6] Cant’ u-Paz E.: Implementing fast and flexible parallel genetic algorithms’, [in:] Practical handbook of genetic algorithms, Chambers L.D. (Ed.), vol. III, CRC Press 1999, 65-84
• [7] Chalermwat P., El-Ghazawi T., LeMoigne J.: 2-phase GA-based image registration on parallel clusters. Future Generation Computer Systems 17, 2001, 467-476
• [8] Chipperfield A., Fleming P.: Parallel genetic algorithms. Parallel and Distributed Computing Handbook, Zomaya A.Y. (Ed.), McGraw-Hill 1996, 1118-1143
• [9] Grabowski J., Pempera J.: New block properties for the permutation flow-shop problem with application in TS. Journal of Operational Research Society, 52, 2001, 210-220
• [10] Holland J.H.: Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press 1975
• [11] Liu J.: A new heuristic algorithm for csum flowshop scheduling problems. Personal Comm. 1997
• [12] Nowicki E., Smutnicki C.: A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91, 1996, 160-175
• [13] Reeves C.R., Yamada T.: Solving the Csum Permutation Flowshop Scheduling Problem by Genetic Local Search. IEEE International Conference on Evolutionary Computation, 1998, 230-234
• [14] Taillard E.: Benchmarks for basic scheduling problems. EJOR 64, 1993, 278-285
• [15] Wang C., Chu C., Proth J.: Heuristic approaches for nJm/F/SCi scheduling problems. EJOR, 1997, 636-644
• [16] Wodecki M., Bożejko W.: Solving the flow shop problem by parallel simulated annealing. Lecture Notes in Computer Science, No. 2328, Springer Verlag 2002, 236-247