Статьи → TechnologiCS 7.1 → Современные алгоритмы планирования в TechnologiCS. Первый шаг на пути к нейросетям и самообучающимся системам

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

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

Реализуемая государством программа перехода к цифровой экономике только повысила актуальность решения данных проблем.

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

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

Под системой далее будем понимать совокупность невыполненных операций.

Каждое состояние системы описывается списком, длина которого равна количеству партий деталей. Каждый элемент списка — номер операции некоторой партии детали, соответствующей порядку в списке.

e_i1— номер первой операции для i-й партии деталей;

N — количество партий деталей;

EL₀ — начальное состояние системы.

Соответственно, в любой момент времени состояние системы примет вид:

e_iki— k_i-я операция для i-й партии деталей.

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

Конечное состояние система принимает, когда все операции всех партий будут распределены по ресурсам (рис. 1).

Рис. 1

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

Начальные времена обработки партий обозначим как S, время конца обработки — как D, времена планируемых моментов сдачи партий — как R.

Решением поставленной задачи будем считать полученные значения S и D.

Целевая функция решения задачи оптимизации планирования:

L=f (S, D, R, w), где w — различные задаваемые пользователем приоритеты для сочетаний параметров.

В качестве функции L может быть выбрана:

w₁+w₂=1;

T_j=max⁡(d_j — r_j, 0) — время задержки;

E_j=max⁡(r_j — d_j, 0) — время опережения;

r_j — планируемое время сдачи партии j;

d_j — рассчитанное время сдачи партии j.

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

Перейдем непосредственно к оптимизационному алгоритму. Рассмотрим граф G = (U, V), где вершинами V являются уже упомянутые состояния системы EL, а ребра U соответствуют переходу из одного состояния в другое, при этом веса ребер зависят от функции расстояния ρ состояний системы. Решение задачи планирования состоит в поиске пути на графе G, позволяющем минимизировать целевую функцию L. Так как данная задача является NP-полной, то ее решение имеет смысл искать среди стохастических алгоритмов. Для решения подобных задач хорошо зарекомендовал себя метод муравьиных колоний (ACO и его модификации).

Рис. 2

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

В задаче планирования каждое ребро графа G помечается начальным количеством феромона τ₀, а затем запускается первый муравей. Выбор каждого следующего состояния системы осуществляется следующим образом:

 — экви-функция расстояния между состояниями i и j;

— вероятность перехода из состояния i в состояние j;

α, β - настраиваемые числовые параметры.

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

Запустив m муравьев из колонии, получаем m вариантов путей, для которых считаем целевую функцию L. Выбираем лучший путь с минимальным значением L и обновляем значения феромонов на ребрах графа системы в соответствии с полученными результатами первого прохода колонии. Дополнительно, чтобы избежать застревания в локальных экстремумах, вводится процесс испарения феромона на каждом из ребер G через коэффициент γ.

γ — коэффициент испарения феромона, ∈ [0,1];

Q — параметр одного порядка с длиной пути L (он же значение целевой функции).

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

После отработки первой колонии прогоняем вторую и так далее, пока не удовлетворим заданному условию сходимости, например, малому изменению целевой функции.

Результатом алгоритма являются полученные даты запуска и выпуска, календари станков и рабочих. Потребности в материалах или инструментах присоединяются проекцией на результирующий расчетный производственный календарь, ориентируясь на даты производственных операций (рис. 3).

Рис. 3

В завершение стоит отметить, что данный математический аппарат уже был успешно апробирован нами в 2018 году на предприятии «Тулаточмаш» (в производстве МП-5). При этом мы проводили сравнение планов, рассчитанных стандартным способом и с применением алгоритма муравьиных колоний. План, посчитанный с применением муравьиного алгоритма, предусматривал (за счет оптимизации производственных потоков, снижения числа переналадок, анализа свободных мощностей) снижение срока выпуска заказов в среднем на 12% при росте OEE до 85%, что является весьма неплохими показателями. Последующая практика показала достоверность этих расчетов, и, начиная с 2019 года, «Тулаточмаш» полностью перешел на производственное планирование с применением новых алгоритмов.