PSumCi

[math]P \mid \mid \sum C_{i}[/math]

Задача:

Дано [math]n[/math] работ с заданными временами выполнения [math]p_{i}[/math]. И [math]m[/math] параллельных станков с одинаковой скоростью выполнения работ. Цель — составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Описание алгоритма

Идея

Пусть [math]p_{i}[/math] заданы в порядке невозрастания ([math]p_{1} \geqslant p_{2} \geqslant \ldots \geqslant p_{n} [/math]). Пусть теперь [math]b_{k} = \left\lceil\dfrac{k}{m}\right\rceil[/math]. Тогда в оптимальном расписании работа с номером [math]i[/math] будет выполнена на станке [math]i \bmod m[/math], [math]b_{i}[/math]-ой с конца.

Псевдокод

list<int> schedule[m]  //Заведём список работ для каждого станка. Ответ будет храниться в нём.
    for i = 0 to n
        schedule[i mod m].push(i) //ставим работу с номером i на станок i mod m в конец.

    //Заметим что расписание для каждого станка получилось перевёрнутым
    //Поэтому развернём расписание для каждого станка.
    for i = 0 to m
        schedule[i].reverse()

Ассимптотика

Так как нам понадобится сортировка для массива [math]p_{i}[/math], то итоговая ассимптотика будет [math]\mathcal{O}(n\log{n})[/math].