Wykorzystanie algorytmów ewolucyjnych do szeregowania zadań z ruchomymi realizatorami

Jerzy Józefczyk

W pracy zaprezentowano wybrane wyniki dotyczące jednego z podzadań realizowanych w Pracowni Systemów Wiedzy i Sztucznej Inteligencji w roku 2003. Dotyczy ono szeregowania zadań niezależnych i niepodzielnych o równych momentach gotowości na ruchomym realizatorze tak, aby suma momentów zakończenia wykonywania wszystkich zadań była jak najmniejsza. Uwzględnienie ruchu realizatorów w problemach szeregowania zadań umożliwia rozszerzenie ich zastosowań na takie przypadki, w których przemieszczanie obiektów, na których są wykonywane zadania produkcyjne jest utrudnione lub niemożliwe ze względu na ich wielkość lub wagę i wówczas jest konieczne przemieszczanie realizatorów tych zadań między nieruchomymi obiektami. Ma to miejsce przede wszystkim w elastycznych systemach produkcyjnych. Można też wskazać zastosowania w systemach usługowych, a także w systemach informatycznych. Ruch realizatorów komplikuje problemy szeregowania, które już dla zagadnień klasycznych są w większości NP-trudne lub silnie NP-trudne. Dlatego istnieje potrzeba opracowywania efektywnych czasowo przybliżonych i heurystycznych algorytmów rozwiązania, m.in. wykorzystujących metody sztucznej inteligencji. W pracy przedstawiono ewolucyjny algorytm szeregowania oraz w badaniach symulacyjnych sprawdzono jego przydatność. Dla niewielkich rozmiarów problemu różnica między proponowanym algorytmem heurystycznym a algorytmem dokładnym wynosiła około pięciu procent.

Słowa kluczowe: szeregowanie, algorytmy genetyczne, algorytmy heurystyczne, badania symulacyjne

Strzałka w lewoSpis referatów, Pełny tekst PDF