P2precpi1Lmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
==Описание алгоритма==
 
==Описание алгоритма==
 
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
 
Полагаем, что ребра в графе ориентированы от работы, к работам, зависимым от нее.
Введем понятие ''вынужденного'' дедлайна <tex>d'_i</tex> время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успеть
+
Введем понятие ''вынужденного'' дедлайна <tex>d'_i</tex> {{---}} максмальное время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успеть
 
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-ой работы.
 
выполнить все работы из <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящих (не обязательно непосредственно) от <tex>i</tex>-ой работы.
 
Заметим, что эта величина может принимать отрицательные значения.
 
Заметим, что эта величина может принимать отрицательные значения.
Строка 36: Строка 36:
 
{{Утверждение #1
 
{{Утверждение #1
 
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
 
|statement= В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с
"вынужденными" дедлайнами.
+
вынужденными дедлайнами.
|proof= <tex>\Leftarrow</tex> Так как "вынужденные" дедлайны меньше обычных, то в эту сторону утверждение очевидно.
+
|proof=  
<tex>\Rightarrow</tex> Напрямую следует из определения вынужденного дедлайна.
+
<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>.
 
}}
 
}}
  

Версия 06:15, 10 июня 2012

Описание алгоритма

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

Утверждение:
Пусть уже посчитаны работы для всех [math]j \in S(i)[/math]. Тогда, если [math]j \in S(i)[/math], то [math]i[/math]-ая работа должна быть закончена до [math]d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil[/math].
[math]\triangleright[/math]

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

[math]d'_j - \lceil \frac{g(i, d'_j)}{2} \rceil[/math].
[math]\triangleleft[/math]

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

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

Доказательство корректности

Утверждение:
В расписании с обычными дедлайнами нет опозданий тогда и только тогда, когда нет опозданий в расписании с вынужденными дедлайнами.
[math]\triangleright[/math]

[math]\Leftarrow[/math] Поскольку вынужденный дедлайн не нарушен, то, больший его обычный дедлайн, также не будет нарушен.

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

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

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

противоречит условии выбора [math]i[/math].
[math]\triangleleft[/math]
Утверждение:
Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
[math]\triangleright[/math]

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

ни один станок не простаивал в течении этого периода.
[math]\triangleleft[/math]