ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

  Аннотация

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

Введение

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

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

1. Общая постановка проблемы

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

  •  ребра предметов параллельны ребрам полосы;
  •  предметы не пересекаются друг с другом;
  •  предметы не пересекаются со сторонами полосы;

  Также прямоугольный раскрой может быть гильотинный (рис. 1. а) и негильотинный (рис. 1 б). Под гильотинным понимается раскрой, реализуемый последовательностью сквозных резов, параллельных кромкам материала (рис. 1 а) [7]. На рис. 1 б представлен негильотинный раскрой. Раскрой, о котором пойдет речь в данной статье будет прямоугольным, гильотинным и рулонным (размер полосы: ширина = const, длина = ∞ ).

pic1
Рисунок 1 - Прямоугольный раскрой

  2. Постановка задачи

  Поставленную задачу, которую необходимо решить в данной работе можно сформулировать следующим образом: имеется исходный материал D = {W, L} полубесконечной прямоугольной формы, т.е. ширина имеет фиксированный размер W = const, а длина является условно бесконечной L ≈ ∞, а также векторы типоразмерностей прямоугольных деталей d = {d 1(w 1, l 1) , d 2(w 2, l 2), … , d i(w i, l i), … , d k-1(w k-1, l k-1), d k(w k, l k)} и их количество n = {n 1, n 2, … , n i, … ,n k-1, n k}. Необходимо оптимально разместить детали d на поверхности материала D с соблюдением следующих условий:

 • wi параллельно или перпендикулярно (если предполагается поворот детали на 90°) W – условие прямоугольности резов; [1]
  • d i∩ d j = {l;∅ }, где l – отрезок – детали не пересекаются друг с другом;
  • d i∩ D = d i – детали не выходят за пределы исходного материала;

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

  1. Оптимальными будут такие последовательности P i размещения деталей, при которых L'(P i) > min, где L' – длина использованного исходного материала L.
  2. Из отобранных по первому приоритету оптимальными будут такие последовательности K i, при которых K(P i) > min, где K' – количество необходимых резов.
 3. Из отобранных по второму приоритету оптимальными будут такие последовательности O i, при которых O(K i) > min, где O – площадь полученных отходов.

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

  • возможность увеличения типоразмера деталей в заданных пределах для минимизации количества отходов и резов;
  • ограничение на количество деталей в подкорзине (одна или несколько);
  • возможность поворотов деталей на 90°;
  • учет величины кромки, как для деталей, так и для материала.

 3. Возможные методы решения.

  Задачи подобного рода относятся к категории NP-сложных в том смысле, что не возможно ее решение полиномиальное от количества элементов время. Классическими образцами в более простых постановках таких задач являются задачи о коммивояжере и упаковке рюкзака. Такие задачи не могут быть решены с использованием только эвристических алгоритмов [4].

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

  Точное решение поставленной задачи можно получить только методом полного перебора перестановок деталей на поверхности исходного материала всех возможных последовательностей размещения. Этот метод имеет смысл применить при небольшом количестве деталей. Но когда речь идет о реальных масштабах производства, применить этот метод становиться проблематичным, так как для такого решения необходимо обработать данные, размер которых равен факториалу от количества деталей, что является в принципе невозможным из-за ограниченности вычислительных ресурсов ЭВМ. Так, например, имея N деталей, мы получаем N! перестановок, а если детали могут быть ориентированы двумя способами, число перестановок будет равна (2N)!, т. е. применяется каждая из них с поворотом на 90 ° предметами [8]. Однако, если все N деталей одного типоразмера, то результат укладки всех перестановок, очевидно, будут одинаковым, то есть число действительно различных перестановок равно 1. В общем случае количество перестановок для нахождения точного решения поставленной задачи без учета повторяющихся за счет одинаковой типоразмерности деталей будет (n 1 + n 2 + … + n k )! / (n 1!+ n 1! + … + n 1! ), что является оценкой поля для поиска решения [9]. Алгоритм генерации таких перестановок основывается на формировании очередной лексограммы такой, что меньше ее может быть только предыдущая.

  Следует отметить, что для оптимизации нахождения оптимумов размещения можно применить известные методы такие как муравьиные алгоритмы, генетические алгоритмы[10]. Очевидно, что методы использующие алгоритмы нейронных сетей нам не подходят, так как они ориентированы на обучение с «учителем», а количество обучающих наборов в этом случае будет бесконечно велико.

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

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

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

 Важной составляющей алгоритма является физическое размещение деталей на поверхности материала. Т.е. необходимо получить однозначную интерпретацию хромосомы как объекта возможного решения не подверженного коллизиям толкования. Для такой цели могут подойти некоторые известные эвристики такие как «первая подходящая», «лучшая» корзины (рис. 2) [3]. «Первая подходящая» эвристика размещает i-ю деталь представленную в хромосоме в ближайшую j-ю корзину, размеры которой не меньше размера детали. «Лучшая» эвристика ищет корзину с минимальным остатком материала после размещения в ней детали. Выбор эвристики не является очевидным, так как при всей привлекательности «лучшей корзины» существуют опасения преждевременной сходимости алгоритма в локальном экстремуме. По этой причине не предполагается использование «жадного» алгоритма.

