Как мы делали оптимизатор, который сократил планирование графика порезки металла с 5 часов до 5 минут

Привет! На связи Анна Данилова и Михаил Телков из центра компетенций Quintiq в «Северстали». Мы тут сделали один классный оптимизатор для производства и хотим о нем рассказать. Немного фактов: активная фаза проекта заняла 26 недель; на стадии разработки реализовано 137 задач; пока тестировали оптимизатор, выявили и решили 86 инцидентов, а за первый месяц эксплуатации — ни одного тикета на изменение; сделали так, что фактические затраты на проект оказались в 4 раза меньше первоначальной оценки; консультантами были европейские коллеги, поэтому иногда задачу осложняли языковые трудности. Но все работает. 

Зачем «Северстали» понадобился оптимизатор

Разработка оптимизатора велась для сталелитейного сердца «Северстали» — Череповецкого металлургического комбината. Это один из самых больших промышленных комбинатов в стране, ежегодно он выпускает более 11 млн тонн стали. Металл производят и обрабатывают в разных цехах. В этом проекте мы решили усовершенствовать систему производственного планирования цеха отделки металла №2 (ЦОМ-2).

В ЦОМ-2 металл режут на листы и ленты (бунты) на разных агрегатах. Входным материалом для агрегатов выступают рулоны стали: горячекатаные (г/к), которые поступают непосредственно после прокатного стана, и травленые горячекатаные рулоны после цеха травления.

Все операции на комбинате происходят по графику. Планирование графика для порезки в ЦОМ-2 происходит так: специалисты-планировщики составляют в специализированной программе DELMIA Quintiq список рулонов, которые должны быть порезаны в сменах. До внедрения оптимизатора такое формирование графика порезки персоналом составляло от 5 до 8 часов, и это была кропотливая ручная работа, провоцирующая усталость и ошибки. Для современного производства крупнейшего в мире производственного комбината это слишком долго. Надо было оптимизировать процесс! Мы немедленно допили чай и выехали… Нет, конечно, какие командировки в локдаун. Мы всё сделали на удалёнке, не отрываясь от чая. Кто мы?

Команда

Задачу разработки и внедрения оптимизатора в ЦОМ-2 взял на себя Центр компетенций Quintiq. В «Северстали» он существует на базе группы детального планирования APS из управления развития и сопровождения сервисов. К проекту подключились сертифицированные сотрудники компании — это Operation Research Scientist-ы, на счету которых уже два успешных проекта по созданию и внедрению оптимизаторов в цехах ЦГП и ЛПЦ-1. В команду также вошли опытные бизнес-консультант (Quintiq Industry Process Consultant) и разработчик (Quintiq Software Expert). От DELMIA Quintiq были приглашены европейские коллеги в качестве консультантов по качеству (Quality Advisor). Работа команды была построена частично на принципах Agile и внутренней методологии ведения проектов Quintiq — QPLC (Quintiq Project Life Cycle).

Для нашей команды этот проект стал уникальным, потому что мы впервые разрабатывали и внедряли оптимизатор полностью своими силами. Держало в тонусе то, что вендор (Quintiq) оценивает и качество внедряемых решений, и качество процесса управления проектом. Одной из сложностей было то, что языком общения с заказчиком был русский, а языком ведения проекта — английский. Но мы засучили рукава и взялись за задачу.

Цель: оптимальный график работы агрегатов

Постановка задачи оптимизации

В ходе анализа определили, в чем должна заключаться задача оптимизации — в составлении последовательности заданий порезки рулонов для каждого агрегата резки по сменам. 

Дано:

• Два агрегата перемотки и продольной резки (АПР-1 и АПР-650) и три агрегата поперечной резки (АПР-2, АПР-3 и АПР-4). 

• От 1500 до 4000 рулонов на порезку (заданий). Рулон может быть назначен в несколько потребностей (задача назначения рулонов в потребности находится за рамками оптимизации и для нас является входной информацией). 

