Algorytm Johnsona - szeregowanie zadań na dwóch maszynach

slmb-slavko · Dołączył: 19 Cze 2006 Posty: 2

Witam !

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.

marcin_an · Wysłany: Pon Cze 19, 2006 7:05 pm Temat postu:

Nie napisałeś niestety, jak te zadania mają być wykonywane na maszynach - czy na obydwu jedna po drugiej, czy tylko na jednej itd. Przyjmuję założenie, że każde zadanie musi zostać wykonane na obydwu maszynach, szeregowo.

1. Potrzebujesz danych wejściowych w postaci czasów wykonywania poszczególnych zadań na każdej z maszyn.
2. Najpierw wybierasz te, których czas wykonania na pierwszej maszynie jest krótszy niż czas wykonania na drugiej maszynie i sortujesz je niemalejąco według czasu wykonania na pierwszej maszynie.
3. Pozostałe sortujesz w kolejności nierosnącej według czasu wykonania na drugiej maszynie. Zaznaczam specjalnie na czerwono, bo podobno ludzie się mylą i sortują wg. pierwszej.
4. Łączysz obydwie listy (w kolejności takiej, w jakiej powstawały) i otrzymujesz uszeregowanie o najkrótszym czasie wykonania. Średni czas przepływu może być natomiast gorszy niż w innych rozwiązaniach i nie należy się tym zrażać - możliwe, że tak wyjdzie.

slmb-slavko · Dołączył: 19 Cze 2006 Posty: 2

Cześć !

Dzięki za zainteresowanie moim problemem. Zadania maja być wykonywane na dwóch maszynach (A,B), określenie czasów wykonywania poszczególnych zadań będzie losowe ( przynajmniej tak sobie to wyobrażam ). Muszę napisać coś o samym algorytmie Johnsona i napisać programik w C++ builder + jakiś wykres. Przyznaje że nie jestem w tym temacie dość biegły, a czas cholernie mnie goni - ( termin sobota ), więc nie brzmi to dość optymistycznie. Widzę, że masz w tym temacie doświadczenie w przeciwieństwie do mnie. Dlatego zwracam się z b. wielką prośbą do Ciebie bys pomógł mi rozwiązać to zadanie. Nie jestem typem lenia i przeważnie sam staram się sobie radzić, ale tego nie przeskocze ze względu na termin. Jeszcze raz bardzo proszę o pomoc.

Pozdrawiam !

marcin_an · Wysłany: Wto Cze 20, 2006 7:39 pm Temat postu:

Weź kartę, weź ołówek lub długopis i narysuj sobie to na spokojnie np. dla 5 procesów. Zobacz jak działa i tyle :-). Jeżeli masz w jakiś sposób to opisać, to zwracam uwagę na taki drobny szczegół: przyjrzyj się i zauważ, że na początku na maszynie A wykonywane są najkrótsze zadania, by na początku od razu i maszyna B była wykorzystana i nie stała bezczynnie. Równocześnie na końcu na maszynie B wykonywane są zadania również najkrótsze - zeby z kolei ona nie przeciągała pracy całego układu.

Znać się nie znam i nie jestem w temacie - po prostu za kilka dni mam z tego egzamin ;-). A ponieważ mam egzamin, to - jak nietrudno się domyślić - mam również sesję. I z tego powodu raczej pełnego kodu, z generowaniem wykresu, nie stworzę. Tym bardziej, że prawdopodobnie oczekują od ciebie wyklikania jakiegoś obrazka w Borland Builderze, a tego programu kompletnie nie znam. Ja bym to mógł napisać najwyżej od zera w C++, bez generatorów - ale do tego trzeba mieć czas.

gagatek · Dołączył: 13 Gru 2009 Posty: 1

mam takie pytanie, jak wyglada rozwiazanie podobnego zadania ale dla trzech maszyn? Bo mam takie zadanie ale nigdzie nie moge znalesc jak to wyglada dla trzech... prosze o pomoc

łodyga · Gość

Proponuję skorzystać z biblioteki. Słowo kluczowe - szeregowanie zadań.

dow1346 · Dołączył: 19 Paź 2009 Posty: 37

Miałem z tego projekt kiedyś. Ogólnie po kilku głębszych zastanowieniach i rozpisaniu sobie na kartce okazało sie ze nie jest to takie trudne jak myslalalem. Zeby to zrozumiec wystarczylo mi przeczytanie tego:http://www.free.of.pl/s/szeregowaniezadan/teoria.html
- jest tak jedno zdanie informujące o 3 maszynach.
pozdr