Harmonogramowania procesów produkcyjnych i przedsięwzięć inwestycyjnych – cześć II

Teoria szeregowania zadań wykorzystywana jest w harmonogramowaniu produkcji przemysłowej, w systemach operacyjnych maszyn cyfrowych, w systemach wspomagania podejmowania decyzji, podczas planowania przedsięwzięć inwestycyjnych, podczas organizowania czasu pracy i podziału obowiązków.

Rysunek 1. Wykres Gantta -opis podstawowych parametrów. Źródło: opracowanie własne

Szeregowanie to wyznaczenie takiego rozdziału w czasie i przestrzeni dostępnych zasobów produkcyjnych, by spełniając założenia projektowe, uzyskać najlepsze możliwe rozwiązanie zaspokajające zapotrzebowanie na produkowane wyroby.

Załóżmy, że dysponujemy zbiorem n zadań Z = {Z₁, ..., Z_n}, wykonywanych przy użyciu m-elementowego zbioru maszyn M = {M₁, ...,M_m}, które są jedynymi zasobami w naszym modelu.

Należy tak pokierować przepływem zadań poprzez zbiór maszyn, aby uzyskać rozwiązanie najkorzystniejsze. Wyróżnia się przepływowe zagadnienie kolejnościowe (np. linia montażowa) oraz ogólne zagadnienie kolejnościowe, w tym szeregowanie zadań na maszynach równoległych.

Zadaniami mogą być przykładowo procesy produkcyjne, czynności inwestycyjne w projektach, obliczenia komputerowe. Maszyny mogą być różnego typu, mogą to być procesory komputerów, ludzie, energia, nakłady finansowe. Możliwości jest wiele. Opiszemy teraz podstawowe parametry charakteryzujące model szeregowania zadań:

• Czas p_ij (ang. processing time) jest to czas wykonywania czynności Z_j,, na maszynie M_i.
• Moment przybycia r_j (ang. release time) zadania Z_j zwany też wymiennie momentem zwolnienia lub gotowości zadania Z_j. Jest to moment, w którym zadanie Z_j staje się dostępne, możliwe do wykonania.
• Termin zakończenie d_j (ang. due date) zadania Z_j jest to termin do którego należy zakończyć wykonywanie zadania Z_j . Dodatkowo terminy, które muszą być bezwzględnie respektowane nazywa się liniami krytycznymi.
• Waga w_j (ang. weight) zadania Z_j określa ważność (koszt) zadania Z_j. Zakłada się, że zadania o jednakowym priorytecie ważności mają także równe wagi.

Przejdziemy teraz do omówienia parametrów, za pomocą których określa się położenie danego zadania w czasie. Każde zadanie produkcyjne Z_j ma swój czas rozpoczęcia S_j i czas zakończenia C_j. Dodatkowo do najczęściej spotykanych parametrów, umożliwiających usytuowanie zadania w czasie należą:

• Opóźnienie L_j (ang. lateness) zadania Z_j wyznacza się pod warunkiem, że dla danego zadania określony jest termin jego żądanego zakończenia d_j . Opóźnienie jest miarą nieterminowości, odpowiada na pytanie, o ile czas zakończenia zadania Z_j przekracza preferowany termin jego zakończenia i wyraża się wzorem L_j = C_j − d_j. Ujemne opóźnienie odpowiada przedterminowemu ukończeniu zadania i lepszej obsłudze systemu.
• Spóźnienie T_j (ang. tardiness) zadania Z_j jest parametrem ściśle powiązanym z powyższym. Przyjmuje wartość 0 gdy zadanie Z_j ukończone zostało przed żądanym terminem zakończenia, w pozostałych przypadkach T_j = L_j , czyli ostatecznie T_j = max{0, L_j}. Parametr ten wprowadzono w odpowiedzi na systemy produkcyjne, w których przedterminowe ukończenie zadania nie przynosi żadnych wymiernych korzyści.
• Jednostkowa kara U_j (ang. unit penalty) zadania Z_j jest parametrem logicznym, sygnalizującym o przekroczeniu preferowanego terminu zakończenia zadania Z_j . W przypadku niedotrzymania planowanego terminu zostaje zwrócona wartość 1, w przeciwnym wypadku otrzymamy wartość 0

Bazując na powyższych danych możemy spróbować ocenić dane uszeregowania zadań. Jak łatwo się domyślić, nie istnieje uniwersalne kryterium optymalności. Za każdym razem minimalizujemy koszty związane z wyborem kolejności wykonywanych operacji, a te związane są ze specyfiką danego przedsiębiorstwa. Czasami największymi kosztami obarczona będzie ilość opóźnionych zadań, innym razem firma narażona będzie na największe straty, gdy przekroczy łączny czas przewidziany na wykonanie całego przedsięwzięcia. Niech f_j(t) będzie kosztem zakończenia zadania Z_j w chwili t, f_j € {C_j, L_j, T_j, U_j}, wówczas do najczęściej rozważanych funkcji kosztów należą:

