9752256895

Załóżmy, źe 7r jest optymalnym porządkiem oraz źe istnieją x,y takie, źe x < y oraz U_x > U_y. Zamieniając i_x oraz i_y miejscami otrzymujemy nowy porządek n' o koszcie:

r(7r') = (n - x + l)t_iy + (n - y + l)t_ix +    ^ (n-k + l)t_ile.

k=ljejtx,y

Nowy porządek jest lepszy, ponieważ

T(tt) - T(ir') = (n - x + 1 )(U_X - U_y) + (n - y + l)(fi_y ~ U_x) — (y - x)(ti_x - U_y) > 0 co jest sprzeczne z założeniem optymalności 7r.    □

7.2.2 Szeregowanie z terminami

Scenariusz: System z jednym procesorem ma do wykonania n zadań. Każde z nich wymaga jednej jednostki czasu procesora. Dla każdego zadania znany jest zysk jaki otrzyma system za jego wykonanie oraz termin. Za wykonanie zadania po terminie system nie otrzymuje żadnego zysku. Naszym celem jest ustawienie zadań w kolejności maksymalizującej zysk.

Definicja 3 Ciąg zadań (ii,*2 ••■*«) taki, źe Vk=i...n k < di_k nazywamy wykonalnym. Zbiór zadań jest wykonalny, jeśli wszystkie jego elementy można ustawić w ciąg wykonalny.

Problem:

Dane:    ciąg d\,... ,dn liczb naturalnych oraz

ciąg 51,.. ■, g_n dodatnich liczb rzeczywistych;

(Interpretacja: dj-termin dla ż-tego zadania; gi~zysk za i-te zadanie).

Zadanie: znale"xć wykonalny podzbiór zadań S C {l,...,n} maksymalizujący sumę YlieSdi-

Strategia zachłanna: Startując od zbioru pustego konstruujemy wykonalny zbiór zadań, na każdym kroku dodając do niego zadanie o największym gi spośród zadań jeszcze nie rozważonych (pod warunkiem, źe zbiór pozostaje wykonalny).

Dowód poprawności (szkic): Załóżmy, źe nasz algorytm wybrał zbiór zadań I, podczas gdy istnieje zbiór optymalny J ^ I. Pokażemy, źe dla obydwu zbiorów zysk za wykonanie zadań jest taki sam. Niech 7r/,7rj-wykonalne ciągi zadań z I i J. Dowód przebiega w dwóch etapach:

1.    Wykonując przestawienia otrzymujemy ciągi 7oraz 7t'j takie, źe wszystkie wspólne zadania (tj. z IflJ) wykonują się w tym samym czasie.

2.    Pokazujemy, źe w pozostałych jednostkach czasowych ir'j oraz 7t'j mają zaplanowane wykonanie zadań o tym samym zysku.

Ad.l. Niech a € Jfl J będzie zadaniem umieszczonym na różnych pozycjach w 7r/ oraz ttj. Niech będą to pozycje odpowiednio i oraz j. Bez zmniejszenia ogólności możemy założyć, źe i < j. Niech ponadto V^<j na pozycji k ciągi 717 oraz 717 mają albo zadania spoza I D J albo takie samo zadanie z I fi J.

Zadanie a w ciągu 717 możemy zamienić miejscami z zadaniem znajdującym się na pozycji j, nazwijmy to zadanie b. Otrzymamy ciąg wykonalny, gdyż:

11