Викиконспекты - Вклад участника [ru]

P2precpi1Lmax

2012-06-18T08:25:12Z

217.66.156.102: /* Ссылки */

==Описание задачи==
Даны два одинаковых станка, на которых необходимо обработать <tex>n</tex> деталей.
Каждую деталь можно обрабатывать на любом станке. Время, необходимое для обработки любой детали,
одинаково и равно одному. Для каждой детали известны момент времени, до
которого необходимо закончить работу над этой деталью — <tex>d_i</tex>, а также номера деталей,
зависимых от нее. Необходимо минимизировать максимальное опоздание, где опоздание рассчитывается как
разность между временем, когда была закончена обработка детали, и временем дедлайна для этой
детали.

==Описание алгоритма==
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
Введем понятие ''вынужденного'' дедлайна <tex>d'_i</tex> {{---}} максмальное время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успеть
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-ой работы.
Заметим, что эта величина может принимать отрицательные значения.
Обозначим через <tex>g(i, d)</tex> количество работ <tex>k</tex> из <tex>S(i)</tex>,
таких что <tex>d'_k \le d</tex>.

{{Утверждение
|statement=Пусть уже посчитаны работы для всех <tex>j \in S(i)</tex>. Тогда, если <tex>j \in S(i)</tex>, то <tex>i</tex>-ая работа
должна быть закончена до <tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
|proof=Рассмотрим все работы <tex>k \in S(i)</tex>, для которых <tex>d'_k \le d'_j</tex>. Все эти работы будут выполнены после
окончания обработки детали с номером <tex>i</tex>. Для них <tex>d'_k \le d'_j</tex>. Пусть работу <tex>i</tex> закончили выполнять в
момент времени <tex>d</tex>. Нужно до момента времени <tex>d'_j</tex> выполнить ещё <tex>g(i, d'_j)</tex> работ.
Так как в нашем распоряжении находятся две машины, то время их выполнения будет не менее, чем <tex>\lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
Поскольку необходимо выполнить все эти работы до <tex>d'_j</tex>, то <tex>i</tex>-ая работа должна быть закончена до момента времени
<tex>d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil</tex>.
}}

Тогда финально получаем формулу для вычисления «вынужденного» дедлайна для <tex>i</tex>-ой работы:
<tex>d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil\}\}</tex>, где <tex>j \in S(i)</tex>.
Для вершин, исходящая степень которых равна нулю, по определению вынужденного дедлайна, считаем его равным обычному дедлайну.
Для подсчета вынужденных дедлайнов будем поддерживать список <tex>L</tex>, содержащий вершины, отсортированные в порядке
неубывания ''дедлайнов''. ''Дедлайн'' равен вынужденному дедлайну, если он уже посчитан, и обычному {{---}} в противном случае.
Будем рассматривать вершины в порядке, обратном топологической сортировке графа, то есть, начиная с вершин нулевой исходящей степени.
Пусть на текущем шаге мы рассматриваем работу с
номером <tex>i</tex>. Перебирая вершины из <tex>S(i)</tex> в порядке списка <tex>L</tex>, пересчитываем вынужденный дедлайн для
<tex>i</tex>-ой вершины по формуле, указанной выше, после чего обновляем дедлайн этой вершины в списке <tex>L</tex>.

После подсчета вынужденных дедлайнов, оптимальное расписание считается жадным алгоритмом.
На каждом шаге на для обработки на станках выбираются работы с минимальным вынужденным дедлайном, для которых все необходимые
работы уже выполнены. Одновременно с этим считается максимальное опоздание.

