1ripippmtnsumwu — различия между версиями
Swanwarp (обсуждение | вклад) (→Динамика) |
Swanwarp (обсуждение | вклад) м (→Псевдокод: убрал фигурную скобку) |
||
(не показано 25 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | <tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex> | + | <tex dpi=200> 1 \mid r_i,p_i=p, pmtn \mid \sum w_i U_i</tex> |
{{Задача | {{Задача | ||
Строка 8: | Строка 8: | ||
== Решение == | == Решение == | ||
− | + | Необходимо найти выполнимое множество работ <tex>O</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in O} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]]. | |
− | |||
− | Необходимо найти выполнимое множество работ <tex> | ||
Предполагается, что работы отсортированы в порядке неубывания дедлайна. | Предполагается, что работы отсортированы в порядке неубывания дедлайна. | ||
− | === | + | === Алгоритм построения расписания === |
− | + | Пусть у нас есть множества работ <tex>O</tex>, для которых надо составить расписание. Возможны два случая: | |
− | # Если машина освободилась, то вставляем в расписание работу <tex>J_i | + | # Если машина освободилась, то вставляем в расписание работу <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>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>O</tex> не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ <tex>O</tex>, которое будет выполнимым, если построить его по данному алгоритму, и чей вес будет максимален. |
{{Лемма | {{Лемма | ||
− | |statement=Пусть <tex>\Theta=\{t \mid t = r_i + l \cdot p | + | |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>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>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> | + | Теперь докажем принадлежность <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> | |
− | + | ||
− | + | Будем основывать динамику на следующей лемме. | |
− | |||
− | |||
{{Лемма | {{Лемма | ||
|statement= | |statement= | ||
− | <tex>\forall t_u, t_v \in \Theta, u | + | <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 = 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(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>, где |
+ | *: <tex>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 < t_y \leqslant \min(d_k, t_v)}}</tex> <tex>(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>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> |
Строка 56: | Строка 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>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>. |
Строка 66: | Строка 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>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>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> | ||
+ | |||
+ | '''for''' <tex>k = 2</tex> '''to''' <tex>n</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) = 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> | ||
+ | |||
+ | '''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> памяти для работы алгоритма. | ||
== См. также == | == См. также == | ||
− | + | * [[1pi1sumwu | <tex> 1 \mid r_i,p_i = 1 \mid \sum w_i U_i</tex>]] | |
− | + | * [[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:16, 8 июня 2016
Задача: |
Дано | работ и 1 станок. Для каждой работы известны её время появления и вес , а также дедлайн . Время выполнения всех работ равно . Каждую работу можно прервать и продолжить ее выполнение в любой момент времени. Требуется выполнить все работы, чтобы значение (суммарный вес просроченных работ) было минимальным.
Содержание
Решение[править]
Необходимо найти выполнимое множество работ динамического программирования. Предполагается, что работы отсортированы в порядке неубывания дедлайна.
такое, что его суммарный вес максимален. Эта проблема решается с помощьюАлгоритм построения расписания[править]
Пусть у нас есть множества работ
, для которых надо составить расписание. Возможны два случая:- Если машина освободилась, то вставляем в расписание работу с наименьшим .
- Если машина занята работой и в момент времени появилась работа , тогда если , то прервем и поставим на выполнение . В противном случае просто продолжим выполнение .
Можно заметить что, если работа была вставлена в расписание после своего дедлайна, то данное множество работ
не является выполнимым. Таким образом, решение задачи сводится к нахождению такого множества работ , которое будет выполнимым, если построить его по данному алгоритму, и чей вес будет максимален.Лемма: |
Пусть . Тогда время начала и время окончания этой работы в расписании будет принадлежать . |
Доказательство: |
Сначала докажем лемму для . Пусть минимальная временная точка такая, что между и станок не простаивает. По структуре расписания . Работы, которые выполняются между и , не могут выполняться ни до , ни после , даже частично. Это следует из структуры алгоритма построения расписания если работа была прервана работой , то после выполнения мы снова вставляем в расписание . Таким образом, делится на . Возможны следующие два случая:
В любом из этих двух случаев есть такое , такое что станок не простаивает между и . Тогда делится на . Следовательно, не превышает , так как станок не простаивает. Поэтому .
|
Динамика[править]
Для любых
и для любого положим множество работ, индекс которых меньше и чьи лежать в интервале Также определим как максимальный вес множества работ такой, что и расписание от разрешимо и заканчивается до . Если такое существует, будем говорить, что реализует . Если же такого нет, тоБудем основывать динамику на следующей лемме.
Лемма: |
|
Доказательство: |
Если , то работа не может быть поставлена ни в какой такой, что расписание от разрешимо и . Тогда, очевидно, что
|
Псевдокод[править]
int solve(int[n] d, int[n] r, int[n] w): Отсортировать работы поforeach if for to for to foreach if else Подсчитать по формуле из леммы return
Асимптотика[править]
Заметим, что множество
содержит не более элементов. Следовательно, цикл по итерируется раз. Внутри этого цикла мы тратим времени на подсчет , так как зная и мы можем посчитать и . Также алгоритм использует шестимерный массив для хранения . Таким образом, учитывая итерации алгоритма по и , нам потребуется времени и памяти для работы алгоритма.См. также[править]
Источники информации[править]
- Philippe Baptiste Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times