577
правок
Изменения
→Асимптотика
Пусть <tex>U</tex> {{---}} множество работ, которое может быть выполнено вовремя, пусть <tex>i</tex> {{---}} работа, не принадлежащая <tex>U</tex>, для которой выполняется неравенство <tex>d_j \leqslant d_i</tex> для любой <tex>j \in U</tex>. Тогда множество работ <tex>V = U \cup \{i\}</tex> может быть выполнено вовремя тогда и только тогда, когда <tex>x(d_i) + \sum\limits_{t = 1}^{d_i - m}(m - h^U(t)) \geqslant m</tex> (1).
|proof=
Неравенство (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t) + m - x(d_i)</tex>. По лемме имеем <tex>\sum\limits_{j = d_i - m + 1}^{d_i}h^V(j) = \sum\limits_{j = d_i - m + 1}^{d_i}h^U(j) + x(d_i)</tex>. Вычитая это равенство из <tex>\sum\limits_{j = 1}^{d_i}h^V(j) = \sum\limits_{j = 1}^{d_i}h^U(j) + m</tex>, получим <tex>\sum\limits_{t = 1}^{d_i - m}h^V(t) = m - x(d_i) + \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Следовательно, мы пришли к тому, что (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Обозначим <tex>T = d_i - m</tex>, тогда предыдущее равенство превращается в <tex>Tm \geqslant \sum\limits_{t = 1}^{T}h^U(t)</tex> (2).<br>
Остается показать, что если равенство (2) выполняется для <tex>T = d_i - m</tex>, тогда оно выполняется и для <tex>T = 1, \ldots d_i - m - 1</tex>. Докажем индукцией по <tex>T</tex>, что равенство (2) выполняется для <tex>T = 1, \ldots d_i - m</tex>, взяв как базу <tex>T = d_i - m</tex>.
#''База.'' По теореме из [[Opij1di#доказательство корректности|доказательства корректности]] <tex>h^V(1) \leqslant m</tex> означает, что <tex>V</tex> может быть выполнено вовремя. С другой стороны, если <tex>h^V(1) \leqslant m</tex>, то выполняется (2), так как <tex>h^V(t) \leqslant m</tex> для всех <tex>t \geqslant 2</tex> по построению <tex>h^V</tex>.
#''Переход.'' Предположим, что (2) выполняется для некоторого <tex>T \in (1, d_i - m]</tex>. Покажем, что тогда неравенство выполняется и для <tex>T - 1</tex>. Рассмотрим два случая в зависимости от значения <tex>h^V(T)</tex>:
#:<tex>(a)</tex> Пусть <tex>h^V(T) = m</tex>. Так как равенство (2) выполняется для <tex>T</tex>, то верно <tex>(T - 1)m \geqslant \sum\limits_{t = 1}^{T}h^V(t) - m = \sum\limits_{t = 1}^{T - 1}h^V(t)</tex>. Следовательно, (2) выполняется и для <tex>T - 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>.
== Доказательство корректности ==