==Доказательство корректности==
{{Утверждение
|about=#1
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
вынужденными дедлайнами.
|proof=
<tex>\Leftarrow</tex> Поскольку вынужденный дедлайн не нарушен, то, больший его обычный дедлайн, также не будет нарушен.

<tex>\Rightarrow</tex> По определению вынужденного дедлайна, <tex>d'_i</tex> {{---}} максимальное время окончания работы
<tex>i</tex>, при котором
ещё можно успеть выполнить все работы из <tex>S(i)</tex>. Значит, если для <tex>i</tex> был нарушен вынужденный дедлайн,
то не все работы из <tex>S(i)</tex> выполнены вовремя, то есть
был нарушен хотя бы один обычный дедлайн, что противоречит условию.

Более формально, пусть был нарушен вынужденный дедлайн. Найдём работу <tex>i</tex> с нарушенным вынужденным дедлайном,
такую, что <tex>\forall k \in S(i) : d'_k </tex> {{---}} не нарушено. Это всегда можно сделать в силу ацикличности графа.
Рассмотрим формулу для подсчёта вынужденного дедлайна:
<tex>d'_i = \min\{d_i, \min\{d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil\}\}</tex>, где <tex>j \in S(i)</tex>.

Минимум достигся либо на <tex>d_i</tex>, что невозможно в силу того, что обычные дедлайны не нарушены, либо на каком-то
<tex>j \in S(i)</tex>. В этом случае, <tex>d'_i = d'_j - \lceil\frac{g(i, d'_j)}{2}\rceil</tex>.
Значит, если <tex>d'_i</tex> нарушено, то будет также нарушен вынужденный дедлайн для какого-то <tex>k \in S(i)</tex>,
так как осталось меньше, чем <tex>d'_j - d'_i > \lceil \frac{g(i, d'_j)}{2} \rceil</tex> единиц времени. Это
противоречит условии выбора <tex>i</tex>.
}}

{{Утверждение
|about=#2
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex> {{---}} расписание, построенное этим алгоритмом, где <tex>x(i)</tex> {{---}} время
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> {{---}} такая работа с
минимальным временем начала, то есть, удолетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>.
Следуя алгоритму, в каждый момент времени
<tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \le d'_i</tex> должна
быть выполнена, так как, иначе, по алгоритму, вместо <tex>i</tex> на этом шаге была бы выбрана работа <tex>j</tex>, имеющая меньшее
<tex>d'</tex> и, по построению модифицированных дедлайнов, независимая от <tex>i</tex>.
Рассмотрим два случая.

'''Первый случай''': в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \le d'_i</tex> выполнена.
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \le d'_i</tex>, кроме того,
ни один станок не простаивал в течении этого периода. Все работы <tex>j</tex>, выполненные в период <tex>[t+1; x(i)]</tex>, а также,
работа <tex>i</tex>, должны быть зависимы от <tex>k</tex>, потому что, иначе, только <tex>j</tex> должна быть выполнена до
момента времени <tex>t+1</tex>. Так как было опоздание,

<tex>\left\lceil \frac{g'(k, d'_i)}{2} \right\rceil \ge \left\lceil\frac{2(x(i) - t) - 1}{2} \right\rceil = x(i) - t</tex>

Из определения вынужденных дедлайнов,
<tex>d'_k \le d'_i - \left\lceil \frac{g(k, d'_i)}2 \right\rceil</tex>
<tex>\le d'_i - x(i) + t < x(i) + 1 - x(i) + t = t + 1</tex>

Значит, работа <tex>k</tex> тоже опоздала, что противоречит минимальности выбора <tex>x(i)</tex>.

'''Второй случай''': в каждый момент времени такой, что <tex>0 \le t < x(i)</tex> выполняются две работы. По написанному выше,
для всех этих работ <tex>j</tex>, выполняется <tex>d'_j \le d'_i</tex>.

Тогда есть хотя бы <tex>2x(i) + 1</tex> работ таких, что <tex>d'_j \le d'_i < x(i) + 1</tex>.
Их невозможно сделать за <tex>x(i)</tex> времени, а значит, в каждом таком расписании есть опоздание.
}}

{{Утверждение
|about=#3
|statement=При сдвиге всех <tex>d_i</tex> на <tex>l</tex>, <tex>d'_i</tex> сдвинутся также на это число.
|proof=
Для работ, от которых ничего не зависит, по определению <tex>d'_i = d_i</tex>, а, значит, для них утверждение верно.

Рассмотрим остальные в порядке топологической сортировки. Тогда, по индукции, для всех потомков рассматриваемой вершины
утверждение будет верно. Также, так как <tex>d'_k + l \le d'_j + l \iff d'_k \le d'_j</tex>,

<tex>(d_i + l)' = \min\{d_i + l, \min\{d'_j + l - \lceil\frac{g(i, d'_j)}{2}\rceil\}\}</tex> для <tex>j \in S(i)</tex>.

Вынеся за минимум общее слагаемое, по определению вынужденных дедлайнов, получим искомую формулу <tex>(d_i + l)' = d'_i + l</tex>
}}

{{Теорема
|statement=Алгоритм строит оптимальное расписание
|proof=
Пускай каким-то образом было вычислено оптимальное значение <tex>l_{max}</tex>. Тогда, по второму утверждению, если сдвинуть все
дедлайны на <tex>l_{max}</tex>, то алгоритм получит для них оптимальное расписание.

По третьему утверждению, для любого сдвига будет получено расписание с одним и тем же опозданием. Значит,
для сдвига на <tex>l_{max}</tex> оно также будет оптимальным.

В силу того, что для любого сдвига будет построено оптимальное расписание, алгоритм находит оптимальное расписание.
}}

==Сложность алгоритма==
В алгоритме требуется знать для двух произвольных работ, зависит ли, возможно, не непосредственно, одна от другой. Для этого нужно транзитивно замкнуть граф по отношению зависимости. Это можно сделать несколькими способами. Первый и самый простой {{---}} за <tex>O(n^3)</tex> алгоритмом Флойда-Уоршалла. Второй {{---}} при помощи метода четырех русских за <tex>O(\frac{n^3}{\log n})</tex>. Третий {{---}} применить алгоритм Фишера-Мейера для построения замыкания графа за <tex>O(n^{\log_2 7})</tex>.

При подсчете вынужденных дедлайнов, за <tex>O(n)</tex> считается вынужденный дедлайн одной работы. Так как всего работ <tex>n</tex>, суммарное время подсчета вынужденных дедлайнов {{---}} <tex>O(n^2)</tex>.

При, непосредственно, составлении расписания, на каждом шаге за <tex>O(n)</tex> обрабатываются одна или две работы. Значит, все работы будут обработаны также за <tex>O(n^2)</tex>.

Итоговая сложность {{---}} <tex>O(TrCl + n^2)</tex>.

==Ссылки==
[http://rjlipton.files.wordpress.com/2009/10/matrix1971.pdf Алгоритм Фишера-Мейера]

P2precpi1Lmax

2012-06-18T08:22:42Z

217.66.156.102:

Opi1sumu

2012-06-18T08:00:28Z

217.66.156.102:

==Описание задачи==
Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить
в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному.
Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ.

==Описание алгоритма==
Отсортируем работы в порядке невозрастания дедлайнов.

{{Утверждение
|statement=Если в оптимальном расписании можно сделать <tex>k</tex> работ, то можно сделать первые <tex>k</tex> работ.
|proof=Пусть в оптимальном расписании были сделаны работы <tex>i_1, i_2, \ldots, i_k</tex>. Докажем, что существует
оптимальное расписание, в котором сделаны работы <tex>1, 2, \ldots, k</tex>. Пусть работы <tex>i_1, i_2, \ldots, i_k</tex>
тоже отсортированы в порядке неубывания дедлайна. Тогда <tex>d_{i1} \le d_1, d_{i2}\le d_2, \ldots, d_{ik}\le d_{k}</tex>.
Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.
}}

{{Определение
|definition=Обозначим за ''тайм-слот t'' множество из не более, чем <tex>m</tex> различных чисел {{---}}
номера работ, которые мы хотим выполнить в момент времени <tex>t</tex>.
}}

Введем тайм-слот для каждого момента времени от <tex>0</tex> до <tex>d_n</tex>.
Каждую работу будем пытаться сделать как можно позже. Будет рассматривать работы в порядке невозрастания дедлайнов.
<tex>i</tex>-ю работу попытаемся добавить в тайм-слоты с <tex>d_i - m + 1</tex> по <tex>d_i</tex>.
После добавления некоторые тайм-слоты могли переполниться (тайм-слот переполнился, если в нём уже находилось
<tex>m</tex> работ, и в него добавили <tex>m+1</tex>-ю).
Для переполнившегося тайм-слота найдём найдем самый правый левее него, который ещё не переполнился и перекинем работу,
которой там еще нет, в него. Так как в нем меньше элементов, то, по принципу Дирихле, это можно сделать.

{{Утверждение
|statement=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
переполнился нулевой тайм-слот.
|proof=
<tex>\Rightarrow</tex>
Расписания не существует, а значит, никакой алгоритм его не найдет.

<tex>\Leftarrow</tex>
Пусть при добавлении <tex>k+1</tex>-й работы произошло переполнение нулевого тайм-слота.

Рассмотрим алгоритм добавления в тайм-слоты: работа <tex>i</tex>добавляется в тайм-слоты <tex>[d_i - m + 1; d_i]</tex>, после чего из переполнившихся работы перебрасываются в более ранние. Временно разрешим хранить в тайм-слоте сколь угодно много работ: отменим перебрасывание. Посмотрим на то, что получилось. Так как работу нельзя выполнять одновременно на двух станках, то ни одну единицу работы отсрочить нельзя. Будем рассматривать тайм-слоты в порядке уменьшения времени. Если в очередном тайм-слоте <tex>t</tex> в данный момент больше, чем <tex>m</tex> работ, то остаток нужно перекинуть на какие-то более ранние тайм-слоты. Заметим, что выгоднее перекинуть на наиболее поздние тайм-слоты: более ранние тайм-слоты могут понадобиться для перекидываний с тайм-слотов, идущих раньше просматриваемого. .

Также заметим, что алгоритм перекидывания работ таков, что итоговое распределение количеств работ в соответствующих тайм-слотах не зависит от того, в каком порядке обрабатывались переполнившиеся тайм-слоты.

При рассмотрении очередного переполнившегося тайм-слота мы необходимо должны куда-то перекинуть несколько работ из него. Так как перекидывание происходит в тайм-слот с наибольшим допустимым временем, то то, что неоходимо перекинуть что-то из нулевого, влечет то, что не существует расписания, в котором можно успеть выполнить все эти работы
}}

Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить. Обозначим его за <tex>k</tex>.

Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным
количеством паросочетаний.

Построим двудольный граф. В левой доле вершинам будут соответствоввать работы, в правой {{---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>.

Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза, и ни в один момент времени не выполняется более одной работы.

Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ.

Достроим граф до регулярного степени <tex>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.
Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями.

При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ.

==Оценка сложности алгоритма==
Рассмотрим добавление очередной работы в тайм-слоты. За <tex>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>O(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>.

Достроение графа до регулярного делается за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество ребер в нем. Количество ребер в регулярном двудольном графе <tex>E = Vd</tex>, где <tex>V</tex> {{---}} количество вершин в одной из долей, а <tex>d</tex> {{---}} степень. Количество вершин в правой доле {{---}} <tex>O(t) = O(nm)</tex>. Значит, граф будет построен за <tex>O(nm^2)</tex>, так как степень каждой вершины {{---}} <tex>m</tex>.

Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.