Szeregowanie zadań elastycznych

Przedstawiono tutaj problem szeregowania n niezależnych zadań w systemie procesorów równoległych. Zadania są elastyczne, tj. zadanie może być wykonywane przez kilka procesorów jednocześnie oraz prędkość wykonywania zadania jest nieliniową funkcją od ilości procesorów przydzielonych do niego. Całkowita liczba procesorów w systemie wynosi m i jest to górna granica liczby procesorów, które mogą być używane przez wszystkie zadania w tym samym czasie. Dodatkowym założeniem jest podzielność zadań oraz możliwość zmiany liczby procesorów przydzielonych do zadania w trakcie jego wykonywania. Celem jest znalezienie uszeregowania, dla którego czas zakończenia wszystkich zadań jest najkrótszy z możliwych. Prezentowany jest prosty algorytm o złożoności 0(n), rozwiązujący ten problem w przypadku, kiedy wszystkie funkcje prędkości wykonywania są wypukłe. Jeżeli funkcje te są wszystkie wklęsłe, przedstawiono algorytm pakowania prostokątów (PACK), który rozwiązuje ten problem w czasie wielomianowym.

---

The problem of optimal scheduling n independent tasks on a parallel processor system is studied. The tasks are malleable, i.e. a task may be executed by several processors simultaneously and the processing speed of a task is a non-linear function of the number of processors allotted to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the tasks are preemptable and the number of processors allotted to one task may change during its execution. The objective is to find a schedule for which the makespan, is minimized. An 0(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave the rectangles packing (PACK) algorithm is presented, which solves the problem in polynomial time.