Optymalne szeregowanie zadań dla wielu procesorów

Optymalne szeregowanie zadań dla wielu procesorów jest jednym z trudnych (NP-zupełnych) optymalizacyjnych zagadnień w informatyce. Jest jednocześnie jednym z problemów zaskakująco prostych w sformułowaniu i bardzo praktycznych.

Zadanie szeregowania zadań polega na przypisywaniu kolejnych procesów obliczeniowych do zasobów, z których one korzystają. W tym przypadku sytuacja jest następująca: mamy m procesorów oraz n zadań obliczeniowych. Każde zadanie i potrzebuje do wykonania na procesorze j pewnego niezerowego czasu: f(i,j). Optymalnym szeregowaniem nazywamy funkcję s przypisującą każdemu procesowi jeden z procesorów w ten sposób, że czas zakończenia ostatniego z nich jest możliwie najkrótszy.

Literatura

• Viggo Kann, Multiprocessor Scheduling