1ripippmtnsumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Решение)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 2 участников)
Строка 8: Строка 8:
 
== Решение ==
 
== Решение ==
  
=== Постановка цели ===
+
Необходимо найти выполнимое множество работ <tex>O</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in O} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
 
 
Необходимо найти выполнимое множество работ <tex>O</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
 
 
Предполагается, что работы отсортированы в порядке неубывания дедлайна.
 
Предполагается, что работы отсортированы в порядке неубывания дедлайна.
  
=== Jackson's Preemptive Schedule ===
+
=== Алгоритм построения расписания ===
<tex>JPS</tex> - это алгоритм построения расписания работ для одной машины с прерываниями. Пусть у нас есть множества работ <tex>O</tex>, для которых надо составить расписание, и множество <tex>P \subset O</tex>, которое состоит из работ, доступных для выполнения на данный момент. Возможны два случая:
+
Пусть у нас есть множества работ <tex>O</tex>, для которых надо составить расписание. Возможны два случая:
# Если машина освободилась, то вставляем в расписание работу <tex>J_i\in P</tex> с наименьшим <tex>d_i</tex>. Также удалим <tex>J_i</tex> из <tex>P</tex>.
+
# Если машина освободилась, то вставляем в расписание работу <tex>J_i</tex> с наименьшим <tex>d_i</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>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_i</tex>.
Можно заметить что, если работа была вставлена в <tex>JPS</tex> после своего дедлайна, то данное множество работ <tex>O</tex> не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ <tex>O</tex>, которое будет выполнимым по <tex>JPS</tex> и чей вес будет максимален.
+
Можно заметить что, если работа была вставлена в расписание после своего дедлайна, то данное множество работ <tex>O</tex> не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ <tex>O</tex>, которое будет выполнимым, если построить его по данному алгоритму, и чей вес будет максимален.
  
 
{{Лемма
 
{{Лемма
|statement=Пусть <tex>\Theta=\{t \mid t = r_i + l \cdot p; i = 1, \dots, n; 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>.
+
|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>\Theta</tex>.
  
 
|proof=
 
|proof=
Сначала докажем лемму для <tex>e_i</tex>. Пусть <tex>t</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>e_i</tex>. Пусть <tex>t</tex> <tex>-</tex> минимальная временная точка такая, что между <tex>t</tex> и <tex>s_i</tex> станок не простаивает. По структуре расписания <tex>t = r_x</tex>. Работы, которые выполняются между <tex>s_i</tex> и <tex>e_i</tex>, не могут выполняться ни до <tex>s_i</tex>, ни после <tex>e_i</tex>, даже частично. Это следует из структуры алгоритма построения расписания <tex>-</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>J_i</tex> вызвало прерывание, тогда <tex>s_i = r_i</tex>.
 
# <tex>J_i</tex> вызвало прерывание, тогда <tex>s_i = r_i</tex>.
 
# <tex>J_i</tex> не вызывало прерываний, следовательно между <tex>r_x</tex> и <tex>s_i</tex> выполнилось некоторое количество работ, тогда <tex>s_i - r_x</tex> делится на <tex>p</tex>.
 
# <tex>J_i</tex> не вызывало прерываний, следовательно между <tex>r_x</tex> и <tex>s_i</tex> выполнилось некоторое количество работ, тогда <tex>s_i - r_x</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>r_y = r_x \vee r_i</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>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>s_i</tex> к <tex>\Theta</tex>. По структуре расписания <tex>s_i</tex> <tex>-</tex> это либо окончание предыдущей работы <tex>e_u</tex>, либо <tex>r_i</tex>. Таким образом, легко понять, что <tex>s_i \in \Theta</tex>.
  
 
}}
 
}}
  
 
=== Динамика ===
 
=== Динамика ===
{{Определение
+
Для любых <tex>t_u, t_v \in \Theta, u \leqslant v</tex> и для любого <tex>k \in [1, n]</tex> положим <tex>U_k(t_u, t_v) = \{J_i \mid i < k \wedge t_u <= r_i < t_v\}</tex> <tex>-</tex> множество работ, индекс которых меньше <tex>k</tex> и чьи <tex>r_i</tex> лежать в интервале <tex>[t_u, 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>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>
|id = def1
+
 
|definition = <tex>\forall t_u, t_v \in \Theta, u <= v, \forall k = 1, \dots ,n:</tex>
+
Будем основывать динамику на следующей лемме.
#<tex>U_k(t_u, t_v) = \{J_i \mid i < k ; 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>}}
 
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
<tex>\forall t_u, t_v \in \Theta, u <= v, \forall k \in (1, \dots ,n), \forall m \in (1, \dots ,n):</tex>
+
<tex>\forall t_u, t_v \in \Theta, u \leqslant v, \forall k \in (1, \dots ,n), \forall m \in (1, \dots ,n):</tex>
 
* <tex>r_k \notin [t_u, t_v) \Rightarrow W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>
 
* <tex>r_k \notin [t_u, t_v) \Rightarrow W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>
 
* Иначе <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>, где  
 
* Иначе <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>, где  
Строка 48: Строка 44:
  
 
|proof=
 
|proof=
Если <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>r_k \notin [t_u, t_v)</tex>, то работа <tex>J_k</tex> не может быть поставлена ни в какой <tex>Z</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>
  
  
Строка 57: Строка 53:
 
* <tex> W_{k-1}(t_u, t_v, m) < W'_k</tex>
 
* <tex> W_{k-1}(t_u, t_v, m) < W'_k</tex>
 
*:Пусть существуют такие <tex>t_x, t_y \in \Theta</tex> и три числа <tex>m_1,m_2,m_3</tex>, такие что
 
*:Пусть существуют такие <tex>t_x, t_y \in \Theta</tex> и три числа <tex>m_1,m_2,m_3</tex>, такие что
*:# <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v)</tex>,
+
*:# <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v)</tex>
*:# <tex> m_1 + m_2 + m_3 = m - 1</tex>,
+
*:# <tex> m_1 + m_2 + m_3 = m - 1</tex>
*:# <tex> p \cdot (m_2 + 1) = t_y - t_x.</tex>
+
*:# <tex> p \cdot (m_2 + 1) = t_y - t_x</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>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>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>.
  
  
Строка 67: Строка 63:
 
*:Тогда <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
 
*:Тогда <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
 
* <tex>J_k \in Z</tex>.  
 
* <tex>J_k \in Z</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>
+
*:Положим <tex>t_x</tex> и <tex>t_y</tex> временем начала выполнения и завершения работы <tex>J_k</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>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>Z_1</tex> не превосходит <tex>W_{k-1}(t_u, t_x, |Z_1|)</tex>, вес <tex>Z_2</tex> не превосходит <tex> W_{k-2}(t_x, t_y, |Z_2|)</tex> и вес <tex>Z_3</tex> не превосходит <tex> 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>, где <tex>weight(Z)</tex> <tex>-</tex> суммарный вес всех работ множества <tex>Z.</tex>
  
Исходя из двух неравенств доказанных выше, можно получить требуемое равенство <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).</tex> Лемма доказана.
+
Исходя из двух неравенств доказанных выше, можно получить требуемое равенство <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).</tex>
 
}}
 
}}
  
 
=== Псевдокод ===
 
=== Псевдокод ===
 
+
    '''int''' solve('''int['''n''']''' d, '''int['''n''']''' r, '''int['''n''']''' w):
    Отсортировать работы по <tex>d_i</tex>
+
      Отсортировать работы по <tex>d_i</tex>
    <tex>fill(W, -\infty)</tex>
+
      <tex>fill(W, -\infty)</tex>
 +
   
 +
      '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
 +
            '''if''' <tex>p \leqslant (\min(d_1,t_v)-\max(r_1,t_u))</tex>
 +
                <tex>W_1(t_u, t_v, 1) = w_1</tex>
 
      
 
      
    '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
+
      '''for''' <tex>k = 2</tex> '''to''' <tex>n</tex>
        '''if''' <tex>p \leqslant (\min(d_1,t_v)-\max(r_1,t_u))</tex>
+
            '''for''' <tex>m = 1</tex> '''to''' <tex>n</tex>
            <tex>W_1(t_u, t_v, 1) = w_1</tex>
+
                '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
 +
                  '''if''' <tex>r_k \not\in [t_u, t_v)</tex>
 +
                      <tex>W_k (t_u, t_v, m) = W_{k - 1} (t_u, t_v, m)</tex>
 +
                  '''else'''
 +
                      <tex>W'_k = </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы
 +
                      <tex>W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k)</tex>
 
      
 
      
    '''for''' <tex>k = 2</tex> '''to''' <tex>n</tex>
+
      '''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex>
        '''for''' <tex>m = 1</tex> '''to''' <tex>n</tex>
 
            '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
 
                '''if''' <tex>r_k \not\in [t_u, t_v)</tex>
 
                  <tex>W_k (t_u, t_v, m) \leftarrow W_{k - 1} (t_u, t_v, m)</tex>
 
                '''else'''
 
                  <tex>W'_k \leftarrow </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы
 
                  <tex>W_k (t_u, t_v, m) \leftarrow \max(W_{k - 1} (t_u, t_v, m), W'_k\})</tex>
 
   
 
    '''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex>
 
  
=== Оценка алгоритма ===
+
=== Асимптотика  ===
 
Заметим, что множество <tex>\Theta</tex> содержит не более <tex>n^2</tex> элементов. Следовательно, цикл по <tex>t_u, t_v</tex> итерируется <tex>O(n^4)</tex> раз. Внутри этого цикла мы тратим <tex>O(n^4)</tex> времени на подсчет <tex>W'_k</tex>, так как зная <tex>t_x, m_1</tex> и <tex>m_2</tex> мы можем посчитать <tex>t_y</tex> и <tex>m_3</tex>. Также алгоритм использует шестимерный массив для хранения <tex>W_k (t_u, t_v, m)</tex>. Таким образом, учитывая итерации алгоритма по <tex>k</tex> и <tex>m</tex>, нам потребуется <tex>O(n^{10})</tex> времени и <tex>O(n^6)</tex> памяти для работы алгоритма.
 
Заметим, что множество <tex>\Theta</tex> содержит не более <tex>n^2</tex> элементов. Следовательно, цикл по <tex>t_u, t_v</tex> итерируется <tex>O(n^4)</tex> раз. Внутри этого цикла мы тратим <tex>O(n^4)</tex> времени на подсчет <tex>W'_k</tex>, так как зная <tex>t_x, m_1</tex> и <tex>m_2</tex> мы можем посчитать <tex>t_y</tex> и <tex>m_3</tex>. Также алгоритм использует шестимерный массив для хранения <tex>W_k (t_u, t_v, m)</tex>. Таким образом, учитывая итерации алгоритма по <tex>k</tex> и <tex>m</tex>, нам потребуется <tex>O(n^{10})</tex> времени и <tex>O(n^6)</tex> памяти для работы алгоритма.
  
 
== См. также ==
 
== См. также ==
 
