81
правка
Изменения
→Алгоритм
== Алгоритм ==
Работу будем обозначать просто ее номером <tex>(i)</tex>, при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r[i]</tex>, время, требуемое для ее выполнения — <tex> p[i] </tex>. Множество ребер графа обозначается как <tex> E </tex>.
===Идея алгоритма===
Будем решать задачу рекурсивно. Разобьем множество работ на блоки, внутри которых работы могут выполняться непрерывно. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на блоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Будем это делать для каждого из получившихся подблоков рекурсивно, пока они не опустеют. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание.
=== Препроцессинг ===
