Размещено на http://www.allbest.ru/

Белорусский Государственный Университет

Алгоритмы для ПРИКЛАДНЫХ Задач Раскроя и Упаковки

АВТОРЕФЕРАТ диссертации на соискание ученой степени

кандидата технических наук

по специальности 05. 13. 17 - теоретические основы информатики

Цао Даюн

Минск, 2012

Работа выполнена в Белорусском государственном университете.

Научный руководитель КОТОВ Владимир Михайлович, доктор физико-математических наук, профессор, заведующий кафедрой дискретной математики и алгоритмики Белорусского государственного университета

Официальные оппоненты:

БУЗА Михаил Константинович, доктор технических наук, профессор, профессор кафедры многопроцессорных систем и сетей факультета прикладной математики и информатики БГУ

ЛЕПИН Виктор Васильевич, кандидат физико-математических наук, доцент, ученый секретарь Института математики НАН Беларуси

Оппонирующая организация Белорусский государственный университет информатики и радиоэлектроники

Защита состоится 04 мая 2012 г. в 10.00 часов на заседании совета по защите диссертаций Д 02.01.14 при Белорусском государственном университете по адресу: 220030, г. Минск, ул. Ленинградская, 8 (корпус юридического факультета), ауд. 407; телефон ученого секретаря 209_57_09.

С диссертацией можно ознакомиться в Фундаментальной библиотеке
Белорусского государственного университета.

Автореферат разослан « » апреля 2012 г.

Ученый секретарь совета

по защите диссертаций

кандидат физ.-мат. наук доцент Е.С.Чеб

КРАТКОЕ ВВЕДЕНИЕ

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

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

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

Исследованием таких задач занимались: Харьковская школа академика Стояна Ю.Г.; институт алгоритмов и научных вычислений Германии (Ленгауэр Т.); Миленковик В., Даниэльс К. (США); Доусланд К., Доусланд В. (Великобритания); российские ученые Верхотуров М.А., Мартынов В.В., Мухачева Э.А., Петунии A.A., Фроловский В.Д. и др. Рассматривались различные подходы, основанные на сведении исходной задачи к задачам линейного, целочисленного и выпуклого программирования, использовании динамического программирования и локального поиска, выявлении эффективно разрешимых классов задач, построении графовых моделей и др.

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

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

Общая характеристика работы

Связь работы с крупными научными программами и темами

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

- НИР «Модели и алгоритмы для логистики и теории расписаний», номер гос. регистрации 20062645, 2006-2010 г.г.;

- НИР «Модели, методы и алгоритмы для задач теории расписаний, разбиения, упаковки и теории графов», 2011-2015 г.г.;

- НИР 478/39 «Модели и алгоритмы дискретной математики для решения задач оптимизации, характеризации и распознавания», номер гос. регистрации 2011 27.47.00, 2011-2015 г.г.;

- грант Белорусского Республиканского Фонда Фундаментальных Исследований НАН Беларуси «Исследование устойчивости и разработка методов решения многокритериальных задач дискретной оптимизации» (договор № Ф11К-095).

Цель и задачи исследования

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

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

- исследовать проблему решения задач раскроя и упаковки, определить классы задач, допускающие высокую степень автоматизации;

- разработать эффективные алгоритмы для задач двумерной прямоугольной упаковки в контейнеры и двумерной прямоугольной упаковки в полосу;

- разработать эффективные алгоритмы для решения задач двумерного прямоугольного гильотинного раскроя полосы и прямоугольника;

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

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

Предметом исследования является разработка эффективных алгоритмов и создание библиотеки программ.

Положения, выносимые на защиту

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

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

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

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

Личный вклад соискателя

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

Апробация результатов диссертации

Отдельные положения работы докладывались и обсуждались на конференциях различного уровня:

l на международной научно-технической конференции «Информационные системы и технологии IST'2010» (Минск, Белорусский государственный университет, 2010);

