Elevators
Лифты кажутся простыми, но их работа скрывает сложнейшие алгоритмы. Самый базовый метод — SCAN, который поднимается до верхнего этажа, затем возвращается, собирая и отпускающих пассажиров по пути. Чаще используется LOOK, который останавливается только на запрошенном этаже и меняет направление. При нескольких машинах центральный планировщик назначает каждый запрос ближайшему лифту, но можно улучшать. Оценка эффективности проводится по частоте wait < 30 s и wait < 90 s, а также по распределению времени ожидания: p50 ≈ 1 мин, p90 ≈ 2 мин. Утренний наплыв делает эти цифры самыми плохими.
Современные системы используют RSR — алгоритм, где каждому лифту начисляется балл: время прибытия к подбору, штраф за загрузку, штраф за «анти‑скопление» в том же направлении, бонус за совпадение направления, бонус за близость к свободному лифту и бонус за низкую нагрузку. RSR пересчитывается каждые 5 сек., позволяя перераспределять вызовы и уменьшать задержки. В отличие от Destination Dispatch, где пассажир обязан ждать назначенного лифта, эта гибкость даёт лучшую производительность; эксперименты показывают, что система с терминалом в обычных зданиях ухудшает среднее время ожидания. В симуляции с 8‑этажами, 4‑машинами и потоком 18/min такие решения показывают, что гибкость важнее жесткой привязки.