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

На правах рукописи

ХАСАНОВА Элина Ильдаровна

ПРОЕКТИРОВАНИЕ РАЗМЕЩЕНИЯ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА МНОГОСВЯЗНОМ ОРТОГОНАЛЬНОМ ПОЛИГОНЕ

Специальность: 05.13.12 - Системы автоматизации проектирования (в промышленности)

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

3 I (.¡АР 2011

Уфа-2011

4841554

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

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

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

д-р техн. наук, доц. Филиппова Айва Сергеевна

д-р техн. наук, проф. Норенков Игорь Петрович, зав. каф. САПР Московского государственного технического университета им. Н. Э. Баумана

д-р техн. наук, доц.

Кульга Константин Станиславович, проф. каф. МСС Уфимского государственного авиационного технического университета

Ведущая организация

ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина»

Защита состоится /У ¿Ьгиь&лл. ЛОМ г. в -/О Со часов

на заседании диссертационного совета Д-212.288.03

при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа-центр, ул. К. Маркса 12, УГАТУ

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

Автореферат разослан « У » ¡МуШмруО- 2011 г.

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

¡¡/и^-С-Н^У В. В. Миронов

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

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

Актуальность темы исследования

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

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

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

Задачи размещения прямоугольных объектов внутри многосвязного ортогонального полигона являются обобщением задач 2DBP (2-Dimensional Bin Packing), то есть, как и они, относятся к классу NP-трудных задач комбинаторной оптимизации. На сегодняшний день не известно алгоритмов поиска оптимального решения полиномиальной сложности для этого класса задач, и точный результат в общем случае может быть получен переборным алгоритмом только за экспоненциальное время. При больших размерностях задач целесообразно использовать эвристические методы поиска рационального решения.

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

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

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

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

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

3. Разработать эффективные алгоритмы декомпозиции многосвязного ортогонального полигона на прямоугольные боксы для определения области размещения;

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

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

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

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

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

2. Методы горизонтального и вертикального заполнения боковых пустот при проектировании размещения объектов в прямоугольную область с использованием уровневых технологий;

3. Метод матричной декомпозиции многосвязного ортогонального полигона на прямоугольные области для последующего размещения в них объектов;

4. Метод условных резов для декомпозиции ортогонального полигона на прямоугольные области для последующего размещения в них объектов;

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

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

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

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

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

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

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

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

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

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

Связь исследования с плановыми исследованиями

Работа выполнялась при поддержке фанта Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации НШ-65497.2010.9.

Апробация работы

Результаты работы, а также отдельные ее разделы докладывались и обсуждались на конференциях: III Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 2008 г.); Всероссийская молодежная научная конференция «Мавлютовские чтения» (Уфа, 2008 г.); IV Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 2009 г.); IV Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2009 г.); Международная школа-конференция для студентов, аспирантов и молодых ученых (Уфа, 2009 г.); Российская конференция «Дискретная оптимизация и исследование операций» (Алтай, 2010 г.); научные семинары кафедры вычислительной математики и кибернетики и кафедры математики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 10 работ, в том числе 3 статьи в рецензируемых журналах из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2010617454.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 187 страниц машинописного текста, включая 53 рисунка, 21 таблицу, список литературы, содержащий 153 название, и 3 приложения.

Выражаю благодарность профессору Э. А. Мухачевой за консультации и советы при выполнении исследований и написании диссертационной работы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

1. Проектирование сверхбольших интегральных схем.

2. Планировка складских помещений и размещение в них товаров.

3. Создание планов размещения грузов на палубах грузовых судов.

4. Раскрой промышленных материалов.

Частным случаем задачи размещения технических объектов в многосвязный ортогональный полигон является задача прямоугольного размещения, когда в качестве области выступает прямоугольник. Такая задача, по сути, близка к задачам раскроя и упаковки. Задачи раскроя и упаковки возникли в результате работы JI. В. Контаровича в 1939 г. М. Garrey и D. Jonson доказали, что задача одномерного раскроя является NP-трудной. В связи с этим стали бурно развиваться приближенные и эвристические методы, в том числе и метаэвристики, обобщение которых привело к появлению технологий конструирования рациональных раскроев и размещений: нижний-левый (D. Liu & Н. Teng, Е. Hopper & В. Turton); мультиметодная технология (И. П. Норенков); блочная технология (Э. А. Мухачева, А. С. Филиппова, А. В. Чиглинцев). Для решения задач с условием гильотинности хорошо себя зарекомендовали уровневые технологии (A. Lodi, S. Martello & D. Vigo). Отдельно рассматриваются задачи размещения в область с препятствиями, которые могут быть сведены к задачам размещения в многосвязный ортогональный полигон. К таким задачам можно отнести прямоугольный раскрой материала с дефектами (Т. Ю. Сиразетдинова, А. Ф. Валеева) и задачу Вебе-ра (В. А. Трубин, J. С. Picard, R. L. Francis).

Задача размещения в область с препятствиями может быть сведена к задаче размещения предметов в прямоугольные контейнеры путем выделения последних из исходной области. Разбиение многосвязного ортогонального полигона на произвольные прямоугольные области можно интерпретировать как задачи покрытия. Задачам покрытия ортогонального полигона наименьшим числом произвольных прямоугольников посвящены работы таких ученых как: Y. Cheng, W. J. Masek, J. С. Culberson, D. S. Franzblau, J. Gudmundsson и другие.

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

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

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

