Optymalizacja kosztów produkcji przez rozmieszczenie stanowisk roboczych, w systemie produkcyjnym, minimalizujące koszt transportu

mgr inż. Tomasz Homel

 

Streszczenie - Artykuł prezentuje problem poszukiwania najlepszego rozmieszczenia maszyn w hali produkcyjnej, minimalizującego całkowite koszty transportu elementów (składników, półfabrykatów, wyrobów gotowych) w hali produkcyjnej. Rozwiązanie problemu otrzymujemy wykorzystując algorytm poszukiwań z zabronieniami (Tabu Search) wspomagany metodą skoku powrotnego (MSP). W artykule przedstawiono wyniki badań komputerowych, które ukazują jaki wpływ na otrzymane wskaźniki zysków (wskaźniki oszczędności kosztów produkcji) ma zastosowanie algorytmu Tabu Search do powyższego problemu.

SPIS TREŚCI

1. Definicja problemu
2. Model matematyczny
3. Algorytmy konstrukcyjne
4. Algorytm Tabu Search
5. Wyniki badań komputerowych
6. Wnioski
Literatura

1. Definicja problemu

   Po rozwiązaniu problemu podziału zbioru maszyn przedsiębiorstwa na komórki względnie hale produkcyjne powstaje nowy problem, dla każdej hali oddzielnie, polegający na takim rozmieszczeniu maszyn, które minimalizuje całkowite koszty transportu półproduktów (np. detali) pomiędzy maszynami. Wyliczany koszt transportu zależy w tym wypadku przede wszystkim od: odległości między maszynami oraz jednostkowego kosztu transportu. Poniżej przedstawiono, jedną z możliwych, koncepcję rozwiązania problemu, w oparciu o kombinatoryczny model wielorzędowego rozmieszczenia maszyn (stanowisk roboczych) w hali produkcyjnej, który określa specyficzny sposób rozmieszczenia maszyn zgodny z rysunkiem nr 1. Dla rozwiązania problemu zaproponowano algorytmy konstrukcyjne, których wynik został poprawiony przez metaheurystykę tabu, tj. algorytm TS (ang Tabu Search).

Rysunek 1.  Wielorzędowe rozmieszczenie maszyn w hali produkcyjnej.

2. Model matematyczny

   Niech będzie permutacją numerów n maszyn (stanowisk roboczych) które podlegać będą rozmieszczeniu. Dalej, niech c_ij będzie kosztem jednostkowym (jednostki półproduktu na jednostkę odległości) transportu półproduktów pomiędzy maszynami (i,j) oraz b_ij jest odległością transportu jednej jednostki półproduktu pomiędzy tymi maszynami, gdzie tablica odległości [b_ij]_n*n jest wyliczana dla każdej permutacji maszyn i zależy zarówno od położenia maszyn określonych przez permutację oraz od zastosowanego systemu transportu międzymaszynowego w hali. Przy tak przyjętych założeniach możemy formalnie zapisać całkowity koszt transportu półproduktów pomiędzy maszynami hali w postaci następującej funkcji celu:

	(1)
gdzie: (j) { 1, 2, …, n}, j = 1, 2, …, n;               (j) - numer maszyny usytuowanej na j-tej pozycji w hali maszyn.

Permutacja wyznacza kolejność z jaką będą rozmieszczane maszyny w hali; sposób rozmieszczenia ilustruje rysunek nr 1. Niech h jest maksymalną długością rzędów w hali produkcyjnej, a_i jest szerokością maszyny i oraz d_ij  minimalnym odstępem między maszynami (i,j). Minimalna długość rzędu potrzebna do rozmieszczenia wszystkich maszyn zgodnie z permutacją jest równa:
 

(2)

W przypadku gdy minimalna długość rzędu wszystkich maszyn D przewyższa maksymalną długość rzędu hali h, D() > h,  tworzymy dodatkowe rzędy w których kolejno rozmieszczamy maszyny zgodnie z permutacją . Niech k jest numerem porządkowym rzędu maszyn w hali. Każdy rząd k hali jest utworzony z maszyn podsekwencji ((k), (k+1), ..., (k)) permutacji . Długość rzędu k maszyn określona jest zależnością:
 

	(3)
k = 1, 2, ..., K, gdzie K jest liczbą utworzonych rzędów maszyn.

Do pierwszego rzędu maszyn należą maszyny podsekwencji (m1), ..., (n1)) spełniające warunki:
 

D( (m1), (n1)) <= h D((m1), (n1+1)) > h

(4)

