Opracowanie na podstawie monografii:

C. Smutnicki - „Algorytmy szeregowania”.

Łukasz Brygała

30 listopada 2010

Spis treści

1

Sterowanie procesami - zadania, metody, algorytmy

1

1.1

System planowania i sterowania. Strategie wytwarzania

. . . . . . . . . . . . . . . . .

1

1.2

Podejście do konstrukcji modeli matematycznych. . . . . . . . . . . . . . . . . . . . . .

1

1.3

Problemy jednomaszynowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4

Problemy przepływowe (flow shop) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5

Problemy gniazdowe (job-shop) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2

Metody rozwiązywania zadań optymalizacji dyskretnej

10

2.1

Kryteria optymalizacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2

Trudność rozwiązywania zadań optymalizacji . . . . . . . . . . . . . . . . . . . . . . .

10

2.3

Dokładne metody optymalizacji dyskretnej

. . . . . . . . . . . . . . . . . . . . . . . .

10

2.4

Przybliżone metody optymalizacji dyskretnej . . . . . . . . . . . . . . . . . . . . . . .

12

1

Sterowanie procesami - zadania, metody, algorytmy

1.1

System planowania i sterowania. Strategie wytwarzania

System Production Planing and Control realizuje proces planowania (dobiera środki do realizacji

zadań produkcyjnych w zadanym czasie) oraz sterowania. Uważany jest za nadrzędny w obiegu i wy-
mianie danych dla procesu wytwarzania. Pracując w obszarach związanych z przepływem informacji
i materiałów, współdziała z innymi systemami informatycznymi przedsiębiorstwa (CAD - wspomaga-
nie projektowania, CAM - integracja faz projektowania i wytwarzania, CAQ - wspomaganie sterowania
jakością). Jest trzonem systemu CIM (Computer Integrated Manufacturing).

Sposób użycia teorii szeregowania w systemie zależy od charakteru produkcji. Dla produkcji krótko-

seryjnej modele szeregowania mogą być używane bezpośrednio. Dla średnio- i wielko-seryjnej narzędzia
teorii szeregowania pozwalają optymalizować fragment procesu wytwarzania, na podstawie parame-
trów poszczególnych cykli produkcyjnych (czas trwania cyklu, rytmiczność dostaw, synchronizacja
pod-procesów).

1.2

Podejście do konstrukcji modeli matematycznych.

Dane liczbowe dotyczące systemu wytwarzania mogą być deteministyczne (ustalone i znane), pro-

babilistyczne lub rozmyte (znamy odpowiednie funkcje przynależności i parametry). W zależności
od charakteru danych do modelowania i analizy problemu korzysta się z: teorii szeregowania; teo-
rii kolejek i procesów stochastycznych; teorii zbiorów rozmytych. Deterministyczna teoria szeregowania
traktowana jest jako fundamentalna dla wszystkich podejść. Problemy deterministyczne z pełną infor-
macją o danych, wyznaczające rozwiązania w trybie off-line, stanowią bazę do modelowania zagadnień
pokrewnych.

W problemach szeregowania rozważa się zadania (polegają na wykonaniu ciągu operacji ) i zasoby

(potrzebne do realizacji operacji). Przykłady zadań: proces obróbki detalu w przemyśle maszynowym,

1

proces montażu w przemyśle samochodowym, realizacja inwestycji w budownictwie, przetworzenie
partii surowca w przemyśle petrochemicznym. Przykłady zasobów: urządzenia, personel, materiały,
kapitał, surowce energetyczne. Cechy charakterystyczne zadań: termin pojawienia się zadania, żądany
termin zakończenia,przerywalność i podzielność. Kategorie zasobów: odnawialne (ograniczenie strumie-
nia dostępności), nieodnawialne (ograniczenie globalnej ilości), podwójnie ograniczone. Dla ustalenia
uwagi w teorii szeregowania często rozważa się specyficzny rodzaj zasobów odnawialnych nazywanych
maszynami.

W konstrukcji modeli matematycznych rozważa się zbiór zadań oraz zbiór maszyn wykonujących

zadania. Zadania zapisuje się w postaci sumy operacji, wykonywanych w określonej kolejności (po-
rządku technologicznym). Przyjmuje się następujące ograniczenia: operacja nie może być przerywana,
każda maszyna może wykonywać najwyżej jedno zadanie w danej chwili.

Rozwiązaniem problemu szeregowania zadań składających się z o operacji nazywa się parę wekto-

rów o-wymiarowych określających: (1) na jakiej maszynie wykonywana jest dana operacja; (2) jaki jest
termin rozpoczęcia operacji. Rozwiązanie spełniające ograniczenia nazywamy dopuszczalnym. Dla za-
dania optymalizacyjnego przyjmuje się pewną funkcję celu, przy pomocy której bada się optymalność
rozwiązania.

Ze względu na złożoność zagadnień szeregowania naukowcy pogrupowali je ze względu na własno-

ści i poziom ogólności. Pozwala to na konstruowanie efektywniejszych algorytmów specjalizowanych,
wykorzystywanych później jako pomocnicze dla zagadnień ogólniejszych. Najprostsze są zagadnienia
jednomaszynowe, bardziej ogólny jest problem przepływowy, jeszcze ogólniejszy jest problem gniazdo-
wy.

1.3

Problemy jednomaszynowe

Problemy jednomaszynowe należą do najprostszych zagadnień szeregowania. Umożliwiają modelo-

wanie i analizę prostych systemów wytwarzania oraz wybranych pojedynczych stanowisk w złożonych
systemach produkcyjnych. Są też używane jako problemy pomocnicze w zagadnieniach trudniejszych.

1. Podstawowe problemy jednomaszynowe

Rozważa się zbiór zadań przeznaczonych do rozwiązania na maszynie o ograniczonej przepusto-
wości. Przepustowość określa liczbę zadań, jakie maszyna może wykonywać jednocześnie. Każde
zadanie posiada określone czasy wykonywania. Rozwiązaniem jest harmonogram pracy stano-
wiska reprezentowany przez wektor terminów rozpoczęcia lub zakończenia zadań. Rozwiązanie
może być reprezentowane permutacją na zbiorze zadań.

Powyższy problem uogólnia się wprowadzając terminy gotowości (pojawienia się zadań). Roz-
wiązaniem tak uogólnionego problemu jest obsługa zadań według reguły FIFO.

Kolejne uogólnienie polega na wprowadzeniu żądanych terminów zakończenia poszczególnych
zadań. Rozwiązaniem tak uogólnionego problemu jest algorytm oparty o zasadę Earliest Due
Date i polega na priorytetowej regule obsługi zgłoszeń według pilności (zadanie o bliższym wy-
maganym terminie zakończenia obsługujemy pierwsze).

Można także wprowadzić do problemu acykliczną relację skierowaną określającą zależności mię-
dzy zadaniami. W takim wypadku dokonuje się odpowiednich modyfikacji czasów rozpoczęcia
i zakończenia dla zadań zależnych i korzysta się z wymienionych uprzednio algorytmów (alg.
oparte o FIFO oraz EDD).

Następny problem powstaje przez wprowadzenie czasów przygotowawczych dla każdego zada-
nia oraz czasów dostarczenia zadania (dostarczanie rozpoczyna się bezpośrednio po zakończeniu
wykonywania zadania, przy czym wszystkie mogą być dostarczanie jednocześnie). Celem jest
minimalizacja czasu dostarczenia wszystkich zadań. Problem ten jest równoważny problemowi
szeregowania na trzech maszynach, z których maszyna pierwsza i trzecia mają nieograniczoną
przepustowość i czasy wykonywania zadań równe odpowiednio czasowi przygotowania i cza-
sowi dostarczenia zadania. Pojęcie maszyny o nieskończonej przepustowości może modelować:
urządzenia o nieograniczonej możliwości wykonawczej (piec grzewczy), proces nie angażujący
urządzenia fizycznego (np. stygnięcie), itp. Omawiany problem ma liczne zastosowania m.in.:

2

w alg. przybliżonych dla problemu gniazdowego, jako dolne ograniczenie dla problemów prze-
pływowych i gniazdowych. Jest silnie NP-trudny, chociaż dla szczególnych przypadków istnieją
algorytmy wielomianowe.

