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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 48429 участника Pokrasko (обсуждение))
(Удалено содержимое страницы)
 
Строка 1: Строка 1:
<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>
 
  
{{Задача
 
|definition=
 
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
 
}}
 
 
== Алгоритм ==
 
 
=== Предисловие ===
 
 
Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
 
Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из <tex>n^2</tex> значений.
 
 
{{Лемма
 
|statement=
 
Существует оптимальное расписание, в котором время начала каждой работы принадлежит множеству:
 
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>
 
 
|proof=
 
Рассмотрим оптимальное расписание <tex>S</tex>. Пусть <tex>j_1, \dots, j_n</tex> — работы в <tex>S</tex> в порядке неубывания дедлайна. Выполнимое расписание может быть получено из <tex>S</tex> следующим образом. Первая работа <tex>j_1</tex> может быть сдвинута влево до времени своего появления. Тогда работа <tex>j_2</tex> сдвигается влево до времени своего появления или времени завершения работы <tex>j_1</tex>. В общем, <tex>j_i</tex> сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы <tex>j_{i - 1}</tex>.
 
}}
 
 
Для любого <tex>k \leqslant n</tex> и <tex>s, e \in T</tex> таких, что <tex>s \leqslant e</tex>, пусть <tex>U_k (s, e)</tex> — множество работ <tex>j \leqslant k</tex> таких, что <tex>s \leqslant r_i \leqslant e</tex>. Кроме того, пусть <tex>W^*_k (s, e)</tex> — максимальный суммарный вес подмножества <tex>U_k (s, e)</tex> такого, что существует выполнимое расписание <tex>S</tex> для работ из этого подмножества такое, что:
 
* <tex>S</tex> свободно до времени <tex>s + p</tex> и после времени <tex>e</tex>,
 
* время начала работ в <tex>S</tex> принадлежат <tex>T</tex>.
 
<tex>W^*_k (s, e) = 0</tex>, если ни для какого подмножества работ не существует выполнимого расписания.
 
 
=== Псевдокод ===
 
 
    Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>
 
    '''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
 
        <tex>W_0 (s, e) \leftarrow 0</tex>
 
    '''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
 
        '''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
 
            '''if''' <tex>r_k \not\in [s, e)</tex>
 
                <tex>W_k (s, e) \leftarrow W_{k - 1} (s, e)</tex>
 
            '''else'''
 
                <tex>W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;</tex>
 
                    <tex>\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}</tex>
 
                <tex>W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}</tex>
 
    '''return''' <tex>W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)</tex>
 
 
Заметим, что <tex>W'_k (s, e)</tex> соответствует выполнимому расписанию, в котором работа <tex>k</tex> начинается в момент времени <tex>s'</tex>.
 
 
=== Время работы ===
 
 
По лемме <tex>T</tex> содержит <tex>O(n^2)</tex> элементов. В каждой итерации алгоритма мы выбираем времена <tex>s</tex> и <tex>e</tex> из <tex>T</tex>, а для каждой такой пары ищем необходимое время <tex>s'</tex>. Из того, что итераций <tex>n</tex>, получаем, что алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени.
 
 
=== Корректность алгоритма ===
 
 
Покажем, что вычисленное алгоритмом <tex>W_k (s, e)</tex> равно <tex>W^*_k (s, e)</tex>, то есть возвращаемое им значение является оптимальным решением.
 
 
{{Теорема
 
|statement=
 
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняется:
 
<tex>W_k (s, e) = W^*_k (s, e)</tex>
 
 
|proof=
 
Докажем индукцией по <tex>k</tex>. Очевидно, что утверждение выполняется при <tex>k = 0</tex>. Допустим, что оно выполняется при <tex>k - 1</tex>.
 
 
Если <tex>r_k \not\in [s, e)</tex>, то <tex>U_k (s, e) = U_{k - 1} (s, e)</tex>, из чего следует, что <tex>W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)</tex>. Осталось показать, что:
 
<tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)</tex>, если <tex>r_k \in [s, e)</tex>.
 
Рассмотрим два неравенства:
 
 
# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
 
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
 
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, s')</tex>
 
#:
 
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
 
#:* работы <tex>k</tex>, выполняющейся в <tex>[s', s' + p]</tex>,
 
#:* подмножества работ <tex>U_{k - 1} (s, s')</tex>, выполняющихся в <tex>[s + p, s']</tex>,
 
#:* подмножества работ <tex>U_{k - 1} (s', e)</tex>, выполняющихся в <tex>[s' + p, e]</tex>.
 
#:
 
# <tex>W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}</tex>
 
#: Пусть <tex>Z</tex> - подмножество <tex>U_k (s, e)</tex>, соответствующее <tex>W^*_k (s, e)</tex>. Если <tex>k \not\in Z</tex>, то <tex>W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)</tex> и неравенство доказано. Иначе, пусть <tex>S^*</tex> - расписание, соответствующее <tex>W^*_k (s, e)</tex>, и <tex>s'</tex> - время начала работы <tex>k</tex>. Нужно, чтобы выполнялось неравенство: <tex>\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>.
 
#:
 
#: Обозначим за <tex>Z^b</tex> и <tex>Z^a</tex> подмножества работ <tex>Z</tex>, которые в <tex>S^*</tex> выполняются до и после работы <tex>k</tex> соответственно. Можем предположить, что времена появления всех работ в <tex>Z^a</tex> больше, чем время <tex>s'</tex> начала работы <tex>k</tex>. Иначе, пусть <tex>i</tex> - работа в <tex>Z^a</tex> такая, что <tex>r_i \le s'</tex>. Так как работы отсортированы в порядке неубывания дедлайна, то <tex>d_i \le d_k</tex>. Таким образом, при перестановке работ <tex>i</tex> и <tex>k</tex> в <tex>S^*</tex> суммарный вес не изменится. Продолжим этот процесс, пока новое расписание <tex>S^*</tex> удовлетворяет нужному свойству.  Получим:
 
#: <tex>W^*_k (s, e) = \sum \limits_{j \in Z} w_j = \sum \limits_{j \in Z^b} w_j + w_k + \sum \limits_{j \in Z^a} \leqslant W^*_{k - 1} (s, s') + w_k + W^*_{k - 1} (s', e) = W_{k - 1} (s, s') + w_k + W_{k - 1} (s', e) \leqslant W'_k (s, e)</tex>
 
#:, так как очевидно, что <tex>Z^b \subseteq U_{k - 1} (s, s')</tex>, и, по предположению, выполняется <tex>Z^a \subseteq U_{k - 1} (s', e)</tex>.
 
}}
 
 
== Прочие задачи ==
 
 
Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист, его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.
 
 
== См. также ==
 
 
* [[P1sumu]]
 
* [[1pi1sumwu]]
 
 
== Источники информации ==
 
 
* Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 

Текущая версия на 00:48, 14 июня 2015