1p1sumu

[math]1 \mid p_i=1\mid \sum U_i[/math]

Задача:

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

Алгоритм

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

Псевдокод

function schedule(d: int[n]): int[] 
  S = [math]\varnothing[/math]
  time = 0
  for i = 1 to n do
    d[i] = min(d[i], n)
  Сортиуем d подсчетом
  for i = 1 to n do
    if time < d[i]
      S = S [math]\cup[/math] {i}
      time += 1
return S
 

Время работы

Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за [math]O(n)[/math], а значит и весь алгоритм будет работать за [math]O(n)[/math]. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле [math]d_i = \min\{d_i, n\}[/math] (в оптимальном расписании мы не выполняем работы позже времени [math]time=n[/math]).

Корректность и оптимальность

В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [math]1 \mid \mid \sum w_{i}U_{i}[/math].

См. также

• Классификация задач
• [math]1 \mid \mid \sum U_{i}[/math]
• [math]1 \mid \mid \sum w_{i}U_{i}[/math]

Источники информации

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 86 стр. — ISBN 978-3-540-69515-8