1sumu

Постановка задачи

Дан один станок и [math]n[/math] работ, для которых заданы их времена выполнения на этом станке [math]p_i[/math] и дедлайны [math]d_i[/math]. Нужно успеть выполнить как можно больше работ.

Алгоритм

Чтобы получить оптимальное расписание, будем строить максимальное множество [math]S[/math] тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из [math]S[/math], упорядоченных по неубыванию дедлайнов. Будем добавлять в [math]S[/math] работы в порядке неубывания значений [math]d_j[/math]. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из [math]S[/math] работу с самым большим временем выполнения.

   Отсортировать работы так, чтобы [math]d_1 \leqslant d_2 \leqslant \dots \leqslant d_n[/math];
   [math]S \leftarrow \varnothing[/math];
   [math]time \leftarrow 0[/math];
   [math]FOR[/math] [math]i := 1\dots n[/math] [math]DO[/math]
       [math]S \leftarrow S \cup \{ i \}[/math];
       [math]t[/math] += [math]p_i[/math];
       [math]IF[/math] [math]t \gt  d_i[/math]
           находим в [math]S[/math] работу [math]j[/math] с наибольшим [math]p_j[/math];
           [math]S = S \setminus\{j\}[/math];
           [math]t[/math] -= [math]p_j[/math];

Теорема:

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