Задача о назначении производственных ресурсов с системой ограничений

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

Введение

Литейный цех – это завод, производящий металлические отливки. Жидкие металлы отливаются в формы, после чего происходит затвердевание металла и удаление материала формы. Один из наиболее распространенных металлов для обработки – алюминий.

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

Для выливки алюминия из электролизера и дальнейшей его транспортировки в пределах литейного цеха используются вакуум-ковши. Объем вакуум-ковша больше объема электролизера, поэтому для заполнения одного вакуум-ковша требуется несколько электролизеров. На предприятии, производящем алюминий, составляется план по выливке алюминия-сырца в вакуум-ковши, причем алюминий в вакуум-ковше, полученный в результате смешивания алюминия из нескольких электролизеров, должен удовлетворять требованиям по содержанию примесей (быть определенной марки) и по массе. В результате перед сотрудниками электролизного отделения литейного цеха встает вопрос об оптимизации процесса выливки электролизеров с алюминием-сырцом в вакуум-ковши. Для решения данной задачи можно использовать метод целочисленного линейного программирования (ЦЛП). Подобный подход использовался в [9] для решения задачи оптимизации в миксерном отделении сталелитейного завода. Метод целочисленного линейного программирования широко используется для решения транспортных оптимизационных задач. В работе [1] была предложена методология для решения комплексных задач принятия решений в управлении металлургическим производством. В публикации [2] модель ЦЛП применяется для решения задачи о назначении “технологического окна” на участках железнодорожной сети. В работе [3] была разработана модель ЦЛП для решения задачи формирования железнодорожных составов и расписания их движения. В работе [8] модели ЦЛП были предложены для решения некоторых задач промышленного планирования. Работы [4; 5] посвящены классическим постановкам и методам решения задач ЦЛП, включая булевскую задачу ЦЛП, а в работах [6; 7] рассматриваются модели ЦЛП для решения различных задач в области управления, планирования и принятия решений.

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

Математическая модель задачи о назначении производственных ресурсов с ограничениями

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

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

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

Также определим множество  доступных к использованию электролизеров для рассматриваемой смены. Каждый элемент множества  представляет из себя вектор , где  - масса алюминия в j-м электролизере,  - содержание примесей кремния в j-м электролизере,  - содержание примесей железа в j-м электролизере,  - содержание примесей меди в j-м электролизере.

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

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

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

Будем считать, что доля содержания примесей сторонних металлов в заполненном вакуум-ковше равна среднему арифметическому долей содержания примесей сторонних металлов в электролизерах, которые использовались для его заполнения.

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

Для того, чтобы решатель мог искать не только полное, но и частичное решение поставленной задачи, введем вспомогательные переменные “на химию” , .  равна единице, если для i-го ковша не удалось найти решение, которое удовлетворяет ограничениям на максимально допустимое содержание примесей кремния и нулю в обратном случае. Аналогично для .

Введем ограничения на максимально допустимые доли содержания кремния, железа и меди в вакуум-ковшах                                

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

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

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

Функционал

С учетом введенных переменных и ограничений получаем следующую задачу минимизации:                                                                  

Смысл вспомогательных переменных

Как можно видеть из определения функционала (7), переменные  входят в него с коэффициентом 1, а вспомогательные переменные , ,  с большими положительными коэффициентами , ,  соответственно. Такой подход необходим, чтобы при решении задачи минимизации программа-решатель отдавала предпочтение использованию переменных , поскольку использование любой из вспомогательных переменных , ,  (то есть присваивание ей значения 1) приведет к значительному увеличению значения функционала. Если же в оптимальном решении, полученном в результате работы программы-решателя будет задействована хотя бы одна из вспомогательных переменных , , , это будет индикатором того, что данного множества электролизеров  недостаточно для выполнения плана по выливке алюминия-сырца в вакуум ковши из множества вакуум-ковшей .

Гипотеза и вычислительный эксперимент

