9
правок
Изменения
Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
==Постановка задачи==
Дан один станок на котором нужно выполнить <tex>n</tex> работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять - <tex>r_{i}</tex> и когда необходимо закончить её выполнение - <tex>d_{i}</tex>. Время выполнения <tex>p_{i}</tex> у всех работ одинаково и равно одному. Необходимо узнать, можно ли построить расписание для этого станка.
==Алгоритм==
Идея алгоритма в том, чтобы из тех работ, которые уже можно выполнить, ставить в расписание ту у которой наименьшее <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>.
==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
<includeonly>[[Категория: В разработке]]</includeonly>
==Постановка задачи==
Дан один станок на котором нужно выполнить <tex>n</tex> работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять - <tex>r_{i}</tex> и когда необходимо закончить её выполнение - <tex>d_{i}</tex>. Время выполнения <tex>p_{i}</tex> у всех работ одинаково и равно одному. Необходимо узнать, можно ли построить расписание для этого станка.
==Алгоритм==
Идея алгоритма в том, чтобы из тех работ, которые уже можно выполнить, ставить в расписание ту у которой наименьшее <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>.
==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