l на 68-й научной конференции студентов и аспирантов (Минск, Белорусский государственный университет, 2011);

l на II международной научно-практической конференции «Технологии информатизации и управления» (Гродно, Белорусский государственный университет, 2011);

l на международной научно-технической конференции «Proceedings of 2011 International Conference on Electronic & Mechanical Engineering and Information Technology» (Харбин, Харбинский научно-технический университет, 2011).

l на международной научно-практической конференции «Информационные технологии и информационная безопасность в науке, технике и образовании ИНФОТЕХ - 2011» (Севастополь, Севастопольский национальный технический университет, 2011).

Опубликованность результатов диссертации

Основные результаты диссертации опубликованы в 11 научных работах, в том числе в 6 статьях в соответствии с п.18 Положения о присуждении ученых степей и присвоении ученых званий в Республике Беларусь (общий объем статей составляет 2,18 авторских листа), в 1 статье в сборнике научных статей, в 3 статьях в сборниках материалов научных конференций, в 1 тезисе.

Структура и объем диссертации

Диссертация состоит из оглавления, введения, общей характеристики работы, четырех глав, заключения, библиографического списка и приложений. Полный объем диссертации составляет 102 страницы, в том числе 41 рисунок занимает 29 страниц, 15 таблиц - 15 страниц, 3 приложения - 9 страниц. Библиографический список состоит из 123 наименований, включая собственные публикации соискателя (занимает 9 страниц).

Основное содержание

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

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

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

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

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

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

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

Для задачи двумерной упаковки в контейнер заданным считается конечное множество небольших прямоугольных элементов I_i, i = 1, …, n, и один большой прямоугольник (контейнер) шириной W и высотой H. Необходимо упаковать некоторые элементы в контейнер таким образом, чтобы минимизировать свободное пространство, и чтобы никакие два элемента не должны перекрывались, границы элементов были параллельны границам контейнера, элемент нельзя поворачивать. Без потери общности считается, что все линейные размеры элементов и контейнеров являются целыми.

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

Для построения алгоритма вводятся специальные понятия, которые описывают границы областей упаковки, возможные места для размещения элементов, наборы допустимых элементов для размещения и целевой функционал качества размещения для принятия решений. Так, учитывая специфику задачи, для размещения определяется количество несвязных областей, а в качестве возможных мест размещения элементов определяется множество углов (называемых в дальнейшем подходящими, или СС углами), образованных сторонами уже размещенных прямоугольников и/или сторонами контейнера. До упаковки первого элемента в контейнер имеется 4 подходящих угла, а количество несвязных областей m = 1. После выбора и упаковки очередного элементы количество областей и множество углов перевычисляется. В контейнере на рисунке 1 размещено 4 предмета, имеется 8 таких углов.

Рисунок 1 Пример подходящих углов

Множество подходящих углов U определяется с помощью формулы (1):

, (1)

где U_i - множество подходящих углов в одной связной области i, а m соответствует количеству несвязных областей в контейнере (рисунок 2). Например, до упаковки элемента I₅ в контейнер, U = {U₁}, U₁ = {C₁, C₂, C₃, C₄, C₅, C₆, C₇, C₈} (одна область, 8 подходящих углов).

При упаковке очередного предмета количество областей может изменяться. После упаковки I₅ получается две несвязные области, т.е. U' = {UЎЇ 1, UЎЇ 2}, множество углов первой области UЎЇ 1={C₁, C₇, C₈, C₉, C₁₂}, а второй соответственно UЎЇ 2= {C₂, C₃, C₄, C₁₀, C₁₁}.

Рисунок 2 Разделение на и

Понятно, что конфигурация получаемых областей важна при последующей упаковке. Необходимо уметь быстро вычислять границы и оптимизировать форму этих областей. Границы области U_i для упаковки элемента определим следующим образом. Пусть l_U₁ обозначает левую границу U₁, l_U₁ = W обозначает правую границу U₁. Аналогично можем определить, что t_U₁ и b_U₁ обозначают верхнюю и нижнюю границы U₁. Таким образом, если U_i делится на UЎЇ e и UЎЇ f, то эти границы можно вычислить с помощью формул (2-5):

