📐 Формулы и краткие пояснения
шпаргалка
В №22 ответ зависит от точной формулировки в условии. Найди в задаче ключевую фразу и определи, к какому из трёх случаев она относится.
🔒 Двигать нельзя
Триггер в условии
время завершения каждого процесса минимально
- Каждый процесс стартует сразу после того, как завершилась его последняя зависимость.
- Процессы фиксированы во времени — двигать запрещено.
- Строим диаграмму, считаем для каждого процесса старт = max(окончание зависимостей) и финиш = старт + длительность.
- На полученной диаграмме ищем максимальный отрезок, где одновременно работает наибольшее число процессов — это и есть ответ.
↔️ Двигать в пределах границы
Триггер в условии
время окончания работы всех процессов минимально
- Сначала находим итоговое время T = длина критического пути (как в случае «двигать нельзя»).
- Это граница: ни один процесс не может закончиться позже T.
- В пределах T процессы можно сдвигать вправо (ставить позже самого раннего старта), не нарушая зависимости и не выходя за T.
- Сдвигаем процессы так, чтобы максимизировать перекрытие. Считаем самый длинный отрезок одновременной работы.
♾️ Двигать как угодно
Триггер в условии
процессы могут выполняться параллельно— без требования минимизации времени окончания.
- Никакой общей границы итогового времени нет — диаграмму можно растянуть сколько угодно вправо.
- Зависимости по-прежнему обязаны соблюдаться (B после A).
- Свободные (без общих зависимостей) процессы можно сдвинуть так, чтобы они полностью перекрывались.
- Ответ — длительность самого короткого процесса в группе наибольшего одновременного выполнения (на сколько хватит самого короткого, столько они и будут параллельно).
💡 Алгоритм действий: сначала прочитай последнее предложение условия — обычно ключевая фраза там. Если её нет вовсе — это случай «двигать как угодно».