Была выдвинута гипотеза, согласно которой решение поставленной задачи целочисленного линейного программирования позволит сократить число отклонений от плана производства. Для проверки гипотезы была написана программа на языке Python и проведен вычислительный эксперимент. В качестве решателя задачи целочисленного линейного программирования была использована open-source библиотека PuLP. Для вычислительного эксперимента были использованы исторические данные электролизного отделения литейного цеха. В табл. указаны значения параметров , , , использованные в вычислительном эксперименте.

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

Значения параметро

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

Анализ полученных результатов

В результате работы алгоритма было получено распределение электролизеров между вакуум-ковшами, которое удовлетворяет требованиям плана производства в 83% случаев. Для сравнения, аналогичный показатель, посчитанный на исторических данных равен 58%. Из этих 83% в 19% случаев план производства был выполнен в точности и в 64% случаев перевыполнен. Для сравнения, аналогичные показатели, посчитанные на исторических данных равны 53,6% и 4,4% соответственно. Из этого можно сделать вывод, что предлагаемый алгоритм чаще перевыполняет план, то есть заполняет вакуум-ковши алюминием-сырцом более высокого качества, чем требуется согласно плану производства. Основываясь на этих данных можно сделать вывод об эффективности предлагаемого алгоритма.

Заключение

По результатам выполнения работы составлена математическая модель задачи о назначении производственных ресурсов с ограничениями в виде задачи целочисленного линейного программирования. Сформулирована гипотеза, согласно которой предложенное решение поставленной задачи позволит сократить число отклонений от плана производства. Для проверки гипотезы написана программа на языке Python с использованием open-source библиотеки PuLP. На основе исторических данных сначала была проведена симуляция процесса распределения электролизеров между вакуум-ковшами. Затем было проведено сравнение распределения электролизеров, полученного в результате решения поставленной задачи и распределения электролизеров из исторических данных. По результатам сравнения сделан вывод об эффективности предлагаемого алгоритма.

В дальнейшей работе планируется проведение эксперимента по замене односторонних ограничений на максимально допустимые доли содержания кремния, железа и меди в вакуум-ковшах на двусторонние. Это необходимо, чтобы алгоритм не пытался перевыполнить план, как это происходит при односторонних ограничениях в текущей математической постановке задачи. Также планируется добавить возможность использования при поиске решения электролизеров не только рассматриваемой бригады, но и других бригад. Согласно гипотезе, это должно повысить качество решения.

1. Кабулова Е. Г. Интеллектуальное управление многостадийными системами металлургического производства // Моделирование, оптимизация и информационные технологии. – 2019. – Т. 7. – № 1(24). – С. 341-351. – DOI 10.26102/2310- 6018/2019.24.1.022
2. О задаче назначения “технологического окна” на участках железнодорожной сети / Гайнанов Д. Н., Игнатов А. Н., Наумов А. В., Рассказова В. А. // Автоматика и телемеханика. – 2020. – № 6. – С. 3-16. – DOI 10.31857/S0005231020060013
3. Лазарев А. А., Мусатова Е. Г. Целочисленные постановки задачи формирования железнодорожных составов и расписания их движения // Управление большими системами: сборник трудов. – 2012. – № 38. – С. 161-169
4. Шевченко В. Н., Золотых Н. Ю. Линейное и целочисленное линейное программирование. Нижний Новгород: Издательство Нижегородского госуниверситета им. Н. И. Лобачевского, 2004
5. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991
6. Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы. М.: Физматлит, 2007
7. Appa G. M., Pitsoulis L. S., Paul W. H. (Eds.) Handbook on modeling for discrete optimization. Springer Series, Int. Series in Operations Research & Management Science, vol. 88, XXII, 2006
8. Pochet Y., Wolsey L. A. Production planning by mixed integer programming. In: Springer Series in Operations Research & Financial Engineering (Eds. Mikosh, T. V., Resnick, S. I., Robinson, S. M.). 2006
9. Integer Linear Programming in Solving an Optimization Problem at the Mixing Department of the Metallurgical Production. / Gainanov D. N., Berenov D. A., Nikolaev E. A., Rasskazova V. A. Lecture Notes in Computer Science (2023) vol. 13621, pp. 145-161. doi: https://doi.org/10.1007/978-3-031-24866-5_12