W trzecim semestrze mamy przedmiot o znamiennej nazwie Optymalizacja Kombinatoryczna. Jak nietrudno się domyślić, jest to dalsza część tematu powiązanego z problemami i algorytmami je rozwiązującymi, jednak tym razem całość krąży wokół szukania rozwiązań optymalnych dla problemów NP-trudnych i silnie NP-trudnych (należących do tzw. NP-zupy). Strasznie zagmatwana dziedzina i do tego bardzo teoretyczna – potrafi być miażdżąca dla umysłu, ale jak się w to wgłębić, to jest dosyć ciekawa (pod warunkiem, że nie trzeba pisać z tego kolokwium). Tym bardziej, że u nas jest bardzo przystępnie tłumaczona (pozdrawiam wykładowcę).
Zadaniem części studentów na laboratoriach jest napisanie rozwiązań do tzw. problemu Job Shop. Polega on w skrócie (i intuicyjnie) na tym, iż mamy M maszyn oraz N zadań do wykonania, dla których określone są dwójki (m0 t0) (m1 t1) … (mn tn), gdzie mi to indeks maszyny, którą potrzebuje dane zadanie, a ti to ilość kwantów czasu, które musi spędzić zadanie na maszynie mi. Etap “produkcji” danego zadania (czyli taka dwójka) musi być wykonany kolejno – najpierw musi przejść pierwszą wymienioną maszynę, potem drugą, trzecią itd. Nie można zmieniać kolejności. Jest też jedna ważna sprawa, przez którą poniższy algorytm działa niepoprawnie (choć będzie poprawny dla innych form tego problemu) – jeżeli dane zadanie dostanie maszynę do dyspozycji, to spędza na niej tyle czasu, ile potrzebuje – nie oddaje jej przed końcem danego procesu (trzyma się kurczowo nóżkami).
Jest to zatem jedna z odmian problemu szeregowania. Jakby tego było mało, jest to jeden z rodzajów bardzo znanego problemu komiwojażera, w którym miasta do odwiedzenia to zadania (a ich liczba N), a maszyna jest jedna i jest to nasz podróżnik.
Jak już wcześniej wspomniałem, jeżeli zadanie dostanie maszynę, to nie może się od niej oderwać przed ukończeniem danego etapu produkcji. Jest to zatem przykład niewywłaszczalności. Poniższy pomysł na algorytm zakłada jednak, że jeżeli nastąpią pewne okoliczności, jedno zadanie może przerwać swój etap i dopuścić maszynę do drugiego zadania. Jest to zatem system wywłaszczalny i w dodatku taki, w którym najwyższy priorytet mają zadania o najmniejszym indeksie.
Cóż, troszkę formalizmu, a teraz konkrety. Muszę z góry przyznać, iż algorytm jest dosyć kiepski – nie działa zbyt optymalnie. Ma jednak taką właściwość, iż jest bardzo prosty i nawet ja umiałem go zaimplementować. A poza tym, przedstawiam ten pomysł jako inspirację dla kogoś, kto być może wymyśli (albo chociaż zna) działający i optymalny algorytm dla Job Shopa. W garści mam też pomysł oparty na algorytmie SJF, ale wolałbym implementować “mądrzejsze” rozwiązania (algorytmy genetyczne, inne metaheurystyki, B&B, itd.)
Może mały przykład. Mamy trzy maszyny do dyspozycji (o indeksach od 0 do 2) oraz trzy zadania (0-2), które zostały zdefiniowane następująco:
T0: (0 2) (1 3) (2 1)
T1: (1 1) (2 2) (0 1)
T2: (1 3) (0 2) (2 3)
Opiszę może słownie jedno z zadań, żeby wszystko było całkowicie jasne – zadanie nr 2 najpierw musi spędzić trzy kwanty czasu na maszynie nr 1, potem przez dwa kwanty czasu jest wykonywane na maszynie nr 0, a na końcu odwiedza maszynę nr 2 i zostaje tam na trzy kwanty.
Uszeregowanie, jakie proponuje opisywany algorytm, wygląda tak:

