1ripmtnsumwu

[math]1 \mid r_i, pmtn \mid \sum w_{i}U_{i}[/math]

Задача:

Дана задача на нахождение расписания: У нас есть несколько работ, которе необходимо выполнит на одном станке. У работ есть время появления [math]r_i[/math] Работы разрешается прерывать в любой момент времени. Все значения целочисленны, веса [math]w_{i}[/math] положительны. Требуется выполнить все работы, чтобы значение [math]\sum w_i U_i[/math] (суммарный вес просроченных работ) было минимальным.

Описание алгоритма

Идея

Назовем множество работ [math]S[/math] выполнимым(англ. feasible), если существует такое расписание для работ из [math]S[/math], что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией EDD правила:

Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением [math]r_{i}[/math]. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.

[math]S[/math] выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже доказанной теоремы. Если в [math]S[/math] содержится [math]n[/math] работ, то построение EDD расписание может быть выполнено за [math]O(n \log n)[/math] времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.

Для данного непустого множества [math]S[/math] определим следующие величины

[math]r(S) = \min\limits_{i \in S} r_{i} ; p(S) = \sum\limits_{i \in S} p_{i}; w(S) = \sum\limits_{i \in S} w_{i}[/math]

Источники информации

• Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 88-93 ISBN 978-3-540-69515-8