Как мы строили эвристический планировщик для типографии и проверяли его точной моделью
Привет! Меня зовут Илья Грошев, я разработчик в KTS и последние полгода отвечаю за планировщик производства для типографии: сотня машин, полторы сотни людей с допусками и графиком смен, у каждого заказа свой маршрут операций. Каждый заказ нужно закончить к обещанному сроку, а для каждой операции найти свободную машину и человека с допуском в одну и ту же смену. Планировщик берёт заказы один за другим, расставляет операции каждого по правилам типографии и к уже поставленным заказам не возвращается. План строился быстро, но заказы в нём опаздывали даже при свободных машинах, и мы не знали, можно ли лучше. На тестовом наборе он укладывал в срок 8 заказов из 15, а точная модель на тех же данных показала, что можно все 15. В статье расскажу, как мы строили этот алгоритм и почему точная модель осталась у нас инструментом отладки и в прод не попала. Разберу задачу, три слоя планировщика с гипотезами, которые сработали и которые провалились, три способа проверить план и то, что проверка изменила в алгоритме. Опыт пригодится тем, кто составляет расписания или распределяет ограниченные ресурсы и выбирает между эвристикой и точной моделью. Читать далее