317
правок
Изменения
→Идея
:''Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.''
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в <tex>\mathrm{EDD}</tex> расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 70 ISBN 978-3-540-69515-8</ref>. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение <tex>\mathrm{EDD}</tex> расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
Для данного непустого множества <tex>S</tex> определим следующие величины:
