B.8 Algorytmy optymalizacji w dyskretnych systemach produkcyjnych

Cel optymalizacji

Oczywistym celem optymalizacji jest poszukiwanie najlepszego (optymalnego) rozwiązania z punktu widzenia przyjętego kryterium. W dyskretnych procesach optymalizacja na ogół polega na zmianie kolejności wykonywanych zadań tak, by lepiej wykorzystać zasoby produkcyjne.

TIP: Należy pamiętać, że przymiotnika „optymalny” się nie stopniuje. To słowo oznacza „najlepszy z możliwych”, a nie „najlepszy ze znanych” albo „lepszy od poprzednio rozpatrywanego”. Często słyszy się jak ludzie mówią „moje rozwiązanie jest bardziej optymalne”. Jest to ewidentny leksykalny błąd semantyczny!!!

Funkcja celu

Funkcja celu to funkcja, której optimum jest poszukiwane. Na ogół przyjmuje postać jakiegoś wskaźnika oceny jakości optymalizowanego procesu – np. czas sumaryczny (szukane minimum), ocena zysku (szukane maksimum), ilość odpadów produkcyjnych (szukane minimum), maksymalne przestoje (szukane minimum).

Kara

W myśl zasady „jest kara, jest jakość” czasem kiedy sama funkcja celu jest niewystarczającym wskaźnikiem wprowadza się funkcję kary uwzględnianą przy optymalizacji. Przykładowo chcemy się szybko uwinąć z robotą, ale jednocześnie nie chcemy olewać niewygodnego zadania. Wówczas funkcją celu jest Cmax, a funkcją kary najdłuższy przestój. Przy optymalizacji należy wziąć pod uwagę oba wskaźniki.

Ścieżka krytyczna

Ciąg takich zadań, że opóźnienie któregokolwiek z nich opóźni zakończenie ostatniego zadania. W praktyce najczęściej jest to najdłuższa ścieżka bez przestojów.

Pojęcie bloku

Podstawowym pojęciem w metodzie blokowej jest pojęcie bloku. Blokiem operacji (krótko blokiem) w metodzie blokowej nazywany fragment najdłuższej drogi (drogi krytycznej) w grafie składający się z maksymalnej liczby węzłów reprezentujących operacje wykonywane na tej samej maszynie. Węzły reprezentujące operacje wykonywane na danej maszynie połączone są łukami wynikającymi z kolejności wykonywania zadań na tej maszynie. Łuki obciążone są wagą równą zero.

Twierdzenie blokowe

Niech π będzie dopuszczalnym zbiorem permutacji określających kolejność wykonywania zadań na maszynach. Jeżeli istnieje dopuszczalny zbiór permutacji γ taki, że Cmax(γ)<Cmax(π), wtedy w γ przynajmniej jedno zadanie dla przynajmniej jednego bloku z π poprzedza pierwsze zadanie lub występuje za ostatnim zadaniem tego bloku lub wykonywane jest na innej maszynie.

Algorytm Schrage i Schrage z podziałami

Są to algorytmy deterministyczne. W Schrage z podziałami można przerywać i wznawiać zadania. Więcej w załączonym pdfie. Nadają się do rozwiązywania problemów typu RPQ.

Algorytm Carliera

Również algorytm deterministyczny. Do swojego działania wykorzystuje algorytm Schrage. Więcej w załączonym pdfie.

NEH

Nadaje się do rozwiązywania problemów przepływowych. Nazwa algorytmu pochodzi od pierwszych liter nazwisk jego twórców: Nawaz'a, Enscore'a i Ham'a. NEH jest algorytmem deterministycznym, czyli zawsze dającym te same wyniki dla danego zestawu danych wejściowych. Kroki:

Krok 1: Uszeregować zadania nierosnącymi sumami czasu przetwarzania na maszynach.

Krok 2: Wziąć dwa pierwsze zadania i zakolejkować je tak, by zminimalizować część okresu produkcyjnego tak jakby wykonywane były tylko te dwa zadania.

Krok 3: Dla k = 3 do n przejść do Krok 4

Krok 4: Wstawić k-te zadanie na miejsce, które minimalizuje okres produkcyjny spośród k możliwych.

Idea algorytmu jest raczej prosta jednak jak się okazuje daje bardzo zadowalające wyniki w stosunkowo krótkim czasie.

SA

Symulowane wyżarzanie to rodzaj algorytmu heurystycznego przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Sposób działania symulowanego wyżarzania nieprzypadkowo przypomina zjawisko wyżarzania w metalurgii.

Kroki algorytmu w klasycznym podejściu podczas minimalizacji funkcji 

1. Losowy wybór punktu startowego . Przyjęcie temperatury ,

2. Wyznaczenie wartości funkcji  w punkcie ,

3. Wyznaczenie , gdzie  jest realizacją zmiennej losowej o rozkładzie normalnym z medianą w punkcie  i średnią wariancją równą ,

4. Wyznaczenie wartości funkcji  w nowym punkcie,

5. Podstawienie wartości  do  z prawdopodobieństwem danym rozkładem Boltzmanna ,

6. Zmniejszenie temperatury , gdzie  jest stałą z przedziału ,

7. Spełnienie kryterium stopu lub powrót do kroku 3.

Ogólnie chodzi o to, że na początku układ algorytm z początku przegląda bardzo szeroki zakres potencjalnych rozwiązań, który z każdą iteracją jest zawężany. Dzięki temu wpierw jest eksploracja, a później eksploatacja.

TS

Procedura (algorytm) (Tabu search - TS) stosowana do rozwiązywania problemów optymalizacyjnych. Wykorzystywana do otrzymywania rozwiązań optymalnych lub niewiele różniących się od niego dla problemów z różnych dziedzin (np. planowanie, planowanie zadań). Podstawową ideą algorytmu jest przeszukiwanie przestrzeni, stworzonej ze wszystkich możliwych rozwiązań, za pomocą sekwencji ruchów. W sekwencji ruchów istnieją ruchy niedozwolone, ruchy tabu. Algorytm unika oscylacji wokół optimum lokalnego dzięki przechowywaniu informacji o sprawdzonych już rozwiązaniach w postaci listy tabu (TL). Twórcą algorytmu jest Fred Glover.