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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
(Динамика)
Строка 44: Строка 44:
 
<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 <= 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>, где <tex>W'_k = w_k + \max(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))</tex>.
<tex>W'_k = w_k + max(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))</tex>
 
  
 
|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 \in [t_u, t_v)</tex>. Сначала докажем, что <tex>W_k(t_u, t_v, m) \geqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
 +
* <tex>W_{k-1}(t_u, t_v, m) > W'_k</tex>
 +
*:Так как <tex>U_{k-1}(t_u, t_v) \subseteq U_k(t_u, t_v)</tex>, то <tex>W_{k-1}(t_u, t_v, m) \leqslant W_k(t_u, t_v, m)</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> \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> 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>.
 
}}
 
}}
  

Версия 22:41, 4 июня 2016

[math] 1 \mid r_i,p_i=p \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]X[/math] такое, что его суммарный вес [math]\sum \limits_{i \in X} w_i[/math] максимален. Эта проблема решается с помощью динамического программирования. Предполагается, что работы отсортированы в порядке неубывания дедлайна.

Jackson Preemptive Schedule

[math]JPS[/math] - это алгоритм построения расписания работ для одной машины с прерываниями. Пусть у нас есть множества работ [math]O[/math], для которых надо составить расписание, и множество [math]P \subset O[/math], которое состоит из работ, доступных для выполнения на данный момент. Возможны два случая:

  1. Если машина освободилась, то вставляем в расписание работу [math]J_i\in P[/math] с наименьшим [math]d_i[/math]. Также удалим [math]J_i[/math] из [math]P[/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_k[/math] добавим в [math]P[/math]. В противном случае просто добавим [math]J_i[/math] в [math]P[/math].

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

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

Сначала докажем лемму для [math]e_i[/math]. Пусть [math]t[/math] - минимальная временная точка такая, что между [math]t[/math] и [math]s_i[/math] [math]JPS[/math] не простаивает. По структуре [math]JPS[/math] [math]t = r_x[/math]. Работы, которые выполняются между [math]s_i[/math] и [math]e_i[/math], не могут выполняться ни до [math]s_i[/math], ни после [math]e_i[/math], даже частично. Это следует из структуры [math]JPS[/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]JPS[/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]JPS[/math] не простаивает. Поэтому [math]e_i \in \Theta[/math].


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

Динамика

Определение:
[math]\forall t_u, t_v \in \Theta, u \lt = v, \forall k = 1, \dots ,n:[/math]
  1. [math]U_k(t_u, t_v) = \{J_i \mid i \lt k ; t_u \lt = r_i \lt t_v\};[/math]
  2. [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]JPS[/math] от [math]Z[/math] разрешимо и заканчивается до [math]t_v[/math]. Если такого [math]Z[/math] не существует, то [math]W_k(t_u, t_v, m) = - \infty.[/math]


Лемма:
[math]\forall t_u, t_v \in \Theta, u \lt = 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(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]JPS[/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) \gt 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]JPS[/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]\triangleleft[/math]

См. также

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

Philippe Baptiste - Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times