• Выбранные пользователем смены для оптимизации (в сутках две смены). Обычно пользователи планируют в горизонте от одних до трех суток. 

• Если после порезки рулона готовая продукция доставляется клиенту по железной дороге, то необходимо учесть правила комбинирования продукции в ж/д вагоны (по характеристикам продукции, станции назначения и пр.), а также учесть, что на складе уже может находиться готовая продукция, которая ждет отправки. 

• Рулоны имеют свои характеристики, с учетом которых на агрегате порезки они группируются в кампании порезки разного типа. Существуют различные ограничения по объему кампаний, по возможному порядку их следования и по количеству кампаний каждого типа на каждом агрегате. Внутри кампаний не допускается остановка на переналадку между рулонами. Одни кампании могут резаться на всех агрегатах, другие – на разрешенном подмножестве.

• На агрегате между кампаниями могут быть переналадки (зависит от типа кампании до и после, от характеристик рулонов). Разные последовательности имеют разное время переналадок. Одна из задач — минимизация переналадок (это значит, что агрегат больше времени будет выполнять полезную работу).

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

• снижения уровня текущих простоев за счет минимизации переналадок на переходах между кампаниями порезки и за счет изменений в геометрии продукта;

• увеличения поставок;

• снижения складских запасов;

• максимальной заполняемости вагонов с соблюдением норм;

• снижения количества рутинных операций для персонала;

• синхронизации агрегатов резки рулонов в цепочках планирования;

• повышения вовлеченности и удовлетворенности персонала.

Итак, перед нами стоит задача составлять графики по сменам так, чтобы учитывать суточный баланс по датам поставки клиентам, правила и ограничения по техническим составляющим кампаний на агрегатах, готовность металла. Для большей части металла надо еще рассматривать возможность планирования его обработки в разрезе вагонной нормы: то есть, планировать можно только тот рулон металла, который сможем отгрузить клиенту в вагон. А для этого необходимо понимать, какие именно рулоны можно комбинировать между собой, и какие именно лучше взять. Чтобы система могла сделать выбор, необходимо понимать, какое решение будет наилучшим. Оценить решения помогают КПЭ — ключевые показатели эффективности. 

Определение ключевых показателей эффективности

Для каждого важного критерия, по которому может быть сделан выбор, определяется свой КПЭ, его формула, по которой система будет выставлять оценки для разных решений. Итоговый выбор решения основывается на сумме взвешенных КПЭ: у каждого КПЭ в рамках выбранной стратегии определен свой вес, с которым этот КПЭ учитывается в итоговом КПЭ. И по итоговому значению КПЭ система выбирает наилучший — наибольший или наименьший показатель в зависимости от принятых правил. 

Определение КПЭ, по которым принимаются решения, осложняет человеческий фактор. Дело в том, что какие-то знания при составлении графиков планировщиками бывают настолько нативными и само собой разумеющимися, что они ускользают от внимания. А нам надо изначально предусмотреть все важные моменты, при этом не перегрузив систему излишними деталями. Ведь каждый новый КПЭ — это дополнительные тонкости в разработке и тестировании, которые потенциально увеличивают время вычисления. Здесь важен баланс. 

Бизнес-консультанты определили 15 значимых КПЭ, которые учитывали время порезки на агрегатах (с настройкой), близость графика к идеальному балансу по типам кампаний, вагонные нормы, штрафы по кампаниям порезки, штрафы за перевозку рулонов между складами и остатки на складе. На основе этих КПЭ была сформулирована целевая функция для оптимизации как сумма всех перечисленных КПЭ с учетом их весов и с учетом направления (хотим мы КПЭ минимизировать или максимизировать). Цель —  максимизировать Total KPI:

Оценка задачи оптимизации              

Первоначальная гипотеза была, что обойдемся одним оптимизатором, но после детального анализа пришли к выводу что исходная задача состоит из 2-х крупных подзадач: 

1. задача комбинирования рулонов в вагоны и рулонов в кампании порезки.

2. задача упорядочения набора рулонов на агрегатах.

Тут есть сложность, которую объясним на примере. Возьмем 20 рулонов, пронумерованных по порядку, которые можно сгруппировать в одну кампанию. Вспомним, что количество подмножеств множества из N элементов равно 2N. Тогда количество вариантов выбора кампании как подмножества из 20 рулонов равно  220= 1 048 576. А если мы имеем 60 подходящих рулонов, и средний размер кампании 20 рулонов, то количество возможных сочетаний будет С2060 = 4 191 844 505 805 495. А у нас на входе от 1500 до 4000 рулонов, и многие рулоны должны группироваться в вагоны (которых может быть много с разным весом), притом один вагон может содержать рулоны из разных кампаний. А еще рулоны могут быть порезаны на разных агрегатах. Все это сильно увеличивает количество вариантов выбора рулонов в кампании порезки. 

Дальше. Допустим мы выбрали 100 рулонов на агрегат порезки.  Тогда количество вариантов последовательностей рулонов будет равно количеству перестановок  P100 = 100! = число порядка 10157. Ладно, ладно, кто внимательно читал выше, скажет, что кампания на агрегате не должна иметь внутри переналадок, а значит, изменение последовательности рулонов внутри кампании исключаем. Ну, кроме первого и последнего рулона в кампании, которые граничат с крайними рулонами соседних кампаний и от которых зависит время переналадки. Используя эвристики при решении задачи комбинирования, можно сильно ограничить количество вариантов, но даже если мы имеем порядка 12 кампаний на агрегате – это грубо P12 = 12! = 479 001 600.

Решение, какой именно рулон использовать с учетом вагонной нормы и наполнения кампании — многовариантно. Необходимо рассмотреть эти варианты и выбрать из них оптимальный. Решение, в каком порядке выстраивать рулоны в графике, также многовариантно. Теперь и вы понимаете, что решить «в лоб» такую задачу невозможно. Для сравнения: атомов в нашей галактике примерно 1069. Атомов во всей наблюдаемой Вселенной порядка 1080. А пользователи хотят найти оптимальное решение максимум за 20 минут. И сейчас самое время задать извечный вопрос: «Что же делать?» 

Как мы решали задачу оптимизации

Мы начали с того, что пользователи могут выбирать разные смены для оптимизации. Поэтому договорились, что будем решать задачу итеративно для каждой выбранной смены — это позволит снизить число возможных вариантов решения. Далее, для смены мы проанализируем рулоны и складскую продукцию, на основе чего создадим возможные типы вагонов, которые могут быть использованы в решении. Типов вагонов не так уж и много, и нам останется только выбрать к какому типу мы привяжем рулоны и количество вагонов каждого типа. Для решения мы использовали алгоритмы MIP и POA.

MIP optimizer

Для решения первой задачи комбинирования мы используем смешанное целочисленное линейное программирование (Mixed Integer Programming, MIP). На вход MIP-а будем подавать предварительно сформированные типы вагонов и комби-кампании. Комби — это маленькая часть решения, возможный вариант кампании. При создании таких комби мы максимально учтем все ограничения на совместимость рулонов и все «тайные знания» пользователей, добытые ими эмпирическим путем (то, что называется soft knowledge). Мы не будем создавать комби, для которых мы точно знаем (или уверены с большой вероятностью), что время переналадки будет большим. 

Стоит отметить, что MIP не решает задачу оптимизации пути. То есть, не учитывает переналадки между рулонами и/или кампаниями. Но с помощью некоторых эвристик мы можем учитывать это в MIP-е в той или иной степени. 

Также мы учтем, что некоторые рулоны как бы «однотипные», поэтому их замена в кампании не повлияет на КПЭ — можно не создавать много вариантов «однотипных» кампаний из «однотипных» рулонов. Так мы сильно сократим количество вариантов, при этом сохраняя разнообразие кампаний и максимально учитывая бизнес-требования.

