317
правок
Изменения
Новая страница: «<tex dpi = "200">1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex> {{Задача |definition=Дана задача на нахождение расписания: # ...»
<tex dpi = "200">1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex>
{{Задача
|definition=Дана задача на нахождение расписания:
# У нас есть несколько работ, которе необходимо выполнит на одном станке.
# У работ есть время появления <tex>r_i</tex>
# Работы разрешается прерывать в любой момент времени.
# Все значения целочисленны, веса <tex>w_{i}</tex> положительны.
Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}
== Описание алгоритма ==
=== Идея ===
Назовем множество работ <tex>S</tex> '''выполнимым'''(англ. feasible), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией [[1precpmtnriLmax#edd|EDD правила]]:
:Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже [[1precpmtnriLmax#correctness|доказанной теоремы]]. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение EDD расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
==Источники информации==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 88-93 ISBN 978-3-540-69515-8
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
{{Задача
|definition=Дана задача на нахождение расписания:
# У нас есть несколько работ, которе необходимо выполнит на одном станке.
# У работ есть время появления <tex>r_i</tex>
# Работы разрешается прерывать в любой момент времени.
# Все значения целочисленны, веса <tex>w_{i}</tex> положительны.
Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}
== Описание алгоритма ==
=== Идея ===
Назовем множество работ <tex>S</tex> '''выполнимым'''(англ. feasible), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией [[1precpmtnriLmax#edd|EDD правила]]:
:Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже [[1precpmtnriLmax#correctness|доказанной теоремы]]. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение EDD расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
==Источники информации==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 88-93 ISBN 978-3-540-69515-8
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
