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
Problemem do rozwiązania jest podział zadań na dwie fabryki, gdzie jedna z nich, nazywana dalej naszą, ma ograniczoną liczbę zadań do wykonania, a druga, nazywana zewnętrzną, ma ograniczony budżet. Optymalizowanym kryterium jest czas wykonania wszystkich zadań równy dłuższemu z czasów działania obu fabryk.
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ść czasochłonna, dlatego nie nadaje się do wykonywania zadań na dużych zbiorach.
W przypadku naszego zadania permutacje można generować na dwa sposoby. Pierwszy z nich to generacja wszystkich możliwych permutacji zbioru zadań, a następnie odrzucanie tych, które nie spełniają podanych ograniczeń, tj. liczba zadań 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.
Do generacji możliwych rozwiązań 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ązań przyjmuje dwa parametry, którymi są liczba zadań 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 zadań jest o jeden mniejszy. Gdy parametr liczby osiągnie 0 to jest wykonywane sprawdzanie, które polega na zsumowaniu kosztów wykonania zadań 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żyć opisana powyżej funkcja rekurencyjna potrafi wygenerować tylko permutacje o konkretnej liczbie zadań we własnej fabryce. Powstaje pytanie, co z permutacjami, gdzie wykonujemy mniej zdań? 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 zadań. Przypadek, w którym wszystkie zadania są wykonane w zewnętrznej fabryce jest sprawdzany jako pierwszy bez wywoływania funkcji rekurencyjnej.
W moim rozumieniu program ma sprawdzić 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 zadań. 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 zadań 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 zadań algorytm wybiera pierwsze od lewej.