Изменения
Нет описания правки
<div styletex dpi ="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;200">Эта статья находится в разработке!1 \mid p_{i}=1 \mid \sum\nolimits w_iU_i</divtex><includeonly>[[Категория: В разработке]]</includeonly>А нельзя ли обозвать как-то по-другому?
{{Задача|definition == Постановка задачи ==1) Дано <tex> n </tex> работ и <tex> 1 </tex> станок. 2) Для каждой работы известны её дедлайн <tex> d_{i} </tex> и вес <tex> w_{i} </tex>. Время выполнения всех работ <tex> p_i </tex> равно <tex> 1 </tex>. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.}}
== Алгоритм ==
Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex> 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n} </tex>. Все работы, дедлайн которых равен <tex> 0 </tex>, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.
В псевдокоде используются переменные:*<tex> S s </tex> {{---}} множество непросроченных работ, *<tex> t </tex> {{---}} текущее время. '''Set'''<'''int'''> p1sumwu('''int''' <tex>w[n]</tex>, '''int''' <tex>d[n]</tex>): '''int''' <tex> t = 1; </tex> '''Set'''<'''int'''> <tex> S s</tex> = <tex>\{\varnothing; }</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex> <tex> S s = S s \cup \{i\} ;</tex> '''if''' <tex> d_{i} \geqslant t </tex> <tex> t = t + 1; </tex> '''else''' найти такое <tex> k </tex>, что <tex> w_{k} = \min \{ w_{j} \mid j \in Ss\}; </tex> <tex> S s = S s \setminus \{k\}; </tex> '''return''' <tex>s</tex>
== Доказательство корректности ==
{{Утверждение|statement=Алгоритм строит корректное расписание.|proof=Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, и следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.}} {{Утверждение|statement=Построенное данным алгоритмом расписание оптимально.|proof=Пусть <tex> S^* </tex> множество непросроченных работ в оптимальном расписании. Также пусть <tex> l </tex> {{---}} первая работа из множества <tex> S </tex>, которая не входит в <tex> S^* </tex>, а <tex> k </tex> {{---}} первая работа из <tex> S^* </tex>, не содержащаяся в <tex> S </tex>. Мы можем предполагать существование этих работ, потому что <tex> S^* </tex> не может содержать <tex> S </tex> как подмножество, иначе это противоречило бы построению <tex> S </tex>. С другой стороны, если <tex> S^* \subseteq S </tex>, то <tex> S </tex> должно быть тоже оптимальным, и правильность алгоритма доказана. Для доказательства покажем, что мы можем заменить работу <tex> k </tex> на работу <tex> l </tex> в оптимальном расписании, не увеличивая минимизируемую функцию. Рассмотрим два случая: *<tex> l < k </tex> :Так как работа <tex> k </tex> не содержится в <tex> S </tex>, то либо она не была добавлена при ее рассмотрении, либо была заменена работой, рассмотренной позднее. В любом случае это означает, что <tex> w_{k} \leqslant w_{l} </tex>. Так же по определению <tex> k </tex> все работы <tex> i \in S^* : i < k </tex> должны содержаться и в <tex> S </tex>. Но тогда заменив в оптимальном расписании <tex> k </tex> на <tex> l </tex>, мы сохраним корректность расписания и не увеличим минимизируемую функцию. *<tex> k < l </tex>
:Так как мы рассматриваем работы в порядке неубывания их дедлайнов, то, следовательно, <tex> d_{k} \leqslant d_{l} </tex>, и замена работы <tex> k </tex> на <tex> l </tex> в оптимальном расписании <tex> S^* </tex> не может сделать его некорректным. Тогда для доказательства нам осталось показать, что <tex> w_{k} \leqslant w_{l} </tex>.
== Время работы ==
Время работы алгоритма зависит от того, насколько быстро мы будем добавлять и удалять работы из множества <tex> S </tex>, а также как быстро мы будем искать работу с минимальным весом. Если в качестве множества <tex> S </tex> использовать структуру данных, умеющую выполнять данные операции за <tex> O(\log n) </tex>, то время работы всего алгоритма будет составлять <tex> O(n\log n) </tex>. Например, такими структурами данных являются [[Двоичная куча | двоичная куча]] и [[Красно-черное дерево | красно-черное дерево]].
== Литература Cм. также ==* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_iU_i</tex>]] == Источники информации ==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 96 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]