Изменения

Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.

Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Далее покажем что Так как нужно рассмотреть <tex>n</tex> временных промежутков будут рассмотрены. Таким образом, задача может быть решена за <tex>O(n^3)</tex>. Так как функция Функция <tex>f_i</tex> монотонно неубывающая, то тогда работы в расписании будем надо располагать как можно раньшедля получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что рабочие места работы нумеруются так: