Имеется n задач и M процессоров. Каждая задача характеризуется временем ее выполнения.
Необходимо распределить задачи между процессорами, чтобы максимально загруженный процессор был загружен
как можно минимально.
Если кто подскажет логику данного приближенного алгоритма и точную оценку — буду признателен.
Здравствуйте, 3DBYTE, Вы писали:
DBY>Имеется n задач и M процессоров. Каждая задача характеризуется временем ее выполнения. DBY>Необходимо распределить задачи между процессорами, чтобы максимально загруженный процессор был загружен DBY>как можно минимально.
DBY>Если кто подскажет логику данного приближенного алгоритма и точную оценку — буду признателен.
По постановке задача похожа на задачу линейного программирования.
Здравствуйте, 3DBYTE, Вы писали:
DBY>Имеется n задач и M процессоров. Каждая задача характеризуется временем ее выполнения. DBY>Необходимо распределить задачи между процессорами, чтобы максимально загруженный процессор был загружен DBY>как можно минимально.
DBY>Если кто подскажет логику данного приближенного алгоритма и точную оценку — буду признателен.
Эта задача решается только перебором или эвристиками, насколько я понимаю.
Можно попробовать использовать жадный алгоритм типа: распределяем самые сложные задачи по всем процессорам, затем более простые и т.п. Каждая новая задача распределяется на процессор с минимальной загрузкой.
Здравствуйте, FDSC, Вы писали:
FDS>Эта задача решается только перебором или эвристиками, насколько я понимаю. FDS>Можно попробовать использовать жадный алгоритм типа: распределяем самые сложные задачи по всем процессорам, затем более простые и т.п. Каждая новая задача распределяется на процессор с минимальной загрузкой.
Это пойдёт только если все задачи не связаны между собой. А если связаны, тогда кранты.
Поль вдруг вскочил и с необыкновенной живостью изобразил ракопаука. Отвратительный скрежещущий вой многоногого чудовища, пробирающегося через джунгли страшной Пандоры, огласил окрестности. И, словно в ответ, издалека донёсся глубокий ревущий вздох.
