Изменения

<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">Эта статья находится в разработке!</div><includeonly>[[Категория: В разработке]]1 \mid r_i, d_i, p_i=1 \mid -</includeonlytex>

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

===Упрощенная версия=== <tex>1 \mid d_i, p_i=1 \mid -</tex> Для начала решим более простую версию исходной задачи, когда все <tex>r_i=1</tex>. ====Описание алгоритма==== Будем выполнять работы в порядке возрастания их дедлайна <tex>d_i</tex>. Утверждается, что это оптимальное расписание.Приведем реализацию, на основе которой мы вскоре построим решение основной задачи: ====Псевдокод==== Пусть <tex>S</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[k] = \min\{d[i] \mid i \in S\}</tex> '''if''' <tex>d[k] \leqslant time</tex> <font color=green>// расписание составить невозможно</font> '''return''' ''false'' '''else''' <font color=green>// выполняем работу номер k</font> <tex>S = 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>1 \mid d_i, p_i=1 \mid - </tex>.|proof=Докажем от противного. Пусть в оптимальном расписании, где все работы укладываются в дедлайны, сначала идет работа <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} \leqslant d_j < d_i</tex>, а значит и <tex>i</tex>-я работа все еще укладывается в свой дедлайн, и наша замена ничего не испортила.}} ===Исходная задача=== <tex>1 \mid r_i, d_i, p_i=1 \mid -</tex> Теперь перейдем к решению основной задачи. ====Описание алгоритма==== Теперь не все задачи доступны изначально. Однако утверждается, что очередную задачу теперь достаточно выбирать с минимальным <tex>d_{i}</tex> из всех, которые уже доступны. Если эта работа уже просрочена, значит хорошее расписание построить нельзя. ====Псевдокод==== Пусть <tex>S</tex> — множество ещё не включенных в расписание работ, к выполнению которых уже можно преступитьприступить. Изначально <tex>S</tex> пустое.

Алгоритм <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\leftarrow1;= 1</tex> '''int '''<tex>time\leftarrow1;= 1</tex> <tex>FOR</tex> '''for''' <tex>i := 1</tex> '''to''' <tex>TOn </tex> '''if''' <tex>nS == \varnothing</tex> <tex>DOtime=r[j]</tex> '''while''' <tex>BEGINtime==r[j]</tex> <tex>IFS = S \cup \{j\}</tex> <tex>Sj =\varnothingj + 1</tex> <tex>THENd[k] = \min\{d[i]</tex> | <tex>BEGINi \in S\}</tex> '''if''' <tex>d[k] \leqslant time:=r_{j}</tex> <texfont color=green>END// расписание составить невозможно</texfont> '''return''' ''false'' '''else''' <texfont color=green>WHILE// выполняем работу номер k</texfont> <tex>timeS =r_S \setminus \{jk\}</tex> <tex>DOtime = time + 1</tex> <tex>BEGIN</tex> '''return''' ''true''  Добавить Сложность алгоритма <tex>j\mathcal{O}(n\log n)</tex> , если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>j:=j+1;d_i</tex> и его удаление за <tex>END\mathcal{O}(\log n)</tex>, например [[Двоичная_куча|двоичная куча]]. ====Доказательство корректности и оптимальности==== Пусть {{Теорема|statement=Приведенный алгоритм строит оптимальное расписание для задачи <tex>k1 \mid r_i, d_i, p_i=1 \in Smid -</tex> и .|proof=Пусть с помощью нашего алгоритма составить хорошее расписание не удалось. Докажем, что в этом случае хорошего расписания не существует.Заметим, что расписание состоит из непрерывных блоков, между которыми есть пропуски — все поступившие работы выполнены, а новых работ ещё не появилось. Расписание может состоять из одного блока. Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем в нём первую работу, для которой не нашлось места. Пусть её индекс будет равен <tex>d_{k}</tex> минимально . Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как <tex>IFr_i</tex> больше или равно времени начала блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то <tex>d_{k}\le timei</tex> -й, которая уже стоит в этом блоке расписания. У всех таких работ <tex>THENd_i \leqslant d_k</tex> Расписание составить невозможно , так как в алгоритме мы каждый раз брали работу с минимальным <tex>ELSEd_i</tex> . Но <tex>BEGINi</tex> Удалить -ю работу нельзя выполнить после <tex>k</tex> из -й. Значит <tex>Sk</tex>-ю работу выполнить нельзя. <tex>time:}} == См. также ==time+1;</tex> * [[1ripipsumwu|<tex>END1 \mid r_i, p_i = p \mid \sum w_i U_i</tex>]] * [[1ripi1sumf|<tex>END1 \mid r_i, p_i=1 \mid \sum f_i</tex>]]

Сложность алгоритма <tex>O==Источники информации==* P. Brucker. «Scheduling Algorithms» (n\log n2006)</tex> если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_{i}</tex> за <tex>O(\log n)</tex>5th edition.