# Zadanie 7 - Lista 2
## Treść:
<img style="width: 100%" src="https://i.imgur.com/c6JxTR6.png" alt="Zadanie 7 Lista 2 2021">

## Rozwiązanie

### Algorytm:
1. Zainicjalizuj dwie zmienne $l=0,r=n-1$
2. Utwórz dwa zbiory:
2. Zbiór $O=\emptyset$ który będzie przechowywał optymalną kolejność wykoywania zadań
3. Zbiór $Z=\{a_i,b_i\},|Z|=n$ który będzie przechowywał pary z czasem wykonywania $i$-tego zadania na maszynach $A$ i $B$.
3. Dopóki zbiór $Z\ne \emptyset$:
3. Znajdź najkrótszy czas wykonywania pewnego zadania na dowolnej z maszyn, i zapisz go jako $p$ (W przypadku gdy takich zadań jest więcej niż jedno, weź pierwsze takie zadanie w zbiorze $Z$).
4. Dla każdego $i$ w zbiorze $Z$ wstaw za parę $\{a_i,b_i\}$, $\{a_i-p,b_i-p\}$
5. Dla każdego $i$ w zbiorze $Z$ jeżeli para jest postaci:
5.1 $\{0,b_i\}$ Dodaj tą parę do zbioru $O$ na indeksie $l$, usuń parę ze zbioru $Z$, $l+=1$.
5.2 $\{a_i,0\}$ Dodaj tą parę do zbioru $O$ na indeksie $r$, usuń parę ze zbioru $Z$, $r-=1$.

### Przykładowy przebieg algorytmu:
<div style="width: 100%; display: table;">
<div style="display: table-row">
<div style="display: table-cell">

1.
| $Z_i$ | $a_i$ | $b_i$ |
| -------- | -------- | -------- |
| a | **1** | 5 |
| b | 6 | 9 |
| c | 7 | 2 |
| d | 2 | 3 |
| e | 4 | 5 |

$O=\{\_,\_,\_,\_,\_\}$

</div>

<div style="display: table-cell">

2.
| $Z_i$ | $a_i$ | $b_i$ |
| -------- | -------- | -------- |
| _ | _ | _ |
| b | 5 | 8 |
| c | 6 | **1** |
| d | 1 | 2 |
| e | 3 | 4 |

$O=\{a,\_,\_,\_,\_\}$

</div>

<div style="display: table-cell">

3.
| $Z_i$ | $a_i$ | $b_i$ |
| -------- | -------- | -------- |
| _ | _ | _ |
| b | 4 | 7 |
| _ | _ | _ |
| d | **0** | 1 |
| e | 2 | 3 |

$O=\{a,\_,\_,\_,c\}$

</div>

<div style="display: table-cell">

4.
| $Z_i$ | $a_i$ | $b_i$ |
| -------- | -------- | -------- |
| _ | _ | _ |
| b | 4 | 7 |
| _ | _ | _ |
| _ | _ | _ |
| e | **2** | 3 |

$O=\{a,d,\_,\_,c\}$

</div>

<div style="display: table-cell">

5.
| $Z_i$ | $a_i$ | $b_i$ |
| -------- | -------- | -------- |
| _ | _ | _ |
| b | 2 | 5 |
| _ | _ | _ |
| _ | _ | _ |
| _ | _ | _ |

$O=\{a,d,e,b,c\}$

</div>
</div>
</div>

### Poprawność:
Algorytm ten korzysta z czterech lematów:
1. Mając pewne ustawienie zadań, zmiana ich kolejności w taki sposób aby kolejność wykonywania zadań na maszynie $A$ i na maszynie $B$, daje nam kolejność nie mniej optymalną niż oryginalna.
1.1 $\implies$ Kolejność wykonywania zadań na maszynie $A$ i $B$ będzie taka sama.

