SZEREGOWANIE ZADAŃ W SYSTEMIE GNIAZDOWYM

W procesie produkcyjnym typu gniazdowego wyprodukowanie każdego wyrobu j (j = 1,.n) wymaga wykonania ciągu różnych operacji (zadań) na m różnych maszynach. Polecenie wykonania wyrobu j nazywa się zleceniem. Dla każdego wyrobu rodzaj i liczba wymaganych operacji oraz odpowiadające im maszyny mogą być inne. Proces wytwarzania wyrobu j składa się z operacji o numerach k należących do K_j. Proces produkcyjny typu gniazdowego stanowi więc najogólniejszy typ procesu produkcyjnego, w którym maszyny tworzą sieć maszyn, a poszczególne wyroby przechodzą w różnej kolejności przez różne podzbiory maszyn. System gniazdowy występuje w maszynach dedykowanych. Przykładem takiego systemu jest system Job shop.

Problem Job shop

Problem Job shop polega na szeregowaniu zadań dla zleceń jednostkowych o ustalonych liniowych marszrutach (opis poniżej). Każde zlecenie składa się z zadań wykonywanych na osobnych maszynach, ustawionych w określonej kolejności, z konkretnymi czasami ich przetwarzania na danej maszynie.

Założenia jakie stosujemy to:

k - indeks operacji oraz indeks zadania w zleceniu j

i - indeks stanowiska roboczego, (i = 1,..., m)
j_j - numer produktu wytwarzanego w zleceniu j
(j,k) - para indeksów identyfikująca k-te zadanie j-tego zlecenia

• Zlecenia są jednostkowe i dotyczą różnych produktów. Dlatego mogą być numerowane indeksem produktów j.
• Zadania są jednostkowe, niepodzielne i będą identyfikowane, jak operacje, parami indeksów (j,k).
• Porządek operacji jest liniowy, a kolejność operacji jest zgodna z ich numeracją.

• Marszruty są ustalone (zadaniom są dedykowane określone maszyny), więc przydział stanowisk do operacji i(j,k) jest dany.

Dane charakteryzujące zlecenie:

	czas wykonania zadania k zlecenia j na maszynie i
	pożądana chwila zakończenia (termin zamknięcia) zlecenia j
	czas gotowości (chwila otwarcia) zlecenia j
	chwila zakończenia zlecenia j
	czas przepływu, czas przebywania zlecenia w systemie
	różnica chwili zakończenia zlecenia j i czasu gotowości
	opóźnienie zlecenia j - różnica między rzeczywistym terminem zakończenia i wymaganym terminem zakończenia zlecenia j. Należy zauważyć, że jeżeli zlecenie jest zakończone przed wymaganym terminem zakończenia to Lj ma ujemną wartość. Przyjmuje się wówczas, że jej opóźnienie ma wartość równą zeru. Wartość większa od zera występuje wtedy, gdy zlecenie jest opóźnione
	spóźnienie zlecenia j
	jeżeli opóźnienie Lj przyjmuje wartość dodatnią to spóźnienie Tj również ma wartość dodatnią, natomiast jeżeli opóźnienie Lj przyjmuje wartość ujemną to spóźnienie Tj jest równe zero

 

Kryteria oceny uszeregowań:

	długość uszeregowania
	średni czas przepływu
	maksymalne opóźnienie, czyli
	średnie spóźnienie, czyli

W problemie Job shop w przypadku gdy więcej niż jedno zadanie oczekuje przed maszyną na wykonanie, wtedy mamy do czynienia z konfliktami na maszynach. Jest to związane z tym, że każda maszyna może wykonywać tylko jedną operację w danej chwili i żadna operacja nie może być jednocześnie wykonywana przez różne maszyny (zasada wzajemnego wykluczania przydziału maszyn do operacji). Do rozwiązania takiego problemu stosujemy jedną z wielu znanych w literaturze reguł priorytetu (algorytmy heurystyczne).

Najczęściej stosowane są następujące reguły priorytetu:

• FIFO - kolejność wykonania zadań według kolejności ich zgłoszeń, czyli według rosnących czasów gotowości (ang. first in first out), inaczej: to zadanie, które weszło na maszynę jako pierwsze, w przypadku konfliktu wykonywane jest jako pierwsze.

• SPT - kolejność wykonania zadań według rosnących czasów przetwarzania zadań (ang. shortest processing time), czyli wybieramy to zadanie, które ma najkrótszy czas przetwarzania.

• EDD - kolejność wykonania zadań według terminów zamknięcia zleceń, czyli ich zadanych czasów zakończenia (ang. earliest due date), inaczej: liczymy sumę czasów począwszy od przybycia zlecenia do systemu aż do zakończenia danego zlecenia i wybieramy zlecenie z mniejszą sumą.

• LIFO - kolejność wykonania zadań odwrotnie do kolejności ich zgłoszeń, czyli według malejących czasów gotowości (ang. last in first out), inaczej: to zadanie, które weszło na maszynę jako ostatnie, w przypadku konfliktu wykonywane jest jako pierwsze.

• LPT - kolejność wykonania zadań według malejących czasów przetwarzania zadań (ang. latest processing time), czyli wybieramy to zadanie, które ma najdłuższy czas przetwarzania.

• LWR - kolejność wykonania zadań według rosnących sum czasów przetwarzania zadań pozostałych do wykonania w zleceniach (ang. least work remaining), czyli w danym zleceniu liczymy sumę czasów pozostałych zadań potrzebnych do wykonania całego zlecenia i wybieramy to z sumą mniejszą.

Rozwiązanie problemu Job shop przedstawiamy za pomocą wykresów Gantta.

Przykład