4087490269

19

4.3. KRYTERIA OPTYMALIZACJI

Si - przyśpieszenie rozpoczęcia zadania, Si =^f \ri — <Si]⁺ fi(t) - niemalejąca funkcja reprezentująca koszt związany z zakończeniem zadania i w chwili t ^ 0,

gi(t) - nierosnąca funkcja reprezentująca koszt związany z rozpoczęciem zadania i w chwili t > 0,

Ti - czas przepływu zadania przez system, Ti =^f Ci — ri

def

Wj - czas przestoju zadania przy przepływie przez system, W* = Ti —

Y^jeOi Pvjj

Tfc - czas przestoju (bezczynności) maszyny /c,

lii - jednostkowe spóźnienie zadania definiowane jako lii = 1 jeśli Ci > di oraz lii = 0 jeśli Ci < di.

Symbol [x]⁺ = max{0,x} będzie używany w dalszym ciągu dla skrócenia zapisu. Domyślnie przyjmuje się następujące założenia i ograniczenia: (a) wykonywanie operacji nie może być przerywane, (b) każda maszyna może wykonywać co najwyżej jedno zadanie w danej chwili czasowej. Przyjęcie innych założeń wymaga jawnego ich wyspecyfikowania.

Nie każdy problem szeregowania wymaga podania wszystkich wymienionych danych oraz wprowadzenia wszystkich wymienionych zmiennych decyzyjnych. Zwykle używamy minimalnego zbioru pojęć wystarczającego do opisu problemu. Przykładowo, w przypadku gdy dla każdego j E O zachodzi nij = 1, lA^ijl = 1 mówimy, że problem posiada maszyny dedykowane bowiem zmienne decyzyjne Vj nie podlegają wyborowi; wówczas też v nie występuje w modelu problemu.

4.3 Kryteria optymalizacji

Rozwiązaniem problemu szeregowania nazywamy parę wektorów (v,S), gdzie v = (v\,..., v₀) jest wektorem sposobów wykonywania operacji, zaś S = (Si,...,S₀) jest wektorem terminów rozpoczęcia operacji. Rozwiązanie spełniające wszystkie ograniczenia występujące w problemie nazywamy rozwiązaniem dopuszczalnym. Dla uproszczenia zapisu, w problemach z maszynami dedykowanymi symbol v będziemy pomijać w oznaczeniu rozwiązania. Ponieważ interesować nas będą głównie rozwiązania dopuszczalne, zatem określenie rozwiązanie będzie się odnosić do rozwiązania dopuszczalnego chyba, że komentarz ustanowi inaczej. Zadanie optymalizacyjne polega na wyznaczeniu rozwiązania dopuszczalnego, dla którego przyjęta funkcja celu osiąga wartość optymalną. Funkcja celu reprezentuje pewną praktyczną miarę jakości funkcjonowania systemu. W zasadzie spotyka się dwie podstawowe