+
* [[1pi1sumwu | <tex> 1 \mid r_i,p_i = 1 \mid \sum w_i U_i</tex>]]
* [[P1sumu]]
+
* [[1ripipsumwu | <tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
* [[1pi1sumwu]]
 
* [[1ripipsumwu]]
 
  
 
== Источники информации ==
 
== Источники информации ==
  
Philippe Baptiste - Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times
+
*[http://www.lix.polytechnique.fr/~baptiste/jsched98.pdf Philippe Baptiste <tex>-</tex> Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times]
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:19, 4 сентября 2022

[math] 1 \mid r_i,p_i=p, pmtn \mid \sum w_i U_i[/math]


Задача:
Дано [math]n[/math] работ и 1 станок. Для каждой работы известны её время появления [math]r_i[/math] и вес [math]w_i[/math], а также дедлайн [math]d_i[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]p[/math]. Каждую работу можно прервать и продолжить ее выполнение в любой момент времени. Требуется выполнить все работы, чтобы значение [math]\sum w_i U_i[/math] (суммарный вес просроченных работ) было минимальным.


Решение

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

Алгоритм построения расписания

Пусть у нас есть множества работ [math]O[/math], для которых надо составить расписание. Возможны два случая:

  1. Если машина освободилась, то вставляем в расписание работу [math]J_i[/math] с наименьшим [math]d_i[/math].
  2. Если машина занята работой [math]J_k[/math] и в момент времени [math]r_i[/math] появилась работа [math]J_i[/math], тогда если [math]d_i \lt d_k[/math], то прервем [math]J_k[/math] и поставим на выполнение [math]J_i[/math]. В противном случае просто продолжим выполнение [math]J_i[/math].

Можно заметить что, если работа была вставлена в расписание после своего дедлайна, то данное множество работ [math]O[/math] не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ [math]O[/math], которое будет выполнимым, если построить его по данному алгоритму, и чей вес будет максимален.

Лемма:
Пусть [math]\Theta=\{t \mid t = r_i + l \cdot p \wedge i = 1, \dots, n \wedge l = 0, \dots, n - 1\}[/math]. Тогда [math]\forall J_i \in O[/math] время начала [math]s_i[/math] и время окончания [math]e_i[/math] этой работы в расписании будет принадлежать [math]\Theta[/math].
Доказательство:
[math]\triangleright[/math]

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

  1. [math]J_i[/math] вызвало прерывание, тогда [math]s_i = r_i[/math].
  2. [math]J_i[/math] не вызывало прерываний, следовательно между [math]r_x[/math] и [math]s_i[/math] выполнилось некоторое количество работ, тогда [math]s_i - r_x[/math] делится на [math]p[/math].

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


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

Динамика

Для любых [math]t_u, t_v \in \Theta, u \leqslant v[/math] и для любого [math]k \in [1, n][/math] положим [math]U_k(t_u, t_v) = \{J_i \mid i \lt k \wedge t_u \lt = r_i \lt t_v\}[/math] [math]-[/math] множество работ, индекс которых меньше [math]k[/math] и чьи [math]r_i[/math] лежать в интервале [math][t_u, t_v).[/math] Также определим [math]W_k(t_u, t_v, m)[/math] как максимальный вес множества работ [math]Z \subset U_k(t_u, t_v), |Z| = m[/math] такой, что [math]m \in (1, \dots ,n)[/math] и расписание от [math]Z[/math] разрешимо и заканчивается до [math]t_v[/math]. Если такое [math]Z[/math] существует, будем говорить, что [math]Z[/math] реализует [math]W_k(t_u, t_v, m)[/math]. Если же такого [math]Z[/math] нет, то [math]W_k(t_u, t_v, m) = - \infty.[/math]

Будем основывать динамику на следующей лемме.

Лемма:
[math]\forall t_u, t_v \in \Theta, u \leqslant v, \forall k \in (1, \dots ,n), \forall m \in (1, \dots ,n):[/math]
  • [math]r_k \notin [t_u, t_v) \Rightarrow W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);[/math]
  • Иначе [math]W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k)[/math], где
    [math]W'_k = w_k + \max\limits_{\substack {t_x, t_y \in \Theta \\ m_1 + m_2 + m_3 = m - 1 \\ p \cdot (m_2 + 1) = t_y - t_x \\ \max(r_k, t_u) \leqslant t_x \lt t_y \leqslant \min(d_k, t_v)}}[/math] [math](W_{k-1}(t_u, t_x, m_1) + W_{k-1}(t_x, t_y, m_2) + W_{k-1}(t_y, t_v, m_3))[/math].
Доказательство:
[math]\triangleright[/math]

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


Теперь рассмотрим случай, когда [math]r_k \in [t_u, t_v)[/math]. Сначала докажем, что [math]W_k(t_u, t_v, m) \geqslant \max(W_{k-1}(t_u, t_v, m), W'_k)[/math].

  • [math]W_{k-1}(t_u, t_v, m) \geqslant W'_k[/math]
    Так как [math]U_{k-1}(t_u, t_v) \subseteq U_k(t_u, t_v)[/math], то [math]W_{k-1}(t_u, t_v, m) \leqslant W_k(t_u, t_v, m)[/math].
  • [math] W_{k-1}(t_u, t_v, m) \lt W'_k[/math]
    Пусть существуют такие [math]t_x, t_y \in \Theta[/math] и три числа [math]m_1,m_2,m_3[/math], такие что
    1. [math] \max(r_k, t_u) \leqslant t_x \lt t_y \leqslant \min(d_k, t_v)[/math]
    2. [math] m_1 + m_2 + m_3 = m - 1[/math]
    3. [math] p \cdot (m_2 + 1) = t_y - t_x[/math]
    Очевидно, что [math]U_{k-1}(t_u, t_x), U_{k-1}(t_x, t_y)[/math] и [math]U_{k-1}(t_y, t_v)[/math] не пересекаются. Следовательно, расписания подмножеств, которые реализуют [math]W_{k-1}(t_u, t_x, m_1), W_{k-1}(t_x, t_y, m_2)[/math] и [math]W_{k-1}(t_y, t_v, m_3)[/math], поставленные друг за другом дадут правильное расписание для [math]m-1[/math] работ взятых из [math]U_{k-1}(t_u, t_v)[/math]. Более того, у нас достаточно места чтобы вставить работу [math]J_k[/math] в промежуток между [math]t_x[/math] и [math]t_y[/math]. Это возможно, так как [math]p \cdot (m_2 + 1) = t_y - t_x[/math] и ровно [math]m_2[/math] работ распределено для [math]U_{k-1}(t_x, t_y)[/math]. Таким образом [math]W'_k \leqslant W_k(t_u, t_v, m)[/math].


Докажем неравенство [math]W_k(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)[/math]. Положим [math]Z[/math] реализует [math] W_k(t_u, t_v, m)[/math].

  • [math]J_k \notin Z[/math].
    Тогда [math]W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)[/math].
  • [math]J_k \in Z[/math].
    Положим [math]t_x[/math] и [math]t_y[/math] временем начала выполнения и завершения работы [math]J_k[/math] в расписании от [math]Z[/math]. Благодаря предыдущей лемме, мы знаем, что [math]t_x, t_y \in \Theta[/math]. Также выполняется условие [math] \max(r_k, t_u) \leqslant t_x \lt t_y \leqslant \min(d_k, t_v).[/math] Пусть [math]Z_1, Z_2, Z_3[/math] будут подмножествами [math]Z/J_k[/math] такими, что все работы в [math]Z_1, Z_2[/math] и [math]Z_3[/math] имеют время появления [math]r_i[/math] в границах [math][t_u,t_x)[/math], [math][t_x, t_y)[/math] и [math][t_y,t_v)[/math] соответственно. По структуре расписания(работа [math]J_k[/math] имеет максимальный дедлайн [math]d_k[/math]) все работы в [math]Z_1[/math] завершаться до [math]t_x[/math]. Более того, все работы в [math]Z_2[/math] начнут выполняться после [math]t_x[/math] и завершаться до [math]t_y[/math], аналогично для [math]Z_3[/math]. Также [math]p \cdot (|Z_2| + 1) = t_y - t_x,[/math] так как [math]J_k[/math] выполнялась в промежутке [math][t_x, t_y).[/math] При этом, [math]|Z_1| + |Z_2| + |Z_3| = m - 1.[/math] Можно заметить, что вес [math]Z_1[/math] не превосходит [math]W_{k-1}(t_u, t_x, |Z_1|)[/math], вес [math]Z_2[/math] не превосходит [math] W_{k-2}(t_x, t_y, |Z_2|)[/math] и вес [math]Z_3[/math] не превосходит [math] W_{k-1}(t_y, t_v, |Z_3|).[/math] Следовательно, [math]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)[/math], где [math]weight(Z)[/math] [math]-[/math] суммарный вес всех работ множества [math]Z.[/math]
