1632
правки
Изменения
м
schedulejobs[i] = <tex>\langle</tex>p[i mod m], i<tex>\rangle</tex> <font color=green>// Создаём пары для востановления номера работы после сортировки.push</font> sort(jobs[i]) <font color=green>// Cтавим i-ую Cортируем массив в порядке уменьшения p[i] работу на станок i mod m в конец.</font><br> '''list'''<'''int'''> schedule[m] <font color=green>// Заметим что расписание Заведём список работ для каждого станка получилось перевёрнутым.<br> // Поэтому развернём расписание для каждого станкаОтвет будет храниться в нём.</font> '''for''' i = 0 '''to''' mn schedule[imod m].reversepushFront(jobs[i].second)<font color=green>// Cтавим i-ую в порядке уменьшения p[i] работу на станок i mod m в конец.</font><br>
rollbackEdits.php mass rollback
=== Псевдокод ===
Итоговым расписанием будет массив <tex>\mathtt{schedule}</tex> где в <tex>\mathtt{schedule[i][j]}</tex> храниться номер работы которую надо исполнить на станке номер <tex>i</tex>, <tex>j</tex>-ой по счёту.
'''function''' getSchedule(jobs p : '''int'''[n]): '''list'''<font color=green'''int'''>// jobs - массив номеров работ отсортированных в порядке невозрастания p[im].</font> list'''Pair'''<'''int''','''int'''> schedulejobs[mn] <font color=green> // Заведём список работ для каждого станка. Ответ будет храниться в нём.</font><br>
'''for''' i = 0 '''to''' n
'''return''' schedule
|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
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
