algorytm.org

Algorytm SPT (Shortest Procesing Time)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm SPT (Shortest Procesing Time)
Ocena użytkowników:***** / 9
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:32

SPT to algorytm listowego szeregowania zadań. Służy on do takiego rozkładu zadań na danych maszynach, by suma zakończeń czasów wykonywania zadań była minimalna. Idea algorytmy jest bardzo prosta: najpierw listę zadań należy posortować niemalejącą, wg czasów wykonywania, a następnie należy przydzielać kolejno zadania do maszyn. Najłatwiej zrozumieć to na prostym przykładzie:

Dane są 3 identyczne maszyny oraz zbiór zadań o następujących czasach wykonania:
1h, 1.5h, 15 min, 2h, 30min, 3h, 0.45h
Zgodnie z tym ,co powiedziałem wcześniej, listę należy posortować: 15min, 30min, 45min, 1h, 1.5h, 2h, 3h.
W kolejnym kroku zaczynamy przydzielać zadania do wolnych maszyn, zaczynając od pierwszej 15min, następnie druga: 30min i trzecia: 45min, powracamy do pierwszej i przydzielamy jej kolejne: 1h (w sumie: 15min+1h), drugiej: 1.5h (w sumie: 30min+1.5h), trzecia: 2h (w sumie: 45min+2h) i znów powracamy do pierwszej: 3h (w sumie 15min+1h+3h).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2010 18:47
Komentarze
photo
-1 # Bartek 2010-01-18 10:59
właściwie co ma wspólnego ten algorytm z algorytmami grafowymi??
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # ciapek 2012-12-02 20:56
Tyle, że wykorzystuje kolorowanie grafu, a treść zadania została napisana na tyle ogólnie, że jednoznacznie tego nie pokazuje
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz