51
правка
Изменения
Нет описания правки
<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 [[Категория: Дискретная математика и алгоритмы]][[1ridipipsumwuКатегория: Теория расписаний]]
