Marek Sobolewski_FlowShop(2).pdf

(700 KB) Pobierz
Problem „Flow Shop”
- przykładowe algorytmy -
Marek Sobolewski
Wprowadzenie
•
Problemy szeregowania zadao:
–
Job Shop – maszyny i kolejnośd dowolne (określone)
–
Open Shop – kolejnośd dowolna (określona)
–
Flow Shop – ta sama kolejnośd dla wszystkich zadao
(„taśma produkcyjna”)
•
Kryterium optymalizacyjne:
–
Tardiness – sumaryczne / ilościowe opóźnienie
–
Flowtime – śreni czas przebywania zadania w systemie
–
Makespan – czas wykonania wszystkich zadao
Marek Sobolewski | Flow Shop - algorytmy
Złożonośd obliczeniowa
•
Dla więcej, niż dwóch maszyn problem Flow Shop jest NP-
zupełny. Oznacza to, że nie da się znaleźd jego rozwiązania
w czasie wielomianowym (tzn. w czasie proporcjonalnym
do
n
α
, gdzie
n
to liczba danych wejściowych).
•
Złożonośd obliczeniowa algorytmu określa ilośd zasobów
lub czasu potrzebną do przeprowadzenia algorytmu w
zależności od rozmiaru wejścia (wielkości
n),
np. O(n) –
zasoby/czas potrzebne do wykonania algorytmu są wprost
proporcjonalne do liczby danych wejściowych.
•
Najprostszy algorytm zwracający zawsze rozwiązanie
optymalne to tzw. Przegląd Zupełny.
Marek Sobolewski | Flow Shop - algorytmy
Przegląd zupełny
•
Złożonośd obliczeniowa O(n!)
•
Załóżmy, że możemy oceniad 1 000 000 000
rozwiązao/sekundę
Liczba danych
wejściowych (n)
5
10
20
25
50
Liczba możliwych
rozwiązao
5!
10!
20!
25!
50!
Czas potrzebny na znalezienie
rozwiązania optymalnego
0,00000012 sekundy
0,0036288 sekundy
~77 lat
~500 milionów lat
~10
47
lat
Marek Sobolewski | Flow Shop - algorytmy
Problem Flow Shop – oznaczenia
•
Liczba zadao: N
•
Liczba maszyn: M
•
Dane rozwiązanie (permutacja
N-elementowa):
•
Czas obróbki i-tego zadania na j-tej maszynie:
•
Czas zakooczenia i-tego zadania na j-tej maszynie:
•
Kryterium optymalizacyjne - makespan (C
max
):
•
Możliwych rozwiązao: N!
Marek Sobolewski | Flow Shop - algorytmy

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin