The problem of scheduling n tasks in a multiprocessor system with m processors to minimize the makespan is studied. Tasks are malleable, which means that a task can be executed by several processors at a time, its processing speed depends on the number of allocated processors, and a set of processors allocated to the same task can change over time. The processing speed of a task is a strictly increasing function of the number of processors allocated to this task. The earlier studies considered the case n ≤ m. This paper presents results for arbitrary n and m including characterizations of a feasible domain and an optimal solution, polynomial time algorithms for strictly increasing convex and concave processing speed functions, and a combinatorial exponential algorithm for arbitrary strictly increasing functions.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00