szeregowanie wielu zadan na wielu maszynach - branch and bound

Odpowiedz Nowy wątek
2011-10-19 16:59
nero1256
0

Potrzebuje algorytm podziału i ograniczeń (branch and bound) dla problemu Pm || Cmax. Przykładem takiego problemu może być np szeregowanie procesów na kilku procesorach. Ja mam zbadać efektywność takiego algorytmu, jak zmienia się czas jego działania w zależności od ilości maszyn i ilości zadań. Dane do programu to podaje ilość maszyn, ilość procesów i czasy wykonania każdego z procesów. Coś w tym stylu: http://csulb.edu/~obenli/Research/IE-encyc/bb.html Pisał już ktoś taki algorytm może, albo pomoże w napisaniu.
PS: Mam taki jeden kod http://pastebin.com/qwcsh1Y7 ale nie jestem jego pewien bo to wygląda na Flow Shop a może się mylę? Do tego jest napisany obiektowo i zawiera elementy algorytmu Schrage. Ten ma być prostszy.

Pozostało 580 znaków

2011-10-21 23:09
0

Jak wymyślałem algorytm przydziału zadań do procesorów i przydzielenia zasobów pomógł mi jeden artykuł - może też coś pomoże tym razem. http://www.google.pl/url?sa=t[...]klE-F9kEu2W06x1Iw&cad=rja

Pozostało 580 znaków

2011-10-23 12:03
0

Ja to bym zrobił tak jak np mamy 3 maszyny i 20 zadań. W pierwszym kroku posortował te czasy od największego do najmniejszego. I teraz tak w drugim kroku przydzielił bym te najdłużej trwające zadanie na maszynę numer 1 potem drugie długie zadanie na maszynę nr 2 i trzecie na maszynę nr 3. No i potem żeby resztę 17 zadań upakować w miarę regularnie trzeba by przy kolejnych dodawaniach zadań do maszyn, kontrolować i sprawdzać jaki jest już czas na maszynie 1 na maszynie 2 i 3. I dodać to zadanie w najbardziej optymalny sposób. Ale czy to jest metoda podziału i ograniczeń to nie wiem? No i czy to optymalne jest myślenie.

Nie jest optymalne. Poczytaj ten artykuł co linkowałem. Chodzi głównie, o to ,żeby wszystkie maszyny kończyły zadania w tym samym czasie i żeby nie było przestoju. Chyba, że działają asynchronicznie. - lukas_gab 2011-10-23 12:27

Pozostało 580 znaków

2011-10-25 15:43
0

A to nie jest problem NP-zupełny? (złożoność wykładnicza)
Bo brzmi trochę jak plecakowy.

Algorytmów na to jest kilka, ale chyba nie ma idealnego. Najbardziej znane:

  • najpierw najkrótsze
  • najpierw najdłuższe
  • i wiele innych:

http://wiki.osdev.org/Scheduling_Algorithms
http://www.ctl.ua.edu/math103[...]ing/scheduling_algorithms.htm


Szacuje się, że w Polsce brakuje 50 tys. programistów

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0