pic1
Рисунок 2 – Использование эвристик «первая подходящая корзина» и «лучшая корзина»
(анимация: 6 кадров, 7 циклов повторения, 19.4 килобайт)

 Для реализации решения, при котором допускается поворот детали можно ген представить в виде пары {i,j}, где i – порядковый номер детали, а j – аллель {0,1}, где 0 – без поворота, 1 – с поворотом. Однако при таком подходе, во-первых, резко возрастает генофонд, а во вторых варианты кроссинговера являются не столь очевидными[1]. Кроме того, если условием будет поворот всех деталей определенного типа, то такое представление будет избыточным.

 Вторым вариантом представления хромосомы является последовательная сцепка двух векторов: вектора порядков и вектора положений (далее будем называть такую хромосому последовательной). Например, 1-3-4-2-5 | 0-1-1-0-1 означает, что деталь № 1 укладывается без поворота, следующая за ней деталь № 3 – с поворотом и т.д. При этом кроссинговер и мутация выполняется отдельно для каждого из векторов. Например, для первого вектора кроссинговер типа PMX (частично отображаемый), а для второго вектора – обычный бинарный одноточечный или двухточечный кроссинговер. Стоит, однако, заметить, что если деталь № 1 и № 2 являются одного типа, то хромосома 2-3-4-1-5 | 0-1-1-0-1 – суть одного и того же раскроя.

Третьим вариантом представления будет модификация второго, где геном вектора порядков выступает порядковый номер типа детали, а вектор положений поворачивает все детали данного типа[5]. Например, заданы детали d = {d 1(w1, l1) , d2(w2, l2), d3(w3, l3)} и их количество n = {1, 2, 3} тогда хромосома 2-3-3-1-3-2 | 0-1-1 означает, ч то первой укладывается деталь 2-го типа, второй – 3-го типа и т.д., причем детали 2-го и 3-го типа размещаются с поворотом. Не трудно заметить, что вектор положения можно интерпретировать как число с системой счисления равной количеству типов и разрядностью равной количеству деталей, а вектор n указывает сколько раз должна использоваться каждая цифра в этом числе. Очевидно, что таким образом резко сокращается поле поиска, кроме того особи хромосомы которых выражены как число легко сравниваются и если в популяции присутствует такая же рассчи-танная особь, то нет необходимости производить вычисление фитнес-функции повторно (а это самая значительная нагрузка на вычислительные ресурсы). Для данного представления хромосомы предстоит разработать соответствующие операторы кроссинговера и мутации, что является новым в реализации поставленной задачи.

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

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

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

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

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

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

  Выводы

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

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

Список источников

1. Мухачева A.C., Ширгазин P.P. Задачи упаковки прямоугольников: рандомизиро-ванная эвристика на базе двойственной схемы локального поиска оптимума // Информационные технологии. 2003. №5. С. 18-23.
2. Мухачева A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001 №3. С. 27-32.
3. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. №1. С. 2-7.
4. Валиахметова Ю.И., Карамова Е.В. Расширение генетического алгоритма комбинирование эвристик для решения задачи прямоугольной упаковки // Вестник ВЄГУ № 2, 2009. С. 40. [Электронный ресурс] – http://www.work.vegu.ru/vegu...
5. Балабанов В.Н. Многокритериальная задача рационального ппланирования продольного раскроя рулонного материала //Проблемы информационных технологий. – 2009. – №2 С. 206. [Электронный ресурс] – http://www.nbuv.gov.ua/portal
6. Петров Ю. Ю. Регуляция вероятностей кроссинговера и мутации /Инфотелекоммуникационные технологии в науке, производстве и образовании // Первая международная научно-техническая конференция. Ставрополь: СевКавГТУ, 2004.
7. Применение распределённого генетического алгоритма при решении задачи об упаковке в контейнеры / Ю. А. Бюргер, В. Й. Гнатюк, В. И. Литвиненко, А. А. Ткачук // Перспективные информационные технологии и интеллектуальные системы, 2003.
8. Данилина И.И. Алгоритмы перебора. [Электронный ресурс] – http://inf.1september.ru/2000...
9. Мастяева И.Н., Семенихина О.Н. Методы оптимизации. [Электронный ресурс] – http://www.google.com.ua/...
10. Скурихин А.Н. Генетические алгоритмы // Новости искусственного интеллекта № 4. – Москва 1995. – С. 6–46.