Koszt maksymalny, który można wyrazić jako f_max = max{f_j : j = 1, ..., n}. Do tej grupy należą na przykład:

• C_max, maksymalny czas zakończenia, zwany też długością uszeregowania,
• L_max, maksymalne opóźnienie,
• T_max, maksymalne spóźnienie.

Koszt całkowity, do którego należą koszt sumaryczny i koszt sumaryczny ważony, nazywany też ważoną lub obciążoną sumą kosztów. Ogólnie koszt całkowity wyraża się wzorem f_sum = ∑w_jf_j. Gdy wszystkie wagi są takie same, przyjmuje się f_sum = ∑f_j i jest to wówczas koszt sumaryczny. Do najczęściej rozpatrywanych kosztów, występujących w tej klasie należą:

• ∑C_j , całkowita, łączna długość uszeregowania,
• ∑L_j , całkowite opóźnienie (analogicznie ∑T_j to całkowite spóźnienie),
• ∑U_j , ilość spóźnionych zadań,
• ∑w_jT_j , łączne ważone spóźnienie.

Z ilości pojęć, zdefiniowanych powyżej, można by wnioskować, iż dokładny opis przykładowego modelu szeregowania zadań ze wszystkimi jego parametrami zajmuje niejednokrotnie kilka linijek tekstu. Byłoby tak z pewnością, gdyby nie istniała elastyczna symbolika, którą wprowadzono, aby uprościć wielolinijkowe zapisy. Jest to tak zwana notację trójpolowa.

maszyny|zadania|kryterium

Za pomocą tego uniwersalnego zapisu można precyzyjnie i zwięźle zdefiniować każde zagadnienie z obszernej teorii szeregowania zadań. My ograniczymy naszą uwagę do tych wartości pól, które odpowiadają problemom rozważanym w szeregowaniu na maszynach równoległych.

Pole maszyny określa typ systemu, czyli środowisko maszynowe. Jeżeli nie jest zaznaczone iloma maszynami dysponujemy, zakładamy, że liczba maszyn stanowi parametr zagadnienia i wówczas stosujemy oznaczenia:

• P – dla maszyn równoległych identycznych (maszyny równoległe)
• Q – dla maszyn równoległych jednorodnych (maszyny równoległe)
• R– dla maszyn równoległych dowolnych (maszyny równoległe)
• F – zagadnienie przepływowe (maszyny dedykowane)
• O – System otwarty (maszyny dedykowane)
• J – System ogólny/gniazdowy (maszyny dedykowane)

Natomiast, jeżeli liczba maszyn z jakiegoś względu jest ustalona i na przykład dysponujemy tylko dwoma identycznymi maszynami pracującymi równolegle, zapisujemy to jako P2. Ogólnie, gdy mamy dane m maszyn danego rodzaju, odpowiada to zapisowi Pm, Qm lub Rm. Jeżeli dysponujemy tylko jedną maszyną wpisujemy w pierwszym polu notacji trójpolowej cyfrę 1, natomiast gdy problem jest bezprocesorowy zostawiamy pierwsze pole puste.

Pole zadania opisuje charakterystyki zadań, dodatkowe ograniczenia. Pole to może pozostać puste, pod warunkiem, że zadania są niepodzielne, niezależne i wszystkie są dostępne z chwilą rozpoczęcia procesu (czyli r_j = 0 dla i = 1, ..., n). W przeciwnym przypadku w polu tym umieszcza się listę niektórych spośród poniższych parametrów:

• pmtn – jeżeli dopuszczalna jest podzielność (ang. preemption) zadań,
• prec – jeżeli występują zależności kolejnościowe (ang. precedence contrains) pomiędzy zadania narzucone przez porządek technologiczny. Rozpatruje się ograniczenia kolejnościowe tworzące drzewo (ang. tree), las (ang. forest), drzewo skierowane (ang. in-tree, out-tree) lub łańcuch (ang. chains),
• r_j – jeżeli momenty przybycia dla zadań są określone i różnią się między sobą,
• p_j = 1 – jeżeli zadania mają jednostkowe czasy wykonywania, zapis równoważny to UET (ang. unit execution tasks). Rozpatruje się również p_j € {0, 1} (ZUET)
• setup – jeżeli występują przezbrojenia
• batch – jeżeli występuje porcjowanie
• no wait – jeżeli proces musi być ciągły, bez czekania

