автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов

ИНФОРМАЦИОННЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОГО РАСКРОЯ-УПАКОВКИ НА ОСНОВЕ КОНСТРУКТИВНЫХ И НЕЙРОСЕТЕВЫХ ПОДХОДОВ

05.13.17 - теоретические основы информатики

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

Красноярск - 2009

003463422

Работа выполнена на кафедре информационных технологий ГОУ ВПО «Сибирский государственный технологический университет»

Научный руководитель кандидат технических наук, доцент

Жуков Леонид Александрович

Официальные оппоненты: доктор технических наук, профессор

Доррер Георгий Алексеевич

доктор технических наук, профессор Миркес Евгений Моисеевич

Ведущая организация: Уфимский государственный авиационный

технический университет

Защита диссертации состоится « 7 » апреля 2009 года в 14.00 часов на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, корпус Ж, ауд. 1-15.

С диссертацией можно ознакомиться в научной библиотеке Сибирского федерального университета по адресу: ул. Киренского, 26, ауд. Г274.

Автореферат разослан « 6 » марта 2009 г.

Ученый секретарь диссертационного совета к.т.н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Фундаментальные научные разработки в области решения задач раскроя-упаковки принадлежат JI.B. Канторовичу и В.А. Залгаллеру (1950). Результаты дальнейших исследований в этой области отражены в работах Э.А. Мухачевой (1979), Е.П. Бороновского (1967), А.Ф. Валеевой (2000), И.П. Норенкова (1999), Ю.А. Кочетова (2000), И.В. Романовского (1977), A.C. Филипповой (1999), Житникова В.П. (2000), В.М. Картак (2004); за рубежом - P. Gilmore & R. Gomory (1965), G. Scheithauer & J. Temo (1970), H. Dyckhoff

3

i

о. •

(1990), А. Вс^ск (1998) и др.

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

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

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

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

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

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

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

В рамках цели решаются следующие задачи:

1. Проанализировать известные постановки и методы решения задач раскроя-упаковки и наметить пути их совершенствования.

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

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

4. Провести серии экспериментов и проанализировать полученные результаты. '

5. Реализовать теоретические результаты в виде алгоритмов и прикладного программного обеспечения.

Методы исследования.

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

На защиту выносятся:

1. Информационные модели задач раскроя-упаковки.

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

3. Алгоритмы формирования безотходных двух и трехмерных упаковок, обеспечивающие получение приоритетных списков для заданного количества объектов.

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

Научная новизна работы:

1. Разработаны методы решения задач двух и трехмерного ортогонального раскроя-упаковки.

2. Разработаны алгоритмы формирования двух и трехмерных безотходных упаковок.

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

Практическая ценность работы:

1. Приведены информационные модели задач «-мерной (и = 1, 2, 3) ортогональной упаковки-раскроя.

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

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

Реализация результатов работы. В настоящее время результаты исследования и разработок используются несколькими организациями, что подтверждается соответствующими актами о внедрении: ГОУ ВПО «Сибирский государственный технологический университет», логистической компанией «Транс-Бизнес».

Апробация работы и публикации.

Результаты работы, а также отдельные ее разделы были представлены на конференциях и семинарах, основными из которых являются: Всероссийская научно-практическая конференция «Лесной и химический комплексы -проблемы и решения (экологические аспекты)», Красноярск, 2004, 2007; Семинар «Новые информационные технологии», Москва, МГИЭМ, 2005; Всероссийская научно-техническая конференция «Нейроинформатика — 2005», Москва, МИФИ, 2005; IV, V Всесибирский конгресс женщин -математиков, Красноярск, 2006, 2008; IX Всероссийский семинар «Моделирование неравновесных систем», Красноярск, ИВМ СО РАН, 2006; IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности», Пенза, 2006; III Всероссийская научно-практическая конференция «Компьютерная интеграция производства и ИЛИ технологии», Оренбург, 2007; X Всероссийская конференция «Проблемы информатизации региона», Красноярск, 2007; Всероссийская научная конференция «Модели и методы обработки изображений», Красноярск, 2007; VI Международная научно-техническая конференция «Материалы и технологии XXI века», Пенза, 2008.

Публикации. Основные результаты работы опубликованы в 12 печатных работах (из них 2 статьи в изданиях по списку ВАК), I свидетельство об официальной регистрации программ для ЭВМ.

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

Диссертация состоит из введения, 4 глав, заключения и списка использованных источников. Основное содержание работы изложено на 126 страницах текста, содержит 29 рисунков и 20 таблиц. Список используемых источников включает 183 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведен обзор многообразия задач раскроя-упаковки и выделен класс задач, решаемых в рамках диссертационной работы. Приведены постановки и мЬдели наиболее известных задач «-мерного ортогонального раскроя-упаковки (и = 1,2, 3) и обзор методов их решения.

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

Во второй главе приведены информационные модели задач раскроя-упаковки. Представлены обобщенная схема решения задач раскроя-упаковки и математические модели задач ортогонального раскроя-упаковки для п = 1, 2, 3. Приведена модель обработки данных с помощью нейронных сетей в нотации ГОЕРО. Представлено формальное описание групп операций при нейросетевом исследовании с помощью нейронных сетей Хопфилда. Такой подход в общем случае позволяет формализовать технологию работы пользователя при нейросетевом исследовании.

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

Рисунок 1 - Подходы к решению задач раскроя-упаковки

В настоящее время существуют различные модели представления п-мерных задач (л = 1, 2, 3) раскроя-упаковки. В диссертационной работе, в качестве основных, представлены модели трехмерной (параллелепипедной) упаковки.

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

<1¥, А Н, к, и, М,м/, I, К т, Ь, г, у, & У>,

где \У= (IV,, ..., \Уь) - ширина, 1= (А, 1ъ-, Ьк) - длина, Н = (Н,, Н2,..., Щ - высота параллелепипедов; к - количество типов параллелепипедов; и =

и2,..., щ) - количество параллелепипедов определенного вида; М - (М/, М2,

..., Мк) - предельно допустимая масса параллелепипедов; = (ж/, м>2,..., \\>щ) -

ширина, / = (/;, 12,..., 1т) - длина, А = (ки Иг,..., И„) - высота коробок; т -

количество типов коробок; Ъ - (Ь/, Ь2< ■■■,Ьт) - количество коробок

определенного типа; е - признак направления: е = 1, если объекты можно

поворачивать, е = 0 в противном случае; у - признак гильотинности: у = 1,

если задачу решают с учетом признака гильотинности, и полагают равным О

в противном случае; £ = g2, —. gm) - масса объектов; V - набор

к

технологических ограничений; с = ^ик - общее количество

.

параллелепипедов; п = — общее количество коробок.

ы

Выходной информацией (в общем виде) является карта раскроя, представленная в виде следующего набора:

<П, X, У, 2, Р, Е>,

где П-преобразованный список коробок; X = (Зс/, х2, ..., х„), У = (уи у2, ..., у„), Ъ - 12, ..., г„) - векторы минимальных координат коробок; Р - множество исходных параллелепипедов, в которые упакованы некоторые коробки; Е = (в/, еь..., е„) - признаки поворота, значение которых может принимать одно из 6 значений.

Зададим КРА - коэффициент раскроя (процентное отношение суммарного объема всех упакованных коробок к занятому объему параллелепипеда), а х ~ время решения задачи.

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

<П,Х, У, г, £> = а (< IV, Н, М, /, И, т, Ь, е, у, & У>).

► тт т —»гшп

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

• ортогональное размещение коробок в параллелепипеде;

• неперекрытие коробок между собой;

• неперекрытие коробками граней параллелепипедов.

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

Для задач с фиксированным сторонами параллелепипедов, необходимо найти их минимальное количество

<П,Х, У, I, Р, Е> = П(<1Г, Ь, Н, к, и, М, I, А, т,Ъ, г,у, & ¥>),

¿,Р, ->шт

КРА 100% т —> тт

На данную систему оказывают влияние следующие факторы:

• способ (метод) решения задачи;

• приоритетный список (последовательность объектов);

• параметры оптимизации.

В третьей главе описаны алгоритмы формирования безотходных двух и трехмерных упаковок. В результате такого разбиения формируется последовательность заданного количества прямоугольников, отвечающего безотходной упаковке, с указанием их размеров при фиксированных значениях больших объектов. Представлено описание метода плоскостей "для решения задач трехмерного (параллелепипедного) и двухмерного (прямоугольного) ортогонального. раскроя-упаковки. Рассмотрены экспериментальные исследования эффективности применения метода плоскостей для решения задач трех и двухмерных упаковок. Приведены данные для сравнения с другими методами для однотипных классов задач, сгенерированных на основе методики Г. Вешера и безотходных примерах Е. Hopper.

Шаги алгоритма для формирования безотходной трехмерной упаковки:

1) задать количество областей qx> qz и qxi;

2) определить целое число коробок в каждой области параллелепипедной формы по формуле:

и/(25>„ •?,■)

3) для одной из отсеченных параллелепипедных областей задать случайным образом координаты правого верхнего угла р - 1 коробок: случайным образом генерируются координаты по ^в диапазоне от 1 до Ы qxi - А, по оси У - от 1 до W/qy - Д, где Д - случайная величина, введенная для устранения попадания на края области; координата по оси Z фиксирована и определяется координатой z параллелепипедной области;

4) координаты последней коробки определяются остатком от незанятой части области;

5) достроить коробки, полностью заполнив текущую параллелепипедную область;

6) повторить шаги 3-5 для оставшихся отсеченных параллелепипедных областей.

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

Метод плоскостей для решения трехмерных задач раскроя-упаковки.

Особенностями метода являются:

- непосредственное решение задач, а не сведение их к задачам меньшей размерности;

- использование как слойной, так и бесслойной стратегий;

- заполнение по, так называемым, приоритетным осям;

- анализ пустот и рассмотрение способов их объединения;

- допускается использование не одного, а нескольких параллелепипедов.

Слойная стратегия. Метод плоскостей, как и большинство методов,

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

Для описания размеров пустых областей используются координаты: у1, у2, г2, а также флаг: 0 - область не заполнена; 1 - область полностью заполнена; -1 - игнорировать при заполнении данного слоя; -2 -игнорировать полностью. Запоминать значение координаты х2 не целесообразно, т.к. для случая слойной стратегии она определяется длиной слоя, для бесслойной - это длина самого параллелепипеда.

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

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

- координаты коробок х¡, х2, у и у 2, 21, 22 относительно параллелепипеда;

- номер коробки из первоначального приоритетного списка;

- номер слоя, в котором размещена коробка.

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

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

• метод сортировки: без сортировки; по невозрастанию объема; по невозрастанию ширины; по невозрастанию массы; по невозрастанию

удельного веса;

• шесть способов поворота коробок;

• шесть вариантов заполнения по приоритетным направлениям;

• использование как слойной, так и бесслойной стратегий.

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

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

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

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

За основу разбиения на различные классы предметов для задачи трехмерной упаковки взято: нижнее ограничение длины предметов - v!: верхнее ограничение длины предметов v^ (v, • W < /, < v2 ■ W, i =1,..., л); нижнее ограничение ширины предметов м>1, верхнее ограничение ширины предметов w2 (w, -W < w,< w2 -W, i=l,..., n); нижнее ограничение высоты предметов rj/, верхнее ограничение высоты предметов ц2(т/, ■ W < 77, <t]1-W, i-1,..., п).

Серия №1. Целью данного эксперимента была проверка необходимости включения в оптимизацию разбиение на слои для разных групп предметов. Выполнены численные эксперименты, параметрами которых являлись: высота параллелепипеда Н= 150, его ширина W= 100; количество предметов п - 50, 100, 200, 250, 500, 1000. Предметы были отсортированы по классам: «мелкие» (v,, = 0.1, v2= 0.2; w, = 0.1, w2 = 0.2; r\i = 0.2, щ2 = 0.25), «средние» (v/= 0.2, v2= 0.4; \v] = 0.2, w2 = 0.4; tji = 0.2, rj2 = 0.25) и «разнородные» (у, = 0.1, v2= 0.3; iv; = 0.1, w2 = 0.2; tji = 0.2, tj2 = 0.25). Для каждого класса задач было сгенерированно по 10 тестовых примеров, усредненные значения коэффициентов раскроя приведены на рисунке 3.

Таким образом, при тестировании метода плоскостей для задач трехмерных упаковок на разной группе предметов было выявлена необходимость совместного использования как процедуры формирования слоя, так и бесслойной процедуры. Это позволяет формировать более плотную упаковку и, следовательно, повышает грузовую стабильность при решении реальных задач. Метод плоскостей показывает лучшие результаты при большом количестве и, в основном, «разнородных» предметов. Время решения задачи на ПК (Celeron (R) CPU 3.2 GHz, 1Гб ОЗУ) от нескольких секунд до двух минут (для п = 1000).

■ Мелкие

В Мелкие (со слоем) • Средние

О Средние (со сгюем) О Разнородные В Разнородные (со слоем)

Рисунок 3 - Усредненные значения коэффициентов раскроя для задач трехмерной упаковки (на основе метода плоскостей)

Серия №2. Выполнены численные эксперименты для анализа различных методов решения задач трехмерной упаковки, параметрами которой являлись: длина параллелепипеда L = 150, его ширина W = 100; количество предметов п = 50, 100, 200, 250. Предметы были отсортированы по классам: «мелкие» (V/, =0.1, v2= 0.2; Wj = 0.1, w2 = 0.2; rj, = 0.1, rj2 = 0.25), «средние» (v;= 0.2, v2= 0.1; w, = 0.2, w2 = 0.25; t]! = 0.2, r)2 = 0.25) и «разнородные» (v;, = 0.1, V2~ 0.25; Wi = 0.1, w2 = 0.2; t], = 0.2, r\2 = 0.25). Значения коэффициентов раскроя приведены в таблице 1.

Таблица 1 - Значения коэффициентов раскроя для задач

Методы Мелкие предметы, % Средние предметы, % Разнородные Предметы, %

MB А - Метод на основе бесслойного алгоритма 71 79 80

EABD - «Наивный» эволюционный алгоритм 74 78 76

GABD - Классический генетический алгоритм 76 77 75

SABD - Метод случайных перестановок 73 74 76

Метод плоскостей 76 82 83

Таким образом, метод плоскостей показывает лучшие результаты в классе «средних» и «разнородных» предметов.

Серия № 3. Метод плоскостей для решения задач двухмерной упаковки был протестированы с помощью безотходных примеров Е. Hopper на определение признака реставрации - способности метода восстанавливать карту раскроя по приоритетному списку. В тестовых примерах в качестве входной информации, кроме размеров прямоугольников и ширины полосы, подавался оптимальный (Опт.) и измененный (Изм.) список (см. таблицу 2).

Таблица 2 - Результаты решения безотходных задач Е

Норрег серии N и С

Задачи п Среднее значение КРА, % Задачи п Сред значе КРА нее ние %

Опт. Изм. Опт. Изм.

Жа-Ше 17 100 92.6 С1 16, 17 100 96.0

№а-Ше 25 100 92.7 С2 25 100 95.4

№а-№е 29 100 94.1 сз 28, 29 100 93.8

N43 -Же 49 100 94.0 С4 49 100 95.2

Ы5а-Юе 73 100 94.9 С5 73 100 97.1

Ыба-Ибе 97 100 96.7 С6 97 100 96.8

Ы7а-Ше 197 100 97.0 С7 196, 197 100 96.6

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

Серия № -/. Целью данного эксперимента было сравнение метода плоскостей с алгоритмом рандомизированного динамического перебора (ОБЯ) для решения задач прямоугольной упаковки. Были сгенерированы следующие классы задач для IV = 225: «малые» предметы (ул = 0.05, 0.1; IV; = 0.1, = 0.15), «средние» предметы (у;, = 0.25, 0.35; и>/ = 0.35, = 0.45) и «малые и большие» предметы (V/, = 0.05, уг= 0.25; м>1 = 0.05, м>} = 0.95). Для каждого класса задач сгенерировано по 10 тестовых примеров. Критерием оценок также выступал коэффициент раскроя КРА, значения которого приведены на рисунке 4.