Ze względu na NP-trudność powyższego problemu istnieje potrzeba wyznaczenia dolnego ograni-
czenia optymalnej wartości funkcji celu, zarówno w B&B jak i dla oszacowań jakości algorytmów
przybliżonych. Istnieje wiele metod konstrukcji ograniczenia opartych o relaksację funkcji celu
i ograniczeń.

Dla problemu opisanego powyżej, po dopuszczeniu możliwości przerywania zadań, otrzymuje się
problem zrelaksowany, posiadający algorytm wielomianowy. (Problem jednomaszynowy z czasa-
mi przygotowawczymi oraz czasami dostarczenia oraz z możliwością przerywania zadań.)

Algorytmy dla problemu jednomaszynowego z czasami przygotowawczymi i czasami dostarczenia:

(a) Algorytmy przybliżone.

• Algorytm S (2-aproksymacyjny).

Najprostszy alg. 2-aproksymacyjny otrzymuje się przez zrelaksowanie analizowanego
problemu poprzez pominięcie albo czasów przygotowawczych, albo czasów dostarcze-
nia. Wtedy za algorytm rozwiązujący zadanie przyjmuje się odpowiednio Earliest Due
Date lub FIFO. Algorytmy te dostarczą w takim wypadku uszeregowania o długo-
ści nie większej niż 2 razy długość uszeregowania optymalnego (stąd nazwa alg. 2-
aproksymacyjny).
Inny algorytm 2-aproksymacyjny - algorytm S - wykorzystuje uogólnioną regułę Jack-
sona, zapobiegającą bezczynności: jeżeli maszyna jest wolna i co najmniej jedno zadanie
jest gotowe do wykonania, należy skierować do obsługi zadanie najpilniejsze (w analizo-
wanym problemie zadanie o najdłuższym czasie dostarczenia). W każdym kroku algo-
rytmu zadania nieuszeregowane tworzą kolejkę, z której pobierane są zadania zgodnie
z ich dostępnością i pilnością. Korzystając z implementacji kolejki priorytetowej na kop-
cu binarnym można uzyskać dla algorytmu S złożoność O(nlogn).

• Algorytm P (3/2-aproksymacyjny).

Alg. P generuje ciąg permutacji zaczynając od permutacji startowej wyznaczonej algo-
rytmem S. Wyszukuje w każdej permutacji tak zwane zadanie interferencyjne dla drogi
krytycznej i podstawia za czas gotowości zadania interferencyjnego czas gotowości za-
dania końcowego drogi krytycznej. Kolejne permutacje generowane są tak długo dopóki
istnieje zadanie interferencyjne lub do momentu osiągnięcia zadanej liczby iteracji. Alg.
zwraca najlepszą permutację z wygenerowanego ciągu.

• Algorytm HS (4/3-aproksymacyjny).

(b) Algorytmy przeglądu.

• Algorytm Carliera.

To schemat B&B generujący dla każdego węzła w drzewie rozwiązań kompletne roz-
wiązanie przy pomocy algorytmu S. Na bazie tego rozwiązania, w oparciu o jego wła-
ściwości określa się zasadę podziału, dolne i górne ograniczenia oraz reguły eliminacji.

• Algorytm blokowy.

Jest oparty na sechemacie B&B i wykorzystuje następującą właściwość bloków (blok to
ciąg zadań drogi krytycznej danej permutacji): jeżeli dla danej permutacji istnieje inna
permutacja dla której czas dostarczenia zadań jest mniejszy, to w danej permutacji
istnieje zadanie nie-początkowe takie, że w tej innej permutacji to zadanie poprzedza
wszystkie pozostałe w bloku.

Wymienione powyżej algorytmy przeglądu uważane są za jedne z bardziej efektywnych sche-
matów B&B - umożliwiają rozwiązanie bez trudu przykładów o n = 1,000. Stanowią bazę dla
jednomaszynowych problemów rozszerzonych, problemów z nieregularnymi funkcjami celu, NP-
trudnych ograniczeń dolnych problemów gniazdowych.

3

2. Kosztowe problemy jednomaszynowe

Kosztowe problemy jednomaszynowe to problemy z addytywnym kryterium oceny (suma warto-
ści funkcji kosztu każdego z zadań). Są zdecydowanie trudniejsze od podstawowych problemów
jednomaszynowych ale mają dość liczne zastosowania i dobre uzasadnienie ekonomiczne.

Każde zadanie w rozważanym problemie ma przypisaną funkcję niemalejącą, reprezentującą koszt
związany z zakończeniem tego zadania w danej chwili. Chociaż w ogólnym przypadku problem
jest silnie NP-trudny, to dla pewnych postaci funkcji kosztów można rozwiązać go w czasie
wielomianowym. Dodatkowo dla pewnych postaci funkcji kosztów problem można sprowadzić
do problemu PL, PLC lub PLB, dla których stosuje się odpowiednio algorytmy sympleks, Lang-
Doig’a lub schemat odcięć, Balasa.

Przy kosztowych problemach jednomaszynowych uwidacznia się słabość schematów B&B zwią-
zana z wyznaczaniem wartości dolnego ograniczenia, które w tym przypadku jest dość trudnym
zadaniem. Powoduje to małą skuteczność metod dokładnych opartych o ten schemat, uniemoż-
liwiając rozwiązanie przykładów o wielkości powyżej 100 zadań.

Trudność konstrukcji algorytmów dla problemów z kryteriami addytywnymi wynika z niedostat-
ku odpowiednich właściwości tych problemów. Dlatego zastosowanie znajdują w tym przypadku
algorytmy poszukiwań lokalnych. Jedną z najczęściej implementowanych technik jest tutaj poszu-
kiwanie zstępujące. Ponieważ każde rozwiązanie może być reprezentowane permutacją, lokalne
otoczenia można stosunkowo łatwo uzyskać, na przykład metodą wymiany elementów przyle-
głych w permutacji. Istnieje wiele metod generacji otoczenia, gdyż w dużym stopniu od jego
kosztu zależy szybkość działania algorytmu. Metody te często pochodzą od przybliżonych metod
rozwiązania problemu komiwojażera.

Dla problemów jednomaszynowych można także stosować algorytmy genetyczne, symulowane
wstrząsanie, wyżarzanie oraz dynamiczne reguły priorytetowe.

3. Złożone problemy jednomaszynowe

O złożonych problemach jednomaszynowych mówi się głównie w kontekście systemów wytwa-
rzania just-in-time. Są jednymi z najtrudniejszych problemów szeregowania i indukują potrzebę
rozwoju nowych podejść.

Podstawowe kryteria optymalizacji dla systemów JIT to kryteria nieregularne. Nieco odmienną
klasę problemów stanowią elastyczne systemy JIT. W takich systemach pomija się koszt przełą-
czania produkowanego modelu wyrobu. Chodzi o nastawienie produkcji na utrzymywanie ilości
produktów jak najbliżej wielkości aktualnego zapotrzebowania. Matematyczne sformułowania
takiego problemu skupiają się na minimalizacji odchyleń w tempie produkcji różnych elementów
na linii.

1.4

Problemy przepływowe (flow shop)

Problemy przepływowe są jednymi z prostszych modeli systemów produkcyjnych. Stosowane są

w procesach chemicznych, niektórych procesach przemysłu elektronicznego czy samochodowego. Sta-
nowią podstawę do analizy struktur szeregowo-równoległych, dominujących we współczesnych syste-
mach wytwarzania. Problemy te (pomijając przypadki szczególne) są NP-trudne.

1. Podstawowe problemy przepływowe

Problem przepływowy to taki, w którym wszystkie zadania posiadają jednakową marszrutę tech-
nologiczną, wymagającą obsługi na wszystkich stanowiskach, zaś każde stanowisko wymaga okre-
ślenia oddzielnej sekwencji wprowadzania zadań.

Problem przepływowy permutacyjny jest podobny do zwykłego przepływowego, jednak ma wy-
maganie, aby kolejność obsługi zadań na wszystkich maszynach była jednakowa (zgodna z ko-
lejnością wprowadzenia zadań do systemu).

Częściej analizowany jest problem permutacyjny ze względu na to, że: (1) ma zdecydowanie
mniejszą liczbę rozwiązań niż problem ogólny, (2) sterowanie systemem tak opisywanym jest

4

