Algorytm genetyczny dla problemu gniazdowego z ograniczeniem bez czekania

Abstract

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. 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.