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

Обязательно ли запускать процесс сразу, как только он готов?

Только если так сказано в условии: «каждый процесс начинается в самое раннее допустимое время». Если этой фразы нет, процесс можно запустить и позже — и ответ ищут среди всех таких расписаний. Часто вместо неё стоит другая: «время окончания всех процессов минимально». Тогда сдвигать можно, но так, чтобы всё закончилось не позже, чем в раннем расписании.

Пример: процессы 1 и 2 по 4 мс ни от кого не зависят, 3 (2 мс) и 4 (4 мс) ждут процесс 2. Если всех запускать сразу, одновременно идут не больше двух процессов, а всё готово к 8:

Процесс 1 никто не ждёт, и его можно начать в 4 — он всё равно закончится к 8. Тогда на 5-й и 6-й мс идут три процесса: 1, 3 и 4.

Сдвигая процесс, проверяй тех, кто его ждёт: их тоже придётся сдвинуть, если поставщик теперь заканчивается позже их начала.

Насколько можно сдвинуть процесс, чтобы всё закончилось к тому же времени?

До его позднего начала. Его считают с конца: процесс должен закончиться не позже позднего начала того, кто его ждёт (если ждут несколько — не позже самого раннего из их поздних начал), а если его никто не ждёт — не позже общего времени. Позднее начало — это позднее окончание минус время работы. Разница между поздним и ранним началом — запас: на столько процесс можно сдвинуть.

В учебном примере общее время 14. Идём с конца. 8 никто не ждёт: он должен закончиться к 14, начать — не позже 13. 6 и 7 ждёт процесс 8: они должны закончиться к 13, значит 6 начинает не позже 9, 7 — не позже 11. Процесс 4 ждут 6 и 7 — он должен успеть к более раннему из их поздних начал, к 9, и начать не позже 7. И так до самого начала:

У процессов критической цепочки 2 → 5 → 7 → 8 запаса нет. Если все процессы поставить на поздние начала, расписание останется допустимым и закончится к 14:

Сколько процессов могут начаться не раньше чем через 7 мс, если всё должно закончиться за минимальное время?

Столько, у скольких позднее начало не меньше 7. Это 4 (позднее начало 7), 6 (9), 7 (11) и 8 (13) — четыре процесса. Расписание «все на поздних началах» допустимо, и в нём все четверо стартуют не раньше 7. У остальных позднее начало меньше 7 — их сдвинуть так далеко нельзя.

Частая ошибка — считать по раннему расписанию. Там не раньше 7 начинаются только 6, 7 и 8 — три. Так спрашивали в основной волне ЕГЭ-2026.

Какое наибольшее время могут идти одновременно три процесса, если всё должно закончиться за минимальное время?

Сначала найди, какие процессы вообще могут идти вместе: ни один из них не должен ждать другого, даже через цепочку. Вместе они идут не дольше самого короткого из них. Потом сдвинь их в пределах запаса так, чтобы они совпали.

В раннем расписании три процесса идут вместе только на 7-й мс. Какие тройки вообще возможны? Процесс 8 ждёт всех, а процессов 1 и 2 ждут почти все. Если перебрать тройки по графу зависимостей, без ожидания внутри останется одна — 3, 4 и 5. Самый короткий из них — 4, 2 мс, значит, больше 2 мс тройка не продержится.

Добиться 2 мс можно: у процесса 3 запас 2 мс, сдвинем его начало с 4 на 6. Тогда 3, 4 и 5 идут вместе на 7-й и 8-й мс, а всё по-прежнему заканчивается к 14:

Ответ таких задач всегда держится на двух доводах: расписание, где нужное время достигается, и причина, почему больше нельзя. Без второго ответ может оказаться не наибольшим.

• Сдвигать нельзя«каждый процесс начинается в самое раннее время»
• Сдвигать можнотакой фразы нет; «минимальное время» — в пределах запаса
• Позднее окончаниераннее из поздних начал тех, кто ждёт; иначе общее время
• Запаспозднее начало − раннее начало
• Не раньше порогасколько поздних начал не меньше порога
• Вместе при сдвигахпроцессы без зависимостей, не дольше самого короткого