Оптимизация производственного планирования

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

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

Дана общая структура алгоритма оптимизации решения. Для погружения в тему требуется серьёзное изучение теории графов, теории массового обслуживания и теории расписаний.

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

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

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

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

Превратности подходов

Самое частое решение, которое приходит на ум многим неискушенным оптимизаторам ­ это найти продукты с самым малым временем переналадки и объединить их в пару. Потом присоединить к этой паре следующего ближайшего соседа и действовать так до тех пор, пока мы последовательно не соберем все наши продукты в цепочку. Однако, такой подход лишь гарантирует решение, которое будет лучше самого плохого. На практике, на случайно сгенерированных матрицах переналадок такой алгоритм даст результат, который будет хуже оптимального в 1,5­2 раза.

Давайте попробуем разобраться почему так происходит. Нарисуем 2 точки на плоскости: точку А и точку В. Думаю, все со школы помнят, что кратчайшим расстоянием между такими точками будет прямая (А­В). Теперь давайте нарисуем еще несколько точек на этой прямой (рис.1.1.) Кратчайшим путем между последовательностью точек остается та же прямая из А в В. Если мы уберем первоначальную линию и попробуем последовательно соединить все точки, учитывая только расстояние между ними (рис. 1.1), то очевидно, что полученный результат будет значительно хуже оптимального. Алгоритмы, основанные на средних или медианных расстояниях, также будут показывать результаты далекие от оптимальных.

Рис. 1­-1.

При поиске решения может возникнуть желание найти все возможные комбинации и выбрать среди них лучшую. Однако на практике такое невозможно по причине того, что число всех возможных комбинаций для 100 продуктов будет равно 9*10^157. Даже если мы решим, что расчет одной такой комбинации будет занимать одну наносекунду, то, я полагаю, что расчет всех возможных комбинаций с использованием всех вычислительных ресурсов, существующих на нашей планете, займет больше времени, чем время существования, самой планеты. Соответственно, такой вариант оптимизации не применим на практике.

Следует признать, что человечество еще не научилось точно решать подобные задачи за “разумное” время, а возможно никогда и не научится. Но что делать, если такие, встречающиеся на практике, задачи все­таки необходимо решать? В этих случаях используются методы дискретной оптимизации, которые хоть и не гарантируют оптимального результата, но позволяют получить решение, которое очень близко к оптимальному.

Использование приближенных алгоритмов. Этапы решения.

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

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

Этап 1.

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

Этап 2.

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

Этап 3. Поиск минимума

Что касается подходов к дальнейшему улучшению результатов, то тут тоже нет ничего сложного. Мы просто пытаемся найти наилучший локальный минимум N­мерной функции. В нашем примере это функция в 100­мерном дискретном гиперпространстве. Как один из рабочих вариантов, мы можем сгенерировать некое конечное множество случайных координатных векторов и рассчитать для каждого из них стоимость, используя нашу функцию. Получив стоимости для каждого такого вектора, мы уже можем представить топологию нашей функции и продолжать поиск вблизи известного минимума. Конечно это довольно прямолинейный метод, есть и более сложные, которые выполняют непрерывный поиск локальных минимумов, но даже такой простой и понятный подход дает достаточно хорошие результаты, особенно если нам необходимо бороться за вычислительную сложность.

Демонстрация эффективности приближенных алгоритмов

Чтобы продемонстрировать какие результаты даёт применение приближенных алгоритмов на практике, я буду использовать матрицу переналадок из 53­ х продуктов, для которой известно оптимальное целевое значение, равное 6’905 единицам. Число возможных комбинаций для данной задачи составит 4*10^69, что также не подразумевает ее решение полным перебором. Тут также необходимо сделать небольшую оговорку, почему я выбрал именно такой размер матрицы, а не больший. Объяснение очень простое ­ в рамках подготовки статьи для вычислений я использую свое собственное железо на базе старенького Intel i7­2600K, который загружает все 4 ядра и 8 потоков на 97%, и не имеет соответствующих подобным задачам системы охлаждения. Такая многопоточность обеспечивается архитектурой самого алгоритма и тем, что весь код написан на Java 8 с использованием Stream API (fork­join parallelism). В рамках промышленной эксплуатации подобных алгоритмов, их работа должна выполняться вне экосистемы SAP (или другой ERP системы) на отдельно стоящих HPC­серверах с уклоном в большую многопоточность, а также обладающих большим процессорным кешем и RAM с малыми таймингами.

