Problem komiwojaŜera
Warunek VIII: Dla kaŜdego detalu moment obróbki na maszynie numer j+1 jest równy
momentowi skończenia odróbki na maszynie numer j.
Dane jest zadanie Johnsona (tzn. spełnione są warunki od I do VIII) w postaci:
maszyny
1
1
3
1
2
2
2
4
3
3
2
1
4
2
2
5
z
a
d
a
n
ia
5
2
4
4
Sprowadź zagadnienie do zagadnienia komiwojaŜera.
Przypadek dla m=3 (trzy maszyny); K={k
1
,k
2
, k
3
,k
4
, k
5
} (n=5 zadań – róŜne kolejności
wykonania).
1. Budujemy macierz wymiaru (n+1)
X
(n+1), czyli 6 na 6.
0 1 2 3 4 5
0
∞
1
∞
2
∞
3
∞
4
∞
5
∞
2.
W miejsca (i,0), i=1,2,3,4,5 wpisujemy 0.
3.
W (0,j), j=1,2,3,4,5: dodajemy czasy obróbki j-tego zadania na maszynach 1 i 2
4. Dla pozostałych miejsc (i,j), i=1,2,3,4,5;j=1,2,3,4,5; i
≠≠≠≠
j,
A) zbuduj modele (5 sztuk) „sztywnych schodów” dla zadań od 1 do 5 obróbki detali na
trzech maszynach.
B) Dla znalezienia liczby, którą trzeba wpisać w miejsce (i,j) weź model (schody) i-tego
zadania i połóŜ na osi czasu od początku diagramu Gantta.
C) Weź model (schody) j-tego zadania i połóŜ przysuwając jak najbliŜej początku
diagramu Gantta.
D) Zmierz długość „dziury” pomiędzy i-tym a j-tym zadaniem i wpisz tę liczbę w miejsce
(i,j)
E) masz macierz wymiaru 6 na 6, przejdź z nią do ostatniego problemu.
0 1 2 3 4 5
0
∞
4 4 5 4 6
1
0
∞
1 1 1 3
2
0
0
∞
0 0 0
3
0
2 1
∞
1 3
4
0
0 0 0
∞
0
5
0
0 0 0 0
∞