Изменения
Новая страница: «==Постановка задачи== Дан один станок и <tex>n</tex> работ, для которых заданы их времена выполн...»
==Постановка задачи==
Дан один станок и <tex>n</tex> работ, для которых заданы их времена выполнения на этом станке <tex>p_i</tex> и дедлайны <tex>d_i</tex>. Нужно успеть выполнить как можно больше работ.
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из <tex>S</tex> работу с самым большим временем выполнения.
Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>;
<tex>S \leftarrow \varnothing</tex>;
<tex>time \leftarrow 0</tex>;
<tex>FOR</tex> <tex>i := 1\dots n</tex> <tex>DO</tex>
<tex>S \leftarrow S \cup \{ i \}</tex>;
<tex>t</tex> <code>+=</code> <tex>p_i</tex>;
<tex>IF</tex> <tex>t > d_i</tex>
находим в <tex>S</tex> работу <tex>j</tex> с наибольшим <tex>p_j</tex>;
<tex>S = S \setminus\{j\}</tex>;
<tex>t</tex> <code>-=</code> <tex>p_j</tex>;
{{Теорема
|statement=
Этот алгоритм строит оптимальное расписание
|proof=
}}
Дан один станок и <tex>n</tex> работ, для которых заданы их времена выполнения на этом станке <tex>p_i</tex> и дедлайны <tex>d_i</tex>. Нужно успеть выполнить как можно больше работ.
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из <tex>S</tex> работу с самым большим временем выполнения.
Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>;
<tex>S \leftarrow \varnothing</tex>;
<tex>time \leftarrow 0</tex>;
<tex>FOR</tex> <tex>i := 1\dots n</tex> <tex>DO</tex>
<tex>S \leftarrow S \cup \{ i \}</tex>;
<tex>t</tex> <code>+=</code> <tex>p_i</tex>;
<tex>IF</tex> <tex>t > d_i</tex>
находим в <tex>S</tex> работу <tex>j</tex> с наибольшим <tex>p_j</tex>;
<tex>S = S \setminus\{j\}</tex>;
<tex>t</tex> <code>-=</code> <tex>p_j</tex>;
{{Теорема
|statement=
Этот алгоритм строит оптимальное расписание
|proof=
}}