, ; (2)

, ; (3)

, ; (4)

, , (5)

где s соответствует числу углов в UЎЇ e.

Ключевым моментом является способ определения функционала, который учитывает специфику задачи. Для оценки качества размещения элемента в определенный угол предлагается целевой функционал pFit_C_k, который вычисляется посредством формулы (6):

(6)

Здесь параметр s соответствует количеству сторон уже размещенных элементов, которых касается размещаемый в угол C_k элемент I_i, параметр p_j равняется 2, если I_i касается одной границы другого упакованного элемента, и p_j равняется 1, если I_i касается одной границы контейнера (рисунок 3).

Рисунок 3 Вычисление pFit_C_i в каждом U_k

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

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

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

На рисунке 4 проводятся результаты сравнения времени работы предлагаемого алгоритма с наиболее известными алгоритмами GRASP и TABU.



Рисунок 4 Сравнение алгоритмов по времени

Эксперимент показал, что для больших тестовых задач время уменьшилось минимум в 2 раза, при этом плотность упаковки не ухудшилась.

Далее рассматривается задача упаковки в полосу. В ней входными данными являются полоса бесконечной высоты, ширины W, и n прямоугольных элементов, элемент I_i имеет ширину w_i и высоту h_i (w_i, h_i ? Z⁺) и, причем один из линейных размеров элемента не превышает W. Требуется осуществить ортогональную упаковку всех элементов в полосу минимальной высоты, причем никакие два элемента не могут перекрываться и элементы нельзя поворачивать на 90^o.

Специфической особенностью задачи является отсутствие верхней границы. Для описания текущего динамического описания состояния полосы был определен параметр «временная упаковочная высота» (TH).

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



Рисунок 5 RCC и SCC

Для нового элемента I_i с w_i ? h_i и угла C_j выясняется отсутствие пересечения с каким-либо уже упакованным элементом или границами полосы. Если I_i можно разместить, то определим s как количество сторон других элементов, которых будет касаться размещаемый элемент, а t как количество подходящих углов, которые он будет занимать. Тогда целевой функционал W_pFit_C_j для оценки качества размещения элемента i в подходящий угол j по формуле (8).

(8)

Здесь q_k равняется 2, если I_i занимает действительный подходящий угол, и q_k равняется 1, если элемент I_i занимает фиктивный подходящий угол. Аналогичным образом можно определить H_pFit C_j, если h_i > w_i.

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

Эффективность алгоритма проверялась на основе вычислительного эксперимента с использованием библиотек стандартных тестов.

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



Рисунок 6 Сравнение алгоритма BF_BCC с другими алгоритмами

Рисунок 7 Сравнение BF_BCC с Best-Fit, GA + BLF и SA + BLF

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

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

Модифицированный принцип «подходящего угла» оказался чрезвычайно практичным и для этой задачи ( рисунок 8).

Рисунок 8 Возможные подходящие углы

Пусть U = {UI₁, UI₂, ?, UI_l} обозначает множество подходящих углов для l контейнеров (i = 1, ?, l). Вычислим длины касания размещаемого элемента с другими элементами или границами контейнера. Для элемента I_t величина I_t_TL_B соответствует длине касания нижней границей I_t с другими элементами в той же контейнере или границей контейнера. Аналогично определяем величины I_t_TL_L, I_t_TL_T и I_t_TL_R ( рисунок 9).

Рисунок 9 Длина касания границ

Пусть r соответствует количеству границ упакованных элементов, которых касается новый элемент, а s соответствует количеству подходящих углов, занимаемых элементом. Тогда значение функционала Fit_A при размещении элемента I_t в угол C_j вычисляется согласно формуле (9).