Образовавшиеся при этом многоугольные области этого прямоугольника, не принадлежащие полигону, представим как виртуальные препятствия. Далее разделим многоугольные препятствия сквозными линиями так, чтобы они разбились на прямоугольники (рис. 1). Таким образом, исходная задача сводится к следующей: Дана прямоугольная область ширины W и длины I, а также набор прямоугольных препятствий заданных размеров, ®V,K, v = 1, ц, где /и - количество препятствий, су,„ Av - ширина и длина v-ro препятствия или его прямоугольной части. Введем прямоугольную систему координат: оси Ох и Оу совпадают соответственно с нижней и боковой сторонами области. Положение каждого прямоугольного препятствия Bv задается координатами (/,„ ;?,,.) его нижнелевого угла (рис. 1). Таким образом, многосвязный ортогональный полигон можно представить следующим набором исходных данных

Рисунок 1 - Пример многосвязного ортогонального полигона

Требуется найти множество #={77/, Л2, ■■■, Пт} прямоугольных боксов 77, = {(*,, У,),^,,/,)) минимальной мощности, где (х,-^) — координаты ниж-не-левого угла г'-го прямоугольника, и /,- - его ширина и длина, т - искомая мощность множества П, удовлетворяющие следующим условиям:

1° Ребра боксов параллельны ребрам области:

где р'х, р'у - проекции прямоугольника 77, на оси координат Ох пОу.

