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

УДК 519.854.2

В.Н. БАЛАБАНОВ, аспирант ДонНТУ

ЭВОЛЮЦИОННЫЙ МЕТОД РАЦИОНАЛЬНОГО

ПЛАНИРОВАНИЯ РАСКРОЕВ РУЛОННОЙ СТАЛИ В

ПРОИЗВОДСТВЕ ЭЛЕКТРОСВАРНЫХ ТРУБ

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

Ключевые слова: рациональный раскрой, многокритериальная модель, метаэвристический метод, эволюционные вычисления.

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

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

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

материала, которая идет в отход и не может быть повторно использована) или общий расход раскраиваемого материала. Определенное распространение получили бикритериальные модели, значительно реже встречаются работы, в которых совместно рассматривается более двух различных критериев [2 - 4].

При рассмотрении задачи рационального планирования продольных раскроев рулонного материала в дополнение к критерию Zj вводится второй критерий z2 для минимизации производственных потерь за счет повышения технологичности планов раскроя: предпочтение отдается таким планам, при выполнении которых необходимость в переналадке отдельных агрегатов линии продольной резки исключается вовсе или же сводится к минимуму. Известно, что при составлении плана раскроя выигрыш по потерям материала в отход приводит к проигрышу по технологичности и требует выполнения большего числа переналадок, т.е. критерии z и z2 по своей природе являются противоречивыми [5, 6]. При составлении плана раскроя требуется отыскать компромисс, который формально описывается векторным критерием

Z =

Один из наиболее популярных подходов, применяемых при решении бикритериальных задач рационального раскроя, основан на сведении исходной многокритериальной задачи к однокритериальной за счет замены векторного критерия (1) скалярным произведением (2) [2, 3, 7]

Z* = Cyzy + .

С помощью коэффициентов C1 и С2 потери материала в отход и потери производственного характера (простои в работе линии продольной резки, необходимые для переналадки раскройного оборудования) сводятся к единому эквиваленту. Данный подход обладает рядом недостатков, поскольку точные значения весов С1 и С2 при решении практических задач рационального раскроя известны достаточно редко, кроме того, не во всех случаях величины С1 и С2 могут считаться константами [8]. Перспективным представляется иной подход, основанный на математическом аппарате Парето -оптимальных решений многокритериальных задач [9]. В последнем случае исключается необходимость в использовании коэффициентов С1 и С2, что делает метод решения задачи рационального раскроя более универсальным. Окончательный выбор плана раскроя из множества эффективных (компромиссных) решений осуществляется мастером или технологом, который при этом руководствуется собственными предпочтениями и опытом.

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

Построение математической модели. В качестве отправной точки для формализации задачи рационального планирования продольных раскроев рулонов воспользуемся моделью, впервые предложенной Канторовичем [10]. Допустим, исходный материал представлен перечнем из т рулонов, каждому из которых присваивается уникальный порядковый номер г . Обозначим пригодную к использованию длину материала как Ц (рулонам с одинаковыми размерами соответствуют различные значения индекса г). Для каждого из п заказов на ленту указывается общая длина I^, набираемая из отдельных полос

шириной w^. Предполагается, что материала достаточно для выполнения

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

полученных при раскрое рулона по карте с номером к, равняется а]к.

Установим связь между рулонами и раскройными картами с помощью булевых переменных Т*:

[1, если рулон г раскраивается по способу к,

[0, в противном случае.

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

*1 = ттXXТгк ;

к г

XXT.ka.kL, > 1] V ] ;

Тк =

к і

X Тк < 1V і;

к

X а к < Н V к;

]

є

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

Необходимость в переналадке оборудования возникает в том случае, если по плану рулоны раскраиваются различными способами: после раскроя

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

раскраиваемых рулонов (рассуждения ведутся для случая ТТт,к > 1, когда

к г

по найденному плану раскраивается более одного рулона). Формализуем задачу минимизации общего количества различных карт в составляемом плане раскроя, воспользовавшись вспомогательной функцией 8(Х^):

*2 = тшХб

к г

IX если X Тгк > 0,

8(ХТ.к ) = | г

' [0, в противном случае.

Однокритериальные задачи рационального раскроя являются ЫР-полными задачами дискретной оптимизации комбинаторного типа и относятся к классическим задачам исследования операций. Для одномерного раскроя доказано, что самостоятельная задача минимизации общего числа различных карт при заданном плане раскроя также является ЫР-полной [11]. Учитывая сложность многокритериальной задачи (3) - (7), предлагается разработать приближенный метаэвристический метод, который может быть эффективно использован для составления рациональных планов продольного раскроя рулонов, полностью удовлетворяющих требованиям реального производства.

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

Схожая стратегия ранее была реализована нами в приближенном методе решения задачи (3) - (7) в работе [7]. Векторный критерий (1) был заменен на скалярное произведение (2), для генерации новых раскройных карт решалась вспомогательная задача о ранце, перебор вариантов (объединение раскройных карт в план раскроя) выполнялся с помощью одного из методов эволюционных

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

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