Теперь, возвращаясь непосредственно к работе алгоритма, давайте взглянем на рис. 2, где отражены 5 отдельных графиков. Первый из них ­ это целевое (минимальное) значение “min”, которое мы стремимся достичь. Второй ­ это результат использования «жадного» алгоритма “greedy”, который получен описанным выше алгоритмом попарного соединения продуктов и дает нам результат в 12’706 единиц. Оставшиеся ­ это три попытки последовательного приближения целевого значения методами дискретной оптимизации “do_1, do_2, do_3”, давшие одинаковый результат. В рамках данного примера для приближения мы используем 30’000 эпох. Эпоха ­ это своего рода отдельная итерация, в рамках которой мы пытаемся улучшить предыдущий результат.

 

Рис.2. Работа алгоритмов оптимизации

На графике мы наглядно видим, как алгоритм дискретной оптимизации постепенно улучшает результат, но тем не менее, несмотря на несколько попыток, нам так и не удается достигнуть целевого значения останавливаясь каждый раз на отметке в 7003 единиц. И тут следует понимать самое важное ­ алгоритмы дискретной оптимизации не гарантируют, что мы в конечном итоге получим оптимальный результат за заданное время или заданное число эпох. Однако, как мы видим из примера, полученные нами результаты отличается от оптимального на 1,4% и от результата «жадного» алгоритма на 81% , что на мой взгляд, более чем приемлемо для решения прикладных задач производственного планирования. А учитывая, что получение такого результата заняло около двух минут на не самом производительном железе, то такой подход становится еще более привлекательным в прикладных задачах.

Что следует учесть на практике?

Использование подобных методов оптимизации предполагает исключительно индивидуальный подход к решаемым задачам. На практике получается так, что от задачи к задаче удается перенести только полученный опыт, но не сами алгоритмы. Настроечные параметры самих алгоритмов очень сильно зависят от: “плотности” данных в матрице, количества оптимизируемых продуктов, каких­то априорных знаний и т.д. В результате получается, что параметры алгоритма сами нуждаются в оптимизации, но параметров алгоритма не много, и мы уже умеем решать подобные задачи. 

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

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

Дана общая структура алгоритма оптимизации решения. Для погружения в тему требуется серьёзное изучение теории графов, теории массового обслуживания и теории расписаний.

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

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

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

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

Превратности подходов

Самое частое решение, которое приходит на ум многим неискушенным оптимизаторам ­ это найти продукты с самым малым временем переналадки и объединить их в пару. Потом присоединить к этой паре следующего ближайшего соседа и действовать так до тех пор, пока мы последовательно не соберем все наши продукты в цепочку. Однако, такой подход лишь гарантирует решение, которое будет лучше самого плохого. На практике, на случайно сгенерированных матрицах переналадок такой алгоритм даст результат, который будет хуже оптимального в 1,5­2 раза.

Давайте попробуем разобраться почему так происходит. Нарисуем 2 точки на плоскости: точку А и точку В. Думаю, все со школы помнят, что кратчайшим расстоянием между такими точками будет прямая (А­В). Теперь давайте нарисуем еще несколько точек на этой прямой (рис.1.1.) Кратчайшим путем между последовательностью точек остается та же прямая из А в В. Если мы уберем первоначальную линию и попробуем последовательно соединить все точки, учитывая только расстояние между ними (рис. 1.1), то очевидно, что полученный результат будет значительно хуже оптимального. Алгоритмы, основанные на средних или медианных расстояниях, также будут показывать результаты далекие от оптимальных.

Рис. 1­-1.

При поиске решения может возникнуть желание найти все возможные комбинации и выбрать среди них лучшую. Однако на практике такое невозможно по причине того, что число всех возможных комбинаций для 100 продуктов будет равно 9*10^157. Даже если мы решим, что расчет одной такой комбинации будет занимать одну наносекунду, то, я полагаю, что расчет всех возможных комбинаций с использованием всех вычислительных ресурсов, существующих на нашей планете, займет больше времени, чем время существования, самой планеты. Соответственно, такой вариант оптимизации не применим на практике.

Следует признать, что человечество еще не научилось точно решать подобные задачи за “разумное” время, а возможно никогда и не научится. Но что делать, если такие, встречающиеся на практике, задачи все­таки необходимо решать? В этих случаях используются методы дискретной оптимизации, которые хоть и не гарантируют оптимального результата, но позволяют получить решение, которое очень близко к оптимальному.

Использование приближенных алгоритмов. Этапы решения.

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

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

Этап 1.

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

Этап 2.

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

Этап 3. Поиск минимума

