81
правка
Изменения
Нет описания правки
<tex dpi ="200"> 1 \mid prec,pmtn,r_i \mid f_{max}</tex> {{Задача|definition = Постановка задачи <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>}}
Задача <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
== Алгоритм ==
Работу будем обозначать просто ее номером (<tex> (i )</tex>), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r_i r[i]</tex>, время, требуемое для ее выполнения — <tex> p_i p[i] </tex>. Множество ребер графа обозначается как <tex> E </tex>.
=== Modify Идея алгоритма===Для началаБудем решать задачу рекурсивно. Разобьем множество работ на подмножества (блоки), модифицируем времена появления внутри которых не будет перерыва между выполнением работ. Если работа <tex> j </tex> зависит от <tex> i </tex>После этого для каждого из блоков найдем работу, токоторую выгоднее всего выполнить последней, очевидно, она не может быть начата раньшеудалим работу из соответствующего блока и повторим разбиение на подблоки для оставшихся работ. Пустые промежутки между подблоками, чем закончится выполнение </tex> i </tex>полученными из данного блока, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_jзаполним выбранной работой. Повторим рекурсивно для каждого из полученных подблоков. Как будет показано далее, r_i + p_i) </tex>данный алгоритм строит корректное и оптимальное расписание. АлгоритмМожно заметить, делающий эточто если на каждом этапе будет получаться всего один блок, представлен ниже (работы рассматриваются алгоритм выродится в порядке топологической сортировки):[[Правило_Лаулера|алгоритм Лаулера]].
=== Разбиение на блоки ===Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> rm_i </tex>. Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя. '''Структура блока''' '''struct''' Block '''int''' start <font color = "darkgreen">// Время начала выполнения блока</font> '''int''' time <font color = "darkgreen">// Время, затрачиваемое на соответствующий блок</font> '''int''' end <font color = "darkgreen"> // Время конца выполнения блока </font> '''int[]''' jobs <font color = "darkgreen">// Номера работ</font> '''void''' add() <font color = "darkgreen">// Добавляет работу в конец jobs[] </font> Нетрудно заметить, что переменная <tex>\mathrm{end}</tex> получается из суммы <tex>\mathrm{start}</tex> и <tex>\mathrm{time}</tex>. Используется для читаемости и уменьшения кода <tex>\mathrm{Decompose }</tex>. Можно воспринимать как макроподстановку. '''Алгоритм разбиения''' '''Block[]''' blocks('''int''' p[n], '''int''' rm[n]): '''int''' j =0 '''int''' t =0 <font color="darkgreen">// Переменная t указывает на время завершения последней работы </font> '''Block''' b[n] '''for''' i = 1 '''to''' nИдея следующая: допустим '''if''' t < rm[i] <font color="darkgreen">// Время появления очередной работы больше, чем время завершения последней </font> t = rm[i] <font color="darkgreen">// работы в блоке, не можем начать её делать. Создаём новый блок </font> j = j + 1 b[j].start = rm[i] b[j].time = 0 b[j].add(i) <font color="darkgreen">// Добавляем к последнему блоку рассматриваемую работу, </font> b[j].time = b[j].time + p[i] <font color="darkgreen">// увеличиваем суммарное время внутри блока и текущее время</font> t = t + p[i] '''return''' b Если значение <tex>n</tex> равно нулю, то считаем, что алгоритм <tex>\mathrm{Blocks}</tex> возвращает пустое множество. Определим время начала блока <tex> B_j </tex> как <tex>s_j = \min\limits_{i \in B_j} rm_i </tex>, а время конца — как <tex> e_j = s_j + \sum\limits_{i \in B_j} p_i </tex>. {{Лемма|statement=Существует оптимальное расписание, такое, что все во все временные интервалы <tex> [s_j; e_j] </tex>, соответствующие блокам <tex> B_j </tex>, построенным алгоритмом <tex>\mathrm{Blocks}</tex>, станок работает без простоя.|proof=Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </tex>. Возьмем некоторую работу <tex> i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> rm_i \leqslant s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \min\limits_{k \in T} rm_k > s </tex>, и внутри блока <tex> B_j </tex> был бы простой <tex> [s_j; r] </tex>, что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени <tex> s </tex> и полностью, либо частично заполнить простой <tex> [s; e] </tex>; так как <tex> f_i </tex> — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.}} === Декомпозиция ===Допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая: найдем работу <tex>i</tex>, которую выгодно выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между этими блокаминими, до них и после них, начиная с <tex> r_i rm_i </tex>. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение <tex>f_{max}</tex>. '''<tex>\langle</tex>int, int[]<tex>\rangle</tex>''' decompose('''Block''' b, '''int[]''' schedule): '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B</font> find l: f[l](e) = <tex> \min \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex> '''int''' ans = f[l](e) b.jobs.remove(l) '''Block[]''' g = blocks(b.jobs.p, b.jobs.rm) '''for''' i = 2 '''to''' g.size schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen"> // Вставляем работу в расписание между блоками</font> schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen"> // Нужно учесть пропуски перед первым и </font> schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блоков соответственно</font> '''for''' b <tex>\in</tex> g ans = max(ans, decompose(b, schedule).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex> {{Теорема|statement=Расписание для блока, построенное алгоритмом <tex>\mathrm{Decompose}</tex>, является корректным и оптимальным.|proof=Докажем сначала корректность. Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> rm_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным. Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется в строках 5-9 алгоритма, которые соответствуют этому требованию, то условие выполняется. Найдем теперь нижнюю оценку на <tex> f_{max} </tex>.Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>. Очевидно, для любой работы <tex> j \in J </tex> выполняется <tex> f_{max}(J) \geqslant f_{max}(J \setminus j) </tex>, значит, <tex> f_{max}(J) \geqslant \max\limits_{j \in J} f_{max}(J \setminus j) </tex>. Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \geqslant f_l(e) </tex>. Отсюда следует <tex> f_{max}(J) \geqslant \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.}}
=== Общий алгоритм ===
Выполним <tex>\mathrm{Modify()}</tex>, после чего разобъем все множество работ на блоки и для каждого блока запустим <tex>\mathrm{Decompose}</tex>: <tex>\langle</tex>'''int''', '''int[]'''<tex>\rangle</tex> makeSchedule('''int[]''' jobs): '''int'''[] schedule <font color="darkgreen">// Расписание работ</font> jobs = topSort(jobs) '''int[]''' rm = modify(jobs) ''sort jobs by'' rm ''values'' '''Blocks[]''' b = blocks(jobs.p, rm) '''int''' ans = <tex> -\infty </tex> '''for''' block <tex>\in</tex> b ans = max(ans, decompose(block,schedule).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>
== Время работы ==