Содержание к диссертации
Введение
1. Модели и методы решения задач упаковки S
1.1. Задача одномерного раскроя 12
1.2. Задача прямоугольной упаковки в полубесконечную полосу 13
1.3. Задача прямоугольной упаковки в листы 15
1.4. Задача гильотинного раскроя 15
1.5. Обзор методов решения задач одно и двухмерного раскроя-упаковки 16
1.5.1. Использование методов математического программирования 18
1.5.2. Применение методов комбинаторной оптимизации 19
1.5.3. Приближенные и эвристические методы 20
1.5.4. Вероятностные методы локального поиска оптимума 26
1.6. Выводы 32
2. Способы кодирования упаковок 33
2.1. Прямой способ кодирования 34
2.2. Кодирование приоритетным списком 34
2.3. Схема парных последовательностей 35
2.4. Блочная технология кодирования-декодирования упаковок 36
2.4.1. Блок структуры упаковок и их свойства 36
2.4.2. Преимущества блочной технологии кодирования упаковок. 41
2.4.3. Алгоритмы построения упаковки - декодеры. Декодер замещения Sub (NF), следующий подходящий 42
2.4.4. Декодер замещения Sub (FF), первый подходящий 45
2.4.5. Декодер жадного замещения Greedy Sub 49
2.4.6. Декодер «пара списков» Dual Local Search (DLS) 54
2.5. Выводы 57
3. Эволюционные методы решения задач упаковки 58
3.1. Наивный эволюционный метод {Naive Search, NS) 58
3.2. Эволюционный алгоритм (1+1) 58
3.3. Метод последовательного уточнения оценок (Sequentative Value Correction, SVC) 60
3.4. Генетические методы решения задачи упаковки. Общая характеристика генетических методов 64
3.5. Схема «жадного» генетического алгоритма 67
3.6. Гибридный генетический алгоритм на базе SVC и Greedy Sub 68
3.7. Модификация методов для решения задачи упаковки на прямоугольные листы 69
3.8. Оценка эффективности алгоритмов. Нижние границы 70
3.8. Выводы 73
4. Вычислительный эксперимент 74
4.1. Программная реализация алгоритмов 74
4.2. Решение задач размещения на полосу на примерах Bortfeld 79
4.3. Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов 81
4.4. Исследование эффективности генетического гибридного алгоритма Genetic Greedy Sub. Сравнительный эксперимент с метаэвристическими алгоритмами 83
4.5. Решение задач размещения на листы на примерах S.P Fekete и J. Schepers 84
4.6. Выводы 88
Заключение 89
Список литературы
- Задача прямоугольной упаковки в листы
- Схема парных последовательностей
- Метод последовательного уточнения оценок (Sequentative Value Correction, SVC)
- Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов
Введение к работе
Актуальность проблемы. Задачи раскроя-упаковки представляют собой важный прикладной раздел дискретной оптимизации. Актуальность проблемы создания эффективных алгоритмов для решения задачи раскроя-упаковки двумерного прямоугольного ресурса обусловлена как широким практическим применением задач в различных отраслях производства, так и трудностью создания адекватных математических моделей и методов их решения.
От качества полученного решения зависит:
эффективность использования ресурсов;
продуктивность использования оборудования;
время проектирования и производительность труда.
Задачи раскроя - упаковки представляют большой интерес для производства. В условиях массового производства изделий даже незначительная экономия сырья на одно изделие даст после приведения к годовому объему продукции многие тонны сэкономленного материала. Этим объясняется внимание, которое уделяется совершенствованию методов расчета раскроя.
Сложность решения задачи раскроя-упаковки обусловлена ее принадлежностью к классу NP-трудных задач комбинаторной оптимизации. Исследуемая задача является NP-трудной в сильном смысле, так как содержит в качестве подзадачи также NP-трудную задачу. Во многих случаях применение точных методов для ее решения невозможно из-за больших затрат вычислительного времени. В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик. В их числе широкое применение получили генетические алгоритмы. Известна асимптотическая сходимость таких методов. На практике метаэвристики очень хорошо себя зарекомендовали. Качество полученного решения зависит не только от выбранного метода расчета раскроя-упаковки. Важную роль выполняют и способы кодирования и декодирования упаковок.
Исходя из вышеизложенного, представляет интерес разработка и
применение новых методов, в том числе эволюционных алгоритмов для
решения задачи раскроя-упаковки прямоугольных предметов на базе
эффективных принципов кодирования упаковок. Важным является создание
программной реализации, которая позволила бы получать качественные
решения производственных задач за приемлемое время. Разработанное
алгоритмическое и программное обеспечение становится
конкурентоспособным в ряду точных и эвристических подходов. В этом состоит актуальность данной разработки.
Целью работы является разработка и реализация эффективных численных методов, алгоритмов и программного обеспечения для решения задач прямоугольной упаковки на базе блочных технологий.
Для ее достижения были поставлены и решены следующие задачи:
1. Рассмотреть постановки задач прямоугольной упаковки и выделить часто встречающиеся в промышленности модели и методы решения задач упаковки и раскроя.
Провести анализ и модифицировать простые алгоритмы конструирования упаковок (декодеры, формирующие упаковку на основе заданного кода), с целью повышения их эффективности.
Разработать новый эффективный декодер на базе блочных структур, совмещающий высокую производительность простых эвристик с оптимальным использованием материала за счет применения «жадных» стратегий.
Разработать "наивный" эволюционный алгоритм на базе простых эвристик и «наивного оператора мутации»
Модифицировать эволюционные алгоритмы с применением жадного декодера замещения для поиска и исследования эффективных методов решения задачи упаковки.
Создать программное обеспечение, реализующее модифицированные и новые разработанные методы.
Провести анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов в сравнении с другими методами, описанными в литературе.
На защиту выносятся:
Эволюционный «наивный» алгоритм на базе простых эвристик типа «подходящий» и «наивного оператора мутации».
Декодер «жадного» замещения Greedy Sub на базе блочной структуры и его модификации.
Генетический алгоритм на базе блочных структур для решения задачи прямоугольной упаковки полу бесконечной полосы и на листы.
Гибридизация генетического алгоритма с блочным декодером «жадного» замещения.
Программное обеспечение, реализующее разработанные алгоритмы и предназначенное для проведения численных экспериментов.
Результаты исследования эффективности предложенных методов на основе проведенного численного эксперимента.
Научная новизна работы. Новыми в работе являются:
«Блочный декодер жадного замещения» - создан новый эффективный метод конструирования двухмерной упаковки, который реализует жадную стратегию одновременно в разных направлениях, оперируя несколькими приоритетными списками прямоугольников; декодер может применяться в различных метаэвристиках.
Новый метод локального поиска оптимальной упаковки, представляющий собой генетический алгоритм с жадным блочным декодером. Показано, что такой подход дает лучшие решения и большую экономию материала по сравнению со многими известными в литературе реализациями.
Модификация метода последовательного уточнения оценок на случай прямоугольной упаковки блочной структуры.
Программное обеспечение, реализующее новые методы расчета упаковок, ориентированное на численные эксперименты и промышленные расчеты.
Практическая значимость работы
Программная реализация генетического алгоритма и жадного блочного декодера показала значительные преимущества перед известными классическими способами применения эвристических методов к задачам упаковки на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах и включать комплекс программ в автоматизированные системы проектирования и управления. Экономический эффект составляет от 1 до 10% экономии материала.
Связь исследования научными проектами: Работа выполнялась при частичной поддержке РФФИ, проект 01-01-00510.
Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:
Международная конференция «Ресурсосберегающие технологии». Санкт-Петербург 2001.
Байкальская международная школа-семинар «Математическое программирование», Иркутск, 2002.
Международная конференция «Математическое программирование и приложения», Екатеринбург 2003.
Международная конференция ESICUP (Европейская специальная группа по раскрою и упаковке) (Germany, 2004г.);
Семинары института вычислительной математики Дрезденского технологического университета, 2005г.
Семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.
Конференция региональной зимней школы-семинара аспирантов и молодых ученых. «Интеллектуальные системы обработки информации и управления», Уфа, 2006г.
В 2004-2005 учебном году прошел по линии ДААД научную стажировку в институте вычислительной математики Дрезденского технического университета. Результаты работа внедрены в учебный процесс УГАТУ и в Центр обработки информации ОАО «Башнефтегеофизика», г.Уфа.
По теме диссертации опубликовано 9 работ: 5 статей (2 из них в изданиях рекомендованных ВАК на 13 машинописных страницах), 3 статьи в материалах конференций. Правовая сторона программного обеспечения защищена в Роспатент свидетельством об официальной регистрации программ для ЭВМ № 2006612649.
Выражаю глубокую благодарность научному руководителю д-ру техн. наук, проф. Элите Александровне Мухачевой и канд.физ.-мат.наук, доц. Анне Сергеевне Мухачевой-Филипповой.
Задача прямоугольной упаковки в листы
С решением задачи ортогональной упаковки связана и задача ее реализации. Она зависит от особенностей раскройного оборудования или характера упаковки. Часто встречается задача гильотинного раскроя (GSP), когда возможными являются только сквозные резы, параллельные кромкам материала (см. рис. 1.2). Обобщением 1DCSP на двухмерный случай являются задачи 1.5DGSP и 2DGSP. Для решения задач гильотинного раскроя применяются аналогичные, с одномерным случаем, методы. Что касается гильотинной упаковки, то это - упаковка рядами, например так размещаются контейнеры и автомашины на палубах судов.
В течение последних пятидесяти лет проблема размещения привлекает внимание научных исследователей и производственников. Начало этому положила в 1951 г. книга Ленинградских ученых Л.В.Канторовича и В.А.Залгаллера [22]. Задачи размещения рассматривались ими как примеры применения ранее развитого Л.В.Канторовичем линейного программирования.
Для решения задач применяется модель линейного программирования с неявно заданной информацией о размещении (столбцах матрицы). Для генерации столбцов В.А.Залгаллером был предложен прием, предвосхитивший появившееся позднее динамическое программирование. Аналогичные методы получили развитие в 60-е годы за рубежом в работах P.Gilmore & R.Gomory [81], [82] и позднее J.Terno, R.Lindeman & G.Scheithauer [108]. Для решения задачи генерирования размещения были разработаны метод склейки И.В.Романовским [51], сеточный метод для линейного раскроя В.А.Булавским и М.А.Яковлевой [7], для гильотинного раскроя Э.А.Мухачевой [40], [33]. На базе линейного программирования Э.А.Мухачевой разработаны также алгоритмы условной оптимизации, учитывающие специфику реального производства [36]. В то время основной целью этих и многих других работ являлось применение линейного программирования в сфере производственных задач. Эта цель в той или иной мере была достигнута в условиях массового и серийного производства. В зарубежной литературе признан приоритет Л.В.Канторовича и В. А.Зал галл ера [22]. Однако задачи размещения по своей сути являются проблемами дискретной оптимизации и их решение с помощью линейного программирования не более чем непрерывная релаксация, которая дает решение близкое к оптимальному при дополнительных ограничениях, возникающих в условиях серийного производства. Далее задачи размещения рассматриваются как прикладные проблемы комбинаторных задач исследования операций.
Впервые качественная типология в области раскроя-упаковки проведена в 1990 г. немецким ученым H.Dykhoff [73]. Она принята в мировой практике и используется при изучении моделей и методов решения задач раскроя-упаковки. Разнообразие моделей определяется, прежде всего, фактором геометрии. Различаются задачи линейного (одномерного), прямоугольного (двухмерного) и параллелепипедного (трехмерного) размещения. Задачи размещения являются типичными представителями NP-трудных проблем и для их решения применяются общие подходы: точные методы, простые эвристики и метаэвристики. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание приближенным методам и эвристикам.
В течение 90-х годов прошлого столетия на тему раскроя-упаковки было выпущено шесть специальных изданий: под редакцией H.Dyckhoff & G.Wascher в 1990 г. [73], S.Martello в 1994 г. [91], [92], Y.Lirov в 1995 г. [87], E.Bischoff & G.Wascher в 1995 г. [66], E.Mukhacheva в 1997 г. [97], H.Yanasse в 1999 г. [114], P.Wang & G.Washer в 2000 г. [112]. Более того, сотни статей опубликованы в международных и российских журналах: European Journal of Operational Research (EJOR), Computers & Operations Research, Computers & Industrial Engineering, Operations Research Letters, Pesquisa Operacional; Информационные технологии, Автоматика и телемеханика, Дискретный анализ и исследование операций, Вестник высшей школы, Кузнечно-штамповочное производство и другие центральные и ведомственные издания. При этом статьи и книги имеют как теоретический, так и прикладной характер.
Схема парных последовательностей
S. Imahori и другие ученые (Япония) в 1995 г разработали схему парных последовательностей [85] (Sequence Pair, Seq Pair) кодирования упаковок для комбинаторного поиска. Для представления решения используется пара перестановок а+ и т_ из m прямоугольников (см. рис. 2.4). Базируясь на кодированном этими последовательностями решении, устанавливают относительные положения для каждой пары і и j прямоугольников: если і располагается перед / в обеих перестановках, следует разместить і левее /. Если і располагается перед /" в а+ и после j в а_, то і помещаем выше /. Например, для пары последовательностей, рис. 2.4а, имеем: прямоугольник Рг расположен перед / 4 в обеих перестановках, следовательно, Рг левее РА ; прямоугольник Р4 располагается перед Р2 в а+ и после Р2 в а_ , и, следовательно, Pi выше, чем Р2 и так далее. Дальнейшее развитие этого метода и его интерпретации на графах приведены в диссертации S.Imahori [85].
Кодирование парой последовательностей: (а) - пара последовательностей (б) - эскиз упаковки Далее рассматривается блочный способ кодирования упаковки (Block Coding Method, ВСМ), основывающийся на блочной модели упаковки.
Блочная технология кодирования-декодирования упаковок
Технология блочных структур предложена Э.А. Мухачевой и развита в работах А.С. Филипповой [30], [31], [32], [33], [44]. Здесь она применяется для описания простых эффективных декодеров. Для удобства изложения повторим некоторые ее основные положения.
Блок структуры упаковок и их свойства
Пусть имеется прямоугольная упаковка RP в полосу ширины W, и ее длина равна L. Проведем через правые стороны прямоугольников вертикальные линии. Они разделяют RP на г прямоугольных блоков одинаковой ширины W и различной длины %р)-\г. При этом lX;=L. (4) 7= Блоки назовем вертикальными, а соответствующее разбиение упаковки -вертикальной блок-структурой (Vertical Block - Structure, VBS), (см. рис. 2.5а). Проведем через верхние стороны прямоугольников горизонтальные линии. Они разделят RP на q прямоугольных блоков одинаковой длины L и различной ширины ц., у = \,q. При этом ir}j=L W. (5) ./=1
Блоки назовем горизонтальными, а соответствующее разбиение упаковки - горизонтальной блок-структурой (Horizontal Block-Structure, HBS), (см. рис.2.56). Сопоставим блок-структурам списки S и S . Каждому блоку j сопоставим в списке кортеж (запись номеров прямоугольников, пересекающих блок) и длину Xj вертикального и (//, - горизонтального блока). Тогда s={\(j\2(j),...,i(j),...)xj,j=\:r\ (6) 5-(1(/-),2(/-),...,/(/),...)7/, 7-й, (?) где /(/) - номер прямоугольника в позиции і, пересекающего j-й блок, г -количество вертикальных, q - горизонтальных блоков.
Пример. Имеется 1.5DBPP с исходными данными {W; т; w; /). JF=55; ш=6; w=(28; 27; 10; 45; 45; 15); /=(20; 30; 63; 22; 26; 15). Соответствующая допустимая упаковка RP изображена на рис. 2.5. Она задана координатами (. УІ), і = їт размещенных прямоугольников, RP={(0; 27) (0; 0) (20; 45) (ЗО; 0) (42; 0) (68; 0)}. Разбиения RP на блоки (вертикальные и горизонтальные) показаны на рис. 3 (а) и (Ь) штриховыми линиями. Там же указаны длины (ширины) блоков.
Длина I(RP)=93 и ее ширина IV=W=55 вычислены по формулам (4) и (5). Легко проверить, что блок-структурам отвечают следующие списки: S- {(Р2; Р1)20; (Р2; Р3)10; (Р4; Р3)22; (Р5; Р3)26; (Р6; Р3)5; (Р6)10); S= {(Р2; Р4; Р5; Р6)15; (Р2; Р4; Р5)12; (Р1; Р4; Р5)18; (Р1; Р3)10}. Таким образом, имея упаковку, легко получить пару списков S и S , отвечающих VBS и HBS.
Метод последовательного уточнения оценок (Sequentative Value Correction, SVC)
Идея генетического алгоритма по аналогии с живой природой состоит в организации эволюционного процесса, целью которого является получение оптимального решения. При этом необходимо идентифицировать законы эволюции так, чтобы быстрее достичь оптимальное или близкое к нему, решение. Основным понятиям и методам конструирования генетических алгоритмов посвящена работа Батищева Д.И. [6]. Базовыми понятиями генетического алгоритма являются ген, хромосома, популяция. Прямоугольники i = \tm идентифицируются как гены. Аллели генов (+/) и (-/) различаются направлением размещения прямоугольника в полосе. В качестве кода упаковки используется приоритетный список ж- і(;г),2(я:),...,/и(;г)} , который идентифицируется как хромосома. Номер / прямоугольника І\ІЇ\ - локус (место) гена в хромосоме. Совокупность хромосом - популяция. В генетическом алгоритме применяются операторы кроссовер, мутация, селекция. Оператор кроссовер (скрещивание) строит соседнее решение, которое добавляется в популяцию, а решение с худшей оценкой удаляется из нее. Если оценка меняется мало или по истечении заданного числа итераций, текущее решение подвергается небольшим случайным изменениям, мутации. . Подробно операторы GTA описаны в работе [44]. Для решения задач 1.5DBP и 2DBP в литературе представлен классический генетический алгоритм, например, в работах D. Liu & H.Teng [88]; Gehring & A.Bortfeld [80].
Генетический блочный алгоритм, (Genetic Block Algorithm, GBA).
Этот алгоритм основан на блочной структуре упаковки. Генами являются блоки упаковки, а хромосомами - блок-структуры, которые не обязательно соответствуют упаковкам. Аллели генов получают путем перестановки элементов внутри блоков. Место блока в псевдо-упаковке определяет локус гена. Кроссовер реализует перестановку элементов в двух блоках. Мутация изменяет блок-структуру, строит новую окрестность решений. Генетический блочный алгоритм для решения 1.5DBP интерпретируется как эволюционный процесс, связанный с изменением блок-структуры и перестановкой элементов в блоках с целью отыскания глобального минимума. Подробно алгоритм описан в работах [44, 34].
Генетический мультиметодный алгоритм (Genetic Multiple Method, GMM). В этом алгоритме в качестве генов используются простые эвристики размещения прямоугольников в незанятой области полосы. Хромосомой является последовательность алгоритмов. Идея мультиметодного генетического алгоритма сформулирована И.П.Норенковым для решения прикладных задач исследования операций [48]. Достоинством алгоритма является его работа без автономного декодера. На каждой итерации после случайного выбора алгоритма размещения осуществляется перебор еще не размещенных прямоугольников. Алгоритм работает быстро для большого количества элементов.
Традиционный генетический алгоритм (Genetic Tradition Algorithm, GTA). Генетический алгоритм (Genetic Algorithm, GA) основан на эволюционных процессах в природе. GA многократно генерирует новые решения Q, применяя операции скрещивания и/или мутации текущих решений Р. Скрещивание генерирует одно или более новых решений, комбинируя два или более текущих решений, а мутация генерирует новое решение путём минимального отклонения от текущего решения.
В качестве представления шаблона упаковки (хромосомы) используется приоритетный список PL: л = 1[тг], 2[ті], ..., т[тг], где і[ти], i=l,m- индексы прямоугольников. Они идентифицируются как гены. Перестановка -последовательность, в которой прямоугольники расположены на полосе в соответствии с определенными правилами. Мы предполагаем, что i[7i] имеет знак, который показывает направление размещения прямоугольника і[п] (проектное решение). Аллели генов (+і[7г]) и (-і[7і]).
Каждая родительская пара создает двух новых потомков с помощью оператора скрещивания (crossover). Операции производятся не над одной хромосомой, а над целым набором хромосом (популяцией). Процесс скрещивания хромосом заключается в следующем:
Пусть 7гг, 7rj - два приоритетных списка, соответствующих паре родителей и 7trnew, 7tjnew - два новых PL, созданные скрещиванием. Сначала выбираются два случайных числа g и q, 1 g, q п. Начиная со случайной позиции g скрещивающий оператор копирует q элементов из тгг в Ttrnew. Потом оставшиеся позиции в 7trnew заполняются другими элементами из щ в той же последовательности, в которой они встречаются в этом списке. Аналогично заполняется
Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов
Приведено описание программного обеспечения для нахождения рационального размещения деталей.
Разработанные и реализованные в программном обеспечении эволюционные методы (1+1)-ЕА с различными декодерами и Genetic Greedy Sub показывают большую эффективностью в решении задачи упаковки при сравнении с известными алгоритмами других авторов. Проведены эксперименты для определения эффективности различных декодеров. Полученные результаты показывают преимущество разработанного блочного «жадного» декодера Greedy Sub среди других декодеров
Проведены эксперименты для определения эффективности генетических алгоритмов и показано что разработанный гибридный генетический алгоритм Genetic Greedy Sub наиболее эффективен в нахождении оптимального решения задач раскроя - упаковки среди алгоритмов других авторов, втом числе и зарубежных:
1) На примерах Бортфельда алгоритм Genetic Greedy Sub показал результат на 4% лучше чем у автора и в среднем на 13% лучше других методов . .
2) Во втором эксперименте в сравнений с другими генетическими методами были получены результаты лучше на 4-5%
3) Во третьем эксперименте, при сравнении с другими наиболее продвинутыми методами, разработанными на кафедре.ВМиК УГАТУ на классе сложных задач (триплеты) получены результаты лучше в среднем на 5%
4) В четвертом эксперименте при решении задач упаковки на листы были получены отклонения от нижней границы лучше в среднем на 1%
Задачи прямоугольной упаковки представляет собой важный раздел задач дискретной оптимизации и исследования операций. От качества полученного решения зависит: эффективность использования ресурсов продуктивность использования оборудования время проектирования и производительность труда
Задачи раскроя - упаковки также представляют большой интерес для производства. В условиях массового производства изделий даже незначительная экономия сырья на одно изделие дает после приведения к годовому объему продукции многие тонны сэкономленного материала.
В последнее время большое распространение получили генетические алгоритмы решения задач прямоугольного раскроя. В данной работе был разработан и усовершенствован традиционный генетический алгоритм, в результате был получен гибридный эвристический метод, главной особенностью которого является новый эффективный блочный декодер.
Основные результаты работы и выводы
1. Представлена обобщенная модель задач прямоугольной упаковки, которая позволила реализовать новые эффективные методы решения задачи прямоугольного раскроя и упаковки.
2. Модифицированы однопроходные эвристические методы конструирования упаковок следующий подходящий, NF; первый подходящий FF; лучший подходящий BF с использованием блок-структур, и на базе этих алгоритмов разработаны высокопроизводительные варианты метода замещения, обеспечивающие эффективное конструирование рациональных упаковок.
3. Разработан новый декодер «жадного» замещения Greedy Sub на базе блочной структуры и его модификации. Впервые в работе декодера стратегия жадности используется в разных направлениях, используя несколько приоритетных списков прямоугольников. Его эффективность превосходит аналогичные показатели других алгоритмов.
4. Разработан «наивный» эволюционный алгоритм (1+1)-ЕА с различными операторами мутации и декодерами. Показана его высокая качественная и временная эффективность с декодером «первый подходящий» и «наивным» оператором мутации,
5. Разработан генетический алгоритм на базе блочных структур для решения задачи прямоугольной упаковки полубесконечной полосы и на листы. Это позволило осуществить гибридизацию алгоритма с другими эвристиками блочной структуры и выбрать наиболее подходящую из них - жадный декодер замещения.
6. Создано программное обеспечение, реализующее разработанные алгоритмы и декодеры и предназначенное для проведения вычислительных экспериментов.
7. Проведены численные эксперименты. Результаты (коэффициенты упаковки и временные показатели) разработанных алгоритмов, в сравнении с другими методами, оказались лучше на 5-10% на различных классах задач. Эти результаты показывают преимущество разработанного декодера и генетического алгоритма и позволяют сделать заключение об эффективности предложенных методов для решения задач ортогональной упаковки в полубесконечную полосу и на листы.