Что касается подходов к дальнейшему улучшению результатов, то тут тоже нет ничего сложного. Мы просто пытаемся найти наилучший локальный минимум N­мерной функции. В нашем примере это функция в 100­мерном дискретном гиперпространстве. Как один из рабочих вариантов, мы можем сгенерировать некое конечное множество случайных координатных векторов и рассчитать для каждого из них стоимость, используя нашу функцию. Получив стоимости для каждого такого вектора, мы уже можем представить топологию нашей функции и продолжать поиск вблизи известного минимума. Конечно это довольно прямолинейный метод, есть и более сложные, которые выполняют непрерывный поиск локальных минимумов, но даже такой простой и понятный подход дает достаточно хорошие результаты, особенно если нам необходимо бороться за вычислительную сложность.

Демонстрация эффективности приближенных алгоритмов

Чтобы продемонстрировать какие результаты даёт применение приближенных алгоритмов на практике, я буду использовать матрицу переналадок из 53­ х продуктов, для которой известно оптимальное целевое значение, равное 6’905 единицам. Число возможных комбинаций для данной задачи составит 4*10^69, что также не подразумевает ее решение полным перебором. Тут также необходимо сделать небольшую оговорку, почему я выбрал именно такой размер матрицы, а не больший. Объяснение очень простое ­ в рамках подготовки статьи для вычислений я использую свое собственное железо на базе старенького Intel i7­2600K, который загружает все 4 ядра и 8 потоков на 97%, и не имеет соответствующих подобным задачам системы охлаждения. Такая многопоточность обеспечивается архитектурой самого алгоритма и тем, что весь код написан на Java 8 с использованием Stream API (fork­join parallelism). В рамках промышленной эксплуатации подобных алгоритмов, их работа должна выполняться вне экосистемы SAP (или другой ERP системы) на отдельно стоящих HPC­серверах с уклоном в большую многопоточность, а также обладающих большим процессорным кешем и RAM с малыми таймингами.

Теперь, возвращаясь непосредственно к работе алгоритма, давайте взглянем на рис. 2, где отражены 5 отдельных графиков. Первый из них ­ это целевое (минимальное) значение “min”, которое мы стремимся достичь. Второй ­ это результат использования «жадного» алгоритма “greedy”, который получен описанным выше алгоритмом попарного соединения продуктов и дает нам результат в 12’706 единиц. Оставшиеся ­ это три попытки последовательного приближения целевого значения методами дискретной оптимизации “do_1, do_2, do_3”, давшие одинаковый результат. В рамках данного примера для приближения мы используем 30’000 эпох. Эпоха ­ это своего рода отдельная итерация, в рамках которой мы пытаемся улучшить предыдущий результат.

 

Рис.2. Работа алгоритмов оптимизации

На графике мы наглядно видим, как алгоритм дискретной оптимизации постепенно улучшает результат, но тем не менее, несмотря на несколько попыток, нам так и не удается достигнуть целевого значения останавливаясь каждый раз на отметке в 7003 единиц. И тут следует понимать самое важное ­ алгоритмы дискретной оптимизации не гарантируют, что мы в конечном итоге получим оптимальный результат за заданное время или заданное число эпох. Однако, как мы видим из примера, полученные нами результаты отличается от оптимального на 1,4% и от результата «жадного» алгоритма на 81% , что на мой взгляд, более чем приемлемо для решения прикладных задач производственного планирования. А учитывая, что получение такого результата заняло около двух минут на не самом производительном железе, то такой подход становится еще более привлекательным в прикладных задачах.

Что следует учесть на практике?

Использование подобных методов оптимизации предполагает исключительно индивидуальный подход к решаемым задачам. На практике получается так, что от задачи к задаче удается перенести только полученный опыт, но не сами алгоритмы. Настроечные параметры самих алгоритмов очень сильно зависят от: “плотности” данных в матрице, количества оптимизируемых продуктов, каких­то априорных знаний и т.д. В результате получается, что параметры алгоритма сами нуждаются в оптимизации, но параметров алгоритма не много, и мы уже умеем решать подобные задачи. 

Автор
Денис Мягков
Архитектор решений SAP
Задать автору вопрос!
Поделиться

Онлайн-покупки с помощью электронной почты: комментирует эксперт TeamIdea
Интервью с экспертом TeamIdea об особенностях перехода на систему "Меркурий"
Комментарий эксперта TeamIdea о функциональных особенностях системы "Меркурий"

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

Зарегистрироваться
Авторизация пользователя
После Регистрации Вам будут доступны к скачиванию материалы с ограниченным доступом.
Нет пароля? Тогда вам сюда — Регистрация?

Войти
Отправить
Регистрация пользователя
Ваша регистрация прошла успешно!

Восстановление пароля
Письмо с новым паролем отправлено Вам на почту

Опытные SAP консультанты TeamIdea ответят на все Ваши вопросы.

Благодарим Вас за обращение в TeamIdea. В ближайшее время наш специалист свяжется с Вами.