Pole kryterium określa postać funkcji kosztów, względem której dokonuje się optymalizacji danego zagadnienia. Zatem będzie przyjmować jedną z postaci: C_max, L_max, ∑T_j , ∑w_jT_j , lub inną ze wspominanych wcześniej. Warto prześledzić jak w praktyce notacja trójpolowa upraszcza zapis. Poniżej przedstawiamy dwa przykłady.

Przykład 1. Załóżmy, że dysponujemy dwoma pracownikami. Każdy z nich może wykonywać te same zadania, jednak każdy z nich w innym tempie, stałym dla danego zadania. Mogą także przerywać swoje obowiązki w dowolnym momencie czasu. Niestety niektóre zadania są im dostarczane dopiero po godzinie 12:00. Interesuje nas taki podział obowiązków między tych dwóch pracowników, który zminimalizowałby ilość spóźnionych zadań przeznaczonych do wykonania w ciągu jednego dnia roboczego. Okazuję się, że jest to problem Q2|r_j, pmtn|_U_j .

Przykład 2. Pewna hala produkcyjna została wyposażona w pięć identycznych maszyn. Kolejność niektórych zadań jest uzależniona od specyfiki procesu technologicznego. Dodatkowo wykonanie każdego zadania obarczone jest pewnym kosztem (związanym z eksploatacją niektórych części maszyn produkcyjnych). Firma, dla której wykonywane jest to zlecenie, zastrzegła sobie w umowie, iż całe przedsięwzięcie powinno być ukończone przed terminem d. Każdy dzień zwłoki obarczony został pewną karą (bez premii dla przedterminowego ukończenia całości przedsięwzięcia). Mając szczegółowe dane o czasie trwania poszczególnych czynności,należy wyznaczyć całkowity ważony koszt procesu, związany z niedotrzymaniem danego terminu oddania przedsięwzięcia ”pod klucz”. Dla porównania, interesuje nas także data możliwie najszybszego terminu ukończenia całości przedsięwzięcia (bez względu na koszty). W tym przykładzie, należałoby rozważać kolejno problemy P5| prec |∑w_jT_j oraz P5| prec |C_max.

Jak widać, wprowadzona symbolika znacznie ułatwia zrozumienie danego problemu szeregowania i w efektywny sposób umożliwia przejście do modelu matematycznego. Także w metodzie służącej przedstawianiu wyników uzyskanych metodami szeregowania zadań nie brakuje przejrzystości. Jeżeli pod pojęciem harmonogramu rozumieć będziemy przyporządkowanie maszyn do zadań w czasie, to wówczas wykres Gantta będzie graficzną metodą przedstawiania harmonogramów na diagramie słupkowym, wyraziście obrazującą etapy projektu na przestrzeni czasu. Czas zaznaczany jest na osi poziomej, a maszyny na pionowej. Praca związana z wykonaniem każdego zadania jest przedstawiana jako prostokąt odpowiedniej długości.

Analizując Rysunek 1 łatwo zauważyć, iż zadanie Z_j udało się ukończyć przed żądanym terminem jego zakończenia (d_j). W związku z tym, pozostałe parametry opisujące zadanie Z_j mają wartości L_j = d_j − C_j < 0, T_j = max{0, L_j} = 0 oraz U_j = 0. Natomiast, aby podać wartości przykładowych funkcji kosztu dla całego harmonogramu, musielibyśmy dodatkowo znać wartości parametru d_j nie tylko dla zadania Zj , ale dla wszystkich zadań. Ponieważ oprócz funkcji C_max, ∑w_jC_j , pozostałe uzależnione są od tego parametru. Na potrzeby przykładu uściślijmy, iż d_j jest linią krytyczną dla całego procesu (d_j = d = const). Wówczas przykładowo:

L_max = max{L_j : j = 1, ..., n} = y,

T_max = L_max = y,

∑T_j = x + y,

∑U_j = 2.

Podsumowując, pełny model problemu szeregowania zadań powinien dokładnie opisywać rzeczywistość (na przykład produkcyjną). Najkorzystniej jakby był sformułowany z wykorzystaniem notacji trójpolowej. Następnie, przy pomocy odpowiedniego algorytmu poszukuje się rozwiązania możliwie najbliższego rozwiązaniu optymalnemu. W wyniku tych operacji powinien powstać harmonogram działań w postaci wykresu Gantta.

Bibliografia

1. „Kombinatoryczna teoria szeregowania” WMS AGH 2004, Anna Dąbrowska, Aleksandra Lipa