Algorytm genetyczny dla problemu gniazdowego z ograniczeniem bez czekania

• Autorzy: Makuchowski M.

Warianty tytułu

EN

Genetic algorithm for no-wait job shop problem

• Języki publikacji: PL

Abstrakty

PL

W pracy analizuje się problem gniazdowy z ograniczeniem bez czekania z kryterium optymalizacji będącym terminem zakończenia wykonywania wszystkich zadań. Przedstawia się klasę rozwiązań superaktywnych oraz jej rozszerzenie - klasę rozwiązań pseudoaktywnych. Na bazie omówionych klas rozwiązań proponuje się dwa algorytmy genetyczne. Jakość proponowanych algorytmów ocenia się na podstawie przeprowadzonych badań numerycznych, wykorzystując literaturowe przykłady testowe.

EN

The paper deals with the no-wait job shop scheduling problem with the makespan criterion. The new class of so called "super-active" solution is introduced. Two genetic algorithms SGA and PGA, based on aforementioned class, and the class of "pseudo-active" schedules, are proposed. These algorithms are tested on "easy" and "hard" benchmarks well-know in literature. Results of computational experiments are given and they are compared with results yielded by the best genetic algorithm discusses in literature.

Słowa kluczowe

PL

problem gniazdowy; ograniczenie bez czekania; rozwiązania superaktywne; rozwiązania pseudoaktywne; algorytm genetyczny

EN

no-wait job shop problem; super active solutions; pseudo active solutions; 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: 127--137
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Makuchowski M.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Wismer D. A .: Solution of the flowshop scheduling-problem with no intermediate queues. Operations Research , 20 , 1972 , 689
• [2] Hall N. , Sriskandarajah C.: A survey of machine scheduling-problems with blocking and no-wait in process. O perations Research , 44 (3) , 1996 , 510
• [3] Grabowski J. , Pempera J.: Sequencing of jobs in some production system. European Journal o f Operational Research , 125 , 2000 , 535
• [4] Lenstra J. , Rinnooy Kan A .: Computational complexity of discrete optimization problems. Annals o f Discrete Mathematics , 4, 1979, 121
• [5] Brucker P . , Jurisch B. , Sieveres B.: A branch and bound algorithm for the job-shop-scheduling- problem. Discrete Applied Mathematics , 49, 1994, 107
• [6] Nowicki E. , Smutnicki C.: A fast taboo search algorithm for the job shop scheduling problem. Managment Science , 42 ( 6 ) , 1996 , 797
• [7] Pezzella F . , Merelli E.: A tabu search method guided by shifting bottleneck for job-shop-schedu- ling-problem, branch and bound algorithm for the job-shop-scheduling-problem . European Journal of Operational Research , 120 , 2000 , 297
• [8] Sahni S. , Cho Y.: Complexity of scheduling shops with no-wait in process. Mathematics of Operations Research , 4, 1979, 448
• [9] Mascis A . , Pacciarelli D.: Job shop scheduling with blocking and no-wait constraints. European Journal o f Operational Research , 142 (3) , 2002 , 498
• [10] Macchiaroli R. , Mole S. , Riemma S.: Modelling and optimization of industrial manufacturing processes subject to no-wait constrains . International Journal o f Production Research , 3 7 ( 11 ) , 1999, 2585
• [11] Raaymakers W . , Hoogeveen J.: Scheduling multipurpouse batch process industries with no-wait restrictions by simulated annealing. European Journal o f Operational Research , 1 26 , 2 000 , 1 3 1
• [12] Schuster C. , Framinan J.: Approximative procedures for no-wait job shop scheduling. Operations Research Letters , 31, 2003 , 308
• [13] Graham R. , Lawler E. , Lenstra J. , Rinnooy Kan A .: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals o f Discrete Mathematics , 5 , 1979, 287
• [14] Holland J. H .: Genetic Algorithms. Scientific American , 267, 1992 , 44
• [15] Makuchowski M.: Problemy gniazdowe z operacjami wielomaszynowymi. Własności i algorytmy . Raport Politechniki Wrocławskiej, seria: Preprinty, nr 37 / 2004