Home - kzajac97/SPD GitHub Wiki
Sprawozdanie SPD - NEH
Metoda przeglądu zupełnego Liczba permutacji n-elemntowego zbioru wyrażona jest wzorem n! Czas obliczania permutacji dla 5 procesów wynosi 997000 ns Dla więszkej liczby procesów czas ten będzie rósł zgodnie ze wzorem Dla 8 procesów czas wynosi 0.1 s.
Metoda ta gwarantuje znalezienie optymalnej kolejności procesów, ale jest bardzo kosztowna obliczeniowo. Najlepiej stosować ją gdy liczba procesow jest mała (poniżej 10). Liczba maszyn nie wpływa na czas obliczeń.
Algorytm Johnsona Algorytm Johnsona gwarantuje znalezienie dobrego uszeregowania dla problemu 2 lub 3 maszynowego, a jego złożoność obliczeniowa jest znacznie lepsza niż w przypadku przeglądu zupełnego. Wadą jest brak możliwości wykorzystania dla problemów wielomaszynowych
Algorym Neh Algorytm zapewnie efetywne znajdowanie rozwiązań dla probleów mających duża liczbę procesów oraz maszyn. Dla problemów zawierających 100 procesów czasy wynoszą około 0.1 sekundy
Neh z akceleracją Zastosowanie akceleracji zmiejsza czas algorytmu neh o około 20%, przyspieszenie zaczyna być widoczne dla problemów mających 10 procesów, dla mniejszych problemów czasy są takie same
Neh z modyfikacją Modyfikacja polegająca na usuwaniu procesu, którego usunięcie spowoduje najwięszką zmianę C_max i ponowne wstawienie go pozwala zredukować całkowity czas wykonywania zadań.
Dla przykładu 100 procesów standardowy algorytm Neh zwraca C_max 6632, a Neh z modyfikacją 6479
Porównanie czasów
Czasy podawane w nanosekundach. Wykorzystano przykłady z programu neh.exe lub gdy nie było przykładu z odpowiednią ilością procesów lub maszyn generowane losowo Wszystkie algorytmy uzyskały taki sam czas C_max
- 0 oznacza czas zbyt mały aby został dokładnie zmierzony
- inf oznacza czas zbyt długi aby został zmierzony
| Liczba procesów | Przegląd zupełny | Johnson | NEH | NEH z akceleracją |
|---|---|---|---|---|
| 5 | 997000 | 0 | 0 | 0 |
| 10 | 1.3e10 | 0 | 1e6 | 1e6 |
| 20 | inf | 0 | 7e6 | 6e6 |
| 100 | inf | 1e6 | 6e8 | 5e8 |