prostsze, (3) ograniczenia technologiczne często pozwalają tylko na wprowadzenie rozwiązań
permutacyjnych, (4) rozwiązanie problemu permutacyjnego może być używane jako rozwiązanie
w problemach przybliżonych dla problemów ogólnych.

Najstarszym problemem przepływowym jest problem permutacyjny dla dwóch maszyn. Jeden
z kilku równoważnych algorytmów dla tego problemu polega na budowaniu permutacji poczy-
nając jednocześnie od obu końców. Z zadań nieuszeregowanych wybierane jest to, które ma
najmniejszą wartość żądanego czasu trwania (brane są pod uwagę czasy zarówno na pierwszej
jak i drugiej maszynie). Jeżeli wartość minimalna odpowiada pierwszej maszynie to zadanie
jest szeregowane na pierwszej pozycji, jeżeli drugiej to na ostatniej. Złożoność obliczeniowa to
0(nlogn). Zwykle wprowadzenie ograniczeń powoduje NP-trudność problemu (wprowadzenie re-
lacji zależności między zadaniami, terminów gotowości).

Problem dla trzech maszyn w pewnych szczególnych przypadkach da się rozwiązać przez spro-
wadzenie do problemu dla dwóch maszyn. Ogólnie dla liczby maszyn większej niż dwa problem
jest NP-trudny.

Problem przepływowy wygodnie można przedstawić w postaci „prostokątnego” grafu o M na N
wierzchołkach reprezentujących operacje (prostokątnej siatki). Obciążenie wierzchołka jest równe
czasowi wykonywania operacji. Zbiór krawędzi dzielimy na technologiczne krawędzie pionowe
oraz sekwencyjne krawędzie poziome. Długość najdłuższej drogi od węzła (1,1) do (i,j) to termin
zakończenia wykonywania zadania j-tego na i-tej maszynie. Termin zakończenia wszystkich zadań
jest długością najdłuższej ścieżki w grafie. Poziome fragmenty ścieżek, odpowiadające ciągowi
zadań wykonywanych kolejno na danej maszynie, nazywamy blokami.

Rozważa się własności blokowe oraz eliminacyjne własności blokowe. Za ich pomocą można okre-
ślić warunki konieczne istnienia rozwiązania lepszego w sensie kryterium maksymalnego terminu
zakończenia zadań (lub innego kryterium nieaddytywnego) od danego rozwiązania. Własność
blokowa mówi, że aby konstruując nową permutację uzyskać poprawę wartości funkcji celu, na-
leży przemieścić pewne zadanie należące do dowolnego bloku wewnętrznego danego bloku (blok
wewnętrzny powstaje z danego bloku przez pominięcie zadania pierwszego i ostatniego), poza
ten blok. Własność blokowa jest trudna do implementacji. W praktyce używa się eliminacyjnej
własności blokowej, która jest jej formą zanegowaną: jeżeli permutacja została otrzymana z innej
permutacji przez przemieszczenie zadań należących do dowolnego bloku wewnętrznego, to nowa
permutacja ma większy lub równy maksymalny termin zakończenia.

Blokowa wł. eliminacyjna ma charakter destrukcyjny - określa, które rozwiązania należy odrzucić.
Korzysta się z niej w schematach B&B, algorytmach TS, DS (poszukiwanie zstępujące) i innych
metodach.

Algorytmy i metody dla problemu przepływowego:

(a) Schematy B&B

Ta metoda dla problemów przybliżonych ma ograniczone zastosowanie. Trudności napoty-
ka się w użyciu B&B już dla 20 zadań na 5 maszynach. Typowe przykłady testowe (50
zadań, 20 maszyn) potrzebują nieraz kilka tygodni pracy. Dlatego schematu B&B uży-
wa się raczej jako narzędzie do generowania rozwiązań referencyjnych do oceny algorytmów
przybliżonych.

(b) Podstawowe algorytmy przybliżone

Poniżej wymieniono typowe podejścia w algorytmach przybliżonych dla problemu przepły-
wowego.

• Priorytety statyczne

• Priorytety dynamiczne

Algorytm MINIT zaczyna od utworzenia dwuelementowej permutacji, która następnie
jest rozszerzana z każdym krokiem o zadanie, które zapewnia minimalny czas przestoju
maszyn dla nowej permutacji. (Nowa permutacja = permutacja poszerzona o wybrane
w bieżącym kroku zadanie.)

5

Algorytm MICOT także zaczyna od permutacji dwuelementowej. Krokowo rozszerza się
permutację o zadanie o minimalnym czasie zakończenia dla nowej permutacji.
Algorytm MINIMAX buduje permutację z obu końców jednocześnie (idea jak w al-
gorytmie dla dwóch maszyn rozszerzona do przypadku wielomaszynowego). Zadania
mające małe czasy wykonywania preferowane są jako początkowe, z dużymi czasami
jako końcowe.
Algorytmy priorytetowe są szybkie, lecz mało efektywne.

• Zastosowanie problemu permutacyjnego dla dwóch maszyn

Algorytmy tego typu polegają na transformacji problemu do problemu prostszego, ma-
jącego wielomianowy algorytm. Różnią się techniką transformacji oraz liczbą genero-
wanych problemów pomocniczych.

• Algorytm NEH (technika wcięć)

NEH jest uważany najlepszy algorytm przybliżonych w klasie konstrukcyjnych dla pro-
blemu przepływowego permutacyjnego. Składa się z dwóch faz. (1) Faza wstępna -
przenumerowanie zadań zgodnie z nierosnącymi wartościami sumy czasów wykonywa-
nia na poszczególnych maszynach. (2) Faza zasadnicza - generowanie ciągu permuta-
cji. W każdym kroku pobiera się kolejne zadanie z ciągu wcześniej ponumerowanych
i wstawia się je do bieżącej permutacji na wszystkie możliwe pozycje sprawdzając, która
pozycja daje nową permutację o najkorzystniejszej wartości funkcji celu. (Intuicyjnie
jest to proces analogiczny do pakowania torby - zaczynamy od największych elementów
dopychając metodą prób elementy mniejsze.)
Algorytm NEH przy odpowiedniej implementacji ma złożoność O(n

2

m). Błąd względ-

ny w odniesieniu do rozwiązania optymalnego wynosi 5-6%. Zachowuje się najlepiej,
kiedy liczba maszyn nie jest znacznie mniejsze niż liczba zadań (kiedy jest zbliżona
lub większa). Metoda ta sprawdza się także dość dobrze dla kryterium addytywnego
(nadaje się do zastosowań dla szerokiej klasy problemów).
Technikę wcięć przenosi się również do bardziej złożonych problemów przepływowych,
czy problemów gniazdowych. Algorytmy charakteryzują się korzystnymi cechami nu-
merycznymi.

• Algorytmy DS

Dla systemów wymagających rozwiązań bliskich optymalnym często korzysta się z przy-
bliżonych algorytmów konstrukcyjnych wspomaganych algorytmem poszukiwania zstę-
pującego. Startując z rozwiązania otrzymanego najlepszym alg. konstrukcyjnym można
w ten sposób otrzymać rozwiązanie problemu z błędem poniżej 5%. Wybór alg. kon-
strukcyjnego jest ważny, gdyż metoda DS jest wrażliwa na wybór punktu startowego.
Startowanie DS z kilku rozwiązań przypadkowych (w celu przeszukania większej liczby
rozwiązań) jest zdecydowanie bardziej kosztowne i wolniej zbieżne niż TS czy GA.

• Algorytmy TS

Dla algorytmu TS wykorzystującego własności blokowe można uzyskać najlepsze wyniki
jeżeli chodzi o dokładność.

• Symulowane wyżarzanie
• Poszukiwania ewolucyjne

Algorytmy takie jak SA, SJ, GS są dobre do umiarkowanej poprawy jakości rozwiązania lub
do problemów o nieznanych własnościach szczególnych. Osiągnięcie wysokiej dokładności
oznacza nieakceptowalnie długi czas obliczeń.

2. Zaawansowane problemy przepływowe

Zastosowanie w problemie przepływowym kryterium addytywnego lub regularnego zwiększa
trudność zadania i wymaga zastosowania innych podejść niż te stosowane w metodach dla pro-
blemu podstawowego. Przykładowo, korzystniejsze własności numeryczne dla takich problemów
mają metody SA, SJ i GA niż LS.

