Abstract

Ostatnimi czasy obserwujemy dwie tendencje w działalności człowieka. Pierwszą jest specjalizacja. Wobec rosnącej wiedzy i zaawansowania technologicznego, niemożliwym stało się, by jedna osoba mogła wiedzieć i robić wszystko. Podobnie jest z maszynami, które im są bardziej wyspecjalizowane tym są tańsze i tym lepiej wykonują swoje zadania. Druga tendencja to wieloprocesorowość, którą inaczej możemy nazwać pracą zespołową. Efekt synergii szczególnie widoczny jest w zespołach ludzkich, gdzie współpraca wielu osób pozwala osiągnąć wartość dodaną. Szeregowanie zadań, jako dziedzina opisująca działania człowieka, musi dostosowywać się do powyższych trendów. Dlatego w tej pracy rozważamy model szeregowania zadań wieloprocesorowych na maszynach dedykowanych z różnymi kryteriami optymalizacji szeregowania. Staramy się ustalić status złożoności obliczeniowej różnych typów instancji dla różnych kryteriów. Sprawdzamy, którędy przebiega granica między problemami wielomianowymi i NP-trudnymi. Zaobserwowaliśmy kilka zależności. Okazuje się, że gęste instancje są trudniejsze do szeregowania, tym niemniej niezależnie od tego proste struktury mogą okazać się łatwe. Niebagatelne znaczenie ma także rodzaj kryterium. Najprostszym jest kryterium długości harmonogramu, a najtrudniejszym listowo-kosztowe. Jako model teoretyczny wiernie obrazujący ten problem wykorzystujemy problem kolorowania krawędzi hipergrafów.

Author (1)