Обсуждение участницы:Анна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
(Доказательство корректности)
Строка 37: Строка 37:
 
Для множества работ с дедлайнами <tex>d_1, d_2, \ldots d_n</tex> задача имеет решение тогда и только тогда, когда <tex>h(1) \leqslant m</tex>.
 
Для множества работ с дедлайнами <tex>d_1, d_2, \ldots d_n</tex> задача имеет решение тогда и только тогда, когда <tex>h(1) \leqslant m</tex>.
 
|proof=
 
|proof=
 +
<tex>\Rightarrow</tex><br>
 +
Если задача имеет решение, то очевидно, что первый временной интервал не может быть переполнен.<br>
 +
<tex>\Leftarrow</tex>
 
Изначально алгоритм присваивает все стадии обработки каждой работы <tex>i</tex> (то есть обработку на каждом станке) попарно различным временным интервалам. Если <tex>\exists k > 1 : h(k) = m + 1</tex> и <tex>h(k - 1) \leqslant m</tex>, то это значит, что существует как минимум одна работа, которая назначена временному интервалу <tex>k</tex>, но которой нет во временном интервале  <tex>k - 1</tex>. Следовательно, после перемещения вектор <tex>h</tex> по-прежнему будет удовлетворять условию, что каждая работа принадлежит <tex>m</tex> разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если <tex>h(1) \leqslant m</tex>, то <tex>h(t) \leqslant m</tex>, где <tex>t = 1 \ldots T</tex>, то есть существует решение, при котором все работы будут выполнены вовремя.
 
Изначально алгоритм присваивает все стадии обработки каждой работы <tex>i</tex> (то есть обработку на каждом станке) попарно различным временным интервалам. Если <tex>\exists k > 1 : h(k) = m + 1</tex> и <tex>h(k - 1) \leqslant m</tex>, то это значит, что существует как минимум одна работа, которая назначена временному интервалу <tex>k</tex>, но которой нет во временном интервале  <tex>k - 1</tex>. Следовательно, после перемещения вектор <tex>h</tex> по-прежнему будет удовлетворять условию, что каждая работа принадлежит <tex>m</tex> разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если <tex>h(1) \leqslant m</tex>, то <tex>h(t) \leqslant m</tex>, где <tex>t = 1 \ldots T</tex>, то есть существует решение, при котором все работы будут выполнены вовремя.
 
}}
 
}}

Версия 15:05, 11 мая 2016

[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]