UWAGA: Na prośbę studentów przedłużyłem termin oddawania projektów do czwartku 29.01, godzina 8:00 rano. Wtedy wszystkie otrzymane projekty drukuję, a nadesłane później będę uznawał za opóźnione (co się wiąże ze spadkiem oceny).

Do rozwiązania są problemy przedstawione poniżej. Do każdego problemu należy zaimplementować rozwiązanie dokładne, branch and bound oraz heurystykę. Projekty należy przesłać w wersji elektronicznej do 21 stycznia 2009 włącznie. Wersja papierowa nie jest wymagana. Na ostatnich zajęciach w celu zaliczenia projektu powinni pojawić się wszyscy autorzy projektu.

Instancje testowe (20.75 kB)

Format pliku z instancjami testowymi jest następujący:

• w pierwszej linii znajdują się dwie liczby n i m - odpowiednio liczba zadań oraz liczba maszyn,
• każda z kolejnych n linii zawiera m liczb - czas wykonywania się zadania na kolejnych maszynach.

Flowshop I

Dane jest n zadań i m maszyn. Dla każdego zadania znany jest czas t_i,j, w którym zadanie i-te wykonuje się na maszynie j-tej. Zanim zadanie będzie wykonane na maszynie i+1, musi się najpierw skończyć wykonywać na maszynie i-tej. Znaleść taką kolejność wykonywania zadań, aby ostatnie zadanie skończyło wykonywać się jak najwcześniej. 

Flowshop II

Dane jest n zadań i m maszyn. Dla każdego zadania znany jest czas t_i,j, w którym zadanie i-te wykonuje się na maszynie j-tej. Zanim zadanie będzie wykonane na maszynie i+1, musi się najpierw skończyć wykonywać na maszynie i-tej. Znaleść taką kolejność wykonywania zadań, aby suma czasów zakończenia wykonywania się ostatniego zadania na wszystkich maszynach była jak najmniejsza.

Permutacyjny Flowshop I i II

Tak jak Flowshop, tylko że na każdej maszynie zadania muszą wykonywać się w takiej samej kolejności.

Przykład

Mamy dwa zadania Z1 i Z2 i dwie maszyny M1 i M2. Czasy wykonania zadań na poszczególnych maszynach są następujące: Z1(M1): 5, Z1(M2): 7, Z2(M1): 3, Z2(M2): 2. W przypadku problemu Flowshop kolejność wykonywania się zadań na maszynach może być następująca:

• M1: Z1 Z2, M2:  Z1 Z2 [I: 14, II: 22]
• M1: Z1 Z2, M2:  Z2 Z1 [I: 17, II: 25]
• M1: Z2 Z1, M2:  Z1 Z2
• M1: Z2 Z1, M2:  Z2 Z1

W nawiasie podana jest wartość czasu będącego wynikiem typu I i II problemu. W przypadku permutacyjnej wersji problemu, zadania mogą się wykonywać jedynie w następujących kolejnościach:

• M1: Z1 Z2, M2:  Z1 Z2 
• M1: Z2 Z1, M2:  Z2 Z1

Wejściowy plik testowy dla powyższego przykładu wyglądałby następująco:

2 2
5 7
3 2

Sprawozdanie 

Sprawozdanie powinno zawierać:

• Opis środowiska (sprzęt i oprogramowanie) w którym realizowany był projekt.
• Opis sposobu implementacji, użytych algorytmów i wyników dla algorytmu dokładnego, branch and bound oraz jednej heurystyki.
• Wyniki powinny zawierać czas wykonania oraz ocenę rozwiązania, w przypadku b&b również liczbę odcięć, a w przypadku rozwiązania dokładnego i b&b liczbę odwiedzonych węzłów i liści.
• Porównanie wyników i czasów wykonania wszystkich algorytmów.
• W momencie gdy alg. dokładny lub b&b działa ponad 3 minuty powinien być zatrzymany, najlepszy zwrócony do tego czasu przez niego wynik zapisany jako wynik działania algorytmu, a czas wykonania uznany za zbyt długi, aby program mógł się zakończyć. Ambitne osoby mogą podwyższyć limit czasowy z 3 min. do dłuższego czasu, ale nie jest to wymagane.
• Analizę złożoności obliczeniowej algorytmów (w tym złożoność liczenia lower bounda).
• Wnioski.
• Dane i wyniki gdzie to tylko możliwe powinny być zaprezentowane i porównywane na wykresach. Na końcu raportu powinny znaleźć się tabele ze wszystkimi liczbami.