Wrocław, 09.01.2011r.

Sprawozdanie z laboratorium

Optymalizacja czasu wykonania zadań przez dwie fabryki za pomocą

przeglądu zupełnego.

Prowadzący: dr inż. Mateusz Gorczyca

Autor: Gwidon Jóźwiak, 171864

1. Treść zadania.

Problemem do rozwiązania jest podział zadao na dwie fabryki, gdzie jedna z nich, nazywana dalej
naszą, ma ograniczoną liczbę zadao do wykonania, a druga, nazywana zewnętrzną, ma ograniczony
budżet. Optymalizowanym kryterium jest czas wykonania wszystkich zadao równy dłuższemu
z czasów działania obu fabryk.

2. Wstęp teoretyczny.

Przegląd zupełny jest algorytmem sprawdzającym wszystkie możliwe rozwiązania z danego zbioru
i wybierający najlepsze z nich. Jest to metoda dośd czasochłonna, dlatego nie nadaje się
do wykonywania zadao na dużych zbiorach.

W przypadku naszego zadania permutacje można generowad na dwa sposoby. Pierwszy z nich to
generacja wszystkich możliwych permutacji zbioru zadao, a następnie odrzucanie tych, które nie
spełniają podanych ograniczeo, tj. liczba zadao oraz budżet. Jest to bardzo czasochłonne i zbędne.
Druga metoda generuje tylko permutacje spełniające ograniczenie liczby wykonywania w pierwszej
fabryce. Jest to o wiele wydajniejsze, ponieważ unikamy generacji wielu niepotrzebnych permutacji
oraz sprawdzania ich poprawności.

3. Opis implementacji.

Do generacji możliwych rozwiązao użyłem drugiego z opisanych powyżej sposobów. Dokonałem tego
używając tablicy binarnej oraz funkcji rekurencyjnej. W tablicy jako 1 oznaczałem zadania do
wykonania w naszej fabryce, natomiast jako 0 te do wykonania w fabryce zewnętrznej.

Moja funkcja generacji rozwiązao przyjmuje dwa parametry, którymi są liczba zadao do wykonania
w naszej fabryce oraz miejsce startu. Jako miejsce startu określamy początkowe położenie „jedynki”
w tablicy. Funkcja w pętli przesuwa tą jedynkę o jedno miejsce i wywołuje siebie samą z parametrem
startu o jeden większym, natomiast parametr liczby zadao jest o jeden mniejszy. Gdy parametr liczby
osiągnie 0 to jest wykonywane sprawdzanie, które polega na zsumowaniu kosztów wykonania zadao
w fabryce zewnętrznej i porównaniu ich z budżetem. Jeżeli ten warunek jest spełniony to obliczamy
czasy wykonania, które zestawiamy z najlepszym dotychczas czasem i zamieniamy w przypadku
osiągnięci lepszego wyniku.

Jak można zauważyd opisana powyżej funkcja rekurencyjna potrafi wygenerowad tylko permutacje
o konkretnej liczbie zadao we własnej fabryce. Powstaje pytanie, co z permutacjami, gdzie
wykonujemy mniej zdao? Służy do tego funkcja sterująca generacją, która wywołuje ją dla parametru
liczba począwszy od 1 aż do ograniczonej liczby zadao. Przypadek, w którym wszystkie zadania są
wykonane w zewnętrznej fabryce jest sprawdzany jako pierwszy bez wywoływania funkcji
rekurencyjnej.

4. Dodatkowe wymyślone zadania.

4.1. Wykonywanie zadań we własnej fabryce od najtrudniejszych o ile

pozwala na to budżet.

W moim rozumieniu program ma sprawdzid tylko te przypadki, gdzie najtrudniejsze zadania są
wykonywane w naszej fabryce zachowując podane ograniczenia.

W tym celu dodałem dwie funkcje, które generują takie właśnie przypadki. Pierwsza z nich przyjmuje
dwa parametry: max – sprawdzenie, czy po raz pierwszy szukamy maximum z trudności wykonania
oraz a – mówiący o tym ile maximów już znaleźliśmy. Funkcja ta przeszukuje tablicę trudności
wykonania w celu odnalezienia zadania najtrudniejszego. Pomijane są zadania, które został wcześniej
znalezione, a odbywa się to za pomocą tablicy, w której przechowujemy indeksy wcześniej
znalezionych najtrudniejszych zadao. Zwracany jest indeks znalezionego zadania. Druga funkcja
wywołuje pierwszą z odpowiednimi parametrami. Za pierwszym razem max jest równe -1,
a w każdym następnym przypadku jest liczbą nieujemną, natomiast a jest kolejną iteracją pętli
zwiększoną o jeden (używamy go do przeglądania tablicy wcześniejszych maximów). Funkcja jest
wywoływana aż do osiągnięcia liczby zadao dozwolonych do wykonania w naszej fabryce. Druga
funkcja przeprowadza również sprawdzanie tak jak to się odbywało w przypadku punktu 3.
W przypadku powtarzających się trudności zadao algorytm wybiera pierwsze od lewej.