Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Диссертация: Проектирование размещения геометрических объектов на многосвязном ортогональном полигоне
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Использованные обозначения
  • Глава 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. Разработана подсистема автоматизации проектирования инвариантных размещений объектов, реализующая предложенные алгоритмы. Она позволяет решать задачи размещения прямоугольных предметов в полосу, прямоугольную область и многосвязный ортогональный полигон.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 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). С. 106 116.
  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. 533 538.
  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. 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., Wascher 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., Wascher 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. 212 228.
  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
Заполнить форму текущей работой

На отлично!