317
правок
Изменения
Нет описания правки
{{Задача
|definition=Дана задача на нахождение расписания:
# У нас есть несколько работ, которе необходимо выполнит выполнить на одном станке.# У работ есть время появления <tex>r_i</tex>.
# Работы разрешается прерывать в любой момент времени.
# Все значения целочисленны, веса <tex>w_{i}</tex> положительны.
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>. За <tex>W = \sum\limits_{j = 1}^{n} {w_j}</tex>
Назовем множество работ <tex>S</tex> '''выполнимым''' (англ. ''feasible''), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией EDD правила (<ref>см. стр 70 в Брукере</ref> (EDD {{---}} правило наименьшего срока (англ. ''earliest due date''):
:Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.
*[[1precpmtnrifmax|<tex>1 \mid prec,pmtn,r_i \mid f_{max}</tex>]]
*[[1sumwu| <tex>1 \mid\mid \sum w_i U_i</tex>]]
==Примечания==
<references />
==Источники информации==
