Изменения

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

=== Идея ===

Заметим, что если <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>.

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

'''else'''

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

Пусть <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>.

#:<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>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>, то есть существует решение, при котором все работы будут выполнены вовремя.

}}