Что проверяет задание

В файле - таблица процессов: ID, время выполнения и список ID процессов, от которых данный процесс зависит (0 - независимый). Процесс B зависит от процесса A, если B нужны результаты A: B может начаться только после того, как A завершился. Независимые процессы выполняются параллельно, сколько угодно одновременно. Приостанавливать процесс нельзя: начавшись, он идёт непрерывно всё своё время.

Вопросы бывают такие:

• за какое минимальное время завершится вся совокупность процессов;
• через какое время завершатся N процессов, сколько процессов завершится за первые T мс;
• сколько процессов выполняется на N-й миллисекунде или в момент t;
• самый длинный отрезок времени, когда одновременно выполняются не менее K процессов (или наибольшее возможное их число).

Задание решается в электронной таблице (LibreOffice Calc или Excel) без программы: один столбец с формулой окончания процесса, протягивание, затем формула под вопрос.

Определения

Процесс - отрезок времени фиксированной длительности. Он либо ещё не начат, либо выполняется непрерывно, либо уже завершён.

Зависимость - отношение «раньше»: процесс B имеет зависимость A, если B нельзя начать раньше окончания A. Зависимости образуют ациклический граф: по стрелкам A → B нельзя вернуться в тот же процесс.

Раннее начало процесса - самый ранний момент, когда завершены все его зависимости. Раннее окончание - раннее начало плюс длительность.

Критический путь - самая длинная по суммарному времени цепочка зависимых процессов. Её длина равна минимальному времени выполнения всей совокупности.

Резерв времени - на сколько можно задержать процесс, не сдвигая окончание всей совокупности. У процессов критического пути резерва нет.

Зависимости по столбцам

В третьем столбце файла записано «0», один ID или список через точку с запятой, например «3;7;12». Формуле нужен каждый ID в своей ячейке:

1. Выделите столбец C (зависимости).
2. Данные → Текст по столбцам, разделитель - точка с запятой (в Excel: Данные → Текст по столбцам → с разделителями → «точка с запятой»).
3. ID разойдутся по столбцам C, D, E, … Посмотрите, сколько столбцов заняла самая длинная строка: столько слагаемых будет внутри МАКС.

Справа от столбца C должно быть пусто, иначе разнесённые ID затрут данные. Если у каждого процесса не больше одной зависимости, разносить ничего не нужно.

Окончание процесса

Процесс начинается, как только завершилась последняя из его зависимостей:

окончание = время процесса + МАКС(окончания его зависимостей)

У независимого процесса начало 0, окончание равно его времени.

Пусть ID - в столбце A, время - в B, зависимости разнесены по C и D, а окончание пишем в E. Тогда в E2:

=B2+МАКС(ЕСЛИОШИБКА(ВПР(C2; $A$2:$E$100; 5; 0); 0); ЕСЛИОШИБКА(ВПР(D2; $A$2:$E$100; 5; 0); 0))

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

• ВПР(C2; $A$2:$E$100; 5; 0) ищет в первом столбце таблицы ID из C2 и берёт значение из 5-го столбца - окончание этого процесса. Последний аргумент 0 - точное совпадение.
• ЕСЛИОШИБКА(…; 0): для «0» и пустой ячейки ВПР процесс не находит и выдаёт ошибку - подставляем 0.
• МАКС(…) - самая поздняя из зависимостей, то есть начало процесса.
• B2+ - плюс собственное время.
• Диапазон $A$2:$E$100 закреплён знаками $, чтобы при протягивании он не съезжал; ячейки C2 и D2 не закреплены - в каждой строке свои.

Формула ссылается на столбец окончаний, в котором стоит сама. Циклической ссылки нет: процесс берёт окончания других процессов, а граф зависимостей ациклический. Таблица сама посчитает ячейки в нужном порядке, даже если зависимость записана ниже по списку.

Если по условию зависимый процесс может начаться только через G мс после окончания зависимости, пауза прибавляется к найденному окончанию внутри ЕСЛИОШИБКА: ЕСЛИОШИБКА(ВПР(C2; $A$2:$E$100; 5; 0)+G; 0). У независимого процесса ВПР даёт ошибку, и пауза не добавляется.

Начало процесса

Начало = окончание − время: в соседнем столбце =E2-B2 и протягиваем.

Процесс занимает на шкале времени полуинтервал [начало; окончание): в момент начала он уже выполняется, в момент окончания - уже нет. Если один процесс кончается в 4 мс, а другой в 4 мс начинается, одновременно они не идут.

Нумерация миллисекунд с 1. Если в условии сказано «на N-й мс» и «нумерация миллисекунд начинается с 1», то N-я мс - это отрезок [N − 1; N). Процесс идёт на N-й мс, если его начало не больше N − 1, а окончание больше N − 1. Процесс, закончившийся в момент N, завершился на N-й мс.

Время всей совокупности

Вся совокупность завершится, когда завершится последний процесс: =МАКС(E2:E100) по столбцу окончаний.

Это длина критического пути. Быстрее нельзя, даже если параллельно идёт сколько угодно процессов: каждый процесс цепочки ждёт предыдущий. Чтобы увидеть сам путь, начните с процесса с наибольшим окончанием и идите назад - каждый раз к зависимости с наибольшим окончанием.

Сколько процессов завершится

Все такие вопросы - по столбцу окончаний (и начал), когда каждый процесс стартует в самое раннее время.