Poniżej znajduje się lista kilku innych, zaawansowanych problemów przepływowych. Najczęściej
wprowadza się w nich dodatkowe ograniczenia do problemu permutacyjnego. Zbiór rozwiązań tak

6

uzyskanych problemów jest zbiorem permutacji, więc do ich rozwiązywania korzysta się również
z takich metod jak SA, SJ, TS czy GS. Specyficzny dla każdego problemu jest za to sposób
wyznaczania funkcji celu.

(a) Relacja poprzedzeń

Wprowadzenie relacji poprzedzeń nie wymaga zmian w grafowej reprezentacji problemu ani
w funkcji celu. Powoduje jednak, że zadania w grafie muszą być ustawione w określonym po-
rządku topologicznym. Pozwala to na eliminację znacznej części rozwiązań co przekłada się
na poprawę szybkości zbieżności algorytmów. W algorytmach rozproszonych takich jak np.
GS, zachodzi potrzeba zaprojektowania specyficznych operatorów genetycznych, ponieważ
generowanie permutacji dopuszczalnych może być problematyczne.

(b) Maszyny o nieograniczonej przepustowości

Przepustowość określa ile zadań jednocześnie może być wykonywanych na danej maszynie.
Taką maszynę wygodnie jest reprezentować liczbą maszyn równoległych równą liczbie tych
zadań.

Maszyny o nieograniczonej przepustowości modeluje się w grafowej reprezentacji problemu
przepływowego przez usunięcie w wierszach im odpowiadających linii poziomych.

Problemy z maszynami o nieograniczonej przepustowości zachowują własności ścieżki kry-
tycznej w grafie i eliminacyjne własności blokowe.

(c) Transport

Transport między maszynami można modelować przez wprowadzanie wag krawędzie pio-
nowych między tymi maszynami. Problemy takie zachowują własności ścieżek w grafie
i eliminacyjne własności blokowe.

(d) Buforowanie

Bufor jest miejscem chwilowego składowania zadania przekazywanego między maszynami
i jest zwykle związany z maszyną. Klasyczne problemy zakładają dowolnie dużą wielkość
bufora. Można jednak rozpatrywać zerową i ograniczoną pojemność. Pierwszy przypadek
wprowadza do zadania ograniczenie, że wykonane zadanie pozostaje na danej maszynie
do momentu gdy będzie możliwe jego rozpoczęcie na kolejnej maszynie. Drugi przypadek
wymaga uzgodnienia reguły obsługi bufora decydującej, które zadanie z kolejki wybierane
jest do obsługi.

Problemy z buforem zachowują własności ścieżki krytycznej i eliminacyjne własności blo-
kowe. Posiadają też dodatkowe własności związane ze skośnymi ścieżkami modelującymi
bufory (własności bloków skośnych).

(e) Przezbrojenia

Przezbrojenie to czas potrzebny na zmianę oprzyrządowania maszyn w związku z zadaniem.
Modelowanie polega na wprowadzeniu wag dla krawędzi poziomych w grafie. Przezbrojenia
wymuszają grupowanie zadań, aby zminimalizować liczbę potrzebnych przezbrojeń.

Problemy takie nie zachowują wszystkich własności ścieżki krytycznej i dotyczących bloków.

(f) Pojemność systemu

Pojemność systemu ogranicza liczbę zadań mogących przebywać jednocześnie w systemie.
Problemy z ograniczoną pojemnością posiadają analogiczne własności jak problemy z bu-
forem.

1.5

Problemy gniazdowe (job-shop)

Problem gniazdowy to taki, w którym różne zadania mogą posiadać różne (co do liczby jak i kolejno-

ści odwiedzania stanowisk) marszruty technologiczne. Uważany jest za szczególnie trudne zagadnienie
optymalizacyjne, ma jednak duże znaczenie praktyczne. Najlepsze algorytmy przybliżone rozwiązu-
ją problemy do 2000 operacji z kryterium maksymalnego czasu wykonania ostatniego zadania. Błąd
wynosi przeciętnie 4-5%.

7

Zadania składają się z sekwencji operacji wykonywanych w ustalonej kolejności. Zwykle dla pro-

stoty zakłada się, że dwie kolejne operacje są wykonywane na dwóch różnych maszynach. Czasem to
ograniczenie usuwa się wprowadzając fikcyjne operacje separujące o nieskończenie małym czasie trwa-
nia. Przepustowość maszyn wynosi jeden. Rozwiązaniem jest wektor terminów rozpoczęcia operacji.
Każde dwie operacje muszą posiadać jednoznaczną kolejność wykonywania na danej maszynie (waru-
nek dysjunktywny). Najczęściej używanym kryterium jest termin zakończenia wykonywania wszyst-
kich zadań. Trudniejsze zadania opierają się na addytywnym kryterium - sumie terminów zakończenia
zadań. Problem gniazdowy jest silnie NP-trudny.

Techniki modelowania problemu:

1. Model dysjunktywny - najstarszy historycznie. Opiera się na pojęciu grafu dysjunktywnego. Skła-

da się on z węzłów reprezentujących operacje, łuków skierowanych przedstawiających kolejność
technologiczną operacji, oraz łuków nieskierowanych (tzw. dysjunktywnych) przedstawiających
możliwe kolejności realizacji operacji na maszynach. Łuki mają obciążenia zerowe, węzły obciąże-
nia równe czasom wykonywania operacji. Ustalenie kolejności wykonywania operacji odpowiada
skierowaniu poszczególnych łuków dysjunktywnych i wybraniu reprezentacji ich zbioru. Każda
reprezentacja jest równoważna jednemu rozwiązaniu. Aby rozwiązanie było dopuszczalne, graf
powstały z danej reprezentacji musi być acykliczny. Terminy rozpoczęcia wykonywania operacji
wyznacza się jako najdłuższe drogi dochodzące do wierzchołków grafu.

Technika grafu dysjunktywnego umożliwia modelowanie, lecz nie generuje konkretnych algoryt-
mów. Ze względu na łatwość programowania model ten jest wciąż popularny.

2. Model kombinatoryczny - technika uważana za najlepszą dla wielu zastosowań. Pozbawiona jest

nadmiarowości charakterystycznej dla modelu dysjunktywnego.

Zbiór operacji może być dekomponowany na podzbiory operacji wykonywanych na ustalonej
maszynie. Kolejność wykonywania operacji na danej maszynie określamy permutacją. Kolejność
wykonywania na wszystkich maszynach jest permutacją należącą do produktu kartezjańskiego
zbiorów wszystkich permutacji dla każdej maszyny. Dla każdej kolejności możemy skonstruować
graf składający się z węzłów oznaczających operacje, łuków oznaczających kolejność wykonywa-
nia operacji danego zadania, oraz łuków oznaczających kolejność wykonywania operacji na ma-
szynach. Dana kolejność jest dopuszczalna jeżeli graf nie zawiera cyklu.

Model dysjunktywny i kombinatoryczny wymagają detekcji cykli grafów. Stosuje się różne po-
dejścia aby złagodzić wpływ tego kosztownego procesu.

3. Model listowy - polega na wprowadzeniu reprezentacji rozwiązania za pomocą jednej listy ope-

racji. Permutacja na zbiorze operacji reprezentuje rozwiązanie dopuszczalne jeżeli: (a) operacje
wchodzące w skład każdego z zadań są w poprawnej kolejność w permutacji, (b) kolejność wyko-
nywania na maszynach jest zgodna z kolejnością pojawiania się w permutacji. Taka permutacja
może być otrzymana jako porządek topologiczny w grafie modelu kombinatorycznego, co ustala
związek tych dwóch modeli.

Chociaż liczba rozwiązań dopuszczalnych w każdym modelu jest jednakowa, to różnią się one liczbą
generowanych rozwiązań niedopuszczalnych. Najbardziej nadmiarowy jest model listowy, najmniej
kombinatoryczny.

Korzystając z reprezentacji grafowych problemu określa się pewne jego własności. Punktem wyjścia