MIP будем запускать итеративно несколько раз, подавая предыдущее найденное решение на вход следующей итерации. На каждой итерации будем получать новый набор комби к предыдущему решению и будем иметь процесс постоянного улучшения целевой функции.

POA optimizer

Для решения второй части задачи мы используем алгоритм оптимизации пути (Path Optimization Algorithm, POA). Так как после MIP-а мы получаем выбранные кампании на агрегатах, то достаточно для каждого агрегата итеративно запускать оптимизатор цепочки на базе POA. В POA-оптимизаторе используем те КПЭ, которые зависят от последовательности рулонов. 

Укажем некоторые базовые характеристики POA-оптимизатора:

• Нодой является рулон в кампании

• Путем для POA будет агрегат

• Вклад ноды в путь — длительность задания порезки на агрегате

• Переход от ноды к ноде — время переналадки между нодами. Также при переходе учитываются штрафы за планирование нод с определенным типом после (перед) другими нодами

• Выбранные стратегии: базовая стратегия поиска нод, стратегия random construction / destruction

Граф компонентов для нашего решения выглядит примерно так:

Прежде чем мы начнем рассказывать о мытарствах разработки оптимизатора для системы планирования, надо чтоб вы понимали, как работает человек-планировщик.

Чтоб вы понимали, как работает человек-планировщик

Работа планировщика по составлению графика одновременно рутинна и алгоритмически сложна. Ему надо:

• выбрать подходящие материалы;

• сбалансировать их по срокам, объемам и готовности к обработке; 

• проверить их на возможности формирования вагонных норм;

• расположить их в определенном порядке друг за другом, чтобы график был наиболее продуктивным;

• помнить правила для каждого агрегата и обращать внимание на подсказки системы.

Система планирования учитывает: 

• Время, к которому надо произвести металл в нужном объеме;

• Узкое место в цепочке агрегатов;

• Альтернативные маршруты (важно понимать, где производить будет выгоднее);

• Затраты времени на настройку и подготовку агрегатов;

• Физические ограничения по агрегатам на вход, либо ограничения по заказам;

• Накопленный опыт эксплуатации оборудования и учет его возможного выхода из строя;

• Последовательности в сортаменте (пример из кулинарии: если одной скалкой раскатывать сухое и масляное тесто, то сухое тесто нельзя катать сразу после масляного, потому что остатки жирного теста со скалки могут смешаться с сухим тестом, и оно потеряет требуемые качества);

• Многие другие критерии и задачи.

Лучшие результаты получаются тогда, когда происходит коллаборация машины и человека при планировании: машина забирает на себя рутинную часть работы и строгое следование жестким правилам, оставляя человеку право на принятие решений в спорных ситуациях. И там, где жесткими правилами руководствоваться неэффективно, наступает звездный час самого планировщика. 

Ну что, пойдем в разработку?

Разработка оптимизатора планирования графика

Как вы, наверное, все любите, на стадии разработки стали появляться новые требования. Представьте, разрабатываем мы, разрабатываем, как вдруг всплывает информация о том, что надо добавить дополнительный критерий — помните, мы говорили про человеческий фактор? Появление этого критерия откатывает нас назад с этапа разработки на этап анализа и дизайна, замораживая текущие работы по моделированию. При моделировании включение в решение ограничений и КПЭ происходит не сразу, а постепенно, одно за другим. Здесь нам важно изначально добиться высокого качества решения, а только потом переходить к проработке проблемы со скоростью выдачи готового решения.   

Затем были ежедневные прогоны оптимизатора и контроль качества решения на разных типах бенчмарков: моделирования, проектной команды, заказчика. И вдруг при тестировании алгоритмов мы обнаружили одну хитрую ошибку. В процессе отладки оптимизатор действительно находил оптимальный план, но оказалось, что рулоны после порезки распределялись по вагонам хаотично. В итоге мы имели оптимальный план со множеством смешанных вагонов. Конечно, при ручном планировании планировщики стараются формировать однотипные вагоны и минимизировать различие продукции внутри вагона. Мы добавили новые условия и задали предпочитаемое направление комбинирования в вагоны. 

