Ogólne Tudu

[Platonn]

DANE algorytmu (trzeba je jakoś spreparować #5):

• o = liczba Operacji
  • dla każdej Operacji: koszt (czas) wykonania operacji [zakładamy, że Maszyna jest już przydzielona więc i koszt wykonania jest już ustalony]
  • dla ułatwienia przyjmijmy, że operacje numerujemy liczbami naturalnymi 0...(o-1)
• porządek technologiczny
  • dla ułatwienia przyjmijmy, że porządek technologiczny to naturalna relacja mniejszości na liczbach naturalnych: 0 < 1 < 2 < ... < (o-1). (tzn. np. operację 2. można wynokonać po 1., ale 1. nie można po 2.)
• n = liczba Zadań
  • dla każdego zadania: ciąg operacji wewnątrz zadań (*) (ciągi Operacji między Zadaniami są rozłączne i "pokrywają" cały zbiór wszystkich Operacji). Ponadto kolejność operacji w zadaniu ma być zgodna z ustalonym wcześniej porządkiem technologicznym!
• m = liczba Maszyn
  • dla każdej Maszyny:
    • ciąg Operacji, reprezentujący kolejność wykonywania operacji na maszynie ciągi Operacji między maszynami są rozłączne i "pokrywają" cały zbiór wszystkich Operacji) (**). (zbiór wszystkich początków tych list będziemy nazywać A, a zbiór końców list B). Ponadto kolejność wykonywania operacji na maszynach ma być zgodna z ustalonym wcześniej porządkiem technologicznym!

Model do zbudowania w naszym programie:

Graf G #6:

• zbiór wierzchołków to wszystkie operacje (o liczbie o)
• (zbiór R) dla każdego Zadania: lista jednokierunkowa łącząca operacje tego zadania według DANEGO porządku technologicznego (*)
• (zbiór K) dla każdej Maszyny: lista jednokierunkowa łącząca operacje wykonywane na tej maszynie według DANEGO porządku (**)

Potem Graf Gplus #7:

• kopiujemy powyższy graf m razy, czyli mamy m+1 kopii (gdzie m to liczba Maszyn), tylko każdej operacji o numerze i z oryginału nadajemy w kopii numer i+l*o, (gdzie l (czytaj "el") jest numerem kopii, a o (czytaj... "o" 😄) jest liczbą wszystkich operacji w oryginale grafu)
• wewnątrz każdej kopii przekopiowujemy wszystkie krawędzie (zbiór R i zbiór K)) z oryginału
• (zbiór W) dla kazdych dwóch kolejnych kopii grafu: stawiamy krawędzie ze zbioru B (ostatnie operacje wykonywane na różnych maszynach) z poprzedniej kopii do zbioru A (pierwsze operacje na różnych maszynach) w następnej kopii - po jednej krawędzi dla każdej maszyny, czyli w sumie tylko m krawędzi

Obliczanie długości najdłuższych ścieżek #8:

• utwórz tablicę L na wyniki poniższych obliczeń (o rozmiarze m x m):
  • dla każdej Operacji a ze zbioru A_1 (jest ich m):
    • dla każdego i = 2,3,...,m+1:
      • oblicz najdłuższą ścieżkę między operacją a, a jej klonem z i-tej kopii
      • trzeba zmodyfikowwać model tak, by wagi były na krawędziach (jak wymaga tego Dijkstra), a nie w wierzchołkach
      • trzeba zmodyfikować algorytm Dijkstry do znajdowania najdłuższych, a nie najkrótszych ścieżek (tak jak ma to w domyśle)
        • pomysł z wikipedii [https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths]: w preprocessingu wszystkie wagi przemnożyć przez (-1), szukać najkrótszej ścieżki, a potem wynik przemnożyć znowu przez (-1). (uwaga: to działa tylko dla grafów acyklicznych, a nasz taki jest, bo wszystkie sciezki sa zgodne z porzadkiem technologicznym = topologicznym)

Wynik:

• zwrócić maksymalną wartość z tablicy L

Testy

• Dobrze by było przeprowadzić na tym proste testy, żeby sprawdzć, czy napisaliśmy to dobrze