jest acykliczny graf reprezentujący rozwiązanie modelu dysjunktywnego lub kolejność modelu kombi-
natorycznego. Rozważane własności mają zastosowanie głównie dla kryterium z maksymalnym czasem
wykonania ostatniego zadania. Ciąg węzłów odpowiadających najdłuższej drodze w danym grafie ro-
zumiemy jako pewną drogę, którą możemy zdekomponować na odcinki odpowiadające ciągom operacji
wykonywanych na jednej maszynie. Takie odcinki nazywamy blokami. Blok wewnętrzny to ciąg operacji
z bloku bez pierwszej i ostatniej. Dla reprezentacji dopuszczalnej stwierdzono następujące własności:

1. Odwrócenie skierowania łuku dysjunktywnego leżącego na drodze generuje inną reprezentację

dopuszczalną.

8

2. Odwrócenie skierowania łuku dys. nie leżącego na drodze generuje reprezentację niedopuszczalną,

lub nie lepszą.

3. Odwrócenie skierowania łuku dys. wewnątrz bloku generuje reprezentację dopuszczalną lecz nie

lepszą.

Brak powyższych własności dla problemu gniazdowego z innymi funkcjami kryterialnymi.

Metody i algorytmy dla problemu gniazdowego:

1. Schemat B&B

Najlepszy znany algorytm wykorzystujący ten schemat korzysta z wielu specyficznych cech pro-
blemu, odznacza się znacznym stopniem skomplikowania, a mimo to potrafi rozwiązywać pro-
blemy o rozmiarze jedynie 200 operacji. Jest to granica aktualnej stosowalności algorytmów
dokładnych dla problemu gniazdowego.

Przyczyny słabości - słabość metod wyznaczania dolnych ograniczeń i brak skutecznych własno-
ści eliminacyjnych.

Zastosowanie - cykliczne systemy wytwarzania o niewielkich rozmiarach problemów, wymagające
bardzo dużej dokładności.

2. Algorytmy priorytetowe

Są jednymi z najczęściej używanych algorytmów dla pr. gniazdowego. Średni błąd zamyka się
w granicach do 30%, a ich implementacja jest względnie prosta. Najczęściej używa się jako
kryterium przydzielenia priorytetu: najkrótszy/najdłuższy czas wykonywania operacji, najwięk-
sza/najmniejsza pozostała pracochłonność (suma czasów wykonywania operacji występujących
po danej operacji), największa/najmniejsza liczba pozostałych operacji w zadaniu, najwcześniej-
sza dostępność, najszybsze zakończenie (EDD), kolejność napływu (FIFO), priorytet losowy
(RANDOM).

Wyróżnia się trzy klasy algorytmów priorytetowych:

• Schemat GT - generuje drzewo rozwiązań (podobnie jak w schemacie podziału i ogra-

niczeń). Opiera się na tworzeniu częściowego uszeregowania dołączając kolejno operacje
z zachowaniem relacji porządku technologicznego. W każdym kroku rozpatruje się zbiór
operacji szeregowalnych, tzn. takich, których wszystkie poprzedniki są już uszeregowane.
Dla każdej operacji z tego zbioru wylicza się najwcześniejszy termin rozpoczęcia wykonywa-
nia. Następnie wyznacza się operację o najmniejszej sumie wyliczonego czasu rozpoczęcia
i czasu trwania, oraz maszynę, której żąda. Dalej rozpatruje się wszystkie operacje o ter-
minie rozpoczęcia niepóźniejszym od wyznaczonej również żądające tej maszyny - operacje
tworzące zbiór konfliktowy. Rozstrzygnięcie konfliktu polega na analizie wszystkich warian-
tów, co odpowiada utworzeniu gałęzi drzewa.

Algorytmy schematu GT rozstrzygają konflikt jednoznacznie poprzez zastosowanie wybra-
nej reguły priorytetowej. Dlatego na każdym etapie w drzewie wybiera się tylko jeden
następnik.

• Uszeregowania częściowe - budują częściowe uporządkowanie dodając w każdym kroku jed-

ną szeregowalną operację. Wybór jest oparty na regule priorytetowej, która uwzględnia
dostępność operacji. Nie analizuje zbioru konfliktowego - jest szybsza kosztem jakości roz-
wiązań.

• Symulacja zdarzeń - to przebieg symulacji komputerowej z dyskretnym zbiorem zdarzeń

oraz określonymi regułami priorytetowymi obsługi kolejki stanowisk.

3. Algorytmy aproksymacyjne

4. Poszukiwania lokalne (TS, SA)

Różne podejścia wynikają ze sposobów budowy sąsiedztw (w zależności od przyjętego modelu).
TS jest najkorzystniejszą obecnie techniką rozwiązywania problemów gniazdowych.

9

5. Poszukiwania ewolucyjne

Podstawowym problemem jest sposób kodowania cech w chromosomie i dobór operatorów gene-
tycznych. Najczęściej chromosom odpowiada permutacji lub ciągowi permutacji.

2

Metody rozwiązywania zadań optymalizacji dyskretnej

2.1

Kryteria optymalizacji

Zadanie optymalizacyjne polega na wyznaczeniu rozwiązania dopuszczalnego, dla którego przyjęta

funkcja celu osiąga wartość optymalną. Funkcja celu łączy funkcje kosztu definiowane dla każdego
z zadań. Przyjęcie funkcji celu oznacza dokonanie wyboru kryterium optymalizacji. Dwie podstawowe
klasy funkcji celu to: (1) kryteria regularne - uwzględniające funkcje reprezentujące koszty związane
z zakończeniem zadań; (2) kryteria nieregularne - dodatkowo uwzględniające funkcje reprezentujące
koszty związane z rozpoczęciem zadań.

Jednym z najczęściej używanych kryteriów jest termin zakończenia wykonania wszystkich zadań.

Inne kryteria to suma terminów zakończenia zadań, oraz modyfikacja tego podejścia, czyli średni
termin zakończenia zadań.

W przypadku gdy zadania mają określone pożądane terminy zakończenia, przyjmuje się za kryte-

rium maksymalną nieterminowość zakończenia zadań (maksymalną różnicę czasu zakończenia danego
zadania i jego pożądanego terminu zakończenia), sumę nieterminowości zakończenia zadań lub średnią
nieterminowość zakończenia zadań.

Pilność zakończenia zdań uwzględnia się poprzez przypisanie im wag.
Inne kryteria praktyczne oparte są o spóźnienia zadań, ich czas (koszt) przepływu przez system

oraz ich czas bezczynności w systemie, czas przestoju maszyn, stopień wykorzystania maszyn. Grupa
miar pochodząca od kryteriów nieregularnych używana jest w kontekście systemów wytwarzania just
in time. Zadania z takimi kryteriami są jednymi z trudniejszych w teorii szeregowania.

2.2

Trudność rozwiązywania zadań optymalizacji

Zadania optymalizacji są kłopotliwe z obliczeniowego punktu widzenia. Cechy zadań: brak kla-

sycznych własności analitycznych (różniczkowalność, liniowość), znaczna liczba ekstremów lokalnych,
NP-trudność.

2.3

Dokładne metody optymalizacji dyskretnej

Celem metod dokładnych jest znalezienie rozwiązania optymalnego globalnie. Metody te często są

czaso- i pamięciochłonne. Problemem jest także wiarygodność danych wejściowych, które mogą ulec
zaburzeniu już po wyznaczeniu rozwiązania optymalnego. Istnieje pewna grupa problemów, dla któ-
rych zastosowanie metod dokładnych jest wskazane (przykład: poszukiwania minimalnego czasu cyklu
dla powtarzalnego procesu produkcyjnego o niewielkim repertuarze wyrobów).

Do metod dokładnych należą:

1. Schemat podziału i ograniczeń.

Schemat Branch-and-Bound nie jest konkretnym algorytmem lecz pewnym podejściem opar-
tym na dekompozycji zbioru rozwiązań dopuszczalnych i przeszukiwaniu tego zbioru w oparciu
o dekompozycję. Zastosowanie algorytmów opartych o ten schemat jest słuszne tylko gdy mamy
pewność o silnej NP-trudności problemu - dostarcza on algorytmów wykładniczych.

Rozbicie zbioru rozwiązań na podzbiory daje szereg podproblemów. Mogą one być rozwiązywane
szeregowo lub równolegle. Dekompozycja ma sens, jeśli podproblemy są łatwiejsze w rozwiązywa-
niu od początkowego zadania. Podproblemy rozwiązuje się korzystając z sekwencji następujących
podejść:

