Szeregowanie zadań

Problem jest nastepujący:

mamy n zadań ktorych czas trwania wynosi t1...tn. Mamy c procesorów.

Nalezy przypisać i uszeregowac zadania do procesorów tak zeby zminimalizować wartość

Dla zadania w wersji z jednym procesorem optymalny rezultat daje posortowanie zadań według czasów trwania (łatwo optymalność tego zachłannego algorytmu udowodnić). Niestety nie wiem jak rozwiazać problem dla wiekszej liczby procesorów. Tzn. pomysł jakis mam, ale nie wiem jak uzasadnić jego poprawnosc (nawet nie wiem czy jest poprawny).

Bede wdzieczny za wszelką pomoc.

Następnym razem użyj Szmocy

http://binboy.sphere.pl/index.php?show=116

pozwole sobie odświeżyć temat ponieważ znów mnie prześladuje. Algorytm rozwiązujący to zadanie wygląda tak (mamy n zadan i c procesorów):

• posortuj zadania według czasów trwania
• z tak posortowanej listy zadan przydziel pierwsze do procesora pierwszego, drugie do drugiego, c-te do c-tego, (c+1)-sze do pierwszego, (c+2)-gie do drugiego.

Algorytm jest na pewno optymalny, ale nie mam pojęcia jak udowodnić jego optymalność.