Изменения

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

Введем понятие "''вынужденного" '' дедлайна <tex>d'_i</tex>~--- — время, до которого необходимо выполнить <tex>i</tex>-ую работу, чтобы успетьвыполнить все работыиз <tex>S(i)</tex>, где <tex>S(i)</tex> — множество работ, зависящие от нее зависящих (не обязательно непосредственно)от <tex>i</tex>-ой работы.

Обозначим через $S(i)$~--- множество работ, зависящих от $i$-ой работы, а через <tex>g(i, d)</tex>~--- количество работ <tex>k</tex> из <tex>S(i)</tex>,таких что <tex>d'_k \le d</tex>, где <tex>k \in S(i)</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>. Используя для нахождения <tex>S(i)</tex> алгоритм Фишера-Мейерса, можно добиться лучшей асимптотики, чем наивным методом. Данный алгоритм будет описан ниже.После подсчета "вынужденных" дедлайнов, оптимальное расписание считается жадным алгоритмом.На каждом шаге на для обработки на станках выбираются работы с минимальным "вынужденным" дедлайном, для которых все необходимые

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