(9)

Здесь q_k равняется 2, если I_t занимает действительный подходящий угол, и q_k равняется 1, если I_t занимает фиктивный подходящий угол. Если для разных углов значения одинаковы, то вычисляется значение Fit_B_C_j, используя формулу (10), затем выбирается лучший угол с максимальным значением Fit_B_C_j.

. (10)

Выполнение алгоритма начинается с вычисления непрерывной нижней оценки L₀ оптимального значения по формуле (11).

. (11)

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

Проведен вычислительный эксперимент по оценке эффективности разработанного алгоритма ( рисунок 10).



Рисунок 10 Сравнительное время в случае IBF и поиска Tabu

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

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

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

Дана бесконечная лента фиксированной ширины W и n малых прямоугольных элементов шириной w_i и высотой h_i, для i = 1, …, n. Цель состоит в упаковке всех этих элементов в полосу с минимальным использованием высоты при условии, что все элементы располагаются ортогонально, их нельзя поворачивать, никакие два элемента не перекрываются, и выполнены гильотинные ограничения.

Для решения задачи был разработан мультирекурсивный гильотинный алгоритм (MRGA), который предполагает несколько этапов решения: внешних рекурсивных уровней (ORLA), внутреннего рекурсивного исправления (IRRA) и алгоритм постобработки (PA), которые решаются с помощью соответствующих алгоритмов ( рисунок 11).

Рисунок 11 Рекурсивный алгоритм

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

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

Если имеются два соседних незанятых пространства A и B на одном уровне удовлетворяют одному из следующих условий, то будем говорить, что область C_AB имеет g-комбинируемость.

Условие 1. Если существует зона SI для A и B, для которой выполняется (12), то C_AB имеет g-комбинируемость.

, (12)

где T есть множество всех ORLA-элементов, поддерживаемых SI.

Условие 2. Предположим, что K является смежной зоной A, и K¹ является смежной зоной B. Если K непосредственно примыкает к K¹, тогда C_AB имеет g-комбинируемость.

Условие 3. Пусть K¹ есть смежная зона B, SQ есть зона A с той же самой y-координатой верхних границ. Если существует K?SQ для которой выполняются следующие условия, то C_AB имеет g-комбинируемость.

1) x_Ii ? x_K + width_K, I_i ? SQ\{K}, i = 1, …, |SQ| ? 1;

2) K¹ есть смежная зона K;

3) y_B + height_B равняется y-координате верхней границы уровня.

Свойство 1. Комбинируемость трансферабельна, т.е., если C_AB и C_BC имеют g-комбинируемость и C_(AB)C ? Ш, то C_(AB)C имеет g-комбинируемость.

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

Для того, чтобы эффективно использовать возможные межуровневые свободные области разработана специальная структура данных, названная троичным деревом упаковки (рисунок 12).

Рисунок 12 Троичное дерево упаковки для гильотинного разреза

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

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

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

Правила упаковки реализованы следующим образом ( рисунок 13).

1) Если существует неупакованный элемент I в P таким образом, что height_I = height_I2 (если такой элемент больше 1, выбирается один элемент с максимальной шириной), то он упаковывается внизу слева в R₃, см. тип I.

2) Если существует неупакованный элемент I в P таким образом, что width_I = width_R2- width_I2 (если такой элемент больше 1, то выбирается элемент с максимальной высотой и высота не превышает высоту I₂), то он упаковывается внизу слева R₃, см. тип II.

3) В остальных случаях выбирается неупакованный элемент I с максимальной высотой P, и высота I не превышает высоту I₂, элемент упаковывается слева внизу в R₃, см. тип III.

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



Рисунок 13 Описание рекурсивного направления и правил выбора в ORLA

Проведен вычислительный эксперимент по оценке эффективности разработанного алгоритма ( рисунок 14).

Рисунок 14 Сравнение результатов

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

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

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

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

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