• Relaksacja (usunięcie lub osłabienie) ograniczeń (wyznaczających zbiór rozwiązań dopusz-

czalnych) lub funkcji celu. Relaksacja funkcji celu to zastąpienie jej funkcją, która zwraca

10

mniejsze wartości (lepszą ocenę) dla każdego rozwiązania. Jeżeli rozwiązanie podproble-
mu zrelaksowanego należy do zbioru rozwiązań podproblemu bez relaksacji, to otrzymane
rozwiązanie jest rozwiązaniem optymalnym. W przeciwnym wypadku otrzymujemy dolne
ograniczenie wartości funkcji celu dla wszystkich rozwiązań podproblemu. W praktyce re-
laksacja jest czymś specyficznym dla każdego problemu, gdyż chodzi o konkretną redukcję
trudności problemu.

• Podejście bezpośredniego rozwiązania podproblemu polega na obliczeniu wartości funkcji

celu dla wszystkich rozwiązań dopuszczalnych w celu wyboru wartości minimalnej, przy
założeniu, że zbiór rozwiązań jest niewielki (ma to miejsce przy dostatecznej dekompozycji
problemu początkowego). W praktyce podejścia tego używa się tylko dla zbiorów jedno-
elementowych.

• Podejście pośredniego rozwiązania podproblemu polega na eliminacji podproblemu jako nie

zawierającego rozwiązań, w przypadku gdy stwierdzimy, że ograniczenie dolne jest większe
od górnego.

• Podział podproblemu stosujemy, gdy nie można go rozwiązać z wykorzystaniem podejść

wymienionych powyżej. Dzielenie podproblemów na dalsze podproblemy powoduje, że wy-
godnie jest przedstawić ten proces w postaci drzewa.

Dla każdego B&B następujące elementy muszą być określone: reguła wyboru podproblemów i ko-
lejności ich rozwiązywania; relaksacja dostarczająca ograniczenia dolne; reguła eliminacji pod-
problemu, odpowiadająca podejściu pośredniemu; zasada podziału, określająca sposób podziału
podproblemu na dalsze podproblemu. Im więcej podproblemów jest eliminowanych w trakcie
działania algorytmu, tym lepszej jest on jakości.

2. Schemat programowania dynamicznego.

To ogólne podejście polegające na przekształceniu zadania optymalizacji w wieloetapowy pro-
ces podejmowania decyzji. Stan każdego etapu zależy od stanu etapu poprzedniego i podjętej
poprzednio decyzji. Decyzje wybierane są ze zbioru decyzji dopuszczalnych. Przy znanym sta-
nie początkowym, przebieg wieloetapowego procesu jest wyznaczony przez ciąg decyzji, zwany
strategią. Z procesem podejmowania decyzji wiąże się skalarną funkcję celu, zaś strategię ją
minimalizującą nazywa się strategią optymalną.

Trudność optymalizacji funkcji celu związanej ze schematem powoduje, że jego zastosowanie jest
ograniczone do pewnej klasy problemów decyzyjnych bez pamięci. Chodzi o problemy mające
własność Markowa (przebieg procesu nie zależy od historii, lecz tylko od aktualnego stanu).
Istnieje wiele problemów o znaczeniu technicznym i ekonomicznym posiadających tą własność.

Dla procesów z własnością Markowa strategia optymalna podlega zasadzie optymalności Bel-
lmana: niezależnie od stanu i decyzji podanych na wejście, pozostałe decyzje muszą tworzyć
strategię optymalną z punktu widzenia stanu wynikłego z decyzji pierwszej.

Schemat PD w problemach szeregowania pełni funkcje zasadnicze (podstawa algorytmu), lub
funkcje pomocnicze (algorytm składowy). Złożoność zależy od aplikacji.

3. Programowanie liniowe całkowitoliczbowe. Schemat odcięć. Algorytm Land-Doig’a.

Zadanie PLC odnosi się do problemu, w którym funkcja celu jest funkcją liniową, zaś zbiór
rozwiązań jest określony zestawem ograniczeń z żądaniem, by składowe wektora rozwiązania były
liczbami całkowitymi. Znanym algorytmem rozwiązywania zadania PL jest metoda sympleks.
Kiedy nie wszystkie składowe wektora są liczbami całkowitymi, to mamy do czynienia z zadaniem
mieszanym (PLCM), do którego można stosować algorytmy oparte na schemacie odcięć lub alg.
Land-Doig’a.

• Schemat odcięć.

Idea polega na rozwiązywaniu ciągu zrelaksowanych zadań PL zbiegających do rozwiąza-
nia optymalnego. Startowym zadaniem jest PLC zrelaksowany poprzez usunięcie warunku

11

całkowitoliczbowości. Proces kończy się jeśli rozwiązanie zadania zrelaksowanego jest do-
puszczalne dla PLC. W przeciwnym wypadku do aktualnego zadania zrelaksowanego do-
łącza się ograniczenie powodujące odcięcie niedopuszczalnego rozwiązania, po czym proces
się powtarza. Różne metody odcięć określają różne algorytmy oparte o ten schemat.

• Algorytm Land-Doig’a.

Algorytm ten rozwiązuje zadanie PLC lub PLCM w oparciu o B&B. Dolne ograniczenie
otrzymuje się przez relaksację warunku całkowitoliczbowości. Górne jest uaktualniane każ-
dorazowo po otrzymaniu rozwiązania podproblemu.

4. Programowanie całkowitoliczbowe binarne. Algorytm Balasa.

Zadanie PLB odnosi się do problemu, gdzie składowe wektora rozwiązań mogą przyjmować
wartości binarne. Stosowanie znanych alg. PLC do tego problemu nie jest zalecane ze względu
na błędy zaokrągleń. Transformacja PLC w PLB korzystająca z dwójkowej reprezentacji liczb
całkowitych powoduje niekorzystny wzrost rozmiaru problemu (więc i koszt obliczeń). Przykła-
dem innego podejścia jest algorytm Balasa, rozwiązujący PLB w oparciu o B&B.

2.4

Przybliżone metody optymalizacji dyskretnej

Metody przybliżone mają wyznaczać rozwiązania bliskie optymalnym globalnie. Metod tego rodza-

ju jest znacznie więcej niż metod dokładnych. Często dla tego samego problemu istnieje wiele alterna-
tywnych metod o różnych cechach numerycznych. Jakość metod przybliżonych ocenia się na podstawie
złożoności obliczeniowej oraz dokładności przybliżenia. Inne brane pod uwagę parametry: gwarancja
zbieżności, szybkość zbieżności.

Błąd przybliżenia można zdefiniować np. jako: różnicę rozwiązania przybliżonego i optymalnego

lub ich stosunek. Może on być badany analitycznie lub eksperymentalnie. Analiza eksperymentalna
jest popularniejszą i łatwiejszą metodą, lecz jej wynik zależy od wyboru przykładowej próbki. Analizy
najgorszego przypadku i probabilistyczna dostarczają, wraz z analizą eksperymentalną oraz analizą
złożoności obliczeniowej, kompletną charakterystykę algorytmu.

Tradycyjne metody przybliżone dzieli się na konstrukcyjne oraz poprawiające. Pierwsze są szyb-

kie, łatwe do zaimplementowania, lecz generują rozwiązania obarczone dość dużym błędem. Drugie są
wolniejsze, polegają na poprawianiu krokowo początkowego rozwiązania i dostarczają wyników bardzo
dobrych. Jednak tylko nieliczne metody poprawiające doczekały się teoretycznej oceny błędu przybli-
żenia.

Eksperymentalnie weryfikowana dobroć algorytmów zależy od krajobrazu przestrzeni rozwiązań.

Krajobraz jest statycznym związkiem pomiędzy odległością rozwiązań a ich wartościami funkcji celu.
Rozkład wartości funkcji celu jest zbliżony do chaotycznego, z licznymi ekstremami lokalnymi, pełnią-
cymi rolę atraktorów. Nowo projektowane algorytmy zbierają informacje o cechach przestrzeni rozwią-
zań i wykorzystują je do modyfikacji kierunków poszukiwań. Dla większości zagadnień potwierdza się
eksperymentalnie istnienie dolin zawierających liczne, blisko położone „dobre” ekstreama lokalne.

Krajobraz bada się generując ścieżki przechodzące przez przestrzeń i łączące wybrane rozwiązania.

