748
правок
Изменения
м
→Алгоритм
Идея алгоритма состоит в том, что на шаге <tex>k</tex> строим оптимальное решение для первых <tex>k</tex> работ с наименьшими дедлайнами.
Пусть работы отсортированы в порядке возрастания дедлайнов. Пусть мы уже рассмотрели первые <tex>k</tex> работ, тогда множество <tex>S_k</tex> содержит только те работы, которые мы успеваем выполнить в порядке возрастания не убывания дедлайнов при оптимальном расписании. Рассмотрим работу <tex>k+1</tex>. Если мы ее успеваем выполнить данную работу, до наступления дедлайна, то добавим в множество <tex>S_{k}</tex> и получим множество <tex>S_{k+1}</tex>. Если же <tex>k+1</tex> работу мы не успеваем выполнить до дедлайна, то найдем в <tex>S_k</tex> работу <tex>l</tex> c наименьшим весом <tex>w_{l}</tex> и заменим ее на работу <tex>k+1</tex>.
Таким образом, рассмотрев все работы, мы получим <tex>S_{n}</tex> — множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.