Библиотека и отдельные ее части легко встраиваются в существующие промышленные системы. Эффективность разработанных программных средств проверялась на реальном производстве. Практическое внедрение модулей библиотеки обеспечило оптимизацию раскроя стекла на 5%-10%.

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

ЗАКЛЮЧЕНИЕ

Основные научные результаты диссертации

В результате выполнения диссертационной работы были получены следующие основные результаты:

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

2. Построены алгоритмы для задач двумерной упаковки в контейнеры и в полосу, учитывающие специфику прикладных задач. Вычислительный эксперимент показал, что качество построенных решений до 80% лучше, а время работы существенно меньше, чем у известных алгоритмов [10, 2, 8, 11, 3].

3. Построены мультирекурсивный алгоритм для решения задач гильотинного раскроя полосы и двухэтапный алгоритм для задачи гильотинного раскроя прямоугольника, основанные на оптимизации межуровневых пространств, что позволяет повысить качество раскроя за счет минимизации отходов. Качество построенных решений до 10% лучше, чем у известных алгоритмов [9, 5].

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

Рекомендации по практическому использованию результатов

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в научных журналах

1. Kotov, V.M. A heuristic algorithm for the two-dimensional single large bin packing problem / V.M. Kotov, Dayong Cao // Bul. Acad. Єtiinюe Repub. Mold. Mat. 2010. №.3. С. 23-28.

2. Kotov, V.M. A heuristic algorithm for the non-oriented 2D rectangular strip packing problem / V.M. Kotov, Dayong Cao // Bul. Acad. Єtiinюe Repub. Mold. Mat. 2011. №.2. С. 81-88.

3. Цао, Д. Улучшенный Best-Fit алгоритм для решения задач двумерной ориентированной упаковки в контейнеры / Д. Цао // Информатика. 2011. №.2. С. 134-138.

4. Cao, Dayong. Hybrid algorithm for two-dimensional off-line oriented bin packing problem / Dayong Cao, Mei Yang, Runtao Liu // Computer Engineering and Applications. 2011.№.7.C. 16-19.

5. Котов, В.М. Мультирекурсивный алгоритм для задачи гильотинного раскроя полосы / В.М. Котов, Даюн Цао // Информатизация образования.2012. №.1(66). С.86-92.

6. Cao, Dayong. A Two-Stage Heuristic Approach for Two-Dimentional Guillotine Bin Packing Problem / Dayong Cao, Mei Yang, V.M. Kotov, Runtao Liu // Computer Integrated Manufacturing Systems. 2012. №.7. С. 1-16.

Статьи в сборниках и тезисы

7. Cao, Dayong. A two-stage approach for two-dimensional bin packing problem with guillotine constraint / Dayong Cao, V.M. Kotov // Информационные системы и технологии Informational systems and technologies: (IST' 2010): материалы VI международной конференции-форума, Минск, 24 - 25 ноября 2010 г. / БГУ; под ред. А.Н Вараскина [и др.]. Минск, 2010. С. 318-322.

8. Cao, Dayong. A best-fit heuristic algorithm for two-dimensional bin packing problem / Dayong Cao, V.M. Kotov // Proceedings of 2011 International Conference on Electronic & Mechanical Engineering and Information Technology, Harbin, 12 - 14 August 2011. Harbin, 2011. P. 3789-3791.

9. Котов, В.М. Мульти-рекурсивный гильотинный подход для задачи двумерной упаковки на ленте / В.М. Котов, Даюн Цао // Информационные технологии и информационная безопасность в науке, технике и образовании: (ИНФОТЕХ - 2011), Севастополь, 5 - 10 сентября 2011 г. / А.П. Фалалеев [и др.]. Севастополь, 2011. С. 88.