Mogą być one generowane przez kombinację rozwiązań, lub kierunkowane za pomocą miary odle-
głości (wychodząc od danego rozwiązania generuje się trajektorię zbieżną w sensie miary odległości
do drugiego rozwiązania).

Do metod przybliżonych należą między innymi:

1. Reguły priorytetowe (dispatching rules).

To najbardziej popularna i powszechnie używana technika szybkiego wyznaczania rozwiązania,
zwłaszcza w systemach produkcyjnych i komputerowych. Zalety: prostota, niski koszt obliczeń,
niska wrażliwość na zaburzenia danych wejściowych, dobre do systemów niedeterministycznych.
Wyróżnia się reguły statyczne (wartość priorytetu nie zmienia się w trakcie oczekiwana na usłu-
gę) oraz dynamiczne. W zależności od problemu i zastosowanej reguły rozwiązania są odległe
od optymalnego o 25% - 500% skrajnie.

Reguły priorytetowe to przykład metod konstrukcyjnych.

12

2. Obcięte B&B (curtailed, truncated B&B).

Powstaje przez wprowadzanie ograniczeń komputerowych (czas pracy procesora, pamięć) do kla-
sycznego schematu. Ograniczenia te mogą przybierać następujące postaci: (1) eliminacja pod-
problemów położonych w drzewie głębiej niż pewna wartość progowa; (2) ograniczenie liczby
rozważanych podproblemów danego podziału (jeżeli podzielono problem na więcej niż s części,
to rozważa się tylko pierwszych s podproblemów); (3) ograniczenie całkowitej liczby węzłów
w drzewie; (4) ograniczenie czasu pracy algorytmu; (5) eliminacja tych podproblemów, dla któ-
rych stosunek ograniczenia górnego do dolnego jest mniejszy od ustalonej wartości. Redukcja
czasu obliczeń w porównaniu ze schematem klasycznym jest znaczna. Jednak pozostaje wada
znacznego wzrostu ilości obliczeń po przekroczeniu względnie niedużego rozmiaru problemu. Do-
datkowo zdarza się, że dla niektórych aplikacji algorytm po zakończeniu działania nie dostarcza
dopuszczalnego rozwiązania.

Szczególne warianty tego podejścia:

• Poszukiwanie adaptacyjne (algorytmy A, lub A*).

Polega na poszukiwaniu rozwiązania przybliżonego, co skutkuje zmniejszeniem nakładu ob-
liczeń w stosunku do klasycznego B&B i pogorszenia funkcji celu. W praktyce eliminuje się
podproblemy korzystając z podejścia (5). Algorytmy tego typu charakteryzują się silną
nieliniowością relacji koszt obliczeń - dokładność.

• Poszukiwanie snopowe (beam search).

Nazwa od podobieństwa do „oświetlania” snopem światła przestrzeni rozwiązań. Każdy
oświetlony punkt przestrzeni rozwiązań staje się źródłem ukierunkowanej wiązki, zawiera-
jącej pewną liczbę rozwiązań potomnych. Ocena przydatności rozwiązań jest prowadzona
w oparciu o funkcję celu lub inne funkcje. W odniesieniu do obciętego B&B poszukiwanie
snopowe ogranicza liczbę bezpośrednich następników węzła w drzewie rozwiązań podlegają-
cych rozwinięciu. Liczba ta nie może być większa od ustalonej szerokości wiązki. Rozwija się
węzły obiecujące w sensie np. wartości dolnego ograniczenia lub innej funkcji oceny. Wybór
węzłów nazywamy filtrowaniem, liczba węzłów wynika z szerokości filtra. Metoda z filtrem
nosi nazwę filtrowanego poszukiwania wiązką.

3. Poszukiwania lokalne (local search).

Bazą metody jest analiza rozwiązań leżących w otoczeniu wybranego rozwiązania bieżącego.
Analiza dostarcza rozwiązań, które stają się kolejnymi źródłami lokalnych otoczeń, zastępując
rozwiązania bieżące. Zalety metod local search: duża szybkość pracy, prostota implementacji,
mały błąd do rozwiązania optymalnego.

Strategie poszukiwania: (1) do pierwszej poprawy (pierwsze rozwiązanie w otoczeniu spełniające
warunek zastępuje bieżące rozw.); (2) do najlepszej poprawy (wykonywany jest proces spraw-
dzania całego otoczenia, rozw. najlepsze zastępuje rozw. bieżące). Pierwsza strategia jest mniej
kosztowna obliczeniowo i mniej zbieżna. Jej dobroć zaś zależy od kolejności przeglądania.

Poszukiwania lokalne często nazywa się metodami popraw lub metodami iteracyjnymi. Pierwsze
określenie jest nieco mylące, gdyż nie zawsze cykl iteracyjny poszukiwań lokalnych dostarcza
rozwiązania poprawionego w sensie wartości funkcji celu.

Liczba rozwiązań powoduje, że techniką local search da się przejrzeć tylko znikomą ich część,
nawet jeżeli obiecujące rozwiązania skupione są w jednej dolinie. Stąd dobry proces poszuki-
wań powinien realizować dwa zadania: (1) intensyfikacji poszukiwań (przeszukiwanie niewielkich
obiecujących obszarów); (2) dywersyfikacja poszukiwań (rozproszone przeszukiwanie odległych
obszarów w celu zlokalizowania tych najbardziej obiecujących).

Przykłady różnych podejść do poszukiwań:

• Poszukiwanie zstępujące (descending search).

Historycznie najstarsza technika poprawy rozwiązania, pokrewna do techniki wspinaczki
(hill climbing ) dla problemów maksymalizacyjnych. Elementarny krok polega na przeszu-
kaniu sąsiedztwa (otoczenia lokalnego) bieżącego rozwiązania w celu znalezienia kolejnego

13

rozwiązania z najmniejszą wartością funkcji celu i zastąpienia bieżącego rozwiązania no-
wym rozwiązaniem. Proces jest powtarzany dopóki wartość funkcji celu maleje. W pewnym
stopniu można ograniczyć wrażliwość metody na lokalne ekstrema przez kilkukrotne jej
uruchomienie z różnych pozycji początkowych.

• Poszukiwanie progowe (threshold search).

Algorytmy te akceptują takie rozwiązania z otoczenia lokalnego, dla których różnica mię-
dzy wartością funkcji celu dla nowo znalezionego rozwiązania i dla rozwiązania bieżącego
(którego otoczenie jest przeszukiwane) jest mniejsza, niż pewna wartość progowa. Jeżeli
wartość progowa jest równa 0, to mamy do czynienia z poszukiwaniem zstępującym. Intu-
icyjnie wartość progu powinna być względnie duża na początku i dążyć do zera w procesie
szukania.

Następujące algorytmy mogą być traktowane jako poszukiwanie progowe z losowo wybie-
raną w każdym kroku wartością progową:

– Poszukiwanie losowe (random serach).

Metoda generuje trajektorię poszukiwań tak, że kolejne rozwiązanie jest wybierane loso-
wo z sąsiedztwa bieżącego. Jako wynik poszukiwań zwracane jest rozwiązanie najlepsze
z trajektorii. Często występuje pod nazwą metody Monte-Carlo. Zaleta: niewrażliwość
na ekstrema lokalne. Wada: słaba zbieżność. W celu skierowania poszukiwań w bar-
dziej obiecujący obszar wprowadza się modyfikacje rozkładu prawdopodobieństwa przy
wyborze sąsiada.

– Symulowane wyżarzanie (simulated annealing).