Рисунок 4 - Усредненные значения коэффициентов раскроя для задач двухмерной упаковки, полученные методом плоскостей

Согласно данным, приведенным А.Ф. Валеевой для такого же класса задач, значения коэффициентов раскроя, полученных методом ОБЯ, для класса «малых» предметов составляет 92 - 96%; «средних» - 98 - 100%; «малых и больших» - 93 - 95%. Таким образом, метод плоскостей показывает сравнимые результаты для класса «малых» и более лучшие для класса«разнородных» («малых и больших») предметов.

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

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

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

Количество прямоугольников/коробок изменялось в диапазоне от 20 до 100, количество примеров для каждой обучающей выборки было сгенерировано в два раза больше количества объектов. Было произведено обучение нейронных сетей, при этом количество правильно решенных примеров составило 100%. В таблице 1 приведены результаты тестирования для задач двухмерной упаковки.

Была исследована зависимость разброса длины и ширины в обучающих примерах на значение ошибки. Выявлено, что при подборе обучающей выборки следует установить фиксированным значение одной из граней полосы на основе известной, например, IV, а другое выбрать в диапазоне: Ьтш = Е5, / (V; Ьтах = /.„,„ + Срзнач(/,), где - суммарная площадь всех прямоугольников, Срзнач(//) - среднее значение длин прямоугольников.

'Как обучающие, так и тестовые примеры были сгенерированы на основе безотходных упаковок. Однако известно, что изменение порядка следования прямоугольников приводит, как правило, к получению другой карты раскроя и, соответственно, длины занятой части полосы. В связи с этим для тестовой выборки случайным образом был изменен порядок следования прямоугольников. Было сгенерировано по 10 тестовых примеров для случая п = 20. Среднее значение ошибки составило 4.4 %.

Таблица 3 - Тестовые данные для задач двухмерной упаковки и полученные значения ошибок ___

№ Кол-во прямоугольников Диапазон изменения Ь Диапазон изменения (V Средняя ошибка, % Средняя максимальная ошибка, %

1. 20 100-200 100-200 46.3 127.3

2. 20 100-300 100-300 50.5 127.9

3. 20 278-288 278-288 12.1 32.3

4. 10 100-120 100 6.3 16.1

5. 10 400-440 400 14.9 29.9

6. 40 400-440 400 14.0 32.8

7. 100 400-440 400 13.4 30.5

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

3. Предложенные в работе эвристические подходы реализованы в виде прикладного программного обеспечения. Полученные в работе результаты используются в ГОУ ВПО «Сибирский государственный технологическом университете» и ГОУ СПО «Красноярский техникум информатики и вычислительной техники» в учебном процессе при выполнении практических, курсовых и дипломных работ, а также логистической компанией «Транс-Бизнес».

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

1. Корчевская, О.В. О преимуществах комбинирования нейросетевого и традиционных подходов при решении дискретных и комбинаторных задач (на примере задачи раскроя) / О.В. Корчевская // Вестник КрасГАУ № 15, 2006.-С. 172-177.

2. Жуков, JI.A. Метод плоскостей: численный эксперимент для задач двух и трехмерной ортогональной упаковки / ЛА.Жуков, О.В. Корчевская II Информационные технологии, 2008. - № Ц. _ с. 41-45.

3. Корчевская О.В., Получение нижних границ для задач двух и трехмерной ортогональной упаковки с помощью нейронных сетей, используя алгоритм безотходной упаковки / О.В Корчевская, Л.А. Жуков // Электронный журнал "Исследовано в России", 62, 2008. - С. 685-694, http: // zhurnal. аре, relarn.ru / articles/ 2008/062.pdf

4. Корчевская, О.В. Элементы формального описания технологии обработки данных с помощью нейронных сетей Хопфилда / О.В. Корчевская, JI.A. Жуков // Новые информационные технологии: сб. материалов восьмого семинара. - М.: МГИЭМ, 2005. - С.89-95.

5. Жуков, Л.А. О формализации нейросетевой технологии решения прикладных задач на примере сетей с учителем и сетей Хопфилда / JI.A. Жуков, Н.В. Решетникова, О.В. Корчевская // Нейроинформатика - 2005: сб.

. научн. тр. VII Всероссийской научно-технической конференции- М.: МИФИ, 2005. - Ч. 1. - С. 68-75.

6. Жуков, Л. А. Особенности применения нейронных сетей Хопфилда для решения прикладных оптимизационных задач / Л. А. Жуков, О. В. Корчевская // Сибирский государственный технологический университет. -Красноярск, 2006. - 44 с. - Деп. в ВИНИТИ 04.12.2006, № 1486 - В2006.

7. Корчевская, О.В. Однопроходный эвристический алгоритм для решения задачи двумерной ортогональной упаковки / О.В. Корчевская // Искусственный интеллект в XXI веке. Решения в условиях неопределенности: Сб.ст. IV Международной научно - технической конференции. - Пенза, 2006. - С. 71-73.

8. Корчевская, О.В. Решение задачи двумерной упаковки в полубесконечную полосу с помощью метода профиля / О.В. Корчевская // Вестник КрасГАУ № 1. - Красноярский государственный аграрный университет, 2007. - С. 34-37.

9. Корчевская, О.В., Конструирование функции энергии сети для задачи ортогональной упаковки / О.В. Корчевская, Л.А.Жуков, А. В. Больсявичус // Компьютерная интеграция производства и ИПИ технологии: Сб. материалов III Всероссийской научно - практической конференции. - Оренбург: ИПК ГОУ ОГУ, 2007.-С. 352-357.

10. Корчевская, О.В. Решение задачи трехмерной упаковки методом профиля / О.В. Корчевская, Л.А. Жуков // V Всесибирский конгресс женщин - математиков: тез. докл. - Красноярск: Изд. РИО СибГТУ, 2007. - С. 58-60.

11. Корчевская, О.В. Обобщенная модель обработки данных с помощью нейронных сетей на примере задачи раскроя / упаковки / О.В. Корчевская, JI.A. Жуков // Альманах современной науки и образования. -Тамбов: Грамота, 2008. - № 1(8): Математика, физика, строительство, архитектура, технические науки и методика их преподавания. - С. 100-103.

12. Корчевская, О.В. Применение метода плоскостей для решения безотходных задач раскроя / упаковки Е. Hopper / О.В. Корчевская, Л.А. Жуков // Материалы и технологии XXI века: Сб.ст. VI Международной научно - технической конференции. - Пенза, 2008. - С. 147-149.

Корчевская Оксана Валериевна

ИНФОРМАЦИОННЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОГО РАСКРОЯ-УПАКОВКИ НА ОСНОВЕ КОНСТРУКТИВНЫХ И НЕЙРОСЕТЕВЫХ ПОДХОДОВ

05.13.17 -теоретические основы информатики Автореферат

Подписано в печать 3 марта 2009г. Формат 60x84/16. Бумага писчая. Объем 1п.л. Тираж 100 экз. Заказ № 843 Отпечатано в Экспресс-Офсет 660062, г. Красноярск, ул. Крупской, 42.

ВВЕДЕНИЕ.

ГЛАВА 1 ПОСТАНОВКА, ПОСЛЕДОВАТЕЛЬНЫЕ ИПАРАЛЛЕЛНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ И РАСКРОЯ.

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

1.1.1 Задачи упаковки н раскроя.

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

1.1.3 Формирование приоритетного списка.

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

1.2.1 Нейронные сети как универсальные аппроксимирующие устройства

1.2.2 Формализация нейросетсвой технологии.

1.2.3 Общие сведения о нейронных сетях Хопфнлда.

1.2.4 Применение нейронной сети Хопфнлда для решения задач комбинаторной оптимизации.

ГЛАВА 2 ИНФОРМАЦИОННЫЕ МОДЕЛИ ЗАДАЧ РАСКРОЯ-УПАКОВКИ.

2.1 Обобщенная схема решення задач ортогонального раскроя-упаковки.

2.2 Модели задач одно, двух н трехмерного раскроя-упаковки.

2.3 Модель обработки данных с помощью нейронных сетей.

2.4 Формальное описание нейронной сслгн Хопфнлда.

ГЛАВА 3 КОНСТРУКТИВНЫЕ МЕТОДЫ РЕШЕНИЯ ТРЕХ И ДВУХМЕРНЫХ ЗАДАЧ РАСКРОЯ-УПАКОВКИ.

3.1 Безотходные алгоритмы для задач раскроя-упаковкн.

3.1.1 Алгоритм формирования безотходных двухмерных упаковок.

3.1.2 Алгоритм формирования безотходных трехмерных упаковок.

3.2 Метод плоскостей.

3.2.1 Метод плоскостей для решения трехмерных задач раскроя- упаковки

3.2.2 Метод плоскостей для решения двухмерных задач раскроя-упаковкн

3.3 Численный эксперимент.

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

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

ГЛАВА 4 ПРИМЕНЕНИЕ АППАРАТА ИСКУССТВЕННЫХ НЕЙРОННЫХ СЕТЕЙ К РЕШЕНИЮ ЗАДА ЧРАСКРОЯ-УПАКОВКИ.

4.1 Подход к определению совокупности прямоугольников, приводящей к минимизации занятой части полосы, для задачи двухмерного раскроя-упаковкн с помощью нейронных сетей Хопфнлда.

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

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

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

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

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

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

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

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

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

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

Фундаментальные научные разработки в области решения задач раскроя-упаковки принадлежат JI.B. Канторовичу и В.А. Залгаллеру (1950). Результаты дальнейших исследований в этой области отражены в работах Э.А. Мухачевой (1979), Е.П. Бороновского (1967), А.Ф. Валеевой (2000), И.П. Норенкова (1999), Ю.А. Кочетова (2000), И.В. Романовского (1977), А.С. Филипповой (1999), В.М. Картак (2004); за рубежом - Р. Gilmore & R. Gomory (1965), G. Scheithauer & J. Terno (1970), H. Dyckhoff

1990), A. Bortfeldt (1998) и др.

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

Особый интерес представляют унифицированные методы, позволяющие на общей теоретической основе создать математическое обеспечение для решения линейных (одномерных), прямоугольных (двухмерных) и параллелепипедных (трехмерных) задач раскроя-упаковки. Такой подход приведен в работах А.Ф. Валеевой: на базе модифицированного метода решения задачи 0-1 рюкзак создано инвариантное математическое обеспечение для решения задач я-мерной (п= 1, 2, 3) упаковки.

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

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

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

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

Основы общей методики решения математических задач в нейросетевом логическом базисе изложены А.И. Галушкиным (2000).

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

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

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

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

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

В рамках цели решаются следующие задачи:

1. Проанализировать известные постановки и методы решения задач раскроя-упаковки и наметить пути их совершенствования.

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

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

4. Провести серии экспериментов и проанализировать полученные результаты.

5. Реализовать теоретические результаты в виде алгоритмов и прикладного программного обеспечения.

Методы исследования.

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

На защиту выносятся:

1. Информационные модели задач раскроя-упаковки.

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

3. Алгоритмы формирования безотходных двух и трехмерных упаковок, обеспечивающие получение приоритетных списков для заданного количества объектов.

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

Научная новизна работы:

1. Разработаны методы решения задач двух и трехмерного ортогонального раскроя-упаковки.

2. Разработаны алгоритмы формирования двух и трехмерных безотходных упаковок.

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

Практическая ценность работы:

1. Приведены информационные модели задач «-мерной (п = 1, 2, 3) ортогональной упаковки-раскроя.

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

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

Реализация результатов работы. В настоящее время результаты исследования и разработок используются несколькими организациями, что подтверждается соответствующими актами о внедрении: ГОУ ВПО «Сибирский государственный технологический университет», логистической компанией «Транс-Бизнес».

Апробация работы и публикации.

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

• Всероссийская научно-практическая конференция «Лесной и химический комплексы - проблемы и решения (экологические аспекты)», Красноярск, 2004, 2007;

• Семинар «Новые информационные технологии», Москва, МГИЭМ, 2005;

• Всероссийская научно-техническая конференция «Нейроинформатика - 2005», Москва, МИФИ, 2005;

• IV, V Всесибирский конгресс женщин-математиков, Красноярск, 2006, 2008;

• IX Всероссийский семинар «Моделирование неравновесных систем», Красноярск, ИВМ СО РАН, 2006;

• IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности», Пенза, 2006;

• III Всероссийская научно-практическая конференция «Компьютерная интеграция производства и ИЛИ технологии», Оренбург, 2007;

• X Всероссийская конференция «Проблемы информатизации региона», Красноярск, 2007;

• Всероссийская научная конференция «Модели и методы обработки изображений», Красноярск, 2007;

• VI Международная научно-техническая конференция «Материалы и технологии XXI века», Пенза, 2008.

Публикации.

Основные результаты работы опубликованы в 12 печатных работах (из них 2 статьи в изданиях по списку ВАК), 1 свидетельство об официальной регистрации программы для ЭВМ.

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

Диссертация состоит из введения, 4 глав, заключения и списка использованных источников. Основное содержание работы изложено на 126 страницах текста, содержит 29 рисунков, 20 таблиц. Список используемых источников включает 183 наименования.

Выводы по четвертой главе:

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

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

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

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

122

ЗАКЛЮЧЕНИЕ

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

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

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

В России наиболее интенсивные разработки в этой области проводятся уфимской школой, под руководством д.т.н., заслуженного деятеля науки РФ, Э.А. Мухачевой; за рубежом аналогичные задачи исследуют A. Bortfeldt, Н. Gehring, Е. Е. Bischoff и др.

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

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

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

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

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

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

- непосредственное решение задач раскроя-упаковки;

- использование как слойной, так и бесслойной стратегии;

-заполнение по, так называемым, приоритетным осям;

- анализ пустот и способы их объединения.

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

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

Метод плоскостей обладает свойством «реставрации». Он восстанавливает карту раскроя по заданным размерам листа (параллелепипеда) и известному приоритетному списку прямоугольников (коробок).

Для проверки свойства «реставрации» и оценки разработанных алгоритмов, большинство специалистов в области раскроя-упаковки используют безотходные примеры Е. Hopper из всемирной электронной библиотеки OR-library. В ней содержатся только данные, представленные, для безотходных двухмерных упаковок, и отсутствуют подобные данные для трехмерных задач.

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

Основное преимущество приведенных безотходных алгоритмов по сравнению с примерами Е. Hopper — это возможность получить безотходную упаковку для практически любых размерах листа и количестве прямоугольников (размеры больших и количество малых предметов задает сам пользователь).

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

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

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

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

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

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

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

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

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

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

3. Предложенные в работе эвристические подходы реализованы в виде прикладного программного обеспечения. Полученные в работе результаты используются в ГОУ ВПО «Сибирский государственный технологическом университете» и ГОУ СПО «Красноярский техникум информатики и вычислительной техники» в учебном процессе при выполнении практических, курсовых и дипломных работ, а также логистической компанией «Транс-Бизнес».

1. А. с. 2006613188. Программа для ЭВМ «Neurons» / В.Г. Азанов, А.В. Шахов, Л. А. Жуков, О.В. Корчевская. № 2006613188; опубл. 08.09.2006.

2. Азанов, В.Г. Создание системы распознавания текстов. Пути достижения / В.Г. Азанов, О.В. Корчевская, Л.А. Жуков // Моделирование неравновесных систем: тез. докл. IX Всероссийского семинара. Красноярск: Изд. ИВМ СО РАН, 2006. -С. 14-16.

3. Алгоритмы решения задачи плотной упаковки геометрических объектов / А.Ф. Валеева и др. // Принятие решений в условиях неопределенности: сб. ст. Уфа, 1996. - С.23-28.

4. Балухто, А.Н. Нейронные сети, минимизирующие свою энергию, и решение задач целочисленного программирования с булевыми переменными / А.Н. Балухто // Нейрокомпьютер. 1997. - № 3, 4. -С. 7-16.

5. Батищев, Д.Ю. Генетические алгоритмы решения экстремальных задач / Д.Ю. Батищев // Учебн. пособие под ред. Я.Е. Львовича. -Воронеж: Воронежский гос. техн. ун-т, Нижегородский ун-т, 1995. — 96 с.

6. Батуев, А.С. Физиология высшей нервной деятельности и сенсорных систем / А.С. Батуев. СПб.: Питер, 2005 — 317 с.

7. Блум, Ф. Мозг, разум и поведение / Ф. Блум, А. Лейзерсян М.: Мир, 1988.-248 с.

8. Бутенин, Н.В. Курс теоретической механики. В 2-х томах. Т. 1: Статика и кинематика / Н.В. Бутенин, Я.Л. Лунц, Д.Р. Меркин. М.: Наука, 1985. - 240 с.

9. Бутенин, Н.В. Курс теоретической механики. В 2-х томах. Т. 2: Динамика / Н.В. Бутенин, Я.Л. Лунц, Д.Р. Меркин. М.: Наука,1985.-496 с.

10. Бухвалова, В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы / В.В. Бухвалова // С.Петербург: Государственный университет. 2001.

11. Валеева, А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя / А.Ф. Валеева // Труды международной конференции по прикладной и индустриальной математике, Новосибирск, ИМ СО РАН, 1997 С. 23-30.

12. Валеева, А.Ф. Задача одномерной упаковки: вычислительный эксперимент с методом динамического перебора / А.Ф. Валеева, И.Р. Гареев // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа, 2000. - С.74-79.

13. Валеева, А.Ф. Задача одномерной упаковки: рандомизорованный метод динамического перебора и метод перебора с усечением / А.Ф. Валеева, И.Р. Гареев, Э.А. Мухачева // Информационные технологии. Приложение. 2003. - № 2. - 24 с.

14. Валеева, А.Ф. Конструктивная эвристика для задачи прямоугольной упаковки / А.Ф. Валеева // Вестник Башкирского университета. — Уфа, 2006.3. С. 5-6.

15. Валеева, А.Ф. Конструктивные методы решения задач ортогональной упаковки и раскроя : автореф. дис. . д-р. тех. наук: 28.09.2006 / А.Ф. Валеева. Уфа, 2006. - 32 с.

16. Валеева, А.Ф. Конструктивные эвристики в задачах раскроя-упаковки / А.Ф. Валеева // Труды международной уфимской зимней школы-конференции по математике и физике для студентов, аспирантов и молодых ученых. Т.1. Математика. Уфа, 2005. — С. 109-119.

17. Валеева, А.Ф. Метод динамического перебора для решения задачи одномерной упаковки / А.Ф. Валеева, И.Р. Гареев, В.А. Габитов // Моделирование, вычисления, проектирование в условияхнеопределенности-2000: тр. междунар. науч. конф. Уфа, 2000. - С. 369-373.

18. Валеева, А.Ф. Методы решения задачи прямоугольной упаковки / А.Ф. Валеева, И.Е. Тоцков, И.Р. Гареев // Интеллектуальное управление в сложных системах-99: тр. респ. науч.-техн. конф. — Уфа, 1999. С.36-38.

19. Валеева, А.Ф. Методы частичного перебора локального поиска оптимума в задаче двухмерной упаковки / А.Ф. Валеева // Информационные технологии. 2004. — № 1. - С. 36-43.

20. Валеева, А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки / А.Ф. Валеева // Информационные технологии.-2005. -№ 10.-С. 36-43.

21. Валеева, А.Ф. Стохастические методы локального поиска для задач упаковки / А.Ф. Валеева // Моделирование, вычисления, проектирование в условиях неопределенности-2000: тр. междун. конф. Уфа: УГАТУ. 2000. - С.25-31.

22. Верхотуров, М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя / М.А. Верхотуров // Информационные технологии. 2000. -№ 5. — С. 37-42.

23. Галушкин, А.И. Нейрокомпьютеры и их применение на рубеже тысячелетий в Китае. В 2-х частях. Т.1 / А.И. Галушкин. М., 2004. -367 с.

24. Галушкин, А.И. Нейрокомпьютеры и их применение на рубеже тысячелетий в Китае. В 2-х частях. Т.2 / А.И. Галушкин. М., 2004.-464 с.

25. Галушкин, А.И. Нейрокомпьютеры и их применение. Кн.1 / А.И. Галушкин. М.: ИПРЖР, 2000. - 416 с.

26. Галушкин, А.И. Нейрокомпьютеры и их применение. Кн.З / А.И. Галушкин. М.: ИПРЖР, 2000. - 528 с.

27. Гери, М.П. Вычислительные машины и трудно разрешимые задачи / М.П. Гери, Д.С. Джонсон. -М.: Мир, 1982.-416 с.

28. Головко, Н.А. Нейроинтеллект: Теория и применения. Книга 1. Организация и обучение нейронных сетей с прямыми и обратными связями / Н.А. Головко. Брест: БПИ, 1999. - 260 с.

29. Гончаров, Е.Н. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения / Е.Н. Гончаров, Ю.А. Кочетов // Дискретный анализ и исследование операций. 1999. - Серия 2.6. -№1. - С. 12-32.

30. Горбань, А.Н. Информационная емкость тензорных сетей / А.Н. Горбань, Е.М. Миркес // Нейроинформатика и ее приложения: тез. докл. IV Всероссийского семинара. Красноярск: Изд. КГТУ, 1996. -С. 22-23.

31. Горбань, А.Н. Нейронные сети на персональном компьютере / А.Н. Горбань, Д.А. Россиев. Новосибирск: Наука, 1996. - 276 с.

32. Горбань, А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей / А.Н. Горбань // Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. -Новосибирск, 1998.-Т. 1 №1.-С. 11-24.

33. Горбань, А.Н. Обучение нейронных сетей / А.Н. Горбань. М.: СП "Paragraph", 1990. - 160 с.

34. Горбань, А.Н. Помехоустойчивость тензорных сетей / А.Н. Горбань, Е.М. Миркес // Нейроинформатика и ее приложения: тез. докл. IV Всероссийского семинара. Красноярск: Изд. КГТУ, 1996. - С. 2425.

35. Горбань, А.Н., Логически прозрачные нейронные сети для производства знаний из данных / А.Н. Горбань, Е.М. Миркес; Вычислительный центр СО РАН в г. Красноярске. Красноярск, 1997. 12 с. - Деп. в ВИНИТИ 17.07.97, № 2434-В97.

36. Дорогов, А.Ю. Быстрые нейронные сети / А.Ю. Дорогов- М.: Изд-во Санкт-Петербургского университета, 2002. 77 с.

37. Ежов, А.А., Нейрокомпьютинг и его применение в экономике и бизнесе / А.А. Ежов, С. А. Шумский. Москва, 1998. - 222 с.

38. Ефимов, В.В. Нейроподобные сети в бортовых информационно-управляющих комплексах космических аппаратов. /В.В. Ефимов. -СПб. ВИКА им. А.Ф. Можайского, 1996. - 113 с.

39. Житников, В.П. Задача прямоугольной упаковки в полубесконечную полосу: поиск решения в окрестности локальной нижней границы / В.П. Житников, А.С. Филиппова // Информационные технологии. 2007. - № 5. - С. 55-61.

40. Жук, С.Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности / С.Н. Жук // Труды Института системного программирования: Том 12. — М.: ИСПРАН, 2006. С. 6-17

41. Жуков, Л.А. Метод плоскостей: численный эксперимент для задач двух и трехмерной ортогональной упаковки / Л.А.Жуков, О.В. Корчевская // Информационные технологии, 2008. № 11. С. 41-45.

42. Жуков, Л.А. Некоторые особенности разработки экспертных систем классического типа по материалам Internet / Л.А. Жуков, О.В. Корчевская; Красноярск, госуд. техн. ун-т, 2004. 34 с. - Деп. в

43. ВИНИТИ 07.05.04, № 765 В2004.

44. Жуков, JI.A. Применение нейронных сетей Хопфилда для обработки данных и распознавания изображений / Л. А. Жуков, О.В. Корчевская // Модели и методы обработки изображений: Сб. ст. Всероссийской научной конференции. Красноярск, 2007. - С.20-24.

45. Жуков, Л.А. Технология классификации с помощью нейронных сетей без учителя / Л.А. Жуков // Теоретические и прикладные вопросы современных информационных технологий: сб. ст. Всероссийской конференции. Улан-Уде: ВСГТУ, 2001. - С.40-47.

46. Жуков, Л.А. Формализация технологии применения нейронных сетей с учителем и особенности их использования для решения прикладных задач: монография / Л.А. Жуков, Н.В. Решетникова. -Красноярск, КГТУ, 2005. 168 с.

47. Задача двумерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума / Мухачева Э.А. и др. // Информационные технологии. -2006.-№4.-С. 45-52.

48. Задачи двумерной упаковки: развитие генетических алгоритмов набазе смешанных процедур локального поиска оптимального решения / А.С. Мухачева и др. // Информационные технологии. Приложение. 2001. - № 9. - 24 с.

49. Ишлинский, А.Ю. Классическая механика и силы инерции / А.Ю. Ишлинский. М.: Наука, 1987. - 320 с.

50. Калан, Р. Основные концепции нейронных сетей: пер.с англ. / Р. Калан. -M.-JL: Вильяме, 2001.-287 с.

51. Калинин, А.В. Технология нейросетевых распределённых вычислений: монография / А.В. Калинин, C.JI. Подвальный. -Воронеж: Воронеж, гос. техн. ун-т, 2004. 122 с.

52. Калинин, В.Н. Теория систем и оптимального управления. Понятия, модели, методы и модели оптимального выбора / В.Н. Калинин, Б.А. Резников, Е.И. Варакин. МО СССР, 1987. - 589 с.

53. Канторович, JI.B. Рациональный раскрой промышленных материалов / JI.B. Канторович, В.А. Залгаллер // Новосибирск: Наука, 1971.-299с.

54. Картак, В.М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу / В.М. Картак // Информационные технологии. 2008. - № 2. - С. 2430.

55. Кацев, С.В. Об одном классе дискретных минимаксных задач / С.В. Кацев. Кибернетика. - 1979. - № 5. - С. 139-141.

56. Кокотов, В.З. Алгоритм плотного размещения разногабаритных элементов на плате / В.З. Кокотов // Информационные технологии. — 1998. -№ 11.-С. 16-21.

57. Комплекс алгоритмов и программ расчета гильотинного раскроя / Э.А. Мухачева и др. // Информационные технологии. 2004. - № 8.-С. 18-25.

58. Коноплев, В.А. Моделирование нейронных сетей с максимально высокой информационной емкостью / В.А. Коноплев, Е.В. Синицын

59. Нейроинформатика и ее приложения: тез. докл. III Всероссийского семинара. Красноярск: Изд. КГТУ, 1995. - С.66.

60. Корчевская, О.В. Решение задачи двумерной упаковки в полу бесконечную полосу с помощью метода профиля / О.В. Корчевская // Вестник КрасГАУ № 1. Красноярский государственный аграрный университет, 2007. — С. 34-37.

61. Корчевская, О.В. Решение задачи трехмерной упаковки методом профиля / О.В. Корчевская, Л.А. Жуков // V Всесибирский конгресс женщин математиков: тез. докл. - Красноярск: Изд. РИО СибГТУ, 2007.-С. 58-60.

62. Корчевская, О.В. Формирование приоритетного списка для шельфовых алгоритмов упаковки в полосу / О.В. Корчевская, Л.А.Жуков, А. В. Больсявичус // Проблемы информатизации региона: сб.ст. X Всероссийской конференции. — Красноярск, 2007. -С. 21-26.

63. Корчевская, О.В. Элементы формального описания технологии обработки данных с помощью нейронных сетей Хопфилда / О.В.

64. Корчевская, JI.A. Жуков // Новые информационные технологии: сб. материалов восьмого семинара. М.: МГИЭМ, 2005. - С.89-95.

65. Кофман, А. Введение в прикладную комбинаторику / А. Кофман. — М.: Наука, Гл. ред. физ.-мат. лит., 1975. — 447 с.

66. Кочетов, Ю. Локальный поиск с чередующимися окрестностями / Ю. Кочетов, Н. Младенович, П. Хансен // Дискрет, анализ и исслед. операций. Сер. 2.-2003.-Т. 10.-№ 1. -С. 11-43.

67. Кочетов, Ю.А. Вероятностный поиск с запретами для задачи упаковки в контейнеры / Ю.А Кочетов, А. Усманова // XII Байкальская международная конференция: сб. ст. Иркутск, 2001. С. 22-27.

68. Леванова, Т.В. Алгоритмы муравьиной колонии и имитации отжига для задачи ор-медиане / Т.В. Леванова, М.А. Лореш // Автоматика и телемеханика. 2004. - №3. - С. 80-89.

69. Легалов, А.И. Нейроинформатика: Уч. пособие / А.И. Легалов, Е.М. Миркес, Н.Ю. Сиротинина. Красноярск, 2006. - 172 с.

70. Липовецкий, А.И. К оптимизации свободного размещения прямоугольников / А.И. Липовецкий // Автоматизация проектирования в машиностроении. Минск, 1985. - С. 80-87.

71. Липский, В. Комбинаторика для программистов / В. Липский. — М.: Мир, 1988.-213 с.

72. Логовский, А.С. Использование нейронных сетей для решения комбинаторных задач с полным перебором / А.С. Логовский // Нейрокомпьютер. 1994. - № 3, 4. - С. 41-50.

73. Маркеев, А.ГТ. Теоретическая механика / А.ГТ. Маркеев. М.: Наука, 1990.-416 с.

74. Марков, В.Н. База знаний для негильотинного раскроя-упаковки / В.Н. Марков // Информационные технологии. 2007. - №4. - С. 1723.

75. Марков, В.Н. Принципы построения экспертной системы гильотинного раскроя / В.Н. Марков // Информационные технологии. 2005. - № 4. - С. 53-56.

76. Меламед, И.И. Нейронные сети и комбинаторная оптимизация / И.И. Меламед // Автоматика и телемеханика. 1994. - № 11. — С. 340.

77. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя / Э.А. Мухачева и др. // Информационные технологии. 2001. - № 6. - С. 25-31.

78. Методы нейроинформатики: Сб. научн. трудов / Под ред. А.Н. Горбаня. Красноярск: КГТУ, 1998.-204 с.

79. Минский, М. Персептроны / М.Минский, С.Пейперт. М.: Мир, 1971.-261 с.

80. Миркес, Е.М. Нейроинформатика: Учеб. пособие для студентов / Е.М. Миркес. Красноярск: ИПЦ КГТУ, 2002. - 347 с.

81. Миркес, Е.М. Нейрокомпьютер. Проект стандарта / Е.М. Миркес. — Новосибирск: Наука, 1999. 337 с.

82. Мухачева, А.С. Задача упаковки прямоугольников:рандомизированная эвристика на базе двойственной схемы локального поиска оптимума / А.С. Мухачева, P.P. Ширгазин // Информационные технологии. 2003. -№5. — С. 18-22.

83. Мухачева, А.С. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума / А.С. Мухачева, А.Ф. Валеева, В.М. Картак. М.: МАИ, 2004. - 193 с.

84. Мухачева, А.С. Конструирование алгоритмов локального поиска оптимума на базе двойственных задач линейного раскроя / А.С. Мухачева, Э.А. Мухачева // Информационные технологии. 2002. -№6.-С. 25-30.

85. Мухачева, А.С. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы / А.С. Мухачева // Информационные технологии. 2002. - № 10. - С. 26-31.

86. Мухачева, Э.А. Генетический алгоритм блочной структуры в задачах двухмерной упаковки / Э.А. Мухачева, А.С. Мухачева, А.В. Чиглинцев // Информационные технологии. 1999. - № 11. - С. 1318.

87. Мухачева, Э.А. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур / Э.А. Мухачева, А.С. Мухачева // Автоматика и телемеханика. 2004. -№2.-С. 101-111.

88. Мухачева, Э.А. Математическое программирование / Э.А. Мухачева, Г.Ш. Рубинштейн. Новосибирск: Наука, 1987. - 272 с.

89. Мухачева, Э.А. Метод динамического перебора в задаче двухмерной упаковки / Э.А. Мухачева, А.Ф. Валеева // Информационные технологии. 2000. - №5. - С. 30-37.

90. Мухачева, Э.А. Метод перестройки для решения задачи прямоугольной упаковки / Э.А. Мухачева, А.С. Мухачева // Информационные технологии. 2000. - №4. - С. 30-36.

91. Мухачева, Э.А. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя / Э.А. Мухачева, А.С. Мухачева, Г.Н. Белов // Информационные технологии. 2000. - №2. - С. 11-17.

92. Мухачева, Э.А. Методы локального поиска в дискретных задачах оптимального распределения ресурса: Учеб. пособие. / Э.А. Мухачева, А.Ф. Валеева, А.С. Мухачева. Уфа: УГАТУ, 2001.- 103 с.

93. Мухачева, Э.А. Методы решения задачи параллелепипедной упаковки на базе алгоритма динамического перебора / Э.А. Мухачева, А.Ф. Валеева, И.Е. Тоцков // Информационные технологии. -2001. -№1. С. 21-29.

94. Мухачева, Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката / Э.А. Мухачева // Оптимизация: сб. научн. тр. СО АН СССР. 1978. - Вып. 22. - С. 83-93.

95. Мухачева, Э.А. Модели и методы расчета раскроя-упаковки геометрических объектов / Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов. Уфа: УГАТУ, 1998. - 216 с.

96. Мухачева, Э.А. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя / Мухачева Э.А., Е.М. Картак // Информационные технологии. 2000. - №9. - С. 15-21.

97. Мухачева, Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ/ Мухачева Э.А. М.: Машиностроение, 1984. — 176с.

98. Назаров, А.В. Нейросетевые алгоритмы прогнозирования и оптимизации систем / А.В. Назаров, А.И. Лоскутов. Беларусь. Минск. Наука и техника, 2003. - 384 с.

99. Нейроинформатика / А.Н. Горбань и др.. Новосибирск: Наука,1998.-296 с.

100. Нейроматематика. Кн. 6: Учеб. Пособие для вузов / А.Д.Агеев и др.. М.: ИПРЖР, 2002. 448 с.

101. Нейронные сети: история развития теории. Кн. 5: Учебн. пособие для вузов / Под общей ред. А. И. Галушкина, Я. 3 Цыпкина. М.: Радиотехника, 2001. 840 с.

102. Нейропрограммы. Учебное пособие: В 2ч. Ч. 1 / JI.B. Гилева и др. Под ред. А.Н. Горбаня. Красноярск: КГТУ, 1994.- 123 с.

103. Нейросетевая технология в задачах оптимизации, прогнозирования и управления / Н.П. Абовский и др.. М-во образования Рос. Федерации, Краснояр. гос. архит.-строит. академия. - Красноярск: КрасГАСА, 2003.- 174 с.

104. Нейросетевые системы управления / В.А. Терехов и др.. — СПб.: Издательство С.-Петербургского университета, 1999. — 256 с.

105. Норенков, И.П. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации / И.П. Норенков, О.Т. Косачевский // Информационные технологии. 1999. — № 2. — С. 28.

106. Норенков, И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии. 1999. -№ 1. - С. 2-7.

107. Осовский, С. Нейронные сети для обработки информации / С. Осовский М.: Финансы и статистика, 2002. — 343 с.

108. Петунин, А.А. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя-упаковки / А.А. Петунин, Э.А. Мухачева, А.С. Филиппова // Информационные технологии. -2008. -№ 1.-С. 28-31.

109. Применение алгоритмов локального поиска оптимума для проектирования СБИС / А.З. Хуббутдинов и др. // Компьютерные науки и информационные технологии: сб. межд. конф. Уфа, 2005.-С. 175-180.

110. Проектирование прямоугольных упаковок на базе развития технологии блочных структур / Э.А. Мухачева и др. // Информационные технологии. 2007. - №1. - С. 20-29.

111. Розенблатт, Ф. Принципы нейродинамики. Перцептрон и теория механизмов мозга / Ф. Розенблатт. М.: Мир, 1965. — 480 с.

112. Романовский, И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. -М.: Наука, 1977. 88 с.

113. Романовский, И.В. Пакетный вариант симплекс-метода. Эволюционное описание основных конструкций / И.В. Романовский // Исследование операций и статистическое моделирование: Изд-во ЛГУ. 1979. - Вып. 5. - С. 55-71.

114. Романовский, И.В. Решение дискретных минимаксных задач методом дихотомии / И.В. Романовский, Н.П. Христова // ЖВМ и МФ. 1973. - 13(5). - С. 1200-1209.

115. Романовский, И.В. Решение задачи гильотинного раскроя методом переработки списка состояний / И.В. Романовский // Кибернетика. -1969.-№1.-С. 102-104.

116. Россиев, Д.А. Медицинская нейроинформатика / Д.А. Россиев // Нейроинформатика. Новосибирск: Наука, 1998. С. 137-221.

117. Сигал, И.Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие / И.Х. Сигал, А.П. Иванова. М.: ФИЗМАТЛИТ, 2002. - 240с.

118. Сиразетдинов, Т.М. Проектирование гильотинного раскроя листового и рулонного материала с использованием послойных алгоритмов: автореф. дис. . канд. тех. наук: 02.07.04 / Т.М. Сиразетдинов. Уфа, 2004. - 16 с.

119. Стоян, Ю.Г. Математические модели и оптимизационные методы геометрического проектирования / Ю.Г. Стоян, С.В. Яковлев. — Киев: Наукова думка, 1986. 268 с.

120. Таха, Хэмди. Введение в исследование операций. 7-е изд./ Хэмди Таха. М.: Вильяме, 2005. - 903 с.

121. Терехов, С.А. Вводные лекции по теории и приложениям искусственных нейронных сетей / С.А. Терехов. Красноярск: ИВМ СО РАН, 2000. - 69 с.

122. Терехов, С.А. Технологические аспекты обучения нейросетевых машин / С.А. Терехов // Лекции по нейроинформатике: сб. ст. М.: МИФИ, 2006.-С. 13-73.

123. Уоссермен, Ф. Нейрокомпьютерная техника / Ф. Уоссермен- М.: Мир, 1992.-240 с.

124. Усманова, А.Р. Экспоненциальная окрестность решений для задачи упаковки в контейнеры / А.Р. Усманова // Информационные технологии. 2005. - №6. - С. 48-51.

125. Филиппова, А.С. Задача двумерной упаковки в полу бесконечную полосу: численный эксперимент с алгоритмами локального поиска и с декодерами блочной структуры / А.С. Филиппова // Информационные технологии. 2005. - №6. - С. 32-47.

126. Филиппова, А.С. Задача ортогональной упаковки в полубесконечную полос: численный эксперимент с безотходными задачами Е. Hopper / А.С. Филиппова, Э.А. Мухачева, А.Г. Чиглинцев // Информационные технологии. 2005. - №7. - С. 4554.

127. Филиппова, А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур / А.С. Филиппова // Информационные технологии. Приложение. 2006. - № 6. - 31 с.

128. Хайкин, С. Нейронные сети: Полный курс. 2-е издание / С. Хайкин. -М.: Вильяме, 2006. 1104 с.

129. Хомич, А.В. Оптимизация топологии рекуррентных и многослойных нейронных сетей с применением генетическихалгоритмов / А. В. Хомич, JL А. Жуков // Нейроинформатика-2004: сб. науч. ст. Ч. 2.-М.: МИФИ, 2004. С. 68-74.

130. Хомич, А.В. Эволюционный метод оптимизации структуры нейронной сети с учителем / А. В. Хомич, JI. А. Жуков // Нейроинформатика-2005: сб. науч. трудов. Ч. 1. М.: МИФИ, 2005. -С.11-18.

131. Царегородцев, В.Г. Взгляд на архитектуру и требования к нейроимитатору для решения современных индустриальных задач / В.Г. Царегородцев // Научная сессия МИФИ-2004: сб. науч. тр. 4.2. М.: МИФИ, 2004. - С. 160-167.

132. Шульговский, В.В. Физиология высшей нервной деятельности с основами нейробиологии: Учебник / В.В. Шульговский. М.: Издательский центр "Академия", 2003. - 464с.

133. Baker, В. S. Orthogonal packing in two dimensions / В. S. Baker, Jr. E. Goffman, R. L. Riverst // SIAM J. Comput. -1980. № 9. p. 846-855.

134. Belov, G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths / G. Belov, G. Scheithauer // European Journal of Operational Research. 2002. - № 141. - P. 274294.

135. Berkey, J. O. Two dimensional finite bin packing algorithms / J. O. Berkey, P.Y. Wang // J. Oper. Res. Soc. 1987. № - 38. - P. 423 - 429.

136. Bischoff, E.E. A comparative evaluation of heuristics for container loading / E.E. Bischoff, M.D. Marriott // European Journal of Operation Research. 44(1990). - P. 267-276.

137. Bischoff, E.E. Issues in the Development of Approaches to Container Loading / E.E. Bischoff, M.S.W. Ratcliff // Omega, Int'U. Management Science, vol. 23. № 3. - 1995. - P. 377-390.

138. Bortfeldt, A. Applying tabu search to container loading problems / A. Bortfeldt, H. Gehring // Operations Research Proceedings 1997. Springer. Berlin, 1998.-P. 533-538.

139. Bortfeldt, A. A genetic algorithm for the container loading problem / A. Bortfeldt, H. Gehring // European Journal of Operation Research. — 131(2001).-P. 143-161.

140. Chazelle, B. The bottom-left bin packing heuristic: An efficient implementation / B. Chazelle // IEEE Trans, on Comput. 2 (1983). - P. 697-707.

141. Chung, F. K. On packing two dimensional bins / F. K. Chung, M.R. Garey, D.S. Jonson // SIAM J. Algebraic Discrete Meth. - 1982/ 3/ - P. 66-76.

142. Coffman, E. Approximation algorithms for bin packing — an updated survey / E. Coffman, M. Garey, D. Johnson // Algorithm Design for Computer System Design. - Berlin et al. 1984.

143. Dorigo, M. Algorithms for Discrete Optimization / M. Dorigo, G. Di Caro, L.M. Gambardella // Artificial Life, 1999. Vol.5. - № 3. - P. 137-172.

144. Dyckhoff, H. Cutting and Packing / H. Dyckhoff, G. Scheithauer, J. Terno // Annotated Bibliographies in Combinatorial Optimization, edited by M.Dell'Amico, F. Maffioli and S.Martello. John Wiley&Sons, 1997. -P. 393-412.

145. Dykhoff, H. A typology of cutting and packing problems / H. Dykhoff // Evropean Journal of Operational research. 1990. - Vol. 44. - P. 145159.

146. Dykhoff, H. Special issue: Cutting and Packing / H. Dykhoff, G. Wascher // European Journal of Operational Research. 1990. - 44 p.

147. Fen, Gang The convergence and parameter relationship for discrete-time continuous-state Hopfield networks / Gang Fen, Christos Douligeris // IEEE Word congress on computational intelligence, 2001. P. 376-381/

148. Folkenauer, E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing / E. Folkenauer // Evolutionary Algorithms in Management Applications. -Berlin, 1995.-P. 167-182.

149. Forster, H. Simulated annealing for order spread minimization sequencing cutting patterns / H. Forster, G. Wascher // European Journal of Operational Research. 1998. -№ 110. - P. 272-281.

150. Gehring, H. A Genetic Algorithm for Solving the Container Loading Problem / H. Gehring, A. Bortfeld // International transactions in operational research. 1997. - V.4. - № 5/6. - P. 401-418.

151. George, A.J. A heuristic for packing boxes into a container / A.J. George, D.F. Robinson // Computers and Operations Research, vol. 7, № 3, 1980. -P. 147-156.

152. Gilmore, P. Multistage cutting stock problem of two and more dimensions / P. Gilmore, R. Gomory // Operations Reseach, 1965. — 13(1).-P. 94-120.

153. Gilmore, P. The theory and computation of knapsack functions / P. Gilmore, R. Gomory // Operations Reseach, 1966. V.14. - P. 10451075.

154. Gilmore, P.C. A Linear Programming Approach to the Cutting-stock Problem / P.C. Gilmore, R.E. Gomory // Operations Research. 9(1961). -P. 849-859.

155. Glover, F. Tabu search and adaptive memory programming advances, applications and challenges / F. Glover // Interfaces in Computer Science and Operations Research 1996. - P. 1-75.

156. Hinxman, A. The Trim-Loss and assortment problems: a survey / A. Hinxman // European Journal of Operational Research 1980. - № 11.—1. P. 863-888.

157. Hopfield, J.J. Neural computation of decisions in optimization problems / J.J. Hopfield, D.W. Tank // Biological Cybernetics. 1985. - Vol. 52. -P. 141-152.

158. Hopper, E. An empirical investigation of meta heuristic and heuristic algorithms of a 2D packing problem / E. Hopper, B. Turton // EJOR 128. -2001.-P. 34-57.

159. Jain, Anil K. Artificial Neural Networks / Anil K. Jain, Jianchahg Mao, K.M. Mohiuddin // A Tutorial, Computer. 1996. - Vol. 29- № 3, March-P. 31-44.

160. Kirkpatrick, S. Optimization by simulated annealing / S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi // Science. -V. 220. 1983. - P. 671-680.

161. Liu D. An improved BL algorithm for genetic algorithm of the orthogonal packing of rectangles / D. Liu, Teng // European Journal of Operation Research. - 1999. № - 112. - P. 413-420.

162. Loris, Faina An application of simulated annealing to the cutting stock problem / Faina Loris // European Journal of Operational Research. -1999.-№ 114.-P. 532-556.

163. Martello, S. Knapsack problems: Algorithms and Computer Implementations / S. Martello, P. Toth // YOHN WILEY&SONS. -Chichester.- 1990.

164. Moura, A. A grasp approach to the container-loading problem / A. Moura, J.F. Oliveira // IEEE Computer Society. July/August 2005. - P. 50-57.

165. Pisinger, D. Heuristics for the container loading problem / D. Pisinger // European Journal of Operational Research. 2002. - № 141. - P. 382392.

166. Rectangle Packing Based Module Placement / H. Murata edit. // Proc. IEEE/ACM International Conf. on Computer - Aided Design. - 1995.1. P. 472-479.

167. Scheithauer, G. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem / G. Scheithauer, J. Terno // Operational Research. 1991: Springer-Verlag. -Berlin.-P. 439-444.

168. Schwerin, P. A New Lower Bound for the Bin-Packing Problem and its integration to MTP / P. Schwerin, G. Wascher // Pesquisa Operational. -1999. 19(2). -P.l 11-131.

169. Schwerin, P. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP / P. Schwerin, G. Wascher // International Transactions in Operational Research. 1997. -№ 4. - P.337-389.

170. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems) / E. Mukhacheva edit. // The International Scientific Collection. 1997. - Ufa. Russia.