Oczywiście, widać, iż nie jest to zbyt optymalne rozwiązanie – zwłaszcza dla zadania drugiego, które smutne i zmechacone powolutku człapie od jednej maszyny do drugiej, w międzyczasie ustępując miejsca zadaniu zerowemu, które ma niższy indeks. W efekcie długość uszeregowania wszystkich zadań wynosi 12 kwantów czasu. Czasami naprawdę się zastanawiam, po co opisuję niedziałające algorytmy. Może dlatego, że są tak proste, że łatwo się o nich pisze notki.
Pierwszą rzeczą, jaką należy wykonać, jest wykorzystanie kolejek FIFO do trzymania informacji o zadaniach, ale w specyficzny sposób. Mając zadanie, które opisane jest jako:
(1 2) (0 1) (2 3)
musimy utworzyć kolejkę o wartościach:
1 1 0 2 2 2
Widać, że na maszynie nr 1 musimy spędzić dwa kwanty czasu (są dwie jedynki), na zerowej jeden, a na drugiej – 3 kwanty. Tak przygotowane kolejki następnie wykorzystujemy w algorytmie i stopniowo zdejmujemy z nich wartości. Ale może najpierw schemat, a nie, że ja tutaj tak szybko myk-myk.
1. Wszystko dzieje się w pętli, która odlicza kolejne kwanty czasu. Jej zakończenie jest uwarunkowane przez stan zmiennej logicznej typu bool.
2. Tworzymy sobie tablicę tf o typie int i rozmiarze N i zapełniamy ją zerami.
3. Robimy sobie herbatę.
4. Tworzymy pętlę dla każdej maszyny.
5. W każdej iteracji tej pętli tworzymy następną pętlę (z licznikiem t), w której sprawdzamy wszystkie zadania, począwszy od zerowego. Jeżeli jakieś zadanie t nie zostało w tym kwancie “wykorzystane” (tf[t] == 0), jego kolejka nie jest pusta, a pierwszy element to indeks aktualnie przetwarzanej maszyny – tf[t] = 1, zapamiętujemy t, zdejmujemy wartość z kolejki zadania t oraz wychodzimy z pętli.
6. Zapisujemy do wektora aktualnie przetwarzanej maszyny wartość t. Jeżeli jednak żadne zadanie nie potrzebuje maszyny w danym kwancie czasu, wpisujemy –1 (jakieś oznaczenie musimy przyjąć).
7. Sprawdzamy (już poza pętlą z punktu 4.), czy kolejka któregokolwiek zadania nie jest pusta. Jeżeli któreś zadanie ma jeszcze jakieś wartości w kolejce – przechodzimy do następnej iteracji pętli zliczającej kwanty czasu. W przeciwnym razie – kończymy algorytm.
W ten sposób, naszym rozwiązaniem będą wektory kolejnych indeksów zadań, które są wykonywane na danej maszynie w określonym kwancie czasu (lub –1, jeżeli maszyna nie jest wykorzystywana). Polecam też wykonywać punkt 3. jedynie raz – potem Wam się namnożą herbaty.
Algorytm jest bardzo prosty, choć nie daje zadowalającego wyniku dla szeregowania z wywłaszczaniem. Nie działa też jakoś nienaturalnie wolno, choć złożoność mówi co innego – O(N*M*i), gdzie i to ilość kwantów czasu, jaka jest potrzebna na nasze uszeregowanie. A że i przy dużych instancjach dąży do nieskończoności…
Na koniec pełny kod naszego rozwiązania (QUANTITY to N, a MAC_QUANTITY to M).
1: #include <cstdio>
2: #include <cstdlib>
3: #include <vector>
4: #include <queue>
5: #include <ctime>
6: #include <cctype>
7:
8: #define QUANTITY 3
9: #define MAC_QUANTITY 3
10:
11: int main (int argc, char* argv[])
12: { 13: // wrzucenie zadań do kolejek
14: // jeżeli jakieś zadanie ma być wykonywane:
15: // na 1-szej maszynie 2 kwanty czasu, a potem
16: // na 2-giej maszynie 3 kwanty czasu, to
17: // obraz kolejki:
18: // 1 1 2 2 2
19: std::queue<unsigned> task[QUANTITY];
20: std::vector<int> machine[MAC_QUANTITY];
21:
22: // zadanie 0
23: task[0].push(0);
24: task[0].push(0);
25: task[0].push(1);
26: task[0].push(1);
27: task[0].push(1);
28: task[0].push(2);
29:
30: // zadanie 1
31: task[1].push(1);
32: task[1].push(2);
33: task[1].push(2);
34: task[1].push(0);
35:
36: // zadanie 2
37: task[2].push(1);
38: task[2].push(1);
39: task[2].push(1);
40: task[2].push(0);
41: task[2].push(0);
42: task[2].push(2);
43: task[2].push(2);
44: task[2].push(2);
45:
46: // odliczamy kolejne kwanty czasu
47: bool end = false;
48: int i;
49:
50: for (i = 0; !end; ++i)
51: { 52: int tf[QUANTITY] = { 0 }; // jeżeli danego zadania jeszcze nie było w określonym kwancie czasu 53:
54: // dla każdej maszyny bierzemy pierwsze zadanie, które ją wymaga
55: for (int j = 0; j < MAC_QUANTITY; ++j)
56: { 57: int t; // zachowujemy numer zadania
58:
59: for (t = 0; t < QUANTITY; ++t)
60: { 61: // jeśli coś jeszcze zostało do zrobienia w danym zadaniu (kolejka nie jest pusta)
62: // oraz zadanie nie zostało już gdzieś "włożone" w danym kwancie czasu
63: if (!task[t].empty() && tf[t] == 0)
64: { 65: // jeśli pierwszy element to indeks danej maszyny
66: if (task[t].front() == j)
67: { 68: tf[t] = 1;
69: task[t].pop();
70: break; // kończymy pętlę
71: }
72: }
73: }
74:
75: // jeżeli t zmieściło się w pętli, to zapisujemy indeks
76: // zadania do wektora danej maszyny - w przeciwnym razie
77: // zapisujemy -1
78: if (t < QUANTITY)
79: { 80: machine[j].push_back(t);
81: }
82: else
83: { 84: machine[j].push_back(-1);
85: }
86: } // for (int j = 0; j < MAC_QUANTITY; ++j)
87:
88: bool e = true;
89:
90: // jeżeli kolejka któregokolwiek zadania nie jest pusta,
91: // to jeszcze nie kończymy algorytmu
92: for (int t = 0; t < QUANTITY; ++t)
93: { 94: if (!task[t].empty())
95: { 96: e = false;
97: break;
98: }
99: }
100:
101: end = e;
102: } // for (i = 0; !end; ++i)
103:
104: for (unsigned i = 0; i < MAC_QUANTITY; ++i)
105: { 106: printf("Maszyna %d: ", i); 107:
108: std::vector<int>::iterator it;
109:
110: for (it = machine[i].begin(); it != machine[i].end(); ++it)
111: { 112: printf("%d ", *it); 113: }
114: printf("\n"); 115: }
116:
117: printf("\n"); 118:
119: printf("Łączny czas uszeregowania procesów: %d\n", i); 120:
121: getchar();
122: return 0;
123: }
Pozdrawiam i dziękuję - SceNtriC