14
правок
Изменения
Новая страница: «{{Шаблон:Задача |definition = Дан один станок и <tex>n</tex> работ, для которых заданы их дедлайны <tex>...»
{{Шаблон:Задача
|definition =
Дан один станок и <tex>n</tex> работ, для которых заданы их дедлайны <tex>d_i</tex>, а все времена выполнения на этом станке <tex>p_i = 1</tex>. Нужно успеть выполнить как можно больше работ.
}}
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>, если успеваем их выполнить.
Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>
<tex>S = \varnothing</tex>
<tex>time = 0</tex>
'''for''' i = 1 '''to''' n '''do'''
'''if''' <tex>time < d_i</tex>
<tex>S = S \cup \{ i \}</tex>
<tex>time</tex> <code>+=</code> <tex>1</tex>
Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]].
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[Классификация задач]]
* [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
|definition =
Дан один станок и <tex>n</tex> работ, для которых заданы их дедлайны <tex>d_i</tex>, а все времена выполнения на этом станке <tex>p_i = 1</tex>. Нужно успеть выполнить как можно больше работ.
}}
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>, если успеваем их выполнить.
Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>
<tex>S = \varnothing</tex>
<tex>time = 0</tex>
'''for''' i = 1 '''to''' n '''do'''
'''if''' <tex>time < d_i</tex>
<tex>S = S \cup \{ i \}</tex>
<tex>time</tex> <code>+=</code> <tex>1</tex>
Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]].
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8
== См. также ==
* [[Классификация задач]]
* [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