2° Взаимное неперекрытие боксов: V/*]'А,] = \,т ((X, >XJ + /,) + /,)МСу( >У} +WJ)^J(yJ + *>,)).

3° Неперекрытие боксов с гранями области: V/=1 ,т (х, > 0) л (у, > 0) л (у, + <Ж)л (х, + /,. < ¿).

4° Неперекрытие боксов с препятствиями:\/1,у:/'=1,т;у=1р

((х, > Ху + ) V (х* * +/,.)) V ((у, > + <у,.) V (7,. > у, + ук, )).

5° Прямоугольные боксы должны покрывать всю свободную область

т р

многосвязного ортогонального полигона: ^ = №' Ь ~ ^ К .

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

боксов 77ь заданных размеров }Уь 1ь к-1,т, где т - количество боксов, Щ, Ьк - ширина и длина к-ой области. Имеется также набор прямоугольных предметов заданных размеров /,-, /=], п, где п - количество прямоугольников, ту,-, /,- - ширина и длина 1-го предмета. Таким образом, исходная информация задачи может быть представлена следующим набором данных:

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

ОР = (х = {х11},у = (уА,}), где хк!, у и - координаты нижне-левого угла

прямоугольника i в боксе к, г = 1, п,к е {1,...т}.

Набор СР^(х,у) является допустимым сквозным размещением, если выполняются следующие условия:

1 Ребра предметов параллельны ребрам бокса: (р'я ~ /,) л (р'у = / = 1, п, где р\, р'у - проекции предмета г на оси координат Ох и Оу.

2° Взаимное неперекрытие предметов: у :/,/ = 1,гс >Хк, + /,)М{у„ >Уllj+WJ.)v(ytJ >Ук! + Н>,)).

3° Неперекрытие предметов с гранями области: V/ = 1, п {хи > 0) л (у, > 0) л (уи +w,<Wt)A (хи + /, <Lt).

Набор GP=(x,y) является сквозным размещением, если при выполнении условий 1°, 2°, 3° имеет место

4° Условие сквозного размещения: для любого прямоугольника Р с

размерами (w, 1), w, v/ Ф1Р i = 1,и, расположенного в любом боксе, выполняется условие разделения на два прямоугольника P'{w\l') и P"{w",l") такое, что ((w' = w" = н-)л (/' + /" = /)) v ((w' + w" = w) л(/' = Г = /)) и V/ = Un, если Р,Г\Р'*ф, то Р,слР" = ф и если Р, п Р" * Ф , то Р, n Р' = ф

Критерием качества может служить модифицированный коэффициент

размещения = -l, -Lk j, где / = (1,2...,и) - исходное множество

предметов; /'- множество предметов, размещенных в областях (/'с/); К = (1, 2...,т) - множество выделенных прямоугольных областей; К'- множество областей, в которых размещены предметы (К' cz К).

При исходных данных ( m;W;L;n;wJ } требуется максимизировать PC

на множестве размещений {GP-(x,y)}, удовлетворяющих условиям 1°, 2°, 3°, 4°.

Методы сквозного размещения предметов в прямоугольных областях. Для решения задачи размещения прямоугольных предметов в прямоугольные области были применены методы, основанные на уровневых технологиях, которые берут свое начало с работ М. Adamowich & A. Albano, где ими были предложены послойные алгоритмы. Независимо аналогичные подходы предложены Э. А. Мухачевой и JI. Ф. Розановой В 2002 году в обзоре A. Lodi, S. Martello и D. Vigo были исследованы уровневые алгоритмы. Они приняты за основу в данной работе. Рассмотрен конструктивный алгоритм первого подходящего и его модификация - первый подходящий по невозрастанию длины, а также одноточечный эволюционный алгоритм (1+1)-ЕА с двумя способами перехода от одной особи к следующей: (1 + 1)-ЕА(гп) -наивный эволюционный алгоритм и (1+1)-ЕА(2) - эволюционный алгоритм поиска решения в окрестности. Алгоритм (1+1)-ЕА(т)

Вход: ( W;m\w = (w],w2,...,wm)\l={lvl2,...,/„,)); количество итераций. Выход: L - длина занятой части полосы; PC- коэффициент размещения; GP = (x,y) - прямоугольное размещение.

Шаг 1. Применение алгоритма первого подходящего к списку п. Шаг 2. Преобразование списка л: список генерируется случайным образом.

Шаг 3. Выполнение алгоритма первого подходящего.

Шаг 4. Сопоставление с рекордом по коэффициенту размещения.

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

Алгоритм (1+1)-ЕЛ(2) - эволюционный алгоритм поиска решения в окрестности, отличается от (1+1)-ЕА(ш) способом генерации нового списка ж. На шаге 2 случайно выбираются номера элементов г и у такие, что /,У е[1,/и],г>У. Формируется новый список к, в котором детали с номерами г и у меняются местами. Таким образом, исследуются размещения не из всей области допустимых решений, а только из окрестности начального списка ж.

С целью улучшения решения в ^

уровневый алгоритм была включена РисУН0К 2 Г ПРимеР »"деления и за-процедура заполнения боковых пус- полне™я боковых пустот: а - гори-тот. Назовем незаполненные области читальным способом; б - верти-каждого уровня справа от размещен- кальным способом ных прямоугольников боковыми пустотами. Будем различать горизонтальный и вертикальный способы выделения боковых пустот (рис. 2).

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

Вход: {\¥\т\1к\у/ = {™[,учг,...,= (/,,/.,,...,/„) - список неразмещенных элементов; (х;, у,), ¡ал* - частичное размещение; хк - координата х левого нижнего угла к-го уровня; / - длина к-го уровня.

Выход: - список элементов, размещенных в к-м уровне; (г,-, уЦ, г е и л* - частичное размещение.

Шаг 1. Нахождение размеров и координат /-й пустой области: для каждого элемента к-го уровня.

Шаг 2. Поиск пустой области с наибольшим значением у.

Шаг 3. Пересчет высоты верхней боковой пустоты.

Шаг 4. Заполнение боковых пустот.

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

Вход: {¡¥;т;-н> = (-н>1,м>2,...,м'„,);/=(/,,/2,...,/„,)); ж~ - список неразмещенных элементов; (*,-, у,), ¡в ж* - частичное размещение; хк - координата х левого нижнего угла к-го уровня;

Выход: п*к - список элементов, размещенных в к-й уровень; (хV.), : е тт1 и ж* - частичное размещение;

Шаг 1. Выделение боковых пустот горизонтальным способом.

Шаг 2. Нахождение пустой области, относящейся к предмету максимальной длины в уровне.

Шаг 3. Объединение смежных боковых пустот и пересчет параметров смежных областей.

Шаг 4. Заполнение выделенной боковой пустоты и проверка целесообразности проведенного объединения.

Шаг 5. Если есть неисследованные пустоты, то переход к шагу 2.

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

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

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

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

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

1. Представление области с препятствиями в матричном виде. Через все грани препятствий проведем сквозные линии (рис. 4). В результате об-

^ в .._____1.5........

а

1 й

; в

Рисунок 3 - Декомпозиция МОП методом условных резов: а - область без препятствий; б - простая область; в - сложная область

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

{О, если (/, <т) - свободная ячейка, 1, если (у,сг)- препятствие. Область с препятствиями будет записана в виде матрицы А = [а,,г] с булевыми переменными.

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

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

4. «Уровневое» выделение пустых прямоугольных областей. Пусть в ходе предыдущих шагов было выделено несколько прямоугольных областей без препятствий и достигнута верхняя граница области с препятствиями (области 1 и 2 на рис. 5). Через правую границу области наибольшей длины проведем условный сквозной рез и продолжим выделение областей без препятствий из области справа от реза. Тогда, по аналогии с уровневой технологией исходная область с препятствиями окажется разделенной на прямоугольные уровни. При выделении прямоугольников без препятствий в уровнях остаются «боковые пустоты», которые целесообразно использовать. Будем называть их вторичными многосвязными ортогональными полигонами. Для них рекурсивно применяется метод матричной декомпозиции свободной области полигона на прямоугольники. Работа алгоритма продолжается до тех пор, пока не останется пустых ячеек.

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

Рисунок 4 - Покрытие многосвязного полигона матричной сетью

■4 г- 1 4 -

[,

■У 4 -

и-

ф

■

-У 1 -

1 \

■ 1

Рисунок 5 - Уровневое выделения областей без препятствий

Алгоритм проектирования размещения прямоугольных объектов на многосвязном ортогональном полигоне

Вход: (^,ЬХхг,г]Л К А)> О*',-,/,), V = / = 1 ,пу

Выход: РС; вР = (х,у).

Шаг 1. Представление области с препятствиями в виде матрицы.

Шаг 2. Выбор исходной ячейки.

Шаг 3. Выбор направления объединения ячеек.

Шаг 4. Объединение пустых ячеек.

Шаг 5. Проверка наличия свободных ячеек над выделенной областью. Если достигнута верхняя граница области: поиск вторичных многосвязных полигонов справа от выделенных областей и добавление их в список; переход к шагу 6. Иначе: Свободная ячейка принимается за исходную; переход к шагу 3.

Шаг 6. Проверка наличия свободных ячеек справа от уровня. Если достигнута правая граница, переход к шагу 7, иначе переход к шагу 2.

Шаг 7. Выбор в качестве рассматриваемой области вторичного многосвязного полигона из списка. Если область выбрана, переход к шагу 2. Если все вторичные многосвязные ортогональные полигоны были исследованы, переход к шагу 8.

Шаг 8. Упорядочение боксов. Области без препятствий в списке упорядочиваются по неубыванию координаты X левого нижнего угла в исходном многосвязном ортогональном полигоне.

Шаг 9. Выбор метода заполнения боксов.

Шаг 10. Выбор пустого бокса из списка.

Шаг 11. Размещение в боксы предметов.

Шаг 12. Пересчет координат предметов в систему исходного многосвязного ортогонального полигона.

Шаг 13. Расчет коэффициента размещения и сравнение с рекордом.

Шаг 14. Проверка выполнения заданного общего количества итераций. Если номер текущей итерации не превышает заданного общего числа, то переход к шагу 15, иначе конец работы алгоритма.

Шаг 15. Проверка выполнения заданного количества итераций для декомпозиции. Если для текущего варианта декомпозиции проведено заданное количество итераций, то переход к шагу 2, иначе переход к шагу 9.

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

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

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

Разработана система автоматизированного проектирования размещения объектов на многосвязном ортогональном полигоне, которая состоит из подсистемы препроцессорной подготовки, расчетного модуля и подсистемы постпроцессорной обработки информации (рис. 6).' Подсистемы препроцессорной и постпроцессорной обработки информации позволяют учитывать технологические особенности области исследования, в расчетном модуле реализованы представленные s третьей главе методы проектирования планов размещения. Расчетный модуль САПР был реализован в программной системе «Проектирование сквозного размещения прямоугольников в МОП». Она предназначена для получения двумерных планов размещения прямоугольных объектов в полосу или на многосвязный полигон.

В четвертой главе для оценки эффективности работы алгоритма проектирования размещения прямоугольных объектов на многосвязном ортогональном полигоне были проведены численные эксперименты. С использованием методик Р. Schwerin и G. Wäscher были сгенерированы безотходные примеры следующих размерных

Рисунок 6 - Схема САПР размещения технических объектов на многосвязном полигоне

Таблица 1

Типы примеров

типов (таблица 1): малые (длина и ширина прямоугольника составляют от 10 да 30% ширины области), большие (от 30 до 60%) и различные (от 5 до 95%). Также различные классы задач отличались принципом назначения препятствий из общего числа прямоугольников: случайным образом, самые большие или самые маленькие по площади прямоугольники. Для каждого типа задач были рассмотрены примеры разной размерности - с количеством прямоугольников 20, 60, 120 180 и 240.

Тип Класс прямо- Критерий назначения

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

1 Малые Случайные

2 Большие Случайные

3 Различные Случайные

4 Различные Самые большие

5 Различные Самые маленькие

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

Также помощью метода размещения геометрических объектов в многосвязный ортогональный полигон было произведено планирование нового складского помещения предприятия ООО «Матрица-трейд».

Эксперименты позволили сделать следующие выводы:

1. Для задач самой большой размерности (240 прямоугольников) время расчета не превышает 1 мин. При этом коэффициенты размещения колеблются от 0,85 до 1,00.

2. Для примеров с большим разбросом размеров коэффициент размещения в среднем на 5% выше, чем для задач с однотипными объектами.

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

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

5. Сравнение с результатами, полученными методом «холодного отжига» показало, что на классе задач с небольшими (размеры объектов равны 10-30% ширины области) однотипными объектами алгоритм проектирования размещения прямоугольных объектов на многосвязном ортогональном полигоне на ряде примеров позволяет улучшить коэффициент размещения в среднем на 9%.

6. При планировании складского помещения ООО «Матрица-трейд» было составлено два плана размещения зон, не используемых для хранения, и проходов. Получившиеся области хранения были заполнены разными типами паллет. Наибольшая доля площади склада, занятой паллетами, составила 87% в случае размещения на одном складе как стандартных, так и ев-ропаллет.

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

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

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

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

2. Эвристические методы проектирования размещения прямоугольных предметов в прямоугольные области (1+1)-ЕА(ш) и (1+1)-ЕА(2), основанные на уровневых методах и отличающиеся тем, что включают в себя процедуру заполнения боковых пустот горизонтальным и вертикальным способом, эффективность которой была доказана численным экспериментом. Предложенные алгоритмы при небольших затратах времени позволяют найти рациональные решения, до 25% превосходящие результаты, полученные алгоритмами без разработанной процедуры.

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

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

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

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

В рецензируемых журналах из списка ВАК

1. Гильотинное размещение контейнеров в полосе: комбинирование эвристических технологий / Э. А. Мухачева, Э. И. Хасанова // Информационные технологии. 2009. № U.C. 8-14.

2. Матричный способ декомпозиции многосвязного полигона на множество прямоугольных областей минимальной мощности / Э. И. Хасанова,

Р. А. Валеев // Вестник УГАТУ. Уфа: УГАТУ, 2010. Т. 14. № 2 (37), С. 83187.

3. Проектирование размещения ортогональных объектов на полигонах с препятствиями / Э. А. Мухачева, Ю. И. Валиахметова, Э. И. Хасанова, С. В. Телицкий // Информационные технологии. 2010. № 10. С. 16-22.

4. Гильотинный раскрой промышленных материалов: эволюционный метод на базе уровневых алгоритмов / Э. И. Хасанова // Актуальные проблемы в науке и технике: сб. ст. 3-й Всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: Диалог, 2008. Т. 1. С. 247-255.

5. Задача гильотинного раскроя: поиск оптимума в окрестностях локальной нижней границы / Э. А. Мухачева, Э. И. Хасанова // Мавлютовские чтения: сб. тр. Всерос. молодежи, науч. конф. Уфа: УГАТУ, 2008. Т. 3. С. 161-163.

6. Алгоритм ортогональной упаковки контейнеров на базе step-технологии / Э. И. Хасанова // Актуальные проблемы в науке и технике: сб. ст. 4-й Всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: Диалог, 2009. Т. 1. С. 546-550.

7. Алгоритм гильотинного размещения контейнеров на базе step-технологии / Э. А. Мухачева, Э. И. Хасанова // Проблемы оптимизации и экономические приложения: матер. IV Всерос. конф. Омск: КАН, 2009.

8. Алгоритм гильотинного размещения контейнеров в полосу с препятствиями / Э. И. Хасанова // Фундаментальная математика и ее приложения в естествознании: матер. Междунар. шк.-конф. для студентов, аспирантов и молодых ученых. Уфа: РИЦ БашГУ, 2009. С. 78.

9. Гильотинное размещение контейнеров в полосе: модификация уровневого алгоритма локального поиска / Э. И. Хасанова // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УГАТУ, 2009. Вып. 6. С. 155-161.

1 ©.Проектирование размещения прямоугольных предметов на многосвязных ортогональных полигонах / Э. А. Мухачева, Э. И. Хасанова // Дискретная оптимизация и исследование операций: матер. Всерос. конф. Новосибирск: ИМ СО РАН, 2010. С. 174.

П.Свид. об офиц. per. программы для ЭВМ №2010617454: Проектирование сквозного размещения прямоугольных предметов в многосвязный ортогональный полигон / Э .И. Хасанова, А. С. Филиппова, Э. Р. Басимов. М.: Роспатент, 2010.

В других изданиях

С. 152.

Диссертант

Э. И. Хасанова

ХАСАНОВА Элина Ильдаровна

ПРОЕКТИРОВАНИЕ РАЗМЕЩЕНИЯ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА МНОГОСВЯЗНОМ ОРТОГОНАЛЬНОМ ПОЛИГОНЕ

Специальность: 05.13.12 - Системы автоматизации проектирования (в промышленности)

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

Подписано в печать 03.03.11. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл.кр.-отг. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 64.

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

Использованные обозначения.

Введение.

Глава 1. Задачи размещения объектов на плоских областях и примыкающие к ним проблемы покрытия: модели и методы решения.

1.1. Сферы применения алгоритма размещения прямоугольных предметов в многосвязный ортогональный полигон.

1.2. Модели и методы решения задач плотного размещения предметов.

1.3. Модели и методы решения задач размещения в область с препятствиями (двухсвязные полигоны).

1.4. Постановки задач покрытия.

Выводы по главе 1.

Глава 2. Задачи и методы проектирования плотного размещения технических объектов на многосвязных полигонах.

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

2.2. Уровневый метод проектирования гильотинного (сквозного) размещения предметов на многосвязных полигонах.

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

2.4. Проектирование плотного размещения технических объектов на многосвязном полигоне.

Выводы по главе 2.

Глава 3. Подсистема автоматизации проектирования инвариантных размещений объектов на многосвязном полигоне.

3.1. Структура системы проектирования размещения геометрических объектов на многосвязном ортогональном полигоне.

3.2. Подсистема проектирования плана размещения.

Выводы по главе 3.

Глава 4. Численные эксперименты.

4.1. Численные эксперименты на безотходных примерах.

4.2. Сравнительный анализ работы алгоритма размещения геометрических объектов в многосвязный ортогональный полигон и метода «холодного» отжига.

4.3. Планирование складского помещения ООО «Матрица-трейд» с использованием метода размещения геометрических объектов в многосвязный ортогональный полигон.

Выводы по главе 4.

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

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

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

Задачи размещения прямоугольных объектов внутри многосвязного ортогонального полигона являются обобщением задач 2DBP (2-Dimensional Bin Packing), то есть, как и они, относятся к классу NP-трудных задач комбинаторной оптимизации. На сегодняшний день не известно алгоритмов поиска оптимального решения полиномиальной сложности для этого класса задач, и точный результат в общем случае может быть получен переборным алгоритмом только за экспоненциальное время.

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

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

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

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

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

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

3. Разработать эффективные алгоритмы декомпозиции многосвязного ортогонального полигона на прямоугольные боксы для определения области размещения;

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

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

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

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

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

2. Методы горизонтального и вертикального заполнения боковых пустот при проектировании размещения объектов в прямоугольную область с использованием уровневых технологий;

3. Метод матричной декомпозиции многосвязного ортогонального полигона на прямоугольные области для последующего размещения в них объектов; 4. Метод условных резов для декомпозиции ортогонального полигона на прямоугольные области для последующего размещения в них объектов;

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

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

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

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

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

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

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

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

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

Связь исследования с научными проблемами

Работа выполнялась при поддержке гранта Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации НШ-65497.2010.9.

Апробация работы

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

1. III Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 2008 г.);

2. Всероссийская молодежная научная конференция «Мавлютовские чтения» (Уфа, 2008 г.);

3. IV Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 2009 г.);

4. IV Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2009 г.);

5. Международная школа-конференция для студентов, аспирантов и молодых ученых (Уфа, 2009 г.);

6. Российская конференция «Дискретная оптимизация и исследование операций» (Алтай, 2010 г.);

7. Научные семинары кафедры вычислительной математики и кибернетики и кафедры математики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 11 работ, в том числе 3 статьи в рецензируемых журналах из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2010617454.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 187 страниц машинописного текста, включая 53 рисунка, 21 таблицу, список литературы, содержащий 153 название, и 3 приложения.

Выводы по главе 4

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

1. В ходе численного эксперимента на безотходных примерах была исследована работа алгоритма на 5 типах задач, отличающихся размерами предметов и препятствий. Также была исследована зависимость качества получаемого решения от доли препятствий в общем числе объектов, влияние количества предметов и количества итераций на время расчетов и получаемый коэффициент размещения. Были получены достаточно высокие коэффициенты размещения (> 0,8) за приемлемое время (< 1,5 мин для примеров размерности 240). Более высокие коэффициенты размещения были получены для задач с большим разбросом размеров предметов и меньшей долей препятствий в общем количестве объектов. Достаточное количество итераций составляет от 10 до 50 тысяч, дальнейшее увеличение числа итераций позволяет лишь незначительно улучшить результат, что не оправдывает временные издержки.

2. Сравнительный анализ на примерах с небольшими однотипными предметами (размеры предметов составляют 10-30% ширины области) показал преимущество алгоритма размещения геометрических объектов на мно

151 госвязном ортогональном полигоне до 12% по сравнению с методом «холодного» отжига. На примерах малой размерности (20 объектов) оба алгоритма показывают одинаковый результат и позволяют найти оптимальное решение, на примерах большей размерности алгоритм размещения геометрических объектов на многосвязном ортогональном полигоне показывает результат в среднем на 9% лучше, чем алгоритм «холодного» отжига.

3. При планировании складского помещения ООО «Матрица-трейд» было составлено два плана размещения зон, не используемых для хранения, и проходов. Получившиеся области хранения были заполнены разными типами паллет. Наибольшая доля площади склада, занятой паллетами, составила 87% в случае размещения на одном складе как стандартных, так и евро-паллет.

Заключение

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

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

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

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

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

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

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

1. Аккуратов Г.В., Березнев В.А., Брежнева O.A. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник / Уфимск. гос.авиац. техн. ун-т. Уфа; 1990.-С. 145-154.

2. Алексеев О. Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.

3. Ахо. А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. / М.: Мир, 1979.

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

5. Борисовский П.А., Еремеев A.B. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика, №3. М.: Наука. 2004. С. 3-9.

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

7. Бухтесв А. Среда проектирования компании Cadence. — CHIP NEWS, № 4 (77), Апрель, 2003. С. 3-8

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

9. Валиахметова Ю.И., Мухачева Э.А., Филиппова A.C., Гильманова H.A., Карипов У.А. Мультиметодная технология ортогональной упаковки и ее применение в задачах транспортной логистики // М.: Приложение к журналу «Информационные технологии», №12. 2009. 31 С.

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

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

12. Гимади Э.Х., Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. №12. С. 2533.

13. Гимади Э.Х., Залюбовский В.В., Шарыгин П.И. Задачи упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. 1997. №12(427). С. 34-44.

14. Емеличев В. А. Лекции по теории графов. М.: Наука, 1990. 110 С.

15. Ермаченко А.И., Сиразетдинов Т.М. Рекурсивный метод для решения задачи гильотинного раскроя // Принятие решений в условиях неопределенности: Межвуз. науч. сб. / Уфимск. гос.авиац. техн. ун-т. -Уфа, 2000. С.35-39.

16. Забудский Г. Г. Алгоритм решения минимаксной задачи размещения объекта на плоскости с запрещенными зонами // АиТ. 2004. № 4. С. 93-100.

17. Забудский Г. Г. Построение моделей и решение задач размещения на плоскости с запрещенными зонами // АиТ. 2006. № 12. С. 136—141.

18. Исследование операций. Модели и их применение / Под ред. Дж.Моудера, С.Элмаграби. М.: Мир, 1981. 213 с.

19. Казенное Г.Г. Основы проектирования интегральных схем и систем. — М.: Бином. Лаборатория знаний, 2005. 97 с.

20. Канторович JI.B. Математические методы организации и планирования производства // JI.: изд-во ЛГУ. 1939. 68 с.

21. Канторович Л.В., Залгаллер В.А. Расчет рационального раскроя материалов// Лениздат, 1951. 72 с.

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

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

24. Корячко В. П., Курейчик В. М., Норенков И. П. Теоретические основы САПР. — М.: Энергоатомпздат, 1987. 243 с.

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

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

27. Кравченко В., Радченко Д. SYNOPSYS — основные средства и возможности. — Электроника: Наука, Технология, Бизнес, 5/2003.

28. Кузнецов В. Ю. Задачи покрытия: модели, алгоритмы и приложения. / Кузнецов В. ГО., Егорова М. С. // Принятие решений в условиях неопределенности: сб.науч.тр. Уфа: УГАТУ. 2007. С.82-88

29. Куреичик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация. М.: Физматлит, 2006. 269 с.

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

31. Лохов А. Средства проектирования СБИС компании Mentor Graphics. Электроника: Наука, Технология, Бизнес, 2003. №7.

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

33. Мухачева А. С. Простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределенности. Межвузовский нацчный сборник. Вып.2. 4.1. Уфа: УГАТУ. 2005. С.38-43.

34. Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем / Мухачева A.C. // Уфа. Дисс. канд. физ-мат. наук. 1999. 117 с.

35. Мухачева A.C. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки // М.: Информационные технологии. Приложение. 2004. №5. С. 18-31.

36. Мухачева A.C., Житников В.П. Метод оценок для решения задач линейной и прямоугольной упаковки // Уфа: Материалы международной научной конференции. Оптимизация численных методов. 1998. С. 40-45.

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

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

39. Мухачева A.C., Чпглшщев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. №3. С. 27-32.

40. Мухачева А С., Чпглшщев A.B. Смагин М.А. Мухачева Э.А. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения // Информационные технологии. 2001, №9. Приложение. 28 с.

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

42. Мухачева Э.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. Вып. 6. С. 43-115.

43. Мухачева Э.А., Бухарбаева Л.Я., Филиппов Д.В., Карипов У.А. Оптимизационные проблемы транспортной логистики: оперативное размещение контейнеров при транспортировке грузов // М.: Информационные технологии. 2008. №7(143). С. 17-22.

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

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

46. Мухачева Э.А., Валеева А.Ф., Сиразетдинова Т.Ю., Сиразетдинов Т.М. Автоматизация проектирования гильотинного раскроя с обходом дефектных областей на базе эволюционных алгоритмов // М.: Приложение к журналу «Информационные технологии», №2. 2009. 32 С.

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

48. Мухачева Э.А., Валиахметова Ю.И., Хасанова Э.И., Телицкий C.B. Проектирование размещения ортогональных объектов на полигонах с препятствиями//М.: Информационные технологии. 2010. № 10. с. 16-22

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

50. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Жукова Т.Ю. Комплекс алгоритмов и программ расчета гильотинного раскроя // М.: Новые Технологии. Информационные технологии. 2004. №8. С. 18-25.

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

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

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

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

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

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

57. Мухачева Э.А., Хасанова Э.И. Гильотинное размещение контейнеров в полосе: комбинирование эвристических технологий. // М.: Информационные технологии. 2009. № 11. С. 8-14

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

59. Норенков И.П. Генетические методы структурного синтеза проектных решений // М.: Информационные технологии. 1998. №1. С. 9-13.

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

61. Пападемитриу X., Стайглец К. Комбинаторная оптимизация. Алгоритмы и сложность // М.: Мир. 1985. 512 с.

62. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.

63. Приказ от 21 апреля 2003 г. N BP-1/п об утверждении правил безопасности морской перевозки

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

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

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

67. Сиразетдинова Т.Ю. Конструирование прямоугольного раскроя в системах автоматизированного проектрирования с учетом дефектных областей материала / Сиразетдинова Т.Ю. // Уфа. Дисс. канд. тех. наук. 2007. 130 с.

68. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов // Киев: Наук, думка. 1976.

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

70. Тарасов А.Е. Автоматизация проектирования раскройно-заготовительного производства светопрозрачных конструкций на основепроблемно-ориентированных методов оптимизации // Диссертация на соискание ученой степени кандидата технических наук. 2007.

71. Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. 1978. № 6. С. 67-70.

72. Филиппова А.С. Блочная технология конструирования алгоритмов для решения задач прямоугольной упаковки полубесконечной полосы // Уфа: Уфимск. гос. авиац. техн. ун-т. Вестник УГАТУ. 2005, т.6, №1 (12). С. 106116.

73. Филиппова А.С. Конструирование ортогональной упаковки в полубесконечной полосе на базе декодеров блочной структуры // Уфа. Вестник БГУ. 2006. №3. С. 6-8.

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

75. Филиппова А.С. Проблемы декодирования прямоугольных упаковок: краткий обзор современных технологий // М.: Новые технологии. Информационные технологии. 2005. № 12. С. 13-20.

76. Хасанова Э.И., Валеев Р.А. Матричный способ декомпозиции многосвязного полигона на множество прямоугольных областей минимальной мощности. //Вестник УГАТУ. Т.14, № 2(37) -Уфа: УГАТУ, 2010. с. 183-187

77. Щемелинин В.М. Автоматизация топологического проектирования -М.: МИЭТ, 2001.

78. Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. 8(1). P. 27-33.

79. Aurts E., Lenstra J., edit. Local Search in Combinatorial Optimization // John Wiley&Sons. 1996.

80. Belov G., Scheitchauer G., Mukhacheva E.A. On dimensional heuristics adapted for two-dimensional rectangular strip packing. Technical report. Dresden University. 2006. URL http://www.math.tu-dresden.de/capad/. Preprint MATH-NM-02-2006.

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

82. Berman P. Approximating rectilinear polygon cover problems / Berman P., Dasgupta B. // Algorithmica. #17(4). 1997. P. 331-356.

83. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem // Annals of OR. 1993. 41(4). P. 313-325.

84. Bortfeldt A., Gehring H. Applying tabu search to container loading problems // Operations Research Proceedings. 1997, Springer, Berlin, 1998, P. 533538.

85. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem // Qua-terly Journal of the Belgian, French and Italian Operations Research Societies, 2002.,

86. Bronnimann H. almost optimal set covers in finite VC-dimension. / Bron-nimann H., Goodrich M. // Discrete comput. Geom., #14. 1995. P.263-279.

87. Burke E., Kendall G. Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem // Accepted for the 1999 International Conference on Artificial Intelligence, Monte Carlo resort. Las Vegas. Nevada. USA. 1999.

88. Cabot A.V., Francis R.L., Stury M.A. A network flow solution to a rectilinear distance facility location problem // AIIE Transactions. 1970. V. 2. No. 2. P. 132-141.

89. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing // CS270 Project Report, Spring, 1999.

90. Cheng Y. A new method for image compression using irreducible covers of maximal rectangles. / Cheng Y., Iyegnar S. S., Kashyap R. L. // IEEE transactions on software engineering. V.14, #5. 1988. P. 651-658.

91. Clautiaux F., Carlier J., Moukrim A. A new exact method for the two- dimensional orthogonal packing problem // European Journal of Operation Research. 2006. 172(3). P. 801-813.

92. Culberson J. C. Covering polygons is hard. / Culberson J. C., Reckhow R. A. // Journal of algorithms, #17. 1994. P. 2-44.

93. Dorigo M., Di Caro G., Gambardella L.M. Ant algorithms for discrete optimization // Artificial Life. 1999. Vol. 5. No. 3. P. 137-172.

94. E)origo M., Gambardella L.M. Ant colonies for the traveling salesman problem // IRIDIA, Technical Report 1996. 3.

95. Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem // IEEE Transactions on Evolutionary Computation. 1997. Vol. 1. No. 1.

96. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University of Copenhagen, Denmark. Dept. of Computer Science, University of Copenhagen.

97. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998. 2(1). P. 5-30.

98. Forster IT., Wascher G. (1997) Simulated annealing for order spread minimization sequencing cutting patterns // European Journal of Operational Research. 1998. 110. P. 272-281.

99. Franzblau D. S. An algorithm for constructing regions with rectangles. / Franzblau D. S., ICleitman D. J. // Information and control, #63. 1984. P.164-189.

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

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

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

103. Giidmnndsson J. Close approximations of minimum rectangular coverings. / Gudmnndsson J., Levcopoulos C. // FST&TCS'96. LNCS,V.l 180. 1996. P. 135-146.

104. Gudmundsson J. Lower bounds for approximate polygon decomposition and minimum gap. / Gudmundsson J., Levcopoulos C. // Information Processing Letters, V.81, Issue 3. 2002. P. 137-141.

105. Hifi M Exact algorithms for the guillotine strip cutting/packing problem //Computers and Operations Research. 1998. (25). P. 925-940.

106. Hinxmnn A. The Trim-Loss and assortment problems: a survey // European Journal of Operational Research. 1980. N11. P. 863-888.

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

108. Hopper E., Turton B.C.H. A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems // Artificial Intelligence Review. 16. 200l.P. 257-300.

109. Imahori S. Local Search Heuristics for the Rectangle Packing Problem // Kyoto: Kyoto University. 2004. P. 606-8501.

110. Jakobs S. On the genetic algorithms for the packing of polygons // European Journal of Operational Research. 1996. V. 88. P. 165-181.

111. Johnson D.S. Approximation algorithms for combinatorial problems // Journal of omputing and systems sciences, #9. 1974. P. 256-278. •

112. Johnson D.S. Near-optimal bin packing algorithms // PhD Thesis, MIT, Cambridge, MA, 1973.

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

114. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research. 2002. 141. P. 410-420.

115. Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems // Discrete Applied Mathematics 123. 2002. P. 379 -396.

116. Loris F. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 114. P. 532-556.

117. Lovasz L. On the ratio of optimal integral and fractional covers // Journal of discrete mathematics, #13. 1975. P.383-390.

118. Martello S., Monaci M., Vigo D. An Exact Approach to the Strip-Packing Problem // Informs Journal on Computing. 2003. 15. P. 310-319.

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

120. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem // Management Science. 1997. 35. P. 64-68.

121. Masek W.J. Some NP-complete set covering problems / Manuscript. MIT, 1977.

122. Morabito M. Arenales M. Staged and constrained two-dimensional guillotine cutting problems: an and/or-graph approach // European Journal of Operational Research. 1996. 94. P. 548-560.

123. Morabito R., Arenales M. An AND/OR graph approach to the container loading problem // International Transactions in Operational Research 1. 1994. P. 59-73.

124. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V.3.N4.P. 463-476.

125. Murata H., Fujiyoshi K., Nakatane S. and Kajitani Y. Rectangle-Packing-Based Module Placement // Proc. IEEE/ACM International Conf. on Computer-Aided Design. 1995. P. 472-479.

126. Naveed Sherwani. Algorithms for VLSI physical design automation. — Boston /Dordrecht/ London: Kluwer academic publishers, 1995.

127. Nickel S., Puerto J. Location theory. A unified approach. Berlin: Springer, 2005.

128. Physical Design Automation of VLSI Systems / Edited by T.Preas and

129. M. Lorenzetti. BCPC, Inc. USA: Menlo Park, 1988.i

130. Picard J.C., Ratliff H.D. A cut approach to the rectilinear distance facility location problem // Operations Research. 1978. V. 26. No. 3. P. 422-433.

131. Rechenberg I. Evolutions strategic: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann —Holzboog Verlag. 1973.

132. Sakanushi K., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pacific Conference on Circuits and systems. 2000. P. 829-832.

133. Schwerin P., Wäscher G. A New Lower Bound for the Bin-Packing Problem and its integration to MTP // Pesquisa Operational. 1999. 19(2). P. 111-131.

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

135. Stoyan Yu., Novozhilova M. Non-guillotine Placement of Rectangles into a Strip of Given Width // Pesquisa Operational. 1999. 19(2). P. 189-211.

136. Stoyan Yu.G., Gill N.I. Minimal area rectangular hull ,of two any polygons being glued // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997. P. 225-244.

137. Tarnowski A.G. Advance polynomial time algorithm for guillotine generalized pallet loading problem // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997.P.93.125

138. Tarnowski T., Terno J., Scheithauer G. A polynomial time algorithm for the guillotine pallet loading problem. INFOR 32. 1994. P. 275-287.

139. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.

140. Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin-Packing Problem: Numerical Study // Proceedings of the 5th International Workshop on Computer Science and Information Technologies, 2003. P. 110-114.

141. Vance P. Branch-and-price algorithms for the one-dimensional cutting stock problem // Computational optimization and Applications 9(3). 1998. P. 212228.

142. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Opera-cional. 2000. V. 20. N2. P. 233-247.

143. Answer Logistic Электронный ресурс.: единый сервис по обработке запросов на перевозку грузов различными видами транспорта. — Режим доступа: http://www.answer-logistic.ru

144. Большая Советская Энциклопедия Электронный ресурс.: Режим доступа: http://bse.sci-lib.com/

145. Деревообработка с фирмой Мосхуд Электронный ресурс.: сайт деревообрабатывающего предприятия Мосхуд, 2010. — Режим доступа: http.V/moshud.info/teorija-derevoobrabotki/raskroi-drevesnykh-materialov/

146. Как устроены морские суда Электронный ресурс.: сайт о морских судах. — Режим доступа: http://www.seaships.ru

147. Оборудование для производства пластиковых окон и стеклопакетов Электронный ресурс.: сайт компании СТАНСТРОЙ, 2010. — Режим доступа: http://stanstroy.ru/index.php?docid=29

148. Оборудование для производства пластиковых окон ПВХ Электронный ресурс.: сайт компании STK, 2009. — Режим доступа: http ://www. stkinfo .га/ steklopaket/rezkastekla/

149. Сайт логистов Электронный ресурс.: информационный ресурс для профессионалов в области логистики. Режим доступа: http://logisty.narod.ru/articles/gadj/gadj.html

150. Склад законов Электронный ресурс.: сборник нормативных документов по логистике. Режим доступа: http://sklad-zakonov.narod.ru

151. Электронная техника Электронный ресурс.: учебник по электронной технике — Режим доступа: http://eutl.ru/index/l/13/index.htm