3582328157

POLITECHNIKA WROCŁAWSKA	Temat: Implementacja i analiza eksperymentalna algorytmów m eta h eu rystycz nyc h.
Wydział Elektroniki Automatyka i Robotyka studia inż.	Data:	Ocena:	Prowadzący:

PROBLEM:

Dany jest zbiór n zadań J={ji, Ji, Jn} oraz zbiór m

identycznych maszyn M={Mi, M2..... Mm}. Każde zadanie Jj<J

(/=l,2,..,n) jest niezależne,

niepodzielne, dostępne w chwili t=0 i musi zostać wykonane przez dokładnie

jedną z maszyn, przy czym jego wykonanie zajmuje każdej z maszyn p/>0

jednostek czasu. Każda maszyna może wykonywać w danym momencie co

najwyżej jedno zadanie. Problem polega na takim przyporządkowaniu zadań

do maszyn, aby zminimalizować czas zakończenia wykonywania ostatniego

zadania (czyli kryterium tzw. długości uszeregowania Cmax): Cmax= max lsi=Sn{Q>,

gdzie Cy oznacza moment zakończenia wykonywania y-tego zadania.

Zaimplementować:

Część I.

Algorytm LSA:

1.    Utwórz dowolną listę zadań 1,2.....n.

2.    Pobieraj zadania kolejno i przyporządkowuj do najwcześniej dostępnej

maszyny.

Algorytm LPT:

1.    Utwórz listę zadań 1,2.....n taką, że pi> p2> ... > p_n.

2.    Pobieraj zadania kolejno i przyporządkowuj do najwcześniej dostępnej

maszyny.

Część II.

Algorytm METAHEURYSTYCZNY:

1.    Utwórz dowolną listę zadań 1,2.....n.

2.    Pobieraj zadania kolejno i przyporządkowuj do dowolnej losowej

maszyny.

3.    Losowo wybrany element wyciąć z jednej maszyny i dodać do innej ponownie policzyć współczynnik, jeżeli po nowym