Викиконспекты - Вклад участника [ru]

1ridipi1

2016-06-04T17:25:06Z

92.100.16.200: /* Литература */

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

==Алгоритм==
Идея алгоритма в том, чтобы из тех работ, которые уже можно выполнить, ставить в расписание ту, у которой наименьшее <tex>d_{i}</tex>. Если эта работа уже просрочена, значит хорошее расписание построить нельзя.

Пусть <tex>S</tex> - множество ещё не включенных в расписание работ, к выполнению которых уже можно приступить. Изначально <tex>S</tex> пустое.
Отсортируем работы по порядку их появления.

Алгоритм <tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>
<tex>S:=\varnothing;</tex>
<tex>j\leftarrow1;</tex>
<tex>time\leftarrow1;</tex>
<tex>FOR</tex> <tex>i := 1</tex> <tex>TO</tex> <tex>n</tex> <tex>DO</tex>
<tex>BEGIN</tex>
<tex>IF</tex> <tex>S=\varnothing</tex> <tex>THEN</tex>
<tex>BEGIN</tex> <tex>time:=r_{j}</tex> <tex>END</tex>
<tex>WHILE</tex> <tex>time=r_{j}</tex> <tex>DO</tex>
<tex>BEGIN</tex>
Добавить <tex>j</tex> в <tex>S</tex>
<tex>j:=j+1;</tex>
<tex>END</tex>
Пусть <tex>k\in S</tex> и <tex>d_{k}</tex> минимально
<tex>IF</tex> <tex>d_{k}\le time</tex> <tex>THEN</tex>
Расписание составить невозможно
<tex>ELSE</tex>
<tex>BEGIN</tex>
Удалить <tex>k</tex> из <tex>S</tex>
<tex>time:=time+1;</tex>
<tex>END</tex>
<tex>END</tex>

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

==Доказательство корректности алгоритма==
Пусть с помощью нашего алгоритма составить хорошее расписание не удалось. Докажем, что в этом случае хорошего расписания не существует.
Заметим, что расписание состоит из непрерывных блоков, между которыми есть пропуски - все поступившие работы выполнены, а новых работ ещё не появилось. Расписание может состоять из одного блока.

Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем в нём первую работу, для которой не нашлось места. Пусть её индекс будет <tex>k</tex>. Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как <tex>r_{i}</tex> больше или равно времени начала блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то <tex>i</tex>-ой, которая уже стоит в этом блоке расписания. У всех таких работ <tex>d_{i}</tex> меньше или равно <tex>d_{k}</tex>, так как в алгоритме мы каждый раз брали работу с минимальным <tex>d_{i}</tex>. Но <tex>i</tex>-ую работу нельзя выполнить после <tex>k</tex>-ой. Значит <tex>k</tex>-ую работу выполнить нельзя.

==Источники информации==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 200

1ridipi1

2016-06-04T17:23:48Z

92.100.16.200: /* Постановка задачи */

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

==Алгоритм==
Идея алгоритма в том, чтобы из тех работ, которые уже можно выполнить, ставить в расписание ту, у которой наименьшее <tex>d_{i}</tex>. Если эта работа уже просрочена, значит хорошее расписание построить нельзя.

Пусть <tex>S</tex> - множество ещё не включенных в расписание работ, к выполнению которых уже можно приступить. Изначально <tex>S</tex> пустое.
Отсортируем работы по порядку их появления.

Алгоритм <tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>
<tex>S:=\varnothing;</tex>
<tex>j\leftarrow1;</tex>
<tex>time\leftarrow1;</tex>
<tex>FOR</tex> <tex>i := 1</tex> <tex>TO</tex> <tex>n</tex> <tex>DO</tex>
<tex>BEGIN</tex>
<tex>IF</tex> <tex>S=\varnothing</tex> <tex>THEN</tex>
<tex>BEGIN</tex> <tex>time:=r_{j}</tex> <tex>END</tex>
<tex>WHILE</tex> <tex>time=r_{j}</tex> <tex>DO</tex>
<tex>BEGIN</tex>
Добавить <tex>j</tex> в <tex>S</tex>
<tex>j:=j+1;</tex>
<tex>END</tex>
Пусть <tex>k\in S</tex> и <tex>d_{k}</tex> минимально
<tex>IF</tex> <tex>d_{k}\le time</tex> <tex>THEN</tex>
Расписание составить невозможно
<tex>ELSE</tex>
<tex>BEGIN</tex>
Удалить <tex>k</tex> из <tex>S</tex>
<tex>time:=time+1;</tex>
<tex>END</tex>
<tex>END</tex>

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

==Доказательство корректности алгоритма==
Пусть с помощью нашего алгоритма составить хорошее расписание не удалось. Докажем, что в этом случае хорошего расписания не существует.
Заметим, что расписание состоит из непрерывных блоков, между которыми есть пропуски - все поступившие работы выполнены, а новых работ ещё не появилось. Расписание может состоять из одного блока.

Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем в нём первую работу, для которой не нашлось места. Пусть её индекс будет <tex>k</tex>. Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как <tex>r_{i}</tex> больше или равно времени начала блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то <tex>i</tex>-ой, которая уже стоит в этом блоке расписания. У всех таких работ <tex>d_{i}</tex> меньше или равно <tex>d_{k}</tex>, так как в алгоритме мы каждый раз брали работу с минимальным <tex>d_{i}</tex>. Но <tex>i</tex>-ую работу нельзя выполнить после <tex>k</tex>-ой. Значит <tex>k</tex>-ую работу выполнить нельзя.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8