Изменения

<tex dpi ="200" >1 \mid r_i, d_i, p_i=Постановка задачи=1 \mid -</tex> {{Шаблон:Задача|definition =Дан один станок на котором нужно выполнить <tex>n</tex> работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять — <tex>r_{i}r_i</tex> и когда необходимо закончить её выполнение — <tex>d_{i}d_i</tex>. Время выполнения <tex>p_{i}p_i</tex> у всех работ одинаково и равно 1. Необходимо узнать, можно ли построить расписание, при котором все работы будут выполнены.}}

===1 | d_i, p_i=1 | -Упрощенная версия===

Для начала решим задачу, если все <tex>r_{i}=1</tex>, то есть <tex>1 | d_{i}\mid d_i, p_{i}p_i=1 | \mid -</tex>.

Для начала решим более простую версию исходной задачи, когда все <tex>r_i=1</tex>. ====Описание алгоритма==== Будем выполнять работы в порядке возрастания их дедлайна <tex>d_{i}d_i</tex>. Утверждается, что это оптимальное расписание.

'''function''' solve(d: '''int'''[n]): '''boolean''' <tex>S = \{1, 2, \ldots, n\}</tex> '''int '''<tex>time = 1;</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>: <tex>d_{d[k} ] = \min\{d_{d[i}</tex> | <tex>] \mid i \in S\}</tex> '''if''' <tex>d_{d[k} ] \le leqslant time</tex>: Расписание <font color=green>// расписание составить невозможно</font> '''return''' ''false'' '''else''': <font color=green>//выполняем работу номер <tex>k</texfont> <tex>S \leftarrow = S \setminus \{k\}</tex> <tex>time = time + 1;</tex> '''return''' ''true''  Сложность алгоритма <tex>\mathcal{O}(n\log n)</tex>, если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_i</tex> и его удаление за <tex>\mathcal{O}(\log n)</tex>, например [[Двоичная_куча|двоичная куча]]. ====Доказательство корректности и оптимальности====

Сложность алгоритма {{Теорема|statement=Приведенный алгоритм строит оптимальное расписание для задачи <tex>O(n1 \mid d_i, p_i=1 \log n)mid -</tex>.|proof=Докажем от противного. Пусть в оптимальном расписании, где все работы укладываются в дедлайны, сначала идет работа <tex>i</tex>, а потом <tex>j</tex>, причем <tex>d_i > d_j</tex>. Посмотрим, что произойдет, если в качестве расписании поменять их местами. Так как они обе выполняются за единицу времени, для всех задач, кроме <tex>Si</tex> использовать структуру-й и <tex>j</tex>-й время их завершения <tex>C_i</tex> не поменялось. Для <tex>j</tex>-й же работы <tex>C_j</tex> стало меньше, которая позволяет поиск элемента с минимальным что только лучше. <tex>d_C_i</tex> увеличилось и стало равно старому <tex>C_j</tex> однако, раз <tex>j</tex>-я работа раньше укладывалась в дедлайн, то <tex>C_i = C_j^{iold}\leqslant d_j < d_i</tex> за , а значит и <tex>O(\log n)i</tex>-я работа все еще укладывается в свой дедлайн, и наша замена ничего не испортила.}}

Докажем от противного. Пусть в оптимальном расписании, где все работы укладываются в дедлайны, сначала идет работа <tex>i</tex>, а потом <tex>j</tex>, причем <tex>d_{i} > d_{j}</tex>. Посмотрим, что произойдет, если в расписании поменять их местами. Так как они обе выполняются за единицу времени, для всех задач, кроме <tex>i</tex>-й и <tex>j</tex>-й время их завершения <tex>C_{i}</tex> не поменялось. Для <tex>j</tex>-й же работы <tex>C_{j}</tex> стало меньше, что только лучше. <tex>C_{i}</tex> увеличилось и стало равно старому <tex>C_{j}</tex> однако1 \mid r_i, раз <tex>j</tex>-я работа раньше укладывалась в дедлайнd_i, то <tex>C_{i} p_i= C_{j}^{old} 1 \le d_{j} < d_{i}mid -</tex>, а значит и <tex>i</tex>-я работа все еще укладывается в свой дедлайн, и наша замена ничего не испортила.

Теперь перейдем к решению основной задачи. ===1 | r_i, d_i, p_i=1 | -Описание алгоритма====

Алгоритм <tex>1 | r_{i} '''function''' solve(r: '''int'''[n], d_{i}, p_{i}=1 | -</tex>d: '''int'''[n]):'''boolean''' <tex>S = \varnothing;</tex> '''int '''<tex>j = 1;</tex> '''int '''<tex>time = 1;</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>: '''if''' <tex>S == \varnothing</tex>: <tex>time=r_{r[j}]</tex> '''while''' <tex>time==r_{r[j}]</tex>: <tex>S \leftarrow = S \cup \{j\}</tex> <tex>j = j + 1;</tex> <tex>d_{d[k} ] = \min\{d_{d[i}]</tex> | <tex>i \in S\}</tex> '''if''' <tex>d_{d[k} ] \le leqslant time</tex>: Расписание <font color=green>// расписание составить невозможно</font> '''return''' ''false'' '''else''': <font color=green>//выполняем работу номер <tex>k</texfont> <tex>S \leftarrow = S \setminus \{k\}</tex> <tex>time = time + 1;</tex> '''return''' ''true''

Сложность алгоритма <tex>\mathcal{O}(n\log n)</tex>, если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_{i}d_i</tex> и его удаление за <tex>\mathcal{O}(\log n)</tex>, например [[Двоичная_куча|двоичная куча]].

====Доказательство корректности алгоритмаи оптимальности==== {{Теорема|statement=Приведенный алгоритм строит оптимальное расписание для задачи <tex>1 \mid r_i, d_i, p_i=1 \mid -</tex>.|proof=

Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем в нём первую работу, для которой не нашлось места. Пусть её индекс будет равен <tex>k</tex>. Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как <tex>r_{i}r_i</tex> больше или равно времени начала блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то <tex>i</tex>-й, которая уже стоит в этом блоке расписания. У всех таких работ <tex>d_{i} d_i \le d_{k}leqslant d_k</tex>, так как в алгоритме мы каждый раз брали работу с минимальным <tex>d_{i}d_i</tex>. Но <tex>i</tex>-ю работу нельзя выполнить после <tex>k</tex>-й. Значит <tex>k</tex>-ю работу выполнить нельзя.}} == См. также ==* [[1ripipsumwu|<tex>1 \mid r_i, p_i = p \mid \sum w_i U_i</tex>]]* [[1ripi1sumf|<tex>1 \mid r_i, p_i=1 \mid \sum f_i</tex>]]

* P. Brucker. Scheduling Algorithms «Scheduling Algorithms» (2006), 5th edition, стр. 200

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]