Minimalizacja czasu cyklu wytwarzania na linii. Podejście genetyczne z ekspresją genów

• Autorzy: Pempera J. , Smutnicki C.

Warianty tytułu

EN

Minimizing cycle time on a flow line. Genetic approach with gene expression

• Języki publikacji: PL

Abstrakty

PL

Praca poświęcona jest deterministycznemu wariantowi problemu optymalizacji przebiegu cyklu wytwórczego w przepływowym systemie wytwarzania powtarzalnego z ograniczeniami składowania. Celem optymalizacji jest wyznaczenie harmonogramu cyklu, na który składają się kolejność wykonywania zadań oraz terminy czasowe rozpoczęcia zadań dla tej kolejności. W pracy przedstawiono modele problemu i pewne jego własności oraz zaproponowano nowej klasy algorytm genetyczny z tzw. ekspresją genów, wykorzystujący nadmiarową informację genetyczną pochodzącą nie tylko od rodziców, ale też od przodków. Przedstawiono wyniki obliczeniowe dla przykładów testowych Taillarda.

EN

This paper deals with the flow shop scheduling problem with no store policy to minimize cycle time criterion. Some properties and models of the problem are presented. We propose new genetic algorithms, with auxiliary gene expression method, which creates offspring using genetic information from both parents as well as from ancestors (grandfather, grandgrandfather). The proposed algorithm has been tested on the Taillard's benchmarks. The presented computational results provide superiority of proposed approach over classical GA.

Słowa kluczowe

PL

system przepływowy; czas cyklu; algorytm genetyczny

EN

flow shop scheduling; cycle time; genetic algorithm

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 189--199
• Opis fizyczny: Bibliogr. 11 poz., tab., rys.,wykr.

Twórcy

autor

Pempera J.

• Instytut Informatyki Automatyki i Robotyki Politechniki Wrocławskiej

autor

Smutnicki C.

• Instytut Informatyki Automatyki i Robotyki Politechniki Wrocławskiej

Bibliografia

• [1] Sabena B., Iyer S.K. : Improved genetic algorithm for the permutation flowshop scheduling problem . Computers & Operations Research, 31, 2004 , 593-606
• [2] Smutnicki C . : Some properties of scheduling problem with storage constraints . Zeszyty Naukowe A G H Automatyka, 34 , 1983, 223-232
• [3] Grabowski J ., Pempera J . : Sequencing of jobs in some production system . European Journal of Operational Research, 125 , 2000 , 535-550
• [4] Leistein R. : Flowshop sequencing with limited buffer storage. International Journal of Production Research, 28, 1990 , 2085-2100
• [5] Nowicki E. : The permutation flow shop with buffers: A tabu search approach. European Journal of Operational Research, 116, 1999 , 205-219
• [6] McCormick M . L ., Pinedo M . L ., Shenker S., Wolf B. : Sequencing in an assembly line with blocking to minimize cycle time . Operations Research, 37, 1989 , 925-935
• [7] Burkowski F. J . : Proximity and prioryty: applying a gene expresion algorithm to the Traveling Salesperson Problem. Parralel Computing, 30 , 2004 , 803-816
• [8] Michalewicz Z. : Genetic Algorithms + Data Structures = Evolution Programs . Berlin Heidelberg, Spinger- Verlag 1996
• [9] Goldberg D.E., L inge R. : Alleles, Loci and TSP . Proccedings of the First Internatonal Conference on Genetic Algorithms. Hillsdale, N J , Lawrence Erlbaum Associates, 1885 , 1 54-159
• [10] Allahverdi A ., Aldowaisan T . : No-wait flowshops with bicriteria of makespan and maximum lateness. European Journal of Operational Research, 152, 2004 , 132-142
• [11]Taillard E. : Benchmarks for basic scheduling problems. European Journal of Operational Research, 64 , 1993, 278-285