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).

Komentarze