1632
правки
Изменения
м
[[Файл{| class="wikitable" style="float:right; margin-left: 10px;"|-! ! style="width:50px;"|<tex>t = 1</tex>! style="width:50px;"|<tex>2</tex>! style="width:30px;"|<tex>...</tex>! style="width:50px;"|<tex>d_i - m + 1</tex>! style="width:50px;"|<tex>d_i - m + 2</tex>! style="width:Shd230px;"|<tex>...jpg</tex>! style="width:50px;"|<tex>d_i - 1</tex>! style="width:50px;"|<tex>d_i</tex>|-! style="width:50px;"|<tex>m = 1</tex>| | | | style="text-align:center;"|<tex>i</tex>| | |300px|thumb|right-! style="width:50px;"|<tex>2</tex>| | | | | style="text-align:center;"|<tex>i</tex>| |||-! style="width:50px;"|<tex>\vdots</tex>| | | | | | style="text-align:center;"|<tex>\ddots</tex>|||-! style="width:50px;"|<tex>m - 1</tex>| | | | || | style="text-align:center;"|<tex>i</tex>||-! style="width:50px;"|<tex>m</tex>| | | | || | | style="text-align:center;"|<tex>i</tex>|-! colspan="9"|РисТабл. 1. Работа <tex>i</tex> назначена на интервалы <tex>d_i - m + 1 \ldots d_i</tex>.]]|}
rollbackEdits.php mass rollback
== Описание алгоритма ==
=== Идея ===
Заметим, что если <tex>d_i < m</tex>, то очевидно, что <tex>C_i > d_i</tex>, следовательно, расписания не существует. Поэтому будем полагать, что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>.
Определим <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>.
'''void''' checkExistenceOfSchedule('''int[]'''* <tex>d</tex>):
<tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex>
'''for''' <tex>t = 1</tex> '''to''' <tex>T</tex>
<tex>h(k_0) = m</tex>
'''if''' <tex>h(1) \leqslant m</tex>
'''return''''' true''
'''else'''
'''return''''' false''
''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex>, на момент <tex>k_0 - 1</tex> в той же машине (этот шаг будет обоснован далее в доказательстве корректности).
#:<tex>(b)</tex> Пусть <tex>h^V(T) < m</tex>. В расписании для множества работ <tex>V</tex> все стадии обработки работы <tex>i</tex> (<tex>k</tex> стадия обработки {{---}} выполнение работы на <tex>k</tex> машине) должны быть назначены на временные интервалы из отрезка <tex>[T - 1, d_i]</tex>, так как <tex>T \leqslant d_i - m</tex> и в период времени <tex>[T - 1, T]</tex> есть свободная машина. Все стадии обработки работ в расписании для <tex>U</tex>, назначенные на временные интервалы из отрезка <tex>[T - 1, d_i]</tex>, в расписании для <tex>V</tex> назначены на временные интервалы из того же отрезка <tex>[T - 1, d_i]</tex>. И так как <tex>U</tex> по условию может быть выполнено вовремя, верно неравенство <tex>(T - 1)m \geqslant \sum\limits_{t = 1}^{T - 1}h^U(t) = \sum\limits_{t = 1}^{T - 1}h^V(t)</tex>. Следовательно, (2) выполняется и для <tex>T - 1</tex>.
}}
Пусть <tex>k = |U|</tex> {{---}} мощность множества <tex>U</tex>. Тогда <tex>\sum\limits_{j = 1}^{d_i - m}(m - h^U(j)) = m(d_i - m) - \sum\limits_{j = 1}^{d_i - m}h^U(j) = m(d_i - m) - (km - \sum\limits_{j = d_i - m + 1}^{d_i}h^U(j))</tex>. Таким образом, (1) равносильно <tex>m(d_i - m) - (km - \sum\limits_{j = 1}^{m}h^U(d_i - m + j)) + x(d_i) \geqslant m</tex> (3). Мы пришли к тому, что нам достаточно знать только значения <tex>h^U(d_i - m + 1) \ldots h^U(d_i)</tex> и мощность <tex>k</tex> множества <tex>U</tex>, чтобы проверить, выполняется ли (3), то есть может ли множество <tex>V = U \cup \{i\}</tex> быть выполнено вовремя. Очевидно, что (3) может быть вычислено за время <tex>O(m)</tex>.<br>Чтобы решить задачу <tex> O \mid p_{i,j} = 1, d_i \mid - </tex> для работ <tex>i = 1, 2 \ldots n</tex> с временами окончаний <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>, для каждого <tex>i \in [1, n]</tex> мы проверяем, может ли множество <tex>U_i = \{1 \ldots i\}</tex> быть выполнено вовремя, если <tex>U_{i - 1}</tex> было выполнено вовремя. Этот шаг осуществляется за <tex>O(m)</tex> проверкой условия (3). Более того, по лемме значения <tex>h^{U_i}(d_i - m + 1) \ldots h^{U_i}(d_i)</tex> могут быть так же вычислены за <tex>O(m)</tex>. Следовательно, алгоритм может быть реализован за время <tex>O(mn)</tex>, если на вход дают работы в порядке неубывания времен окончания.
== Доказательство корректности ==
