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

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

Автор: Вяткина, Кира Вадимовна

Шифр специальности: 05.13.17

Научная степень: Кандидатская

Год защиты: 2004

Место защиты: Санкт-Петербург

Количество страниц: 75 с. ил.

Артикул: 2627864

Автор: Вяткина, Кира Вадимовна

Стоимость: 250 руб.

Задачи раскроя, упаковки и теории расписаний . Задачи планирования при ограниченных ресурсах . Размещения и графы. Граф размещения на плоскости. Граф многомерного размещения. Модели вычислений. Размещения, содержащие вырожденные прямоугольники . Нижняя оценка сложности. Построение разделяющей последовательности разрезов . Трехмерный случай . Алгоритм построения графа размещения. Доказательство оптимальности. Обобщение для гофров . Задача региональною поиска. Два метода построения графа размещения. Построение. Нижняя оценка сложности. Обоснование корректности . Обработка вырожденных случаев. Минимальный и максимальный номер прямоугольника . Заключение
ния класс размещений. Исследованию их свойств и возникающих в применении к ним задач было посвящено немало работ. В качестве примеров работ по тематике гильотинного раскроя, имеющихся в отечественной литературе, можно привести статьи Э. А. Мухачсвой , 3, И. В. Романовского , С. Ю. Дремина и В. А. Залгаллера , а в зарубежной статьи П. К. Агравала Р.


Классификация задач раскроя. Классификация задач упаковки . Задачи планирования при ограниченных ресурсах . Модели вычислений. Размещения, содержащие вырожденные прямоугольники . Построение разделяющей последовательности разрезов . Обобщение для гофров . Плоский случай. Алгоритм построения графа размещения. Доказательство оптимальности. Случай мерного пространства . Задача региональною поиска. Два метода построения графа размещения. Построение. Нижняя оценка сложности. Обоснование корректности . Обработка вырожденных случаев. Минимальный и максимальный номер прямоугольника . Множество Я невырожденных прямоугольников на плоскости, стороны которых параллельны осям координат, называется размещением, если прямоугольники из Я попарно не перекрываются. Размещения естественным образом возникают в задачах прямоугольного раскроя, ортогональной упаковки, теории расписаний и т. Понятие размещения легко обобщается на пространства высших размерностей. В данной диссертационной работе рассматривается ряд задач, возникающих в применении к размещениям, а именно задача о разделении множества прямоугольников посредством угловых разрезов, задача о построении графа размещения, задача о построении наклонной нумерации, задача об упаковке в полосу прямоугольников с заданной наклонной нумерацией, а также обобщение этих задач па случай мерного пространства. Задача раскроя является одной из классических задач комбинаторной оптимизации. Суть се постановки заключается в том, чтобы вырезать требуемое количество деталей из имеющегося в нашем распоряжении листа или нескольких листов сырьевого материала, минимизируя при этом потери. Данная задача допускает естественное обобщение на случай пространств высших размерностей. В пространстве размерности с 3 соответствующую задачу называют обычно задачей об упаковке рюкзака. Сразу отметим, что некоторые задачи теории расписаний могут быть переформулированы в терминах задач многомерной упаковки. Впервые задача оптимального раскроя была сформулирована Л. В. Канторовичем в г. Очень важное значение для развития данной тематики имела опубликованная в 1 г. П. С. Гилмора Р. С. i и Р. Е. Гомори . Е. , в которой был предложен подход к решению задачи раскроя, основанный на методе линейного программирования. Практическое значение задач раскроя и упаковки чрезвычайно велико широта спектра их применений может быть наглядно проиллюстрирована нижеследующим списком, приведенным А. Задачу раскроя, очевидно, можно рассматривать как частный случай задачи упаковки в пространстве размерности 2. Таким образом, классификация задач упаковки, которой будет посвящен следующий параграф, может быть использована также и для классификации задач раскроя. В данном же разделе мы остановимся более подробно на классификации задач прямоугольного раскроя, в которых предполагается, что все объекты, а также лист сырьевого материала, имеют форму прямоугольников, и что стороны каждого прямоугольника параллельны осям координат. Задачи прямоугольного раскроя принято классифицировать в соответствии с типом результирующего размещения. При этом различают два класса размещений гильотинные и пегилъотиппые то есть, все остальные. Ггигьотинпый рчзрез на плоскости осуществляется вертикальной или горизонтальной прямой. Размещение прямоугольников называется гильотинным. Рис. Пример гильотиипого размещения б пример негильотинного размещения.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.210, запросов: 244