Изменения

=== Постановка цели === Необходимо найти выполнимое множество работ <tex>O</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in XO} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].

=== Jackson's Preemptive Schedule Алгоритм построения расписания ===<tex>JPS</tex> - это алгоритм построения расписания работ для одной машины с прерываниями. Пусть у нас есть множества работ <tex>O</tex>, для которых надо составить расписание, и множество <tex>P \subset O</tex>, которое состоит из работ, доступных для выполнения на данный момент. Возможны два случая:# Если машина освободилась, то вставляем в расписание работу <tex>J_i\in P</tex> с наименьшим <tex>d_i</tex>. Также удалим <tex>J_i</tex> из <tex>P</tex>.# Если машина занята работой <tex>J_k</tex> и в момент времени <tex>r_i</tex> появилась работа <tex>J_i</tex>, тогда если <tex>d_i < d_k</tex>, то прервем <tex>J_k</tex> и поставим на выполнение <tex>J_i</tex>, а <tex>J_k</tex> добавим в <tex>P</tex>. В противном случае просто добавим продолжим выполнение <tex>J_i</tex> в <tex>P</tex>.Можно заметить что, если работа была вставлена в <tex>JPS</tex> расписание после своего дедлайна, то данное множество работ <tex>O</tex> не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ <tex>O</tex>, которое будет выполнимым , если построить его по <tex>JPS</tex> данному алгоритму, и чей вес будет максимален.

|statement=Пусть <tex>\Theta=\{t \mid t = r_i + l \cdot p; \wedge i = 1, \dots, n; \wedge l = 0, \dots, n - 1\}</tex>. Тогда <tex>\forall J_i \in O</tex> время начала <tex>s_i</tex> и время окончания <tex>e_i</tex> этой работы в <tex>JPS</tex> расписании будет принадлежать <tex>\Theta</tex>.

Сначала докажем лемму для <tex>e_i</tex>. Пусть <tex>t</tex> <tex> - </tex> минимальная временная точка такая, что между <tex>t</tex> и <tex>s_i</tex> <tex>JPS</tex> станок не простаивает. По структуре <tex>JPS</tex> расписания <tex>t = r_x</tex>. Работы, которые выполняются между <tex>s_i</tex> и <tex>e_i</tex>, не могут выполняться ни до <tex>s_i</tex>, ни после <tex>e_i</tex>, даже частично. Это следует из структуры <tex>JPS</tex> алгоритма построения расписания - если работа <tex>J_u</tex> была прервана работой <tex>J_v</tex>, то после выполнения <tex>J_v</tex> мы снова вставляем в расписание <tex>J_u</tex>. Таким образом, <tex>e_i - s_i</tex> делится на <tex>p</tex>. Возможны следующие два случая:

В любом из этих двух случаев есть такое <tex>r_y = r_x \vee r_i</tex>, такое что <tex>JPS</tex> станок не простаивает между <tex>r_y</tex> и <tex>e_i</tex>. Тогда <tex>e_i - r_y</tex> делится на <tex>p</tex>. Следовательно, <tex>e_i - r_y</tex> не превышает <tex>n \cdot p</tex>, так как <tex>JPS</tex> станок не простаивает. Поэтому <tex>e_i \in \Theta</tex>.

Теперь докажем принадлежность <tex>s_i</tex> к <tex>\Theta</tex>. По структуре <tex>JPS</tex> расписания <tex>s_i</tex> - это либо окончание предыдущей работы <tex>e_u</tex>, либо <tex>r_i</tex>. Таким образом, легко понять, что <tex>s_i \in \Theta</tex>.

#<tex>U_k(t_u, t_v) = \{J_i \mid i < k ; \wedge t_u <= r_i < t_v\};</tex>#<tex>W_k(t_u, t_v, m)</tex> - максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и <tex>JPS</tex> расписание от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> нет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}

Если <tex>r_k \notin [t_u, t_v)</tex>, то работа <tex>J_k</tex> не может быть поставлена ни в какой <tex>Z</tex> такой, что <tex>JPS</tex> расписание от <tex>Z</tex> разрешимо и <tex>Z \subset U_k(t_u, t_v)</tex>. Тогда, очевидно, что <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>

*: Очевидно, что <tex>U_{k-1}(t_u, t_x), U_{k-1}(t_x, t_y)</tex> и <tex>U_{k-1}(t_y, t_v)</tex> не пересекаются. Следовательно, <tex>JPS</tex> расписания подмножеств, которые реализуют <tex>W_{k-1}(t_u, t_x, m_1), W_{k-1}(t_x, t_y, m_2)</tex> и <tex>W_{k-1}(t_y, t_v, m_3)</tex>, поставленные друг за другом дадут правильное расписание для <tex>m-1</tex> работ взятых из <tex>U_{k-1}(t_u, t_v)</tex>. Более того, у нас достаточно места чтобы вставить работу <tex>J_k</tex> в промежуток между <tex>t_x</tex> и <tex>t_y</tex>. Это возможно, так как <tex>p \cdot (m_2 + 1) = t_y - t_x</tex> и ровно <tex>m_2</tex> работ распределено для <tex>U_{k-1}(t_x, t_y)</tex>. Таким образом <tex>W'_k \leqslant W_k(t_u, t_v, m)</tex>.

*:Положим <tex>t_x</tex> и <tex>t_y</tex> временем начала выполнения и завершения работы <tex>J_k</tex> в <tex>JPS</tex> расписании от <tex>Z</tex>. Благодаря предыдущей лемме, мы знаем, что <tex>t_x, t_y \in \Theta</tex>. Также выполняется условие <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v).</tex> Пусть <tex>Z_1, Z_2, Z_3</tex> будут подмножествами <tex>Z/J_k</tex> такими, что все работы в <tex>Z_1, Z_2</tex> и <tex>Z_3</tex> имеют время появления <tex>r_i</tex> в границах <tex>[t_u,t_x)</tex>, <tex>[t_x, t_y)</tex> и <tex>[t_y,t_v)</tex> соответственно. По структуре <tex>JPS</tex>расписания(работа <tex>J_k</tex> имеет максимальный дедлайн <tex>d_k</tex>) все работы в <tex>Z_1</tex> завершаться до <tex>t_x</tex>. Более того, все работы в <tex>Z_2</tex> начнут выполняться после <tex>t_x</tex> и завершаться до <tex>t_y</tex>, аналогично для <tex>Z_3</tex>. Также <tex>p \cdot (|Z_2| + 1) = t_y - t_x,</tex> так как <tex>J_k</tex> выполнялась в промежутке <tex>[t_x, t_y).</tex> При этом, <tex>|Z_1| + |Z_2| + |Z_3| = m - 1.</tex> Можно заметить, что <tex>weight(Z_1) \leqslant W_{k-1}(t_u, t_x, |Z_1|), weight(Z_2) \leqslant W_{k-2}(t_x, t_y, |Z_2|)</tex> и <tex>weight(Z_3) \leqslant W_{k-1}(t_y, t_v, |Z_3|).</tex> Следовательно, <tex>W_k(t_u, t_v, m) = w_k + \sum\limits_{i = 1}^3weight(Z_i) \leqslant W'_k \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k).</tex>