1632
правки
Изменения
м
rollbackEdits.php mass rollback
В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или, например, дробными, данная задача может быть решена с помощью перебора.
Будем перебирать все перестановки чисел от <tex>1</tex> до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum \limits_{i=1}^n w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ.
Данное решение будет работать за <tex>\mathcal{O}(n \cdot n!)</tex>.
==Перебор с битовыми масками==
Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке.
Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.
Перебор всех масок может быть произведен за <tex>\mathcal{O}(2 ^ n)</tex>, и <tex>\mathcal{O}(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>\mathcal{O}(n \cdot 2^n)</tex>.
==Псевдополиномиальное решение==
* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в <tex>d[i] </tex> {{---}} дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения.
'''function''' <tex> \mathrm{getAnswer}(p : </tex> '''int''' <tex>\mathbf{[n]},</tex> <tex> w : </tex> '''int''' <tex>\mathbf{[n]},</tex> <tex> d : </tex> '''int''' <tex>\mathbf{[n] } ):</tex> '''int'''
'''int''' <tex>T = 0 </tex>
'''for''' <tex>i = 1 .. n</tex>
<tex>T = T + p[i]</tex>
'''int''' <tex>F[][]</tex>
сортируем работы по неубыванию времен дедлайнов <tex>d[i]</tex>;
'''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
'''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ <tex>L</tex>, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
'''function''' <tex> getSchedule\mathrm{getLate}(F : </tex> '''int''' <tex>\mathbf{[n][p_{max}]},</tex> <tex> p : </tex> '''int''' <tex>\mathbf{[n]},</tex> <tex> w : </tex> '''int''' <tex>\mathbf{[n]},</tex> <tex> d : </tex> '''int''' <tex>\mathbf{[n] } ):</tex> '''set<int>'''
'''int''' <tex>t = d[n]</tex>
'''set<int>''' <tex>L = \varnothing</tex>
<tex> t = t - p[j] </tex>
'''return''' <tex>L</tex>
Согласно лемме, само расписание будет состоять из работ, не попавших в <tex>L</tex>, отсортированных по неубыванию <tex>d_i</tex> и работ из <tex>L</tex>, записанных в конец в любом порядке.
===Время работы===
В функции <tex>\mathrm{getAnswer()}</tex> пересчет динамики происходит за <tex>\mathcal{O}(n \cdot T)</tex>, а функция <tex>\mathrm{getLate}</tex> восстанавливает список просроченых просроченных работ за <tex>\mathcal{O}(n)</tex>. Дальнейшее восстановление расписания происходит в худшем случае за <tex>\mathcal{O}(n \cdot \log n)</tex>. Отсюда видно, что время работы приведенного выше алгоритма {{---}} <tex>\mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.
==См. также ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
