1ripipsumwu

[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] максимален. Эта проблема решается с помощью динамического программирования. Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из [math]n^2[/math] значений.

Лемма:

Существует оптимальное расписание, в котором время начала каждой работы принадлежит множеству: [math]T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}[/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим оптимальное расписание [math]S[/math]. Пусть [math]j_1, \dots, j_n[/math] — работы в [math]S[/math] в порядке неубывания дедлайна. Выполнимое расписание может быть получено из [math]S[/math] следующим образом. Первая работа [math]j_1[/math] может быть сдвинута влево до времени своего появления. Тогда работа [math]j_2[/math] сдвигается влево до времени своего появления или времени завершения работы [math]j_1[/math]. В общем, [math]j_i[/math] сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы [math]j_{i - 1}[/math].

[math]\triangleleft[/math]

Для любого [math]k \leqslant n[/math] и [math]s, e \in T[/math] таких, что [math]s \leqslant e[/math], пусть [math]U_k (s, e)[/math] — множество работ [math]j \leqslant k[/math] таких, что [math]s \leqslant r_i \leqslant e[/math]. Кроме того, пусть [math]W^*_k (s, e)[/math] — максимальный суммарный вес подмножества [math]U_k (s, e)[/math] такого, что существует выполнимое расписание [math]S[/math] для работ из этого подмножества такое, что:

• [math]S[/math] свободно до времени [math]s + p[/math] и после времени [math]e[/math],
• время начала работ в [math]S[/math] принадлежат [math]T[/math].

[math]W^*_k (s, e) = 0[/math], если ни для какого подмножества работ не существует выполнимого расписания.

Псевдокод

   Отсортировать работы так, чтобы [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math]
   foreach [math]s, e \in T \mid s \leqslant e[/math]
       [math]W_0 (s, e) \leftarrow 0[/math]
   for [math]k = 1[/math] to [math]n[/math]
       foreach [math]s, e \in T \mid s \leqslant e[/math]
           if [math]r_k \not\in [s, e)[/math]
               [math]W_k (s, e) \leftarrow W_{k - 1} (s, e)[/math]
           else
               [math]W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;[/math]
                   [math]\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}[/math]
               [math]W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}[/math]
   return [math]W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)[/math]

Заметим, что [math]W'_k (s, e)[/math] соответствует выполнимому расписанию, в котором работа [math]k[/math] начинается в момент времени [math]s'[/math].

Время работы

По лемме [math]T[/math] содержит [math]O(n^2)[/math] элементов. В каждой итерации алгоритма мы выбираем времена [math]s[/math] и [math]e[/math] из [math]T[/math], а для каждой такой пары ищем необходимое время [math]s'[/math]. Из того, что итераций [math]n[/math], получаем, что алгоритм работает за [math]O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)[/math] времени.

Корректность алгоритма

Покажем, что вычисленное алгоритмом [math]W_k (s, e)[/math] равно [math]W^*_k (s, e)[/math], то есть возвращаемое им значение является оптимальным решением.

Теорема:

Для любого [math]k = 0, \dots, n[/math] и для любого [math]s, e \in T \mid s \leqslant e[/math], выполняется: [math]W_k (s, e) = W^*_k (s, e)[/math]

Доказательство:

[math]\triangleright[/math]

Докажем индукцией по [math]k[/math]. Очевидно, что утверждение выполняется при [math]k = 0[/math]. Допустим, что оно выполняется при [math]k - 1[/math]. Если [math]r_k \not\in [s, e)[/math], то [math]U_k (s, e) = U_{k - 1} (s, e)[/math], из чего следует, что [math]W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)[/math]. Осталось показать, что: [math]\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)[/math], если [math]r_k \in [s, e)[/math]. Рассмотрим два неравенства: [math]\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)[/math] Так как [math]U_{k - 1} (s, e) \subseteq U_k (s, e)[/math], то [math]W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)[/math]. Кроме того, если [math]W'_k (s, e) \gt 0[/math], то существует такое время [math]s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p[/math], что: [math]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, e)[/math] Неравенство выполняется, так как [math]w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)[/math] - суммарный вес расписания, состоящего из: работы [math]k[/math], выполняющейся в [math][s', s' + p][/math], подмножества работ [math]U_{k - 1} (s, s')[/math], выполняющихся в [math][s + p, s'][/math], подмножества работ [math]U_{k - 1} (s', e)[/math], выполняющихся в [math][s' + p, e][/math]. [math]W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}[/math] Пусть [math]Z[/math] - подмножество [math]U_k (s, e)[/math], соответствующее [math]W^*_k (s, e)[/math]. Если [math]k \not\in Z[/math], то [math]W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)[/math] и неравенство доказано. Иначе, пусть [math]S^*[/math] - расписание, соответствующее [math]W^*_k (s, e)[/math], и [math]s'[/math] - время начала работы [math]k[/math]. Нужно, чтобы выполнялось неравенство: [math]\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p[/math]. Обозначим за [math]Z^b[/math] и [math]Z^a[/math] подмножества работ [math]Z[/math], которые в [math]S^*[/math] выполняются до и после работы [math]k[/math] соответственно. Можем предположить, что времена появления всех работ в [math]Z^a[/math] больше, чем время [math]s'[/math] начала работы [math]k[/math]. Иначе, пусть [math]i[/math] - работа в [math]Z^a[/math] такая, что [math]r_i \le s'[/math]. Так как работы отсортированы в порядке неубывания дедлайна, то [math]d_i \le d_k[/math]. Таким образом, при перестановке работ [math]i[/math] и [math]k[/math] в [math]S^*[/math] суммарный вес не изменится. Продолжим этот процесс, пока новое расписание [math]S^*[/math] удовлетворяет нужному свойству. Получим: [math]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)[/math] , так как очевидно, что [math]Z^b \subseteq U_{k - 1} (s, s')[/math], и, по предположению, выполняется [math]Z^a \subseteq U_{k - 1} (s', e)[/math].

[math]\triangleleft[/math]

Прочие задачи

Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист, его автор, показал, что задача [math]1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i[/math] может быть решена за [math]O(n^{10})[/math].

См. также

• P1sumu
• 1pi1sumwu

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

• Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8