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

Задача нахождения минимального времени завершения для взвешенной системы представляет собой (1) набор J из n заданий, каждому из которых присвоены положительный вес (<math>w_j \;</math> для <math>j \in J \;</math>) и дата запуска <math>r_j \;</math>, ранее которой это задание не может быть спланировано; (2) набор из m вычислительных машин, каждая из которых может обрабатывать не более одного задания в одно и то же время; (3) произвольный набор положительных значений <math>\{ p_{i, j} \} \;</math>, где <math>p_{i, j} \;</math> обозначает время обработки задания j на машине i. План представляет собой назначение заданий машинам и выбор порядка их обработки. Обозначим за <math>C_j \;</math> время завершения задания j в рамках выполнения конкретного плана. Определим время завершения для взвешенной системы как <math>\sum_{j \in J} w_j C_j \;</math>. Задача заключается в вычислении плана, имеющего минимальное время завершения.