Szeregowanie zadań jest jednym z najważniejszych zagadnień w algorytmice. Jest toproblem często spotykany częst zarówno przy projektowaniu różnorodnego typu algorytmów jak i przy badaniu ich efektywności. W ramach laboratorium którego dotyczy to sprawozdanie realizowaliśmy jednomaszynowy problem szeregowania zadań z uwzględnieniem kryterium ważonej sumy obciążeń dla algorytmu Branch and Bound.
1.Jednomaszynowy Problem szeregowania zadań z kryterium ważonej sumy obciążeń
Problem polega na odpowiednim uszeregowaniu dostępnych zadań funkcja kosztów dla tego problemu była minimalna. Każde z zadań posiada trzy parametry"
Pj - Czas wykonania zadania
Dj - Oczekiwany czas realizacj
Wj - Waga zadania
Dodatkowo można wyznaczyć jeszcze Cj która jest sumą wszystkich czasów zadań poprzedzajacych obecne (włącznie z nim)
Kryterium prezentuje się następująco: Min( Max(0,Cj-Dj)*Wj);
Poszukujemy takiej permutacji elementów dla której wartość tego kryterium będzie najmniejsze.