Algorytm Johnsona - Pomocy!!!

slmb-slavko · ~user **Dołączył:** 19 Cze 2006 **Posty:** 3

Dostałem w sumie z pozoru dosyć proste zadanie na zaliczenie, mianowicie wykorzystać algorytm Johnsona do szeregowania zadań na dwóch maszynach. Mam duży problem ze znalezieniem czegoś sensownego na temat algorytmu Johnsona. Przeszukałem już całe zasoby sieci i nic. Zwracam się z prośbą do Was, może dysponujecie jakąś wiedzą na ten temat bądź mateiałami. Z góry dziekuje za wszelkie zainteresowanie i pomoc.

_________________
Pozdrawiam !

donkey7 · ~user **Dołączył:** 17 Cze 2005 **Posty:** 135

cormen: http://www.wnt.pl/product.php?action=0&prod_id=466&hot=1

slmb-slavko · ~user **Dołączył:** 19 Cze 2006 **Posty:** 3

Dzięki za linka do książki - kurcze żeby to był jakiś torrent to by było w ogóle bajka. Mam 4 dni na wykonanie tego zadania, a nie ruszyłem z miejsca

_________________
Pozdrawiam !

donkey7 · ~user **Dołączył:** 17 Cze 2005 **Posty:** 135

możesz spróbować edonkeya2000. polecam!

atsd:
spróbuj popytać jakichś belfrów, powinni mieć książki o tym. ewntualnie napisz do któregoś z wymienionych gości: tomasz czajka (ile to już tysięcy dolarów wywalczył?), filip wolski (który to już laptop wygrał?), http://www.oi.edu.pl/php/show.php?ac=p171400 , http://www.topcoder.com/tc?module=AlgoRank i inni Cool

ps. ogólnie cormen to na razie dla mnie czarna magia. nawet nie mogę zrozumieć jak działają zrównoważone drzewa binarne, bo tak to zamotał Shocked

TPJ · Wysłany: 25-06-06 10:03

No proszę, coś z mojej dziedziny. Nie wiem, czy problem wciąż aktualny, ale co tam - szeregowanie zadań to moja naukowa pasja.

Algorytm Johnsona służy oczywiście do optymalnego (ze względu na kryterium długości uszeregowania) szeregowania zadań na dwóch maszynach w tzw. systemie przepływowym (Flow-Shop, w skrócie FS).

Mamy dwie maszyny i N zadań. Każde z zadań jest wykonywane na obydwu maszynach, najpierw na pierwszej, potem na drugiej. Dla każdego z zadań znamy czasy ich wykonywania na każdej z maszyn. Zakładamy, że nie ma awarii, a obydwie maszyny są dostępne w początkowej chwili czasu.

Algorytm sprowadza się do wykonania trzech prostych kroków:

1) Podzielenie zadań na dwie grupy. W pierwszej powinny się znaleźć te zadania, dla których czas wykonywania na pierwszej maszynie nie jest dłuższy, niż czas wyknywania na drugiej maszynie. W drugiej grupie - wszystkie pozostałe.

2) Szeregujemy zadania z pierwszej grupy w taki sposób, aby najpierw były wykonywane te zadania, które mają mniejsze czasy na pierwszej maszynie.

3) Zadania z drugiej grupy szeregujemy w taki sposób, aby najpierw były wykonywane te zadania, które mają większe czasy na drugiej maszynie.

Prosty przykład:

slmb-slavko · ~user **Dołączył:** 19 Cze 2006 **Posty:** 3

Bardzo dziękuje za pomoc TPJ O to chodziło !!! Jeszcze raz wielkie dziękuje !

_________________
Pozdrawiam !

Idalgo · Wysłany: 25-06-06 23:53

nie ten dzial, przenioslem w algorytmy

_________________
Shutdown v3.0
--------------------------------------------------------
27 kwietnia 2007 Świerzo upieczony inz inf :>
obronione na 5 :>

tomaprzem · ~user **Dołączył:** 16 Sty 2007 **Posty:** 2

TPJ
Mam nadzieje ze jeszcze to odwiedzasz.
Mam troszke podobny problem co slmb-slavko, ale...
Moze od poczatku. Moj model sklada sie z magazynu, 2 maszyn i wozka, ktory porusza sie cyklicznie, ale w obu kierunkach. Na drugiej maszynie znajduje sie bufor: 1 na wejscie i 1 na wyjscie. Zadania sa pobierane z magazynu, wykonywane na 1 maszynie, nastepnie na 2 i znowu trafiaja do magazynu. Do tego modelu mam juz zaimplementowany algorytm Johnsona, mam tez zrobiony algorytm poruszania sie wozka, ale byl on tworzony dla modeli bez buforow. Moje pytanie brzmi. Co nalezalo by zmienic w algorytmie szeregowania i/lub algorytmie poruszania wozka, aby skrocic czas przetwarzania oraz czas bezczynnosci maszyn.
Dane sa odleglosci od maszyn oraz magazynu, ilosc zadan, predkosc wozka, czas zaladunku/rozladunku

TPJ · Wysłany: 18-01-07 13:38

Ciekawy problem.

Do czego służy ten bufor na drugiej maszynie? (Rozumiem, że wprowadza to jakieś dodatkowe ograniczenia, lecz jakie?)

Co znaczy "wózek porusza się cyklicznie"? Nie mamy wpływu na chwile czasu, w których wózek zaczyna się i kończy poruszać? Nie możemy nim sterować?

Nie jestem pewien, czy algorytm Johnsona da w tym przypadku rozwiązanie optymalne (oczywiście ze względu na długość uszeregowania), bo w tym algorytmie nie ma mowy o żadnych buforach.

Gotowego algorytmu nie podam (bo takowego nie znam) - ja wszędzie stosuję mój własny algorytm ewolucyjny.

Jedyna rada, jaka mi przychodzi na myśl, to przeprowadzić parę symulacji i zastosować TOC (Theory of Constraints).

tomaprzem · ~user **Dołączył:** 16 Sty 2007 **Posty:** 2

1.Bufor oznacz ze maszyna moze miec 1 zadanie na wejsciu jedno wykonywac i 1 na wyjsciu, gdy nie ma buforu zadanie jest ladowane od razu na maszyne do przetwarzania.
2.Moze zle sie wyrazilem: sa trzy obiekty A,B,C, ktore tworza trojkat, wozek porusza sie po krawedziach, wozek moze zatrzymac sie tylko przy obiekcie. standardowo wozek porusza sie tylko w jednym kierunku, ale mozna zrobic tez ruch w dwoch kirunkach
3. Proszę o wiecej informacji o twoich algorytmach.