Изменения

|definition = Дано <tex>n</tex> работ с заданными временами выполнения <tex>p_{i}</tex>. И и <tex>m</tex> параллельных станков с одинаковой скоростью выполнения работ.<br>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

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

'''function''' getSchedule(p : '''int'''[n]): '''list'''<'''int'''>[m] '''Pair'''<'''int''','''int'''> jobs[n] '''for''' i = 0 '''to''' n jobs[i] = <tex>\langle</tex>p[i], i<tex>\rangle</tex> <font color=green>// Создаём пары для востановления номера работы после сортировки.</font> sort(jobs) <font color=green>// Cортируем массив в порядке уменьшения p[i].</font><br> '''list'''<'''int'''> schedule[m] <font color=green> //Заведём список работ для каждого станка. Ответ будет храниться в нём.</font> '''for''' i = 0 '''to''' n schedule[i mod m].pushpushFront(jobs[i].second) <font color=green>//ставим Cтавим i-ую в порядке уменьшения p[i] работу с номером i на станок i mod m в конец.</font><br> <font color=green>//Заметим что расписание для каждого станка получилось перевёрнутым<br> //Поэтому развернём расписание для каждого станка.</font> '''for''' i = 0 ''return'to''' m schedule[i].reverse()

Так как нам понадобится [[Быстрая сортировка | сортировка]] для массива <tex>p_{i}</tex>, то итоговая ассимптотика будет <tex>\mathcal{O}(n\log{n})</tex>. == Доказательство корректности ==Докажем две леммы:{{Лемма|id=lemma1|statement= В оптимальном расписании на каждом станке работы выполняются в порядке неубывания времён выполнения.|proof= Пусть это не так. Заметим что <tex>\sum\limits_{i=0}^{n-1} C_{i} = \sum\limits_{i=0}^{n-1} p_{i} \cdot b_{i}</tex>. Следовательно каждая работа даёт вклад равный <tex>p_{i} \cdot b_{i}</tex>. Тогда поменяем местами две работы которые нарушают порядок невозрастания. Заметим что <tex>\sum\limits_{i=0}^{n-1} C_{i}</tex> уменьшилась. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие.}} {{Лемма|id=lemma2|statement= В оптимальном расписании количество выполненных работ на любых двух станках отличается не более чем на <tex>1</tex>.|proof= Пусть это не так. Как было отмечено в предыдущей лемме, каждая работа даёт вклад в <tex>\sum\limits_{i=0}^{n-1} C_{i}</tex> равный <tex>p_{i} \cdot b_{i}</tex>. Найдём два станка количество работ на которых отличается больше чем на <tex>1</tex>. Пусть это станки <tex>x</tex> и <tex>y</tex>. Причём на стнаке <tex>x</tex> выполняется больше работ. Тогда если отправить первую с начала работу со станка <tex>x</tex> на станок <tex>y</tex> то <tex>\sum\limits_{i=0}^{n-1} C_{i}</tex> уменьшится на разность количества работ на станках <tex>x</tex> и <tex>y</tex>. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие.}} {{Теорема|id=theorem1|statement= Алгоритм <tex>P \mid \mid \sum C_{i}</tex> строит оптимальное расписание.|proof= Пусть это не так и оптимальное расписание отличается от расписания построенного алгоритмом. Заметим что расписание построенное алгоритмом удовлетворяет обеим леммам. Тогда можно воспользоваться одной из них чтобы улучшить оптимальное раписание. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие. }} == См. также ==* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]== Источники информации ==* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 22 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]