Сложность решаемых оптимизатором задач постепенно наращивалась. Параллельно мы дорабатывали модель ручного планирования под новые требования. Время работы оптимизатора в наших системах согласно договоренностям с заказчиками не должно было превышать 20 минут. Достичь оптимальных результатов в указанное время с учетом новых требований было непросто, но нам помогла методология QPLC (Quintiq Project Life Cycle). Она похожа на водопадную модель, но у нее есть свои особенности. Весь процесс состоит из определенных фаз, в каждой из которых свои задачи. Благодаря этому команда уложилась в одну дополнительную неделю, которую в дальнейшем смогли сократить на фазе приемки заказчиком. Более того, в дальнейшем мы сократили время работы оптимизатора в два, а порой и в три-четыре раза в зависимости от входного набора данных. Сейчас время работы оптимизатора на продуктивной системе составляет от 2 до 7 минут. Скромно заметим, что это довольно комфортно для пользователей. 

Кстати, о пользователях. У планировщиков были сложности с принятием оптимизатора — им пришлось психологически перестраиваться на то, что теперь часть их рутинной работы будет выполнять машина. Так что во время обучения персонала новому инструменту приходилось сталкиваться с преодолением страха потерять рабочее место и привычных паттернов в работе. Всегда ведь легче делать так, как уже умеешь и знаешь, даже если получается хуже и дольше — мозг еще не построил новые нейронные связи. На помощь приходит обучение, поддержка руководства и определение новых регламентов работ. 

Ну, а мы в нашей истории подошли к финалу.

Оптимизатор оптимизирует!

В результате проделанной в течении 26 недель работы заказчик подтвердил ввод оптимизатора в промышленную эксплуатацию. Советники максимально высоко оценили качество реализации всех сторон проекта. Несмотря на трудности объяснения задачи оптимизации нашим англоязычным советникам; несмотря на то, что задача оказалась сложнее, чем выглядела сразу после анализа; несмотря на долгий поиск решения и обсуждения команда успешно завершила проект, сумев получить среднее время работы оптимизатора всего 5 минут.

Не можем не отметить труд коллег из поддержки мастер-данных QMET. Они проделали большую работу по формализации и поставке в APS (ПО для производственного планирования) актуальных мастер-данных: производительность, расходные коэффициенты и т.п. 

Факты о проекте:

• 137 задач было реализовано на стадии разработки;

• 86 инцидентов было выявлено и решено при тестировании оптимизатора;

• За месяц полноценной эксплуатации не создано ни одного инцидента или заявки на изменение в оптимизаторе;

• Фактические затраты на проект оказались в 4 раза меньше первоначальной оценки;

• При заданном лимите времени на построение графиков 20 минут оптимизатор укладывается в среднем в 5 минут.

Философский вывод: в проекте по оптимизации при поиске лучшего решения, применимого в реальной жизни, важно дать машине оптимальный уровень «свободы воли». Потому что слово “оптимальный” звучит умно. Ладно, потому что отсутствие “свободы” — это абсолютно детерминированный алгоритм решения задачи “в лоб”, а полная свобода — это великий рандом (вспомним парадокс об обезьяне и печатной машинке). Поэтому, чтобы зародилась жизнь на Земле, нужно было какое-то оптимальное расстояние до Солнца (Меркурий с Нептуном как близкая и дальняя точки не подошли. И да, олдскулы негодуют, но с 2006 года вроде как Плутон уже не планета, а просто крупнейший объект пояса Койпера). А поскольку машина может найти решение быстрее и точнее человека, качественно выполнять рутинную работу, человек переходит на другой, более высокий уровень принятия решений. То есть, машина может стать помощником в переходе на следующую ступень осознанности и развития.