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 W OKRESIE WAKACYJNYM BIBLIOTEKA BĘDZIE FUNKCJONOWAŁA W ZMIENIONYCH GODZINACH::
od 15 do 31 lipca:
Wypożyczalnia i Czytelnia Główna:
9.00 - 15.00
(poniedziałek-piątek)
Czytelnia Działu Zbiorów Specjalnych:
9.00 - 15.00
(poniedziałek-piątek)
od 1 do 31 sierpnia:
BIBLIOTEKA BĘDZIE NIECZYNNA
UWAGA:
Zwrotu wypożyczonych materiałów można dokonać u dyżurującego bibliotekarza w Wypożyczalni Głównej od 9.00 do 15.00.
Na pozycje, których termin zwrotu przypadnie od 1 do 31 sierpnia, wprowadzona zostanie prolongata (nowy termin zwrotu – 6 września).