Редактирование: Участник:Dominica
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
<tex dpi = "200" >1 \mid\mid \sum w_i U_i</tex> | <tex dpi = "200" >1 \mid\mid \sum w_i U_i</tex> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлаин <tex>d_i</tex> и стоимось выполнения этой работы <tex>w_i \geqslant 0</tex> | |
| − | + | Необходимо сотавить такое расписание, что <tex>\sum w_i U_i</tex> будет минимальна. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Решение== | ==Решение== | ||
| − | |||
| − | + | {{Лемма | |
| − | + | |id=lemma1 | |
| − | + | |statement= Пусть все работы отсортированы в порядке неубывания дедлайнов <tex>d_i</tex>. | |
| − | + | Тогда существует оптимальное расписание вида <tex>i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n </tex>, где <tex>i_1 < i_2 < \ldots < i_s </tex> {{---}} номера работ, которые успеют выполниться вовремя, а <tex>i_{s+1}, \ldots, i_n </tex> {{---}} номера просроченных работ. | |
| + | |proof= Это можно показать следующим образом | ||
| + | }} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
отсортиртировать работы по неубыванию времен дедлайнов <tex>d_i</tex> | отсортиртировать работы по неубыванию времен дедлайнов <tex>d_i</tex> | ||
| Строка 65: | Строка 24: | ||
F_0(t) = 0 | F_0(t) = 0 | ||
'''for''' <tex>j = 1</tex> '''to''' <tex>n</tex> | '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex> | ||
| + | '''begin''' | ||
'''for''' <tex>t = 0</tex> '''to''' <tex>d_j</tex> | '''for''' <tex>t = 0</tex> '''to''' <tex>d_j</tex> | ||
| − | '''if''' <tex> F_{j-1} | + | '''if''' <tex> F_{j-1} + w_j < F_{j-1}(t-p_j) </tex> |
<tex> F_j(t) = F_{j-1}(t) + w_j </tex> | <tex> F_j(t) = F_{j-1}(t) + w_j </tex> | ||
'''else''' | '''else''' | ||
| Строка 72: | Строка 32: | ||
'''for''' <tex>t = d_j + 1</tex> '''to''' <tex>T</tex> | '''for''' <tex>t = d_j + 1</tex> '''to''' <tex>T</tex> | ||
<tex> F_j(t) = F_{j}(d_j) </tex> | <tex> F_j(t) = F_{j}(d_j) </tex> | ||
| + | '''end''' | ||
| − | |||
| − | |||
| − | |||
t = d_n | t = d_n | ||
L = \varnothing | L = \varnothing | ||
'''for''' <tex>j = n</tex> '''downto''' <tex>1</tex> | '''for''' <tex>j = n</tex> '''downto''' <tex>1</tex> | ||
| + | '''begin''' | ||
<tex>t = \min(t, d_j)</tex> | <tex>t = \min(t, d_j)</tex> | ||
'''if''' <tex> F_j(t) = F_{j-1}(t) + w_j </tex> | '''if''' <tex> F_j(t) = F_{j-1}(t) + w_j </tex> | ||
<tex> L = L \cup \{j\} </tex> </tex> | <tex> L = L \cup \{j\} </tex> </tex> | ||
'''else''' | '''else''' | ||
| − | <tex> t = t - p_j </tex> | + | <tex> t = t - p_j </tex> |
| + | '''end''' | ||
==Доказательство корректности и оптимальности== | ==Доказательство корректности и оптимальности== | ||
| Строка 89: | Строка 49: | ||
{{Лемма | {{Лемма | ||
|id=lemma1 | |id=lemma1 | ||
| − | |statement= | + | |statement= Существует оптимальное расписание <tex>S</tex> в котором все <tex>n</tex> задач распределены по всем временам <tex>t_i (i = 1\ldots n)</tex>, которые выбирает приведенный выше алгоритм. |
| − | + | |proof= Предположим, что в некоторое оптимальное расписание <tex>S</tex> входят времена <tex> t_1 \ldots t_j, </tex> где <tex> j < n</tex> и из всех возможных оптимальных расписаний мы возьмем то, у которого <tex>j</tex> будет максимально. | |
| − | |proof= | + | Из того, как в алгоритме выбирались значения для <tex>t_i</tex> следует, что <tex>t_{j + 1}</tex> {{---}} минимальное возможное время, большее <tex>t_j,</tex> в которое можно начать выполнять какое-нибудь из оставшихся заданий. Если во время <tex>t_{j+1}</tex> в расписании <tex>S</tex> не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени <tex>t_{j+1}</tex> выполняется в <tex>S</tex> позднее. Значит оно может быть перемещено в нашем расписании <tex>S</tex> на время <tex>t_{j+1}</tex> без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью <tex>j</tex>. Значит из всех оптимальных расписаний нам подходят только те, в которых <tex>j = n</tex>. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
==См. также == | ==См. также == | ||
* [[Классификация задач]] | * [[Классификация задач]] | ||
| − | * [[ | + | * [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] |
| − | |||
| − | |||
| − | |||
== Источники информации == | == Источники информации == | ||
| − | * P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. | + | * P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20 |