10. Cao, Dayong. A heuristic algorithm for two-dimensional strip packing problem / Dayong Cao, V.M. Kotov // Технологии информатизации и управления: сборник научных статей. / редкол.: А.М. Кадан (отв.ред.) [и др.]; - Минск: БГУ, 2011. Выпуск 2. С. 114-118.

11. Цао, Даюн. Алгоритмы для решения двумерной задачи упаковки / Даюн Цао // Сборник работ 68 научной конференции студентов и аспирантов Белорусского государственного университета, Минск, 16-19 мая 2011 г.: В 3 ч. / Белорус. гос. ун-т. Минск, 2011. Ч. 1. С. 169-174.

РЭЗЮМЭ

Цао Даюн

алгарытмы для прыкладных задач раскрою і ўпакоўкі

Ключавыя словы: задача раскрою i ўпакоўкi, задача двухмернай упакоўкi ў кантэйнеры, задача двухмернай упакоўкі на ленце, гільяцінны раскрой, рэкурсіўны алгарытм, эўрыстычны алгарытм.

Мэта даследвання: распрацоўка метадаў i алгарытмаў для рашэння задачы двухмернага раскрою i ўпакоўкi, іх скарыстанне.

Метады даследвання: тэарэтычны аналіз навуковай літаратуры, лакальны пошук, структуры дадзеных, дыскрэтная матэматыка, вылічальны эксперымент.

Атрыманыя вынiкi i iх навiзна. У дысертацыі былі распрацаваны новыя алгарытмы для вырашэння розных задач двухмернага раскрою і ўпакоўкі, у тым ліку алгарытм BCC для задачы двухмернай упакоўкі у адзін вялікі кантэйнер, алгарытм BF_BCC для задачы двумернай упакоўкі ў паласу, мадыфікаваны Best-Fit алгарытм для рашэння задач двухмернай арыентаванай упакоўкі ў некалькі кантэйнераў, мультырэкурсіўны гільяцінны метад (MRGA) для задачы двухмернага раскрою паласы і двухэтапны метад для гільяціннага двухмернага раскрою прамавугольніка. У параўненні з добра вядомымі класічнымі алгарытмамі з літаратуры, прапанаваныя алгарытмы дазволілі атрымаць больш якасныя і надзейныя вынікі ўпакоукі і раскрою за больш кароткі час, асабліва для задач вялікага памеру.

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

РЕЗЮМЕ

Цао Даюн

Алгоритмы для ПРИКЛАДНЫХ Задач Раскроя и Упаковки

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

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

Методы исследования: теоретический анализ научной литературы, локальный поиск, структуры данных, дискретная математика, вычислительный эксперимент.

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

Область применения. Алгоритмы могут быть использованы при решении практических задач двумерного раскроя и упаковки в промышленности (распил фанеры, разрезка стекла, верстка материала в газетах).

SUMMARY

Cao Dayong

algorithms for APPLIED cutting and packing problemS

Key words: cutting and packing problem, two-dimensional packing problem, two-dimensional strip packing problem, guillotine, recursive algorithm, heuristic algorithm.

The aim of the research is construction of methods and algorithms for solving the two-dimensional cutting and packing problem, their implementation.

The methods of the research: theoretical survey of literature, local search, data structures, discrete mathematics, computational experiment.

The results obtained and their novelty. In the thesis we have presented new algorithms for variety two-dimensional cutting and packing problems, which include algorithm BCC for two-dimensional single large bin packing problem, the algorithm BF_BCC for two-dimensional strip packing problem, the modified best-fit algorithm for two-dimensional packing problem, the multi-recursive algorithm for two-dimensional guillotine strip packing problem and the two-stage hybrid algorithm for two-dimensional guillotine bin packing problem. Compared with some classical algorithms from literatures, these proposed algorithms could provide better and reliable packing results with less computable time, especially for the large scale packing problem.

The area of application. The algorithms proposed in the thesis could be used for solving two-dimensional cutting and packing problem in the industry such as wood or glass cutting and newspapers paging.

Размещено на Allbest.ru