4087490262

12

3. WSTĘP

rozmiarach i dużym poziomie ogólności. Stąd też, w ostatnich latach można zaobserwować tendencję do wyróżniania i grupowania zagadnień ze względu na ich własności i poziom ogólności. Umożliwia to określenie szeregu własności szczególnych, które mogą być użyte do konstrukcji efektywniejszych algorytmów specjalizowanych. Tak otrzymane algorytmy często są wykorzystywane jako pomocnicze dla zagadnień ogólniejszych i trudniejszym. Dodatkowo, badania te pozwoliły na zarówno na precyzyjne określenie granicy NP-trudności problemów optymalizacji dyskretnej jak i granic przydatności metod dokładnych, takich jak na przykład wymieniony wyżej schemat B&B. Kolejnym argumentem do prowadzenia badań jest wzrost możliwości narzędzi używanych do konstrukcji i badania algorytmów komputerowych. Mam tu na myśli zarówno burzliwy rozwój przybliżonych technik obliczeniowych opartych na metodach sztucznej inteligencji, jak i wzrost mocy obliczeniowej komputerów, umożliwiający rozwiązywania problemów uznawanych dotychczas za beznadziejnie trudne z obliczeniowego punktu widzenia.

Wymienione kłopoty z konstrukcją algorytmów rozwiązywania spowodowały powstanie, wewnątrz dziedziny szeregowania zadań, specyficznych podejść umożliwiających wykonanie kompletnej analizy problemu począwszy od budowy jego modelu matematycznego, poprzez zbadanie złożoności obliczeniowej, określenie charakterystycznych własności, aż do konstrukcji algorytmu rozwiązywania wraz z implementacją. Niektóre z tych metod, przekraczając ramy pojedynczych publikacji, stały się podstawą wielu użytecznych algorytmów i weszły na trwałe do teorii szeregowania zadań.

Niejako “przy okazji” prowadzenia niektórych badań nad modelami i algorytmami szeregowania zadań, w ostatnich latach rozwinięte zostały nowe, ogólne podejścia i techniki przybliżone, mające dalsze zastosowanie przy rozwiązywania trudnych problemów optymalizacji występujących w innych dziedzinach, np. planowanie zajęć, tras transportowych, pracy personelu, projektowanie filtrów cyfrowych, układów optycznych, konstrukcji mechanicznych, sieci komputerowych, kanałów telekomunikacyjnych, rurociągów, itp. Metody te są stosunkowo dobrze odporne na podstawowe kłopoty optymalizacji, takie jak na przykład brak klasycznych własności analitycznych (różniczkowalność, wypukłość), wieloekstremalność, przekleństwo wymiaro-wości, itp. Jednocześnie charakteryzują się zaskakująco wysoką efektywnością obliczeniową przy relatywnie małym stopniu skomplikowania algorytmu. Ostatecznie, dziedzina szeregowania jest obszarem badawczym, na którym ścierają się i są testowane przeróżne podejścia do rozwiązywania trudnych problemów optymalizacyjnych, prowadząc w konsekwencji do rozwoju strony algorytmicznej komercyjnych pakietów oprogramowania, wspierających działania człowieka w wielu różnych dziedzinach życia.