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>
<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>