Wyprowadzanie trajektorii poszukiwań z ekstremum lokalnego i unikanie takiego eks-
tremum jest w tej metodzie podobne do termodynamicznego procesu studzenia. Stany
ciała są porównywane do rozwiązań, energia ciała do wartości funkcji celu.
SA generuje trajektorię poszukiwań takich, że każde kolejne rozwiązanie jest wybierane
w następujący sposób. Najpierw wybiera się z sąsiedztwa rozwiązania bieżącego roz-
wiązanie zaburzone w sposób uporządkowany lub losowo, z równomiernym rozkładem
prawdopodobieństwa. Jeżeli wartość funkcji celu zaburzonego rozwiązania jest mniej-
sza lub równa wartości funkcji celu rozwiązania bieżącego, to rozwiązanie zaburzone
jest akceptowane natychmiast. W przeciwnym wypadku rozwiązanie zaburzone jest
akceptowane z prawdopodobieństwem zależnym od temperatury bieżącej iteracji. Jeśli
rozwiązanie zaburzone nie zostało zaakceptowane to pozostawiamy rozwiązanie bieżące
jako obowiązujące w kolejnej iteracji.
Temperatura zmienia się w czasie iteracji według schematu studzenia. Stosowane sche-
maty zmian temperatury: geometryczny i logarytmiczny.
Liczne parametry metody SA dobiera się eksperymentalnie. Silny wpływ na metodę ma
dobór schematu studzenia. Zbyt szybkie studzenie upodabnia metodę do poszukiwania
zstępującego, zbyt powolne daje nie do zaakceptowania wydłużony czas działania.
Modyfikacje metody: (1) w każdej iteracji generujemy próbkę rozwiązań zaburzonych
i wybieramy najlepszą; (2) akceptujemy z jednakowym prawdopodobieństwem zaburze-
nia korzystne i niekorzystne; (3) dopuszczamy okresowe wzrosty (skoki) temperatury
do wartości początkowej.
Metoda SA przy spełnieniu pewnych założeń zbiega do optymalnego z prawdopodobień-
stwem 1. SA uważa się za jedno z mocniejszych narzędzi do rozwiązywania trudnych
problemów optymalizacji dyskretnej.

– Symulowane wstrząsanie (simulated jumping).

SJ także używa analogii termodynamicznej do sterowania poszukiwaniami i unika-
nia ekstremów. Proces wstrząsania polega na naprzemiennym gwałtownym ogrzewaniu
i oziębianiu ciała, powodując potrząsanie jego stanem energetycznym. Proces ten jest
kontynuowany do osiągnięcia pożądanego stanu końcowego o niskiej energii. Wstrzą-
sanie pozwala na uzyskanie dostępu do wielu obszarów zbioru rozwiązań, zapobiega
pozostaniu w ekstremum i zwiększa prawdopodobieństwo osiągnięcia minimum global-
nego.

14

W praktyce SJ wprowadza do SA dodatkowy schemat podgrzewania, który jest stoso-
wany w przypadku niezaakceptowania rozwiązania zaburzonego. SJ wymaga ekspery-
mentalnego doboru większej liczby parametrów niż SA.

• Poszukiwanie z zakazami (tabu search).

Metoda zaproponowana przez Glovera. TS zaczyna od pewnego rozwiązania początkowego,
zaś elementarny krok wykonuje przeszukanie sąsiedztwa rozwiązania bieżącego. Sąsiedztwo
definiowane jest przez ruchy przejścia, które można wykonać z rozw. bieżącego. (Ruch to
transformacja jednego rozwiązania w drugie.) Celem jest znalezienie w sąsiedztwie roz-
wiązania o najmniejszej wartości funkcji oceny. Proces jest powtarzany od najlepszego
znalezionego rozwiązania. Metoda zwraca jako wynik najlepsze rozwiązanie z trajektorii.
Aby zapobiec cyklicznemu powtarzaniu się trajektorii, zatrzymaniu na ekstremum, oraz
aby prowadzić trajektorię w obiecujące obszary wprowadza się pamięć historii poszukiwań.
Najczęściej używa się krótkoterminowej pamięci zwanej listą zabronień (listą tabu). Lista
ta przechowuje: najświeższe rozwiązania z trajektorii, wybrane atrybuty rozwiązań, ruchy
do nich prowadzące lub atrybuty tych ruchów. TS traktuje tą listę jako formę zabronienia
dla ruchów przyszłych.

Zabronienie dla danego ruchu może zostać cofnięte, jeżeli funkcja aspiracji uzna ten ruch
za wystarczająco korzystny.

Kryteria zatrzymania algorytmu: wykonanie pewnej liczby iteracji bez poprawy wartości
funkcji celu, wykonie założonej z góry liczby iteracji, przekroczenie czasu, znalezienie od-
powiedniego rozwiązania.

4. Poszukiwania ewolucyjne (evolutionary, genetic search).

Metoda ta wykorzystuje podzbiór rozproszonych rozwiązań dopuszczalnych, do prowadzenia po-
szukiwań równocześnie w wielu obszarach zbioru rozwiązań. Podzbiór ten nazywamy populacją.
Pozwala to na uniknięcie ekstremów lokalnych i zbadanie wielu obszarów.

Każde rozwiązanie (nazywane osobnikiem) kodowane jest przez zbiór atrybutów w materiale
genetycznym. Technika kodowania zależy od typu problemu. Populacja jest kontrolowana przez
następujące po sobie procesy: (1) reprodukcji (powielanie osobników proporcjonalnie do ich miary
adaptacji - funkcją adaptacji może być wartość funkcji celu dla danego osobnika), (2) krzyżowania
(wybranie z rozszerzonej populacji puli rodzicielskiej oraz generacja odnowionego pokolenia za
pomocą losowego kojarzenia par rodziców i stosowania operatora krzyżowania genetycznego), (3)
mutacji (stanowi ona ubezpieczenie na wypadek utraty istotnych atrybutów rozwiązań i pozwala
na wprowadzanie atrybutów innowacyjnych), (4) przeżycia lub selekcji (wybrania osobników
wchodzących w skład kolejnej populacji).

Dla tej metody należy określić: sposób kodowania atrybutów w chromosomach, postać funkcji
adaptacji, schemat wyboru puli rodzicielskiej, schemat kojarzenia rodziców, operatory krzyżo-
wania, schemat mutacji, schemat przeżywania.

Właściwości algorytmów genetycznych wymagające poprawy: przedwczesna zbieżność do lokal-
nego ekstremum (powodowana niewłaściwym sterowaniem dynamiką rozwoju - preferowanie naj-
lepszych osobników powoduje stałe zmniejszanie rozproszenia genetycznego populacji, co zmniej-
sza możliwości znalezienia istotnie lepszego rozwiązania), słaba zbieżność do rozwiązań bliskich
optymalnym.

Techniki kontrolowania zbieżności algorytmu: zapobieganie kazirodztwu, podział populacji na
wyspy (model migracyjny), nakładające się sąsiedztwa (model dyfuzyjny), wprowadzanie zacho-
wań społecznych.

Metoda poszukiwań ewolucyjnych wymaga przeprowadzenia dużej liczby eksperymentów w celu
ustalenia parametrów algorytmu.

Podklasę metody poszukiwań ewolucyjnych stanowi ewolucja różnicowa (differential evolution).
Wykorzystuje ona inne mechanizmy mutacji i krzyżowania. Każdy osobnik jest rodzicem jed-
nego rozwiązania próbnego (powstałego na bazie rodzica) oraz dwóch rozwiązań kierunkowych

15

(wybranych losowo z populacji). Generowanie potomka polega na przeprowadzeniu kombinacji
liniowej rozwiązań z elementami losowości. Losowość zapobiega powielaniu rodzica. Mutacja jest
samo-adaptacyjna. Jeśli rozwiązanie próbne jest lepsze w sensie wartości funkcji celu to zastępuje
rodzica, inaczej jest odrzucane. Odnawianie populacji jest powtarzane do momentu osiągnięcia
zadanej liczby generacji, lub przy wystąpieniu stagnacji poszukiwań. Liczne parametry tej me-
tody dobierane są eksperymentalnie.

Ewolucja różnicowa jak na razie nie jest stosowana dla problemów szeregowania. Opisano im-
plementacje dla problemów projektowania filtrów cyfrowych, projektowania konstrukcji mecha-
nicznych oraz optycznych.

5. Inne metody przybliżone.

Metody w fazie rozwoju, nie będące jeszcze konkurencyjne w stosunku do GS, TS, SA:

• Podejście immunologiczne (artificial immune system).

Początki w latach 90. Termin: antygen - chwilowe wymagania narzucone na rozwiązanie,
przeciwciało - lista instrukcji (algorytm) na utworzenie rozwiązania spełniającego wyma-
gania antygenu (mechanizm agregacji oraz rekombinacji pozwala na przechowywanie i kon-
struowanie nowych przeciwciał), dopasowanie - dobranie przeciwciała do antygenu.

• Poszukiwanie mrówkowe (ant search).

• Sieci neuronowe.

16