Участник:Qtr
Задача: |
<wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Работы можно прерывать, у каждой работы есть время появления $r_{i}$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1..n}{f_j(C_j)}$, где $C_j$ — время окончания выполнения $j$-ой работы, была минимальна.</wikitex> |
Задача является обобщением , но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
Содержание
Алгоритм
Работу будем обозначать просто ее номером
, при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — , время, требуемое для ее выполнения — . Множество ребер графа обозначается как .Препроцессинг
Для начала, модифицируем времена появления работ. Если работа топологической сортировки):
зависит от , то, очевидно, она не может быть начата раньше, чем закончится выполнение , поэтому нужно заменить на . Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядкеvoid modify({1...n})
rm = r
for u = 1 to n
for (u, v)
E
rm[v] = max(rm[v], rm[u] + p[u])
После выполнения этого алгоритма для любых двух работ
, таких, что зависит от , выполняется , поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.Разбиение на блоки
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных
.Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
Структура блока
struct Block int start // Время начала выполнения блока int time // Время, затрачиваемое на соответствующий блок int end // Время конца выполнения блока int[] jobs // Номера работ void add() // Добавляет работу в конец jobs[]
Алгоритм разбиения
Block[] blocks({1...n}) int j = 0 int t = 0 Block[] b for i = 1 to n if t < r[i] t = rm[i] j = j + 1 b[j].start = rm[i] b[j].time = 0 b[j].add(i) b[j].time = b[j].time + p[i] t = t + p[i] return b
Если алгоритм
вызывается от пустого множества, то считаем, что он возвращает также пустое множество.Определим время начала блока
как , а время конца — как .Лемма: |
Существует оптимальное расписание, такое, что все во все временные интервалы , соответствующие блокам , построенным алгоритмом , станок работает без простоя. |
Доказательство: |
Возьмем произвольное оптимальное расписание Возьмем некоторую работу , в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал , что в есть период простоя внутри (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за . , такую, что она начинается позже, чем в момент времени , не имеет в графе зависимостей предков, завершаемых позже, чем в момент и . Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент , было бы , и внутри блока был бы простой , что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени и полностью, либо частично заполнить простой ; так как — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством. |
Декомпозиция
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма
следующая: найдем работу , которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим в промежутки между ними, до них и после них, начиная с . Псевдокод этого алгоритма представлен ниже.int, int[] decompose(Block b, int[] schedule): int e = b.end // e — время завершения работ блока B. find l: f[l](e) = int ans = f[l](e) Block[] g = blocks( ) for i = 2 to b.size for j = g[i - 1].end to g[i].begin - 1 schedule[j] = l // Вставляем работу в расписание между блоками schedule[g[g.size].end to b.end - 1] = l for b[j] g ans = max(ans, decompose(b[j],schedule).first) return ans, schedule
Теорема: |
Расписание для блока, построенное алгоритмом , является корректным и оптимальным. |
Доказательство: |
Докажем сначала корректность. Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении на блоки существует не более одного блока , расположенного до момента времени — иначе после вставки в промежутки между блоками, выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока , находятся внутри интервала ; это относится и к блоку . Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем , будут помещены в блок , следует, что порядок выполнения будет правильным.Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строках 5-8 алгоритма, которая соответствует этому требованию, то условие выполняется. Найдем теперь нижнюю оценку на . Пусть — ответ для множества работ .Очевидно, для любой работы выполняется , значит, .Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке Отсюда следует , то . . По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки. |
Общий алгоритм
Выполним
, после чего разобъем все множество работ на блоки и для каждого блока запустим :int, int[] makeSchedule(Job[] jobs): int[] schedule // Расписание работ topSort(jobs) modify(jobs) Blocks[] b = blocks(jobs) int ans = for b[j] b ans = max(ans, decompose(b[j],schedule).first) return ans, schedule
Из доказанной ранее леммы следует, что
, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.Время работы
Теорема: |
Время работы алгоритма MakeSchedule — операций. |
Доказательство: |
Обозначим за время, необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:
Здесь - размер блока с номером , построенного алгоритмом Blocks(). Заметим, что .Если , то имеем:
Так как , то можно переписать неравенство в следующем виде:
Чтобы получить максимальную нижнюю оценку на , оценим снизу :Значит, при требуемое неравенство будет выполняться. |
См. также
Источники информации
- Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 63-67 стр. — ISBN 978-3-540-69515-8