1ripi1sumf
Версия от 02:57, 16 мая 2016; Dominica (обсуждение | вклад)
Для каждой работы задана монотонно неубывающая функция
. Необходимо минимизировать где каждая считается на значении времени завершения выполнения задания с номером .Содержание
Решение
Эта задача может быть решена сведением к решению задачи о назначениях. А именно, покажем, что решение задачи состоит в сопоставлении различным заданиям различных времен начала выполнения работы. Если сопоставляем работе время , то вклад в целевую функцию будет .
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего
различных времен начала работ. Следовательно, подобная задача может быть решена за .Поскольку
— монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые самых ранних для начала исполнения времен могут быть вычислены следующим алгоритмом :отсортиртировать по неубыванию времена появления= for =
Для того, чтобы найти оптимальное расписание, построим полный двудольный граф, в котором будут доли и ребра между ними:
Решив задачу о назначениях для данного графа, получим оптимальное расписание.
Доказательство корректности и оптимальности
Лемма: |
Существует оптимальное расписание в котором все задач распределены по всем временам , которые выбирает приведенный выше алгоритм. |
Доказательство: |
Предположим, что в некоторое оптимальное расписание Из того, как в алгоритме выбирались значения для входят времена где и из всех возможных оптимальных расписаний мы возьмем то, у которого будет максимально. следует, что — минимальное возможное время, большее в которое можно начать выполнять какое-нибудь из оставшихся заданий. Если во время в расписании не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени выполняется в позднее. Значит оно может быть перемещено в нашем расписании на время без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью . Значит из всех оптимальных расписаний нам подходят только те, в которых . |
См. также
Источники информации
- P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20