Sekwencja maszyn umieszczona w drugim rzędzie spełnia zależności:
 

D((m2), (n2)) <= h D((m2), (n2+1))> h

(5)

I tak dalej, gdzie:
= ((1), (2), ..., (n)) = ((1), ..., (1)(2), ..., (2), (3), ..., (nK))
i 1 = 1, 2 = 1+1, 3 = 2+1, ..., K = (K-1) = n.
 

3. Algorytmy konstrukcyjne

   Aby rozwiązać tak zdefiniowany problem, zaproponowano dwa algorytmy konstrukcyjne których celem jest pozyskanie dobrego rozwiązania początkowego (wstępnego rozmieszczenia maszyn), które po poprawie przez główny algorytm poprawy (algorytm TS) może dać nam zadawalające rozwiązanie (rozmieszczenie maszyn).

Algorytm "Constr1" (o złożoność 0(n²)), na podstawie jednostkowego kosztu transportu materiałów c_ij rozmieszcza maszyny w linii tak aby zminimalizować "lokalne" koszty transportu.
Schemat algorytmu "Constr1":

Krok 1. W macierzy [cij]n*n znajdź maksymalny element cij = max{ckl : ( k, l {1, 2, ..., n} ), ( k l )} i przypisz cik = cjk := - dla k = 1, 2, ..., n oraz jako rozwiązanie częściowe przypisz := ( i, j ). Krok 2. Jeżeli częściowe rozwiązanie = ((), (+1), ..., ())  nie zawiera wszystkich maszyn to dla macierzy kosztów [cij]n*n znajdź maksymalny element:   Jeżeli j = () to przypisz := (i, (), ..., ()) oraz cik := - dla k = 1, 2, ..., n; w przeciwnym wypadku podstaw := ((), ..., (), j) oraz cik := - dla k = 1, 2, ..., n.

Algorytm "Constr2" (o złożoności 0(nlogn)), wyznacza sekwencję maszyn według obliczonej funkcji priorytetu:

rozmieszczając maszyny rozpoczynając od największej wartości priorytetu - w położeniu centralnym sekwencji , do najmniejszej wartości priorytetu - położenia skrajne sekwencji . Schemat algorytmu "Constr2":        Krok 1. Dla każdej maszyny j { 1, 2, …, n} oblicz wartość priorytetu:  Krok 2. Utwórz listę maszyn (m1, m2, …, mn) według niemalejącej wartości funkcji priorytetu: w(m1) w(m2) … w(mn). Krok 3. Wyznacz rozwiązanie przypisując (1) := m1, (n) := m2, (2) := m3, (n-1) := m4, (3) := m5, i tak dalej.

4. Algorytm Tabu Search

   Otrzymane w wyniku zastosowania algorytmów konstrukcyjnych rozwiązanie, poprawiamy przez zastosowanie algorytmu Tabu Search. Do otrzymania lepszego rozwiązania stosujemy algorytm TS [poz.1] wyposażony w mechanizmy dywersyfikujące i intensyfikujące proces poszukiwań takie jak: pamięć krótko terminowa, pamięć długo terminowa, metoda skoku powrotnego [poz. 2].
Ogólnie, klasyczny algorytm tabu (TS) można opisać następująco:
Po wyborze sąsiada y z otoczenia N(ⁱ), niezależnie od relacji między wartościami funkcji celu q(y), q(ⁱ), przechodzi się do niego, kładąc ⁱ⁺¹=y. Otoczenie N(ⁱ), to otoczenie które jest zbiorem rozwiązań powstałych w skutek wzajemnej wymiany (ruchu) pozycji dwóch maszyn w rozwiązaniu ⁱ. Ruch taki nazywamy ruchem typu wymień (ang. Swap), a liczba możliwych do wykonania ruchów względem rozwiązania o rozmiarze n maszyn wynosi n(n-1)/2.  W celu uniknięcia cyklu (powstawanie cyklu jest naczelną wadą standardowych metod poszukiwania) pewne rozwiązania z sąsiedztwa N(ⁱ) uważa się za zabronione i nie bierze się pod uwagę podczas wyznaczania y. Są to rozwiązania, które były już rozwiązaniami lokalnie optymalnymi w ostatnich kilku lub kilkunastu iteracjach. Rozwiązania te nie są bezpośrednio pamiętane, ale z reguły są pamiętane w postaci pewnych ich „atrybutów”. Powoduje to, że zabronienia z nich wynikające w danej iteracji dotyczą także rozwiązań, które nie były dotychczas rozwiązaniami lokalnie optymalnymi. Tak zorganizowany sposób pamiętania rozwiązań lokalnie optymalnych nosi nazwę pamięci krótko terminowej GLT. W trakcie wykonywania kolejnych iteracji pamięta się aktualnie najlepsze znalezione rozwiązanie ^TS w sensie wartości funkcji celu i odpowiadającą mu wartość tej funkcji q^TS=q(^TS). Poszukiwania przerywa się w momencie zaistnienia odpowiednich warunków stopu. Innym mechanizmem polegającym na różnicowaniu procesu poszukiwań jest pamięć długoterminowa. Istota tego mechanizmu polega na tym, że zliczamy liczbę tych iteracji w których wymieniamy daną parę maszyn, i zależnie od liczby wymian oraz innych współczynników, o których powiemy poniżej, nakładamy karę na funkcję celu obliczaną dla rozwiązania otrzymanego poprzez przestawienie pary maszyn notowanych w długoterminowej liście tabu.

