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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 60: Строка 60:
 
{{Утверждение #2
 
{{Утверждение #2
 
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
 
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex>~---расписание, построенное этим алгоритмом, где <tex>x(i)</tex>~--- время  
+
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex> {{---}} расписание, построенное этим алгоритмом, где <tex>x(i)</tex> {{---}} время  
 
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно  
 
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно  
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> работа с  
+
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> {{---}} такая работа с  
минимальным временем начала, удолетворяющая следующему условию: <tex>d'_i < x(i) + 1</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>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>k</tex>, такая что <tex>d'_k \le d'_i</tex> выполнена.
 
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
 
Выберем максимальное время <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</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\rceil\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>.
 
}}
 
}}

Версия 20:57, 16 июня 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]i[/math] на этом шаге была бы выбрана работа [math]j[/math], имеющая меньшее [math]d'[/math] и, по построению модифицированных дедлайнов, независимая от [math]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]j[/math], выполненные в период [math][t+1; x(i)][/math], а также, работа [math]i[/math], должны быть зависимы от [math]k[/math], потому что, иначе, только [math]j[/math] должна быть выполнена до момента времени [math]t+1[/math]. Так как было опоздание,

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

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

Значит, работа [math]k[/math] тоже опоздала, что противоречит минимальности выбора [math]x(i)[/math].
[math]\triangleleft[/math]