1ripi1sumf — различия между версиями
Dominica (обсуждение | вклад) |
Dominica (обсуждение | вклад) |
||
Строка 56: | Строка 56: | ||
Отсортируем задания по неубыванию <tex>r_i</tex>, а дальше будем выполнять задания по мере появления. В полученном расписании работы будут идти в порядке <tex>4, 2, 1, 3</tex> и давать в ответе <tex>2^{1 + 1} + (2 + 1)^2 + 5(3 + 1) + (4 + 1) + 4 = 42 </tex>, что является оптимальным результатом. | Отсортируем задания по неубыванию <tex>r_i</tex>, а дальше будем выполнять задания по мере появления. В полученном расписании работы будут идти в порядке <tex>4, 2, 1, 3</tex> и давать в ответе <tex>2^{1 + 1} + (2 + 1)^2 + 5(3 + 1) + (4 + 1) + 4 = 42 </tex>, что является оптимальным результатом. | ||
− | ==Пример 2== | + | ===Пример 2=== |
Пусть у нас есть три задания, и каждое из них имеет время появления <tex>r_i = 0.</tex> Заданы функции <tex>f_i</tex>: | Пусть у нас есть три задания, и каждое из них имеет время появления <tex>r_i = 0.</tex> Заданы функции <tex>f_i</tex>: | ||
Строка 67: | Строка 67: | ||
Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем {{---}} не понятно, в каком порядке сортировать задания с одинаковым временем появления. | Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем {{---}} не понятно, в каком порядке сортировать задания с одинаковым временем появления. | ||
− | Тогда нучно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим: <tex>t_1 = 0, | + | Тогда нучно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим: <tex>t_1 = 0, t_2 = 1, t_3 = 2</tex>. |
Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях: | Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях: | ||
Строка 84: | Строка 84: | ||
В результате будет работы Венгерского алгоритма будет выбран порядок работ <tex>2, 3, 1</tex>, что даст лучший результат {{---}} <tex>19</tex>. | В результате будет работы Венгерского алгоритма будет выбран порядок работ <tex>2, 3, 1</tex>, что даст лучший результат {{---}} <tex>19</tex>. | ||
− | ==Пример 3== | + | |
+ | На этом примере хорошо видно, что решение, выбирающие в каждый момент времени <tex>t_i</tex> несделанную работу с минимальным значением f_i(t_i + 1) будет давать плохой результат. | ||
+ | |||
+ | ===Пример 3=== | ||
== См. также == | == См. также == |
Версия 04:53, 5 июня 2016
Для каждой работы задана монотонно неубывающая функция
. Необходимо минимизировать где каждая считается на значении времени завершения выполнения задания с номером .Содержание
Решение
Эта задача может быть решена сведением к решению задачи о назначениях. А именно, покажем, что решение задачи состоит в сопоставлении различным заданиям различных времен начала выполнения работы. Если сопоставляем работе время , то вклад в целевую функцию будет .
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего
различных времен начала работ. Следовательно, подобная задача может быть решена за .Поскольку
— монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые самых ранних для начала исполнения времен могут быть вычислены следующим алгоритмом :отсортиртировать по неубыванию времена появления= for =
Для того, чтобы найти оптимальное расписание, построим полный двудольный граф, в котором будут доли и ребра между ними:
Решив задачу о назначениях для данного графа, получим оптимальное расписание.
Доказательство корректности и оптимальности
Лемма: |
Пусть значения вычислены приведенным выше алгоритмом. Тогда существует оптимальное расписание в котором все задач распределены по всем временам |
Доказательство: |
Предположим, что в некоторое оптимальное расписание Из того, как в алгоритме выбирались значения для входят времена где а вместо времени используется какое-то другое. Из всех возможных таких оптимальных расписаний мы возьмем то, у которого будет максимально. следует, что — минимальное возможное время, большее в которое можно начать выполнять какое-нибудь из оставшихся заданий. Если во время в расписании не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени выполняется в позднее. Значит оно может быть перемещено в нашем расписании на время без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью . Значит из всех оптимальных расписаний нам подходят только те, в которых . |
Частный случай
В случае, когда все времена появлений заданий различны, оптимальное решение может быть посчитано за
.Поскольку любое задание выполняется за единицу времени, а все функции
являются неубывающими, то будет достаточно отсортировать работы по возрастанию времен появления и выполнять каждую работу как только она появится. Поскольку все различны, то промежутки выполнения работ не будут пересекаться — расписание будет корректным.Примеры
Пример 1
Даны четыре задания.
Отсортируем задания по неубыванию
, а дальше будем выполнять задания по мере появления. В полученном расписании работы будут идти в порядке и давать в ответе , что является оптимальным результатом.Пример 2
Пусть у нас есть три задания, и каждое из них имеет время появления
Заданы функции :
Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем — не понятно, в каком порядке сортировать задания с одинаковым временем появления.
Тогда нучно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим:
. Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях:
В результате будет работы Венгерского алгоритма будет выбран порядок работ
, что даст лучший результат — .На этом примере хорошо видно, что решение, выбирающие в каждый момент времени
несделанную работу с минимальным значением f_i(t_i + 1) будет давать плохой результат.Пример 3
См. также
Источники информации
- P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20