Задание №22. Короткий конспект
Максимум окончаний предшественников, границы миллисекунд и условия допустимого сдвига процессов.
Таблица задаёт длительность каждой работы и её предшественников. Работа запускается после завершения всех зависимостей и выполняется без остановки. Независимые процессы могут идти параллельно; число 0 в зависимостях означает пустой список.
Начало и окончание
Для процесса i: d_i — длительность, S_i — начало, F_i — окончание. Список предшественников обозначен P_i.
- Ранний запуск: S_i=\max_{j\in P_i}F_j; без зависимостей S_i=0.
- Окончание: F_i=S_i+d_i. Сначала рассчитываются все предшественники, независимо от порядка строк.
- Минимальный общий срок: T=\max_iF_i раннего расписания. Критический путь — самая длинная по сумме длительностей цепочка зависимостей.
Выбор ответа
| Вопрос | Действие |
|---|---|
| Завершение k процессов | k-е окончание в возрастающем списке, с повторениями |
| Завершено за первые t мс | Число строк с F_i\le t |
| Работает на k-й мс | Число строк с S_i<k\le F_i |
| Длительность совместной работы | Длина непрерывного интервала с нужным числом процессов |
Момент 0 предшествует первой миллисекунде. Работа с начала 4 до окончания 12 занимает миллисекунды 5–12: 12-4=8 мс.
Когда разрешён сдвиг
Самый ранний запуск и минимальный общий срок — разные требования. Если немедленный запуск не обязателен, начало можно перенести, сохранив длительность и готовность всех предшественников. При требовании минимального общего срока дополнительно сохраняется F_i\le T для всех работ, включая последователей.
Для интервала одновременной работы время делится по событиям запуска и окончания. Соседние участки объединяются, пока нужное число сохраняется. Состав процессов может меняться. Максимум подтверждается допустимым расписанием и объяснением, почему большего значения получить нельзя.
Возможные ловушки
- Сумма ожиданий запрещает допустимую параллельность. Нужен максимум окончаний предшественников.
- Последняя строка не обязательно заканчивается последней. Общий срок выбирается по всему столбцу.
- Удаление одинаковых окончаний теряет процессы. Каждая строка даёт отдельное завершение.
- Добавление единицы к F_i-S_i завышает длительность. Номера миллисекунд и моменты времени учитываются раздельно.