ВВЕДЕНИЕ 3
Глава I Описание математической модели 7
Описание математической модели для задачи гильотинного раскроя 7
Модификация алгоритма ФГР 11
Построение карты раскроя с применением метода ветвей и границ 14
Псевдокод алгоритма ФГР рулонного материала 21
Псевдокод алгоритма выбора оптимального целочисленного плана методом ветвей и границ 23
Глава II Структура приложения 25
Архитектура приложения 25
Взаимодействие приложения с пользователем 26
Разработка Windows - приложения 32
Глава III Анализ результатов 35
Интерпретация результатов, полученных в результате применения модификации алгоритма ФРГ рулонного раскроя с ограничением на размеры рабочего стола
Анализ результатов, полученных с применением метода ветвей и границ 44
Заключение 49
Литература 51
Приложение
Купить

Внедрение современных методов в производственный процесс является весьма актуальной задачей на сегодняшний день. Без исключения каждому предприятию важно производить продукцию с минимальным количеством затрат. Одним из источников затрат является расход материалов, большие сроки подготовки раскроя, а также нерациональное размещение деталей на листе, что впоследствии ведет к превышению запланированного бюджета. Рациональным решением данной проблемы является построение карт раскроя с использованием современных алгоритмов раскроя материала. Именно этой проблеме посвящена данная работа.
Впервые задачи раскроя были сформулированы Леонидом Витальевичем Канторовичем в 40-х годах XX века, однако потребность в ее решении впервые возникла в 30-х годах, когда задачами теории раскроя занимался Фельдман Х.; он интересовался задачами оптимальной распиловки бревен. Однако сформулированные им требования не полностью охватывали все условия и полученные результаты на практике могли быть неверными.
В свою очередь Канторович в 1951 году, задолго до широкого распространения компьютеров, вместе с Залгаллером предложили способ решения задачи раскроя методом линейного программирования.
Сегодня, в век компьютерных технологий эту задачу можно решать значительно быстрее, поскольку нет необходимости делать расчеты вручную.
Рациональный раскрой, как уже было ранее сказано, преимущественно зависит от эффективности того или иного алгоритма раскроя. А вычислительная сложность зависит от затраченного времени, то есть количества шагов, и памяти, используемой в процессе вычислений.
В зависимости от вида материала различают одномерный, двумерный раскрои и трехмерный раскрой-упаковку [1]. В одномерном случае материал для раскроя поступает в виде однотипных полос, например, раскрой на заготовки бревен или труб. В случае трёхмерного раскроя - упаковки, рассматриваются задачи организации складских помещений. Двумерный раскрой применяется при работе с различными листовыми материалами, например, раскрой рулонного материала на прямоугольные заготовки.
Среди существующих задач раскроя можно выделить фигурный раскрой, который позволяет размещать детали непрямоугольной формы, косоугольный раскрой, включающий в себя детали прямоугольной формы и грани которого располагаются не параллельно кромкам материала, а также прямоугольный - раскрой, состоящий из фигур прямоугольной формы, грани которых параллельны кромкам материала [2].
В свою очередь, прямоугольный раскрой [3,2] делится на гильотинный [4] и негильотинный. Гильотинный раскрой осуществляется с помощью гильотинных ножниц. Особенность данного оборудования состоит в том, что каждый рез происходит от одного края материала до другого, параллельно кромкам. Таким образом, гильотинный раскрой - раскрой материала путем сквозных резов, параллельных граням материала. Соответственно, при негильотинном раскрое сквозных резов не допускается.
Из того, что рассматриваемая задача гильотинного размещения является NP-трудной [5] следует, что не существует алгоритма полиномиальной сложности для ее решения, поэтому точный результат может быть определен только за экспоненциальное время.
Несмотря на это, подходов к решению данной задачи было предложено немало; в их числе эволюционные - модифицированный генетический алгоритм и алгоритм муравьиной колонии [6,4], а также вероятностные - поиск с запретом [7] и имитация отжига [8]. Имитация отжига и поиск с запретами — это алгоритмы, принцип которых заключается в построении последовательности решений, где каждое из решений является соседним для предыдущего в заданном диапазоне. В генетическом алгоритме для нахождения нового решения используется процедура скрещивания и мутаций. Идея метода муравьиной колонии заключается в сборе статистической информации о найденных успешных решениях [6]. Однако все эти методы являются метаэвристическими.
В качестве неплохой эвристики, предназначенной непосредственно для задачи гильотинного раскроя можно выделить послойный метод, основы которого заложены в работах М. Адамовича и А. Албано, а также Э.А. Мухачевой и Л.Ф. Розановой в [1]. Принцип данного алгоритма заключается в слоевом размещении элементов, где каждый слой состоит из определенной группы элементов. Послойные алгоритмы строят планы раскроя сложности О(п * т2 Iодт), где m - количество типов деталей, а n - общее количество деталей. Однако к недостатку данного алгоритма можно отнести плохо заполненные области в конце полосы, которые сильно сказываются на итоговом результате [9].
В статье [5] Mir-Bahador Aryanezhad был представлен другой быстрый эвристический алгоритм, решающий поставленную задачу. Данный подход сводится к приведению к задаче о рюкзаке. В задаче о рюкзаке выбор деталей в карту раскроя осуществляется в зависимости от ценности детали, с учетом того, что вместимость рюкзака ограничена. Предполагается, что неиспользуемые детали будут храниться на складе. Данный алгоритм показывает достаточно неплохие результаты на больших размерностях, но, это все же эвристический метод.
Однако часто эвристические и метаэвристические алгоритмы дают решение, далекое от оптимального и не всегда можно оценить погрешность полученного решения. Таким образом, важно разрабатывать и исследовать и точные методы решения задачи.
В качестве примера точного метода можно привести задачу целочисленного программирования, представленную в статье [10]. Такая модель задачи является одной из самых сложных с вычислительной точки зрения, поскольку учет целочисленных значений накладывает огромное количество ограничений. Для решения этой задачи используется метод ветвей и границ, который подразумевает производить разбиения по каждой переменной.
Другой точный метод решения задачи гильотинного раскроя основан на применении функции гильотинного размещения [11].
Функцией гильотинного размещения (ФГР) для набора прямоугольников Dбудем называть функцию f (■; D)(f (•; D) : R ^ R),значение которой в точке х равно минимальной длине листа шириной х, достаточной для того, чтобы разместить набор прямоугольников Dдля гильотинного раскроя [11].
Целью моей научно-исследовательской работы является разработка модификации алгоритма ФГР, учитывающего увеличение количества ограничений для размещаемого набора, а также определения фиксированных размеров листа. Это необходимо в связи с введением ограничений на размеры рабочей поверхности - стола, на котором происходит раскрой. Таким образом, ширина и длина стола будут фиксированы и при построении карты раскроя будет необходимо сохранять величину первого разреза, а также размещение детали после него.
Следовательно, можно выделить следующие задачи:
1. Разработка модификации алгоритма ФГР с учетом ограничений размеров рабочего стола и типа исходного материала.
2. Разработка модификации алгоритма с применением метода ветвей и границ, при условии целочисленности полученного результата, а также наличия ограничения на размер полученных карт.
3. Анализ полученных результатов каждого из алгоритмов.
4. Реализация пользовательского интерфейса для демонстрации результатов работы программ

Купить