Techniczna realizacja pamięci długoterminowej polega na wykorzystaniu dolnej części  macierzy LT_nxn, w której  zliczamy przestawienia kolejnych maszyn:
 

DLT(m₁,m₄)=s oznacza iż w procesie poszukiwań maszyny m₁ i m₂ były wymieniane s razy. Wykorzystując pamięć długoterminową definiujemy postać wzoru według którego będziemy obliczać funkcję celu przy przeszukiwaniu otoczenia rozwiązania w danej iteracji:

(i,j) -	Rozwiązanie otrzymane z rozwiązania przez wymianę maszyn i i j.
-	Waga z jaką funkcja kary wpływa na funkcję celu, jest parametrem ustalanym przez użytkownika.
k -	Aktualny numer iteracji.
	Względna częstotliwość przestawiania pary (i,j) prowadząca do pozyskania rozwiązania lokalnie optymalnego.

W każdej iteracji tablica DLT jest odpowiednio modyfikowana, to znaczy jeżeli nastąpiła wymiana maszyn (i,j) to DLT(i,j)=DLT(i,j)+1.
 

Poziom aspiracji.
   Zapisywanie na liście tabu atrybutów rozwiązań, a właściwie atrybutów rozwiązań i ruchów, i w konsekwencji traktowanie pewnych ruchów jako zabronionych, ma oprócz oczywistych zalet także poważną wadę. Może to bowiem powodować zabronienie wykonania ruchu, który  jest jednak interesujący z punktu widzenia dalszego procesu poszukiwania. Przykładowo prowadzi bezpośrednio lub pośrednio (po wykonaniu kilku dalszych iteracji) do rozwiązań lokalnie optymalnych o wartości funkcji celu mniejszej niż dotychczas znaleziona. W celu uniknięcia tej wady wprowadza się funkcję aspiracji ruchu oraz poziom aspiracji do zabronienia. Jeżeli dany ruch (wymiana) jest zabroniony, ale jego wartość funkcji aspiracji jest mniejsza niż poziom aspiracji do zabronienia , to ruch ten traktuje się jako ruch niezabroniony.
Oznaczenia:

-	Rozwiązanie należące do zbioru rozwiązań dopuszczalnych.
qk -	Wartość funkcji celu w k-tej iteracji.
min -	Rozwiązanie poprawione przez algorytm TS.
qmin -	Najlepsza wartość funkcji celu znaleziona przez algorytm TS.
k -	Licznik wykonanych iteracji.
K -	Globalna liczba iteracji przewidzianych do wykonania.
k_lokal -	Licznik iteracji wykonanych bez poprawy funkcji celu.
MaxIter -	Liczba iteracji wykonana bez poprawy funkcji celu po której następuje zakończenie pracy algorytmu.
GLT -	Górna lista tabu – pamięć krótkoterminowa.
DLT -	Dolna lista tabu – pamięć długoterminowa.
pa -	Poziom aspiracji.
T -	Okres tabu
-	Stała różnicowania procesu poszukiwań.

Schemat algorytmu TS z zastosowaniem pamięci krótkoterminowej, długoterminowej i kryterium aspiracji:

