Metoda podziału i oszacowań - przykład

Mamy następujące dane: 4 zadania o czasach t_j i żądanych terminach zakończenia zadania d_j:

Ekran wprowadzania danych - program Metoda podziału i oszacowań
 znajdujący się w portalu

Na tym przykładzie zostaną wykonane strategie: jumptracking i backtracking.

Strategia jumptracking

Wykres przedstawiający rozwiązanie problemu metodą podziału i oszacowań
dla strategii jumptracking

           -  dolne oszacowanie, na początku równe zero,
q              -  suma czasów zadań nieustawionych,
q = 10     -  suma czasów tj.

Analizując wykresy z powyższego rysunku widzimy, że kolejność wykonywania zadań stosując strategię jumptracking metody podziału i oszacowań to: 1|3|2|4|, natomiast stosując regułę EDD kolejność to: 1|3|4|2. Porównując obie metody możemy zauważyć, że w przypadku metody podziału i oszacowań, trzy z czterech zadań zakończyły się w satysfakcjonującym nas czasie, chodzi tu o zadania 1, 3, i 2, zadanie 4 ma spóźnienia cztery jednostki czasu. W przypadku reguły EDD, dwa z czterech zadań zakończyły się w zadawalającym nas czasie, a mianowicie zadanie 1 i 3, natomiast zadania 4 i 2 ma w sumie 5 jednostek czasu spóźnienia. Z przykładu tego wynika, że dla tych danych metoda podziału i oszacowań daje lepsze rezultaty. Na wykresie kolejność skreślania podproblemów opisano w prostokątach.

Do wyliczania b oraz q można skorzystać z następujących zależności:

gdzie:
akt    - aktualne, patrząc na wykres jesteśmy na aktualnym poziomie
pop   - poprzednie, jesteśmy na poziomie wcześniejszym

 

Strategia backtracking

Wykres przedstawiający rozwiązanie problemu metodą podziału i oszacowań
dla strategii backtracking

Widzimy, że problem rozwiązany strategią backtracking jest dużo obszerniejszy i wykonanie go zawiera więcej czasu.

powrót