Problem job shop - przykład
System gniazdowy składa się z czterech maszyn:
Należy wykonać cztery zlecenia o następujących czasach przybycia, marszrutach (sekwencjach zadań) i czasach wykonania zadań. Uszeregowanie poszukiwane jest za pomocą wszystkich reguł.
Zlecenia |
Czas przybycia |
Marszruta (czas wykonania) |
1 |
0 |
M1(10) - M2(5) - M3(35) |
2 |
0 |
M2(25) - M1(5) - M3(30) - M4(15) |
3 |
0 |
M2(5) - M4(10) |
4 |
30 |
M2(15) - M3(10) - M4(20) - M1(10) |
Ekran wprowadzania danych - program Job shop znajdujący się w portalu
Rozwiązanie problemu otrzymuje się analizując kolejne chwile, które mogą być chwilami startu jakichś zadań. Zadanie może być rozpoczęte w chwili:
- otwarcia zlecenia (jeśli zadanie jest pierwsze w zleceniu i wolna jest
maszyna, na której zadanie to ma być wykonane), - zakończenia poprzedniego zadania w zleceniu (jeśli wolna jest maszyna,
na której ma być wykonane zadanie), - zwolnienia maszyny, na której zadanie ma być wykonane.
W ostatnim z wymienionych przypadków może się zdarzyć, że na zwolnienie maszyny oczekuje więcej niż jedno zadanie. Wówczas powstaje konflikt, a do jego rozstrzygnięcia stosuje się przyjętą regułę priorytetu.
Harmonogram pracy maszyn uzyskany za pomocą reguły LWR
Harmonogram pracy maszyn uzyskany za pomocą reguły FIFO
Harmonogram pracy maszyn uzyskany za pomocą reguły LIFO
Harmonogram pracy maszyn uzyskany za pomocą reguły SPT
Harmonogram pracy maszyn uzyskany za pomocą reguły LPT
Harmonogram pracy maszyn uzyskany za pomocą reguły EDD
Rozwiązanie problemu przedstawiono w formie wykresów Gantta, pokazujących przebiegi czasowe obciążenia poszczególnych maszyn zadaniami kolejnych zleceń. Dla przejrzystości rysunków, nad prostokątami reprezentującymi zadania wypisano tylko numery zleceń. Numery zadań w zleceniach mogą być jednoznacznie odczytane z kolejności ich wykonania.
W rozpatrywanym przykładzie konflikty występują na maszynach 2 i 3. Na obu maszynach w różnych chwilach, w zależności od wybranej reguły priorytetu. Tylko dla tych chwil konieczne jest stosowanie reguł (FIFO, LIFO, SPT, LPT, EDD, LWR) dla zleceń, których zadania oczekują na wykonanie. Na wykresach chwile te zaznaczone są w czarnych prostokątach.
Ponadto wyznaczone zostały: C1 - C4 - chwile zakończenia poszczególnych zleceń, F1 - F4 - czasy przepływu, czyli czasy przebywania poszczególnych zleceń w systemie, Cmax - długość uszeregowania, maksymalny termin zakończenia, Fśr - średni czas przepływu.
Wszystkie dane zostały zestawione w tabeli poniżej. W ten sposób może wyglądać analiza problemu job shop w zależności od wybranej reguły priorytetu.
Reguła
C1
C2
C3
C4
Cmax
F1
F2
F3
F4
Fśr
FIFO
95
75
40
135
135
95
75
40
105
78,75
LIFO
65
120
60
105
120
65
120
60
75
80
SPT
110
80
15
110
110
110
80
15
80
71,25
LPT
65
110
60
140
140
65
110
60
110
86,25
EDD
70
115
15
145
145
70
115
15
115
78,75
LWR
70
125
15
110
125
70
125
15
80
72,5
Analiza problemu job shop w zależności od wybranej reguły priorytetu
W zależności od tego jakie kryterium jakości jest dla nas istotne, taka reguła priorytetu wybierana do szeregowania zadań będzie najlepsza.