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.
0
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&rct=j&q=przydzielanie%20zada%C5%84%20zbigniew%20buchalski&source=web&cd=2&sqi=2&ved=0CCoQFjAB&url=http%3A%2F%2Fwww.ptzp.org.pl%2Ffiles%2Fkonferencje%2Fkzz%2Fartyk_pdf_2011%2F016.pdf&ei=It-hTta2N-jb4QTq57TgBA&usg=AFQjCNEACQCm9p2lwklE-F9kEu2W06x1Iw&cad=rja
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.
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/scheduling/scheduling_algorithms.htm