414223737

61

Harmonogramemanie linii montażowej jako element projektowania...

y^N’¹

opt

= min V^NJ

1 źlźN

Ą pNJ ^ropt

8. Metody ograniczania liczby generowanych stanów

Deterministyczny charakter przedstawionego algorytmu generowania stanów, powoduje wykładniczy przyrost ich liczby na kolejnych etapach procesu decyzyjnego. W szczególności, gdy macierz poprzedników i następników nie zawiera żadnych zależności wymuszających ograniczenia kolejnościowe przydziału operacji, na ostatnim etapie procesu wystąpi n\ harmonogramów dopuszczalnych. Znalezienie w takiej sytuacji rozwiązania optymalnego wydaje się nieosiągalne, zwłaszcza gdy trzeba to zrobić w czasie rzeczywistym, lub przynajmniej z praktycznego punktu widzenia akceptowalnym. Choć złożoność obliczeniową algorytmu klasyfikuje się jako 0(n\), istnieje kilka dróg ograniczenia liczby generowanych wektorów stanu, a zarazem i czasu potrzebnego do ich stworzenia i wybrania spośród nich rozwiązania optymalnego.

Pierwszy sposób polega na odpowiednim wypełnieniu macierzy poprzedników i następników, stanowiącej o kolejności technologicznej wykonywania poszczególnych operacji na harmonogramowanej linii produkcyjnej. W im większym stopniu kolejność ta zostanie zdeterminowana, tym mniej powstanie wariantów przebiegu procesu, a tym samym wygenerowana zostanie mniejsza liczba wektorów stanu. W szczególnym przypadku, stopień wypełnienia macierzy kolejności może być tak duży, że marszruta technologiczna będzie tylko jedna i zagadnienie optymalizacji przestanie istnieć.

Drugi sposób na skrócenie czasu działania algorytmu polega na zastosowaniu heury-styk, których cechą wspólną jest klasyfikacja wektorów stanu na te, które w dalszej perspektywie mogą dać rozwiązanie optymalne i te nieperspektywiczne.

Rys. 5. Idea eliminacji stanów nieperspektywicznych