Данная работа развивает метаэвристический подход, предложенный в [7]: теперь исходная многокритериальная задача не сводится к однокритериальной - вместо поиска единственного плана раскроя аппроксимируется множество компромиссных решений, которые в пространстве оценок образуют так называемый фронт Парето. Схема кодирования решений, операторы скрещивания и мутации были оставлены в прежнем виде, потребовалось существенно изменить лишь способ оценивания приспособленности хромосом и дополнить генетический алгоритм специальным механизмом "краудинга", который позволяет аппроксимировать фронт Парето более равномерно [12].

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

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

Список литературы: 1. Шевакин, Ю. Ф. Производство труб: учеб. пособие для студентов вузов, обучающихся по спец. 150106 (110600) - "Обработка металлов давлением" / Ю.Ф. Шевакин,

А.П. Коликов, Ю.Н. Райков; под ред. Ю.Ф. Шевакина. - М.: "Интермет Инжиниринг", 2005. -564 с. 2. Schilling G. An algorithm for the determination of optimal cutting patterns / G. Schilling, M.C. Georgiadis // Computers & Operations Research. - 2002. - Vol. 29. - № 8. - P. 1041-1058. 3. Belov G. Setup and open-stacks minimization in one-dimensional stock cutting / G. Belov,

G. Scheithauer // INFORMS Journal on Computing. - 2007. - Vol. 19. - № 1. - P. 27-35. 4. Munoz C. Improving cutting-stock plans with multi-objective genetic algorithms / C. Munoz [et al.] // Bio-inspired modeling of cognitive tasks: Proceedings of the second international work-conference on the interplay between natural and artificial computation, IWINAC 2007, Part I (La Manga del Mar Menor, Spain, June 18-21, 2007) / ed. by J. Mira, J.R. Alvarez. - Berlin [etc.]: Springer-Verlag, 2007. - P. 528-537. 5. Foerster H. Pattern reduction in one-dimensional cutting stock problems / H. Foerster, G. Wascher // International Journal of Production Research. - 2000. - Vol. 38. - № 7. - P. 1б57-1б7б. б. Cui Y. A heuristic for the one-dimensional cutting stock problem with pattern reduction / Y. Cui [et al.] // Journal of Engineering Manufacture. - 2008. - Vol. 222. - № б. - P. б77-б85. Т. Балабанов В.Н. Многокритериальная задача рационального планирования продольного раскроя рулонного материала [Электронный ресурс] / В.Н. Балабанов // Проблемы информационных технологий. -2009. - № 2 (GG6). Режим доступа к журналу: http://www.nbuv.gov.ua/portal/natural/

pit/2009_2/balab.htm. 8. Moretti A. C. Nonlinear cutting stock problem model to minimize the number of different patterns and objects / A. C. Moretti, L. L. de Salles Neto // Computational & Applied Mathematics. - 2008. - Vol. 27. - № 1. - P. б1-78. 9. Подиновский В.В. Парето-оптимальные решения многокритериальных задач / В.В. Подиновский, В.Д. Ногин. - М.: Наука, 1982. 256 с. 10. Канторович Л.В. Рациональный раскрой промышленных материалов / Л.В. Канторович,

В.А. Залгаллер. - 2-е изд., испр. и доп. - Новосибирск: Наука, 1971. - 299 с. 11. McDiarmid C. Pattern minimisation in cutting stock problems / C. McDiarmid // Discrete Applied Mathematics. - 1999. - Vol. 98. - № 1-2. - P. 121-130. 12. Deb K. A fast and elitist multiobjective genetic algorithm: NSGA-II / K. Deb [et al.] // IEEE Transactions on Evolutionary Computation. - 2002. - Vol. б. - №. 2. -P. 182-197.

Статья представлена д.т.н., проф. ДонНТУ Скобцовым Ю.А.

УДК 519.854.2

Еволюційний метод раціонального планування розкроїв рулонної сталі у виробництві електрозварних труб / Балабанов В.М. // Вісник НТУ "ХПІ". Тематичний випуск: Інформатика і моделювання. - Харків: НТУ "ХПІ". - 2010. - № 31. - С. 4 - 9.

У статті розглядається задача раціонального розкрою рулонів, що виникає у виробництві електрозварних труб. Пропонується багатокритеріальна модель, яка окрім втрат рулонного матеріалу у відхід дозволяє враховувати виробничі втрати і ряд важливих технологічних обмежень. Розроблено наближений метаевристичний метод розв'язання розкрійної задачі, що використовує апарат еволюційних обчислень. Бібліогр.: 12 назв.

Ключові слова: раціональний розкрій, багатокритеріальна модель, метаевристичний метод, еволюційні обчислення.

UDC 519.854.2

Evolutionary approach for roll trim planning in production of electric-welded pipes / Balabanov V.N. // Herald of the National Technical University "KhPI". Subject issue: Information Science and Modelling. - Kharkov: NTU "KhPI". - 2010. - №. 31. - P. 4 - 9.

This paper is concerned with roll trim problem in production of electric-welded pipes. Proposed model with vector criteria allows us to take into account not only trim waste but also production losses and a number of important technological constraints. To cope with this multiobjective one-dimensional cutting stock problem we developed efficient evolutionary-based metaheuristic method. Refs: 12 titles.

Key words: roll trim problem, model with vector criteria, metaheuristic method, evolutionary computation.

Поступила в редакцию 25.05.2010