Изменения

<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]): <tex>S = \{1, 2, \ldots, n\}</tex> <tex>time = 1;</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>: <tex>d_{k} d_k = min\{d_{i}</tex> | <tex>d_i \mid i \in S\}</tex> '''if''' <tex>d_{k} d_k \le leqslant time</tex>: Расписание составить невозможно '''else''': //выполняем работу номер <tex>k</tex> <tex>S \leftarrow S \setminus \{k\}</tex> <tex>time = time + 1;</tex>

Сложность алгоритма <tex>\mathcal{O}(n\log n)</tex>, если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_{i}d_i</tex> и его удаление за <tex>\mathcal{O}(\log n)</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> однако, раз <tex>j</tex>-я работа раньше укладывалась в дедлайн, то <tex>C_{i} = C_{j}^{old} \le d_{j} < d_{i}</tex>, а значит и <tex>i</tex>-я работа все еще укладывается в свой дедлайн, и наша замена ничего не испортила.==Исходная задача===

===<tex>1 | \mid r_i, d_i, p_i=1 | \mid -===</tex>

Теперь перейдем к решению основной задаче — <tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>задачи.

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

Сложность алгоритма <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

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