• Через какое время завершатся N процессов: N-е по возрастанию окончание - =НАИМЕНЬШИЙ(E2:E100; N).
• Сколько процессов завершится за первые T мс: окончание не больше T - =СЧЁТЕСЛИ(E2:E100; "<=T"). Процесс, закончившийся ровно в момент T, успел.
• Сколько процессов не успеет за T мс: =СЧЁТЕСЛИ(E2:E100; ">T").
• Несколько условий сразу (начнётся не раньше a и закончится не позже b): =СЧЁТЕСЛИМН(F2:F100; ">=a"; E2:E100; "<=b"), где F - столбец начал.
• Окончание конкретного процесса - его ячейка в столбце окончаний.

Шкала времени

Чтобы узнать, сколько процессов идёт в каждый момент, строят шкалу времени: столбец моментов 0, 1, 2, … до наибольшего окончания минус 1. Первый момент - 0, ниже =H2+1 и протягиваем.

Рядом для каждого момента t считаем процессы, у которых начало не позже t и окончание позже t:

=СЧЁТЕСЛИМН($F$2:$F$100; "<="&H2; $E$2:$E$100; ">"&H2)

Диапазоны закреплены, момент H2 - нет. Условие окончания строгое: ">", потому что в момент окончания процесс уже не идёт.

Все времена целые, поэтому между соседними целыми моментами число идущих процессов не меняется: строка шкалы для момента t описывает весь отрезок [t; t + 1).

• Сколько процессов идёт на N-й мс - строка момента N − 1 (или сразу одна формула СЧЁТЕСЛИМН с числом N − 1 вместо H2).
• Наибольшее число одновременно идущих процессов - =МАКС столбца счётчика.

Если шкала длинная (тысячи моментов), удобнее заполнить её через Лист → Заполнить ячейки → Заполнить ряды, а формулы протянуть двойным щелчком по маркеру заполнения.

Самый длинный отрезок

Самый длинный непрерывный отрезок, когда одновременно идут не менее k процессов, считает столбец «подряд» рядом со счётчиком:

• в первой строке =ЕСЛИ(I2>=k; 1; 0);
• ниже =ЕСЛИ(I3>=k; J2+1; 0) и протягиваем.

Условие выполнено - на 1 больше, чем строкой выше; нарушено - сброс в 0. Каждый момент - 1 мс, поэтому =МАКС столбца «подряд» - длина самого длинного отрезка.

Если нужно «ровно k процессов», в условии =k вместо >=k. Если нужна суммарная длительность (отрезки с паузами складываются), достаточно =СЧЁТЕСЛИ по столбцу счётчика.

Если сказано, что каждый процесс начинается в самое раннее время (или время завершения каждого процесса минимально), шкала строится по ранним началам и окончаниям - и это ответ.

Сдвиг процессов

Формулировка «в течение которого возможно одновременное выполнение K процессов, при условии, что все независимые процессы могут выполняться параллельно» разрешает задерживать процессы: процесс не обязан стартовать сразу, как только завершились его зависимости. Задерживать можно сколько угодно, лишь бы каждый процесс начинался не раньше окончания всех своих зависимостей.

Как пользоваться этой свободой:

1. Найдите ранние начала и окончания, как обычно, и постройте по ним шкалу: это отправная точка.
2. Посмотрите на ветки, которые друг от друга не зависят (независимые цепочки процессов). Их можно сдвигать целиком, чтобы они шли одновременно с другими ветками.
3. Внутри отрезка процессы могут сменять друг друга: если в одной «линии» процесс кончается, а следующий в ней же сразу начинается, число идущих процессов не падает. Так цепочка A → B держит линию занятой время A + время B.
4. Отрезок длится, пока заняты не меньше K линий одновременно, и обрывается, когда кончается самая короткая из них.

В таблице это делается двумя новыми столбцами: «Новое начало» (сначала копия ранних начал, потом у сдвинутых процессов вписываем новое начало числом) и «Новое окончание» = новое начало + время. Шкала и столбец «подряд» строятся по новым столбцам. Проверьте, что каждый сдвинутый процесс начинается не раньше окончания своих зависимостей.

Наибольшее число одновременно

Одновременно могут идти только процессы, которые друг от друга не зависят, даже через цепочку: если A → C → B, то A и B никогда не идут вместе. Поэтому наибольшее число процессов, которые можно запустить одновременно (со сдвигами), - размер самого большого набора попарно независимых процессов.

Когда в вопросе «одновременное выполнение максимального количества процессов», сначала найдите это количество (набор попарно независимых процессов), потом - самый длинный отрезок, когда идёт именно столько процессов.

Если же каждый процесс стартует в самое раннее время, наибольшее число одновременно - просто максимум счётчика на шкале времени.

Окончание всех минимально

Формулировка «а время окончания работы всех процессов минимально» тоже разрешает задержки, но только такие, после которых вся совокупность заканчивается за своё минимальное время (длину критического пути).

Насколько можно задержать процесс, говорит его резерв: позднее начало минус раннее. Позднее начало считают с конца: процесс должен закончиться не позже, чем начинается самый ранний из зависящих от него процессов (в их поздних сроках), а последний - не позже общего окончания. У процессов критического пути резерв 0, двигать их нельзя.

Дальше - как при сдвиге процессов: выравниваем процессы с резервом так, чтобы одновременно шло как можно больше процессов как можно дольше, и проверяем шкалой времени по новым началам и окончаниям.

Общий алгоритм решения

1. Разнести зависимости по столбцам (Данные → Текст по столбцам).
2. Столбец окончаний: время + МАКС(ЕСЛИОШИБКА(ВПР(…); 0)) с протягиванием.
3. Столбец начал: окончание − время.
4. Формула под вопрос: МАКС, НАИМЕНЬШИЙ, СЧЁТЕСЛИ / СЧЁТЕСЛИМН или шкала времени со столбцом «подряд».
5. Если процессы можно задерживать - сдвинуть независимые ветки и пересчитать шкалу по новым срокам.