Krok 1. Początek poszukiwania. Podstaw:  := st;;               min := ; qmin := q();               pa := q();               k_lokal := 0;   Krok 2. Dla k:=1  do K wykonaj:   a) Wyznacz najlepsze rozwiązanie w otoczeniu:         Jeżeli GLT( i, j ) = 0 to           Jeżeli GLT( i, j ) > 0 to   Podstaw: := ( i*, j* ); qk := q();   b) Poprawa rozwiązań:         Jeżeli qmin > qk to podstaw: qmin := qk; min := ; pa := qmin; k_lokal := 0;         Jeżeli pa > q( ( i', j' ) ) to wykonaj instrukcje: # :=  {   Podstaw:    := ( i', j' );    min := ;    qk := q();    qmin := qk;    pa := qmin;    k_lokal := 0; }         Podstaw k_lokal := k_lokal+1;         Jeżeli k_lokal = MaxIter to STOP; c) Korekta stanu pamięci: Dla (i, j) podstaw GLT(i, j) := max{ 0, GLT(i, j)-1 }. Jeżeli wykonano instrukcje # to podstaw:       GLT(i', j') := T;  i  DLT(i', j') := DLT(i', j') +1; w przeciwnym wypadku:      GLT(i*, j*) := T;  i  DLT(i*, j*) := DLT(i*, j*) +1;

   Zawansowanym mechanizmem metody TS, zastosowanym do rozwiązania problemu, jest mechanizm skoku powrotnego, który przeciwdziała powstawaniu cykli. Mechanizm ten łączy w sobie technikę intensyfikacji i dywersyfikacji poszukiwań i ogólnie mówiąc polega na cofaniu się (wykonywaniu skoku powrotnego) do rozwiązań lokalnie optymalnych w celu wyjścia z tych rozwiązań inną niż wykorzystywaną już drogą i dalszym poszukiwaniu rozwiązania atrakcyjniejszego.
 

5. Wyniki badań komputerowych

   Do rozwiązania opisanego powyżej problemu została stworzona aplikacja komputerowa przy pomocy której możemy dokonać rozwiązania problemu, to znaczy możemy znaleźć możliwie najbardziej zadawalające rozwiązanie przybliżone. W naszym wypadku do eksperymentów użyto danych generowanych losowo.

Tabela 1 przedstawia wyniki obliczeń komputerowych.
 

zestaw danych	Alg. Constr1			Alg. Constr2
	Qst	Qtabu	I	Qst	Qtabu	I
Z40a (Wyk. 2a)	54795,47	50657,25	63	54623,32	50263,91	62
Z40b (Wyk. 2b)	38702,16	37670,10	70	38746,97	37666,28	59
Z40c (Wyk. 2c)	43122,26	41072,38	132	44189,74	41072,40	66
Z40d (Wyk. 2d)	48825,80	47637,42	64	48889,60	48019,05	58

Tabela 1. Wyniki obliczeń komputerowych

Objaśnienia do tabeli 1:

zestaw danych -	zestaw 40 maszyn, o różnych  losowo dobranych parametrach geometrycznych i kosztach jednostkowych transportu,
Qst -	wartość funkcji celu osiągnięta przez algorytm konstrukcyjny,
Qtabu -	wartość funkcji celu osiągnięta przez algorytm tabu search,
I -	liczba iteracji po jakiej osiągnięto warunek stopu.

Wykres 2a.	Wykres 2b.
Wykres 2c.	Wykres 2d.

Tabela 2 przedstawia procentowy wskaźnik zysku wynikający z zastosowania metody TS do poprawy rozwiązania otrzymanego poprzez algorytm konstrukcyjny.

Tabela 2. Procentowy wskaźnik zysku wynikający z zastosowania metody TS do poprawy rozwiązania otrzymanego poprzez algorytm konstrukcyjny
 

6. Wnioski

   Podsumowując całokształt przeprowadzonych badań i eksperymentów możemy powiedzieć, że rozwiązanie problemu rozmieszczenia maszyn w systemie produkcyjnym przy wykorzystaniu metody „Tabu Search” daje zadawalające rezultaty w porównaniu z rozwiązaniami otrzymanymi prostymi metodami konstrukcyjnymi. Poprzez właściwe rozmieszczenie maszyn możemy w sposób znaczny zredukować koszty transportu elementów w procesie produkcyjnym, co w sposób oczywisty przekłada się na oszczędność w kosztach produkcji.
 

Literatura
 

[1]	Glover F. and Laguna M., Tabu search. In Modern Heuristics for Combinatorial Problems, ed. C. Reeves, Blackwell Scientific Publishing, 1995
[2]	Nowicki E., Metoda tabu w problemach szeregowania zadań produkcyjnych, Wydawnictwa Politechniki Wrocławskiej, Wrocław 2000
[3]	Homel T., Wala K., Optimization of the machine layout problem in manufacturing cell, International Carpathian Control Conference ‘2001, Krynica, Poland, May 22-25, 2001, pp. 139-144