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

∞