403
правки
Изменения
→Алгоритм
== Алгоритм ==
Идея алгоритма состоит в том, чтобы на шаге <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> с наименьшим весом <tex> w_{l} </tex> и заменим ее на работу <tex> k + 1 </tex>.
Таким образом, рассмотрев все работы, мы получим <tex> S_{n} </tex> {{---}} множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.
== Псевдокод ==
== Доказательство корректности ==
