Studenci Notatki

Algorytmy

Program powinien być w stanie:

  • wczytywać dane systemu produkcyjnego oraz procesów produkcyjnych
  • wczytywać i zapisywać stan systemu produkcyjnego (oraz stan realizacji procesów produkcyjnych)
  • symulować działanie systemu produkcyjnego:
    • krok po kroku
    • do następnego zdarzenia wymagającego uruchomienia algorytmu
    • do końca symulacji (zakończenia wszystkich procesów produkcyjnych)
  • pokazywać (graficzna prezentacja) działanie algorytmów sterowania (podejmowania decyzji)
    • krok po kroku
    • do następnego "ciekawego" momentu
    • do końca

Przykład algorytmu: algorytm Johnsona

Wynikiem działania tego algorytmu jest decyzja o kolejności wykonywania zadań w systemie składającym się z dwóch maszyn.

1. Stwórz zbiór zadań, dla których czas wykonywania na pierwszej maszynie nie jest większy od czasu wykonywania na drugiej maszynie.
2. Uporządkuj zadania w tym zbiorze według rosnących czasów wykonywania na pierwszej maszynie.
3. Pozostałe zadania uporządkuj według malejących czasów wykonywania na drugiej maszynie.
4. Połącz uporządkowane zbiory zadań utworzone w punktach 2. i 3.. Kolejność zadań w powstałym zbiorze jest wynikiem działania algorytmu.

W algorytmie tym mamy cztery kroki do wykonania, a każdy z nich składa się z wielu czynności (czynnością będę nazywał elementarną część kroku algorytmu):

Krok 1: Stwórz zbiór zadań, dla których czas wykonywania na pierwszej maszynie nie jest większy od czasu wykonywania na drugiej maszynie.

1.1. Podkreślenie czasów trwania zadań na obydwu maszynach.
1.2. Podkreślenie tych zadań, dla których t_1 <= t_2.
1.3. Podzielenie zadań na dwie listy. Do drugiej listy powinny zostać przeniesione te zadania, które nie są podkreślone.

Krok 2: Uporządkuj zadania w tym zbiorze według rosnących czasów wykonywania na pierwszej maszynie.

Mamy już zadania podzielone na dwie odrębne listy.

2.1. Podkreślenie czasów wykonywania zadań na pierwszej maszynie dla zadań z pierwszej listy.
2.2. Posortowanie tych zadań tak, aby na początku listy znajdowały się zadania o mniejszych czasach wykonywania na pierwszej maszynie.

Krok 3: Pozostałe zadania uporządkuj według malejących czasów wykonywania na drugiej maszynie.

3.1. Podkreślenie czasów wykonywania zadań na drugiej maszynie dla zadań z drugiej listy.
3.2. Posortowanie tych zadań tak, aby na początku listy znajdowały się zadania o większych czasach wykonywania na drugiej maszynie.

Krok 4: Połącz uporządkowane zbiory zadań utworzone w punktach 2. i 3.. Kolejność zadań w powstałym zbiorze jest wynikiem działania algorytmu.

4.1. Połączenie zadań w jedną listę.
4.2. Podkreślenie numerów zadań.
4.3. Pokazanie kolejności zadań, która jest wynikiem działania algorytmu.

Zadania dla dyplomanta

Opracować podobny sposób dla algorytmu Johnsona zastosowanego do systemu z większą liczbą maszyn.

W analogiczny sposób opracować algorytmy LPT, SPT, EDD, LWR, FIFO oraz LIFO dla problemów klasy Job-Shop.

W analogiczny sposób opracować algorytm szeregowania zadań (wykorzystujący powyższe algorytmy) dla problemów klasy Job-Shop.

Należy to wykonać jeszcze przed rozpoczęciem tworzenia właściwej aplikacji.

Pytania do dyplomanta

Czy ma jakieś doświadczenie w pisaniu gier?

Czy ma jakieś doświadczenie w programowaniu animacji? (Zwykła animacja 2D, ewentualnie wektorowa.)

Czy ma jakieś doświadczenie w programowaniu GUI?

Symulacja procesów biznesowych

Program powinien umożliwiać:

  • wczytywanie i zapisywanie danych systemu produkcyjnego oraz procesów biznesowych
  • wczytywanie i zapisywanie stanu systemu produkcyjnego (oraz stanu realizacji procesów biznesowych)
  • symulowanie działania systemu produkcyjnego:
    • krok po kroku
    • do następnego zdarzenia wymagającego uruchomienia algorytmu
    • do końca symulacji (zakończenia wszystkich procesów produkcyjnych)
  • graficzne projektowanie systemu produkcyjnego oraz procesów biznesowych
    • można to zrealizować podobnie do programów graficznych: dostępne "płótno", paleta "narzędzi", z której użytkownik wybiera element i umieszcza go na płótnie
    • dodatkowo powinna być dostępna opcja podglądu tabel reprezentujących system oraz procesy; w tabelach powinno być możliwe modyfikowanie danych oraz ich usuwanie (dodawanie nowych elementów systemu oraz procesów nie musi być dostępne)

Przykład projektu: system przepływowy

Każdy system składa się z dwóch "warstw": strukturalnej oraz sterującej. Warstwa strukturalna określa elementy, z których składa się system (maszyny, bufory, etc.). Warstwa sterująca składa się z algorytmów, które sterują pracą elementów systemu.

Potrzebne będą następujące elementy ("narzędzia"):

  • wejście systemu
  • wyjście systemu
  • maszyna (elementarny element systemu biznesowego)
  • algorytm Johnsona (wyznaczający kolejność wykonywania zadań)
  • algorytm szeregowania zadań "sekwencyjny"

Do systemu dodajemy dwie maszyny, łącząc wyjście pierwszej z nich z wejściem drugiej. Dodajemy wejście systemu, które łączymy z wejściem pierwszej z maszyn. Dodajemy wyjście systemu, które łączymy z wyjściem drugiej z maszyn.

Następnie tworzymy warstwę sterującą. Dodajemy algorytm Johnsona i łączymy jego wejście z wejściem systemu. Dodajemy dwa algorytmy "sekwencyjne", których wejścia łączymy z wyjściem algorytmu Johnsona. Wyjścia tych algorytmów łączymy z wejściami sterującymi maszyn (każdy algorytm dla innej maszyny).

(Algorytm sekwencyjny jako wejście przyjmuje sekwencję numerów /identyfikatorów/ zadań, a następnie tak steruje maszyną, aby zadania były wykonane dokładnie w tej kolejności.)

Przykład projektu: system gniazdowy

Potrzebne będą następujące elementy ("narzędzia"):

  • wejście systemu
  • wyjście systemu
  • narzędzie grupujące
  • algorytm JobShop
  • algorytm JobShop-SPT

Używając narzędzia grupującego, dodajemy do systemu np. cztery maszyny. Maszyny te będą traktowane jako jedna całość, jeśli chodzi o wejście oraz wyjście. Wejście systemu będzie połączone z wejściem tej grupy, zaś wyjście z wyjściem grupy.

Warstwa sterująca będzie się składała z czterech algorytmów JobShop-SPT, po jednym dla każdej z maszyn. Wejście każdego z tych algorytmów łączymy z wyjściem informacyjnym danej maszyny, a wyjście każdego z tych algorytmów łączymy z wejściem sterującym (decyzyjnym) danej maszyny. Dodatkowo dodajemy algorytm JobShop, którego wejście łączymy z wejściem systemu, a wyjście z wejściem sterującym grupy.

Jak działa grupa maszyn:

  • dane na wejściu dostępne są na wyjściu informacyjnym grupy