Обсуждение участницы:Анна

[math] O \mid p_{i,j} = 1, d_i \mid - [/math]

Задача:

Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — время, до которого она должна быть выполнена. Необходимо проверить, существует ли расписание, при котором все работы будут выполнены вовремя.

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

Идея

Заметим, что если [math]d_i \lt m[/math], то очевидно, что [math]C_i \gt d_i[/math], следовательно, расписания не существует. Поэтому будем полагать, что [math]m \leqslant d_i[/math] для [math]i = 1 \ldots n[/math].

Определим [math]T = \max\limits_{i \in [1, n]}d_i[/math] — количество временных интервалов [math][t - 1, t][/math], где [math]t = 1 \ldots T[/math]. Будем обозначать [math][t - 1, t][/math] как [math]t[/math]. Для каждого из них мы можем назначить не более [math]m[/math] работ (по одной на каждый станок). Для каждой работы [math]i[/math] будем назначать времена обработки на каждой из машин следующим образом: на машине [math]m[/math] работа займет временной интервал [math]d_i[/math], на машине [math](m - 1)[/math] — интервал [math](d_i - 1)[/math] и так далее, на машине [math]1[/math] работа займет временной интервал [math]d_i - m + 1[/math]. В случае коллизий, то есть если найдется временной интервал [math]k \gt 1[/math], содержащий [math]m + 1[/math] работу, возьмем минимальный такой [math]k[/math] и перенесем лишнюю работу из него на ту же машину, но на один временной интервал левее. Будем повторять этот процесс, пока необходимо (и пока [math]k \gt 1[/math]). Таким образом, только первый временной интервал может содержать более [math]m[/math] работ. Причем это может произойти тогда и только тогда, когда задача не имеет решения, то есть не существует расписания, при котором все работы будут выполнены вовремя.

Псевдокод

Определим [math]h(t)[/math] — количество работ во временном интервале [math]t[/math].

void checkExistenceOfSchedule(int* [math]d[/math]):
  [math]T = \max\{d_i \mid i = 1 \ldots n\}[/math]
  for [math]t = 1[/math] to [math]T[/math]
     [math]h(t) = 0[/math]
  for [math]i = 1[/math] to [math]n[/math]
     for [math]j = d_i[/math] to [math]d_i - m + 1[/math]           (1)
        [math]h(j) = h(j) + 1[/math]
     while [math]\exists k \gt  1[/math] and [math]h(k) = m + 1[/math]     (2)
        find [math]\min\{k_0 \mid h(k_0) = m + 1\}[/math]
        [math]h(k_0 - 1) = h(k_0 - 1) + 1[/math]
        [math]h(k_0) = m[/math]
  if [math]h(1) \leqslant m[/math]
     return true
  else
     return false

Замечание: если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы [math]i[/math] на момент [math]j[/math] в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале [math]k_0 - 1[/math], но которая есть в [math]k_0[/math] на момент [math]k_0 - 1[/math] в той же машине.

Асимптотика

Покажем, что данный алгоритм может быть реализован за время [math]O(nm)[/math].

Доказательство корректности

Теорема:

Для множества работ с дедлайнами [math]d_1, d_2, \ldots d_n[/math] задача имеет решение тогда и только тогда, когда [math]h(1) \leqslant m[/math].

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] Если задача имеет решение, то очевидно, что первый временной интервал не может быть переполнен. [math]\Leftarrow[/math] Изначально алгоритм присваивает все стадии обработки каждой работы [math]i[/math] (то есть обработку на каждом станке) попарно различным временным интервалам. Если [math]\exists k \gt 1 : h(k) = m + 1[/math] и [math]h(k - 1) \leqslant m[/math], то это значит, что существует как минимум одна работа, которая назначена временному интервалу [math]k[/math], но которой нет во временном интервале [math]k - 1[/math]. Следовательно, после перемещения вектор [math]h[/math] по-прежнему будет удовлетворять условию, что каждая работа принадлежит [math]m[/math] разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если [math]h(1) \leqslant m[/math], то [math]h(t) \leqslant m[/math], где [math]t = 1 \ldots T[/math], то есть существует решение, при котором все работы будут выполнены вовремя.

[math]\triangleleft[/math]