Исходя из двух неравенств доказанных выше, можно получить требуемое равенство [math]W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).[/math]
[math]\triangleleft[/math]

Псевдокод

   int solve(int[n] d, int[n] r, int[n] w):
      Отсортировать работы по [math]d_i[/math]
      [math]fill(W, -\infty)[/math]
    
      foreach [math]t_u, t_v \in \Theta \mid t_u \leqslant t_v[/math]
           if [math]p \leqslant (\min(d_1,t_v)-\max(r_1,t_u))[/math]
               [math]W_1(t_u, t_v, 1) = w_1[/math]
   
      for [math]k = 2[/math] to [math]n[/math]
           for [math]m = 1[/math] to [math]n[/math]
               foreach [math]t_u, t_v \in \Theta \mid t_u \leqslant t_v[/math]
                  if [math]r_k \not\in [t_u, t_v)[/math]
                      [math]W_k (t_u, t_v, m) = W_{k - 1} (t_u, t_v, m)[/math]
                  else
                      [math]W'_k = [/math] Подсчитать [math]W'_k[/math] по формуле из леммы
                      [math]W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k)[/math]
   
      return [math]\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))[/math]

Асимптотика

Заметим, что множество [math]\Theta[/math] содержит не более [math]n^2[/math] элементов. Следовательно, цикл по [math]t_u, t_v[/math] итерируется [math]O(n^4)[/math] раз. Внутри этого цикла мы тратим [math]O(n^4)[/math] времени на подсчет [math]W'_k[/math], так как зная [math]t_x, m_1[/math] и [math]m_2[/math] мы можем посчитать [math]t_y[/math] и [math]m_3[/math]. Также алгоритм использует шестимерный массив для хранения [math]W_k (t_u, t_v, m)[/math]. Таким образом, учитывая итерации алгоритма по [math]k[/math] и [math]m[/math], нам потребуется [math]O(n^{10})[/math] времени и [math]O(n^6)[/math] памяти для работы алгоритма.

См. также

Источники информации