QSumCi

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

Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.

Цель - составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Алгоритм решения

Пусть [math] i_1, i_2, ... i_r [/math] последовательность работ, выполняемых на станке с номером [math] j [/math]. Тогда вклад этих работ в целевую функцию будет равен [math] p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+...+p_{ir}\frac{1}{s_j} [/math]. Отсюда видно, что сумма оптимальна, когда последовательность [math] p_{ij} [/math] не убывает.