2. Mając pewne optymalne rozwiązanie dla zbioru $Z=\{a_i-p,b_i-p\}$ będzie ono również optymalne dla zbioru $Z=\{a_i,b_i\}$.
2.1$\implies$ Możemy uzyskać rozwiązanie optymalne poprzez odejmowanie w każdym kroku minimalnej wartości w zbiorze $Z$ od każdego z jego elementów.
3. Mając w $k$-tej pętli algorytmu dla pewnego zadania $i$, czasy $\{0,b_i\}$ możemy dodać to zadanie na pierwszą wolną pozycję w optymalnej kolejności wykonywania zadań, nie pogarszając optymalności naszego rozwiązania.
4. Mając w $k$-tej pętli algorytmu dla pewnego zadania $i$, czasy $\{a_i,0\}$ możemy dodać to zadanie na ostatnią wolną pozycję w optymalnej kolejności wykonywania zadań, nie pogarszając optymalności naszego rozwiązania.

3.1 $\land$ 4.1 $\implies$ Możemy rozwiązanie optymalne uzyskać poprzez budowanie go "od końców", wstawiajać odpowiednio zadania typu $3$ na pierwszej wolnej pozycji w zbiorze $O$, oraz zadania typu $4$ na ostatniej wolnej pozycji w zbiorze $O$.
### Dowody lematów:
#### Lemat 1:
Załóżmy, że mamy pewne rozwiązanie w którym na maszynie $A$ i na maszynie $B$, zadania nie są wykonywane w takiej samej kolejności, tj. istnieją pewne zadania $i$ oraz $j$ takie, że zadanie $j$ zostanie wykonane na maszynie $A$ wcześniej niż zadanie $j$, a na maszynie $B$ zadanie $j$ zostanie wykonane przed zadaniem $i$.

W takim wypadku możemy łatwo zauważyć, że zamieniając kolejność na maszynie $B$, tak aby zadanie $j$ wykonało się po zadaniu $i$, w żaden sposób nie wpłynie negatywnie na optymalność naszego rozwiązania. W najgorszym wypadku czas wykonywania zadań na maszynie $B$ nie ulegnie zmianie ($a_j$=0), w innych wypadkach zmniejszymy czas oczekiwania na maszynie $B$ w rezultacie uzyskując rozwiązanie bardziej optymalne.

gantt
    title Przykład:
    section Maszyna A
    a_i           :a1, 2023-04-30, 3d
    a_k           : 2d
    a_j           : 5d
    section Maszyna B
    b_k           :2023-05-5, 4d
    b_j           :2023-05-10,4d
    b_i           : 8d
    section A
    a_i           :a1, 2023-04-30, 3d
    a_k           : 2d
    a_j           : 5d
    section B po zamianie
    b_i           : 2023-05-03, 8d
    b_k           : 2023-05-11, 4d
    b_j           :4d

#### Lemat 2:
Załóżmy, że mamy pewne optymalne rozwiązanie dla zadań o czasach $\{a_i,b_i\}$. Głównym czynnikiem wpływającym na optymalność naszego rozwiązania jest czas oczekiwania na maszynie $B$.

Korzystając z **Lematu 1** wiemy, że kolejność wykonywania zadań na maszynach $A$ i $B$ będzie taka sama.

Aby pokazać, że zwiększenie czasu wykonywania wszystkich zadań o pewne $p$, w żaden sposób nie wpłynie na czasy oczekiwania na maszynie $B$, rozważmy przypadek w którym wykonujemy kolejno zadania $i,j,k$ oraz $a_j>b_i$. Oznaczmy kolejno:
1. $\textrm{DUR}_{a_j}$ jako czas wykonywania zadania $a_j$, który będzie również czasem rozpoczęcia zadania $b_j$
2. $\textrm{DUR}_{b_i}$ jako czas wykonywania zadania $b_i$
3. $m$ jako czas oczekiwania na maszynie $B$ między zadaniami $b_i$ oraz $b_j$, gdzie wiemy, że $m=\textrm{DUR}_{a_j}-\textrm{DUR}_{b_i}$

Zwiększmy zatem czas wykonywania wszystkich zadań o $p$. Możemy zauważyć, zatem, że:
$\textrm{DUR}_{a_j+p}=\textrm{DUR}_{a_j}+p$
$\textrm{DUR}_{b_i+p}=\textrm{DUR}_{b_i}+p$
$m'=\textrm{DUR}_{a_j+p}-\textrm{DUR}_{b_i+p}=\textrm{DUR}_{a_j}+p-\textrm{DUR}_{b_i}-p=\textrm{DUR}_{a_j}-\textrm{DUR}_{b_i}=m$

Zatem możemy zauważyć, że zwieksząjąc czasy wykonywania wszystkich zadań o $p$, czas oczekiwania na maszynie $B$ nie ulegnie zmianie, $\implies$ rozwiązanie optymalne dla zadań postaci $\{a_i,b_i\}$ będzie nadal optymalne dla zadań postaci $\{a_i+p,b_i+p\}$.

> Czas wykonywania takich zadań wzrośnie dokładnie o $(n+1)\cdot p$, ponieważ czas wykonywania każdego zadania zwiększamy o $p$ $(+n\cdot p)$, oraz na rozpoczęcie wykonywania zadań na maszynie $B$ będziemy musieli dodatkowo poczekać $p$ $(+p)$.

gantt
    title Przykład:
    section Maszyna A
    a_i           :a1, 2020-04-30, 3d
    a_j           : 2020-05-03, 5d
    a_k           : 8d
    section Maszyna B
    b_i           :2020-05-3,4d
    m : 1s
    b_j           :2020-05-8,9d
    b_k           :2d
    section Maszyna A + p
    a_i+p         :a1, 2020-04-30, 5d
    a_j+p         : 7d
    a_k+p         : 10d
    section Maszyna B + p
    b_i+p         :2020-05-5,6d
    m : 1s
    b_j+p         :2020-05-12,11d
    b_k+p         :4d

#### Lemat 3:
Załóżmy, że mamy zadanie $i$ postaci $\{0,b_i\}$. Niech $a_j$ będzie pierwszym zadaniem wykonywanym na maszynie $A$.
Rozpatrzmy 2 przypadki:
1. $b_i\leq a_j$ : W takim wypadku, ustawiając $i$-te zadanie jako pierwsze, w żaden sposób nie opóźnimy czasu rozpoczęcia wykonywania kolejnych zadań na maszynie $B$. (A zatem i czasu skończenia wykonywania zadań na maszynie $B$).
2. $b_i>a_j$ : W takim wypadku, ustawiając $i$-te zadanie jako pierwsze, mimo, że wydłużymy czas wykonywania wszystkich zadań na maszynie $B$, nadal jak najbardziej zwiększamy swoje szanse na "załatanie dziur" na maszynie $B$. Zatem istnieje szansa, że zmniejszymy sume czasów oczekiwania na maszynie $B$ i tym samym w możliwie najmniejszym stopniu wydłużymy czas działania maszyny $B$.

##### Dlaczego w k-tej pętli takie zadanie powinno trafić na pierwszą wolną pozycję w zbiorze przechowującą optymalną kolejność? (Budowanie $O$ "od końców")

Należy pamiętać o tym, że w $k$-tej pętli naszego algorytmu, zadanie postaci $\{a_i=0,b_i\}$ uzyskamy na skutek odejmowania kolejnych minimów ze zbioru $Z$.
Oznacza to, że $\{0,b_i\}=\{a_{\textrm{og }i}-p_1-p_2- \dots -p_k,b_{\textrm{ og }i}-p_1-p_2\dots -p_k\}$ gdzie oryginalnymi czasami wykonywania $i$-tego zadania było $\{a_{\textrm{og }i},b_{\textrm{og }i}\}\in Z$.
Zatem w $k$-tej pętli algorytmu będzie zachodzić $\forall \{a_j,b_j\} \in Z\setminus O: a_i<a_j$. Zatem $i$-te zadanie powinno zostać wykonane przed wszystkimi innymi zadaniami które pozostały w zbiorze $Z$, ponieważ zależy nam na jak najmniejszym opóźnieniu czasu rozpoczęcia wykonywania zadań na maszynie $B$.

Zatem ustawiając takie zadanie na pierwszej wolnej pozycji zbioru $O$, na mocy **lematu 2** uzyskamy również optymalne rozwiązanie dla oryginalnego zbioru $Z$.

gantt
    title Przykład:
    section Maszyna A
    a_j         :a1, 2020-04-30, 5d
    a_k         : 7d
    a_l         : 10d
    section Maszyna B
    b_j         :2020-05-5,6d
    b_k         :2020-05-12,10d
    b_l         :4d
    section A + ai=0
    a_i         :2020-04-30,1h
    a_j         :a1, 2020-04-30, 5d
    a_k         : 7d
    a_l         : 10d
    section B + bi<aj
    b_i         :2020-04-30,3d
    b_j         :2020-05-5,6d
    b_k         :2020-05-12,10d
    b_l         :4d
    section B + bi>aj
    b_i         :2020-04-30,7d
    b_j         :2020-05-7,6d
    b_k         :2020-05-13,10d
    b_l         :4d

#### Lemat 4:
Załóżmy, że mamy zadanie $i$ postaci $\{a_i,0\}$. Niech $b_l$ będzie ostatnim zadaniem wykonywanym na maszynie $B$.
Rozpatrzmy 2 przypadki:
1. $a_i\leq b_l$ : W takim wypadku, ustawiając $i$-te zadanie jako ostatnie, w żaden sposób nie opóźnimy czasu rozpoczęcia wykonywania kolejnych zadań na maszynie $B$. (A także ponieważ $b_i=0$ : czasu skończenia wykonywania zadań na maszynie $B$).
2. $a_i>b_l$ : W takim wypadku, ustawiając $i$-te zadanie jako ostatnie, mimo, że wydłużymy czas wykonywania wszystkich zadań na maszynie $B$, w żaden sposób nie opóźnimy czasu rozpoczęcia wykonywania wcześniejszych zadań na maszynie $B$, zatem w możliwie najmniejszym stopniu wydłużymy czas wykonywania zadań na maszynie $B$.
##### Dlaczego w k-tej pętli takie zadanie powinno trafić na ostatnią wolną pozycję w zbiorze przechowującą optymalną kolejność? (Budowanie $O$ "od końców")

Należy pamiętać o tym, że w $k$-tej pętli naszego algorytmu, zadanie postaci $\{a_i,b_i=0\}$ uzyskamy na skutek odejmowania kolejnych minimów ze zbioru $Z$.
Oznacza to, że $\{a_i,0\}=\{a_{\textrm{og }i}-p_1-p_2- \dots -p_k,b_{\textrm{ og }i}-p_1-p_2\dots -p_k\}$ gdzie oryginalnymi czasami wykonywania $i$-tego zadania było $\{a_{\textrm{og }i},b_{\textrm{og }i}\}\in Z$.
Zatem w $k$-tej pętli algorytmu będzie zachodzić $\forall \{a_j,b_j\} \in Z\setminus O: b_i<b_j$. Zatem $i$-te zadanie powinno zostać wykonane po wszystkich innych zadaniach które pozostały w zbiorze $Z$, ponieważ zależy nam na jak najmniejszym wydłużeniu czasu wykonywania zadań na maszynie $B$.

Zatem ustawiając takie zadanie na ostatniej wolnej pozycji zbioru $O$, na mocy **lematu 2** uzyskamy również optymalne rozwiązanie dla oryginalnego zbioru $Z$.

gantt
    title Przykład:
    section Maszyna A
    a_j         :a1, 2020-04-30, 5d
    a_k         : 7d
    a_l         : 10d
    section Maszyna B
    b_j         :2020-05-5,6d
    b_k         :2020-05-12,10d
    b_l         :4d
    section A + a[i]<b[l]
    a_j         :a1, 2020-04-30, 5d
    a_k         : 7d
    a_l         : 10d
    a_i         : 2d
    section B + b[i]
    b_j         :2020-05-5,6d
    b_k         :2020-05-12,10d
    b_l         :4d
    b_i=0       :1h
    section A + a[i]>b[l]
    a_j         :a1, 2020-04-30, 5d
    a_k         : 7d
    a_l         : 10d
    a_i         : 5d
    section B + b[i].
    b_j         :2020-05-5,6d
    b_k         :2020-05-12,10d
    b_l         :4d
    b_i=0       :2020-05-27,2h