Минимальное время завершения для взвешенной системы

Ключевые слова и синонимы

Среднее время завершения для взвешенной системы задач

Постановка задачи

При нахождении минимального времени завершения для взвешенной системы задач мы рассматриваем (1) набор J из n задач, каждой из которых присвоены положительный вес (wj для j 2 J) и дата запуска, ранее которой эта задача не может быть спланирована; (2) набор из m вычислительных машин, каждая из которых может обрабатывать не более одной работы в одно и то же время; (3) произвольный набор положительных значений fpi;jg, где рц обозначает время обработки работы j на машине i. План представляет собой назначение работ машинам и выбор порядка их обработки. Обозначим за Cj время завершения работы j в рамках выполнения конкретного плана. Определим время завершения для взвешенной системы как Pj2J wjCj. Задача заключается в вычислении плана, имеющего минимальное время завершения.