Дипломы, курсовые, рефераты, контрольные...
Срочная помощь в учёбе

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

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

Разработаны методы и алгоритмы, позволяющие учитывать ряд технологических ограничений: припуски на резы, окантовку рулона или листов, дефекты раскраиваемого материала, реализованные в виде программного обеспечения. Программное обеспечение в составе системы 20Я-СиТ автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования… Читать ещё >

Содержание

  • 1. Обзор моделей и методов решения задач раскроя
    • 1. 1. Автоматизация проектирования и технологической подготовки производства
    • 1. 2. Классификация задач раскроя
      • 1. 2. 2. Постановка задачи прямоугольного раскроя
      • 1. 1. 1. Постановка задачи прямоугольного раскроя с дефектами материала
    • 1. 3. Математическая модель задачи двумерного раскроя
    • 1. 4. Обзор методов решения задачи раскроя
      • 1. 4. 1. Точные методы решения задач раскроя
      • 1. 4. 2. Приближенные и эвристические методы
      • 1. 4. 3. Вероятностные методы локального поиска оптимума
      • 1. 4. 4. Использование декодеров
      • 1. 4. 5. Применение методов решения задач раскроя-упаковки в автоматизированных системах раскроя-упаковки
    • 1. 5. Выводы
  • 2. Методы решения задач прямоугольного раскроя
    • 2. 1. Метод имитации отжига
    • 2. 2. Метод «холодного» отжига
    • 2. 3. Декодер «вставки»
    • 2. 4. Применение метода (1+1)-ЕА к задаче прямоугольного раскроя
    • 2. 5. Метод «поиск с запретами» с декодером «вставки»
    • 2. 6. Работа декодера «вставки» с учетом обхода дефектных областей материала
    • 2. 7. Выводы
  • 3. Автоматизированная система двумерного прямоугольного раскроя 2БК-СиТ
    • 3. 1. Современное состояние раскройно-заготовительного производства
    • 3. 2. Структура САПР раскроя-упаковки
    • 3. 3. Программа-оболочка 2БК-СиТ, ее взаимодействие с расчетными модулями
    • 3. 4. Интеграция системы 2БК-С1Л в стороннюю систему автоматизированного проектирования
    • 3. 5. Алгоритмы, реализованные в системе 2БК-СиТ
    • 3. 6. Выводы
  • 4. Численный эксперимент
    • 4. 1. Результаты численного эксперимента
    • 4. 2. Выводы

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

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

Актуальность темы

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

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

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

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

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

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

Цель работы.

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

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

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

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

4. Разработать оптимизационнное ядро САПР раскроя листового и рулонного материала на основе предложенных методов и алгоритмов в виде прикладного программного обеспечения.

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

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

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

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

1. Декодер «вставки», разработанный для реализации технологических ограничений и обхода дефектных областей раскраиваемого материала.

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

3. Программная реализация разработанных методов в составе системы прямоугольного раскроя 2БК-СиТ.

4. Результаты численных экспериментов и рекомендации по использованию предлагаемых алгоритмов.

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

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

2. Предложен метод «холодного» отжига, основанный на принципах метаэвристики «имитация отжига», который в отличие от последней:

— работает с постоянным параметром температуры;

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

— использует новые способы расчета элементов вектора достижимости.

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

Практическая значимость работы.

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

Разработанное программное обеспечение, реализующее методы и алгоритмы расчета прямоугольного раскроя листового и рулонного материала с учетом технологических ограничений, в качестве подсистемы для решения задач прямоугольного раскроя интегрировано в известную систему автоматизированного проектирования «Сириус», внедренную на следующих предприятиях: ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), ЗАО «Курганстальмост» (г. Курган), ОАО «Мечел» (г. Челябинск). Применение разработанного программного обеспечения позволило повысить эффективность использования материала на 5−8%.

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

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

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

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

1. Международной уфимской зимней школе-конференции по математике (Уфа, 2005);

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

3. Зимней школе для аспирантов и молодых ученых (Уфа, 2006, 2007);

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

Публикации. По теме диссертации опубликовано 7 работ: 3 статьи, в том числе 1 в рецензируемом журнале из списка ВАК, 3 трудов конференций, выполненных по теме диссертации при непосредственном участии автора, и один акт о регистрации программы.

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

Диссертация состоит из введения, четырех глав, выводов, списка литературы, и приложений. Работа изложена на 130 страницах машинописного текста, кроме того, содержит 37 рисунков. Библиографический список включает 123 наименования и занимает 13 страниц.

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

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

Реализован алгоритм (1+1)-ЕА как частный случай алгоритма «имитация отжига» с нулевой температурой.

2. Разработан новый метод проектирования прямоугольного раскроядекодер РЦР, учитывающий дефекты раскройного материала. Этот декодер используется в составе метаэвристик (1+1)-ЕА, «холодного» отжига и «поиска с запретами». Они включены в автоматизированную систему расчета прямоугольного раскроя 20Я-Си1. Использование нового декодера позволяет повысить качество решения по сравнению с известными декодерами на 3−5%.

3. Разработаны методы и алгоритмы, позволяющие учитывать ряд технологических ограничений: припуски на резы, окантовку рулона или листов, дефекты раскраиваемого материала, реализованные в виде программного обеспечения. Программное обеспечение в составе системы 20Я-СиТ автоматизированного рабочего места технолога раскройно-заготовительного производства позволяет повысить коэффициент использования материала в среднем на 5−8% по сравнению с простыми эвристиками и значительно сократить время проектирования.

4. Разработано оптимизационное ядро САПР в виде программного комплекса проектирования прямоугольного раскроя листового и рулонного материала с учетом дефектных областей на базе модифицированных эволюционных методов в рамках системы САПР раскройно-заготовительного производства. Результаты диссертационной работы приняты к внедрению в виде алгоритмов и программного обеспечения на ООО «Центр автоматизации проектирования и высоких технологий» (г. Екатеринбург), на предприятии, производящем мебель.

5. Исследована эффективность предложенных методов на базе численного эксперимента с использованием системы двумерного прямоугольного раскроя 2Б11-СиТ. При раскрое полосы наблюдается заметное улучшение качества решения задачи раскроя на некоторых классах задач.

Заключение

.

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

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

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

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

Показать весь текст

Список литературы

  1. Г. В., Березнев В. А., Брежнева O.A. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 1990. С. 145 154.
  2. Ф.В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978.- С. 72.
  3. Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. -М.: Машиностроение. 1982. 85с.
  4. Е.В. Задача оценки сложности раскроя в условиях автоматизированного управления производством // Принятие решений в условиях неопределенности: Межвуз. науч. сб. -Уфа: УГАТУ, 2000. -С.136−141.
  5. Е.В. Модель сменной загрузки раскройного оборудования // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2002.-С. 184−190.
  6. Д.Ю. Генетические алгоритмы решения экстремальных задач // учебное пособие под ред. Я. Е. Львовича. Воронеж: Воронежский гос. техн. ун-т- Нижегородский ун-т. 1995. 96с.
  7. П.А. Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации: диссертация кандидата физ.-мат. наук: 05.13.18. Омск, 2005.109 с.
  8. В.А., Яковлева М. А. О решении задач оптимального раскроя линейных материалов на ЭВМ // Математические методы в техникоэкономических расчетах: Материалы научного совещания, т. IV. М.: АН СССР. 1961. С. 83−87.
  9. В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы // С. Петербург: Государственный университет. 2001.120с.
  10. А.Ф., Сиразетдинова Т. Ю. Задача прямоугольного гильотинного раскроя на базе метаэвристики «Имитация отжига» // Проблемы оптимизации и экономические приложения, III Всероссийская конф.: матер, конф. Омск, 2006. С. 55−62.
  11. А.Ф., Сиразетдинова Т. Ю. Решение задачи прямоугольного гильотинного раскроя с применением процедур имитации отжига // Социально-экономические и технические системы. Электронный ресурс. Набережные Челны, № 9 2006 (http://kampi.ru/sets). 7 с.
  12. М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя // Информационные технологии. 2000. № 5. С.37−42.
  13. В.Я., Липовецкий А. И., Петунин A.A. Автоматизация проектирования раскройных карт в условиях индивидуального производства // Кузнечно-штамповочное производство, 1982.-N3 -С.26−27.
  14. М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи // М. Мир. 416с.
  15. E.H., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения .// Дискретный анализ и исследование операций. 1999. Серия 2. 6. № 1. С. 12−32. Работа поддержана РФФИ: проекты 99−01−601,98−07−90 259.
  16. Г. К., Бендерева Э. И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М. Машиностроение, 1981.-455 с.
  17. .С., Бритарев К. Ф. Арцишевский Ю.Ю. Система автоматизированного проектирования на ЭВМ процессов холодной листовой штамповки. -М.: Кузнечно-пггамповочное производство. 1979. № 6. С. 13−14.
  18. А.И., Сиразетдинов Т. М. Метод поиска с запретами для решения задач прямоугольного гильотинного раскроя // Дискретный анализ и исследование операций: сб. трудов всерос. конф. Новосибирск: НГТУ, 2002. С. 230.
  19. А.И., Сиразетдинов Т. М. Рекурсивный метод для решения задач гильотинного прямоугольного раскроя // Математическое моделирование в решении научных и технических задач. Уфа: Технология, 2001. С. 18−23.
  20. Жукова (Сиразетдинова) Т. Ю. Применение метода «моделирования отжига» для решения задачи раскроя // Принятие решений в условиях неопределенности: сб. статей. Уфа: УГАТУ. 2003. С. 45−51.
  21. JI.B., Залгаллер В. А. Рациональный раскрой промышленных материалов // Новосибирск: Наука СО. 1971.299с.
  22. JI.B., Заллгаллер В. А. Расчет рационального раскроя материалов // Лениздат. 1951.
  23. C.B. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, № 5, с. 139−141.
  24. Н.А. САПР одежды: исторический экскурс и обзор существующих систем // Текстильная промышленность. 2003. № 5. С.61−62. № 6. С. 63−65.
  25. Ю., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // Иркутск: XII Байкальская международная конференция. 2001. С.22−27. Работа поддержана РФФИ: проект 01−01−510.
  26. А.И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. Минск. 1985. С. 80−87.
  27. .А., Батозский В. И. и др. Автоматизация раскроя тонколистового проката. -М.: Кузнечно-штамповочное производство. 1978. № 6. С. 30−33.
  28. В.В. Информационная система раскроя плоских геометрических объектов сложной формы: основные проблемы и подходы к их решению // Вестник УГАТУ. -Уфа, Изд. УГАТУ, 2001. С. 105−113.
  29. А.С., Куреленков С. Х., Смагин М. А., Ширгазин P.P. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. 2002. № 10. С. 26−31. Работа поддержана РФФИ, проект 01−01−510.
  30. A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001 № 3. С. 27−32.
  31. Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката // Оптимизация: Сб. науч. трудов СО АН СССР. 1978. Вып. 22. С. 83−93.
  32. Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М. Машиностроение. 1984. 176с.
  33. Э.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. Вып. 6. С. 43−115.
  34. Э. А. Валеева А.Ф. Метод динамического перебора в задаче двумерной упаковки // Информационные технологии. 2000. № 5. С. 3037. Работа поддержана РФФИ: проект 99−01−947.
  35. Э.А., Валеева А. Ф., Картак В. М., Мухачева A.C. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур// Информационные технологии. Приложение. 2004. № 5.31 с.
  36. Э.А., Верхотуров М. А., Мартынов В. В. Модели и методы расчета раскроя-упаковки геометрических объектов // Уфа. УГАТУ. 1998.216 с.
  37. Э.А., Ермаченко А. И., Сиразетдинов Т. М., Усманова А. Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. № 6. С. 25−31. Работа подцержана РФФИ: проект 99−01−947,01−01−510.
  38. Э.А., Ермаченко А. И., Сиразетдинов Т. М., Жукова (Сиразетдинова) Т. Ю. Комплекс алгоритмов и программ расчета гильотинного раскроя // Информационные технологии. 2004. № 8. С. 18−25.
  39. Э.А., Картак В. М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. № 9. С. 15−22. Работа поддержана РФФИ: проект 99−01−947.
  40. Э.А., Мухачева A.C. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000 № 4. С. 30−36. Работа подцержана РФФИ, проект 99−01−947.
  41. Э.А., Мухачева A.C., Белов Г. Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя Информационные технологии. 2000 № 2. С. 11−17. Работа поддержана РФФИ: проект 99−01−947.
  42. Э.А., Рубинштейн Г. Ш. Математическое программирование // Новосибирск. Наука СО. 1987.272 с.
  43. И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. № 1. С. 2−7.
  44. A.A. Интегрированная САПР «Сириус» для автоматизации раскройно-заготовительного производства // С. Петербург: ОПТИМ-2001. С.123−126.
  45. И.В. Алгоритмы решения экстремальных задач // М.: Наука. 1977. 170с.
  46. И.В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. 1969. № 1. С. 102−104.
  47. И.В., Христова Н. П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). С. 12 001 209.
  48. А.С. Задачи двумерной прямоугольной упаковки в контейнеры с запрещенными областями // Магистерская диссертация, 2006. 120с.
  49. А. Вероятностные жадные эвристики для задачи упаковки в контейнеры // С. Петербург: ОПТИМ-2001. С. 141−146. Работа поддержана РФФИ: проекты 99−01−947,01−01−510.
  50. В. Моделирование и оценка качества проектных решений в системах сквозного проектирования корпусных изделий из листового материала//Информационные технологии. 2000. № 5. С. 18−25.
  51. В.Д. Целочисленная аппроксимация и оптимальное группирование геометрических объектов в задачах размещения // Научный вестник НГТУ. № 1(8). 2000. С. 37−46.
  52. Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении. М. Машиностроение, 1988.-648с.
  53. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996. P. 10−15.
  54. Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. 8(1). P.27−33.
  55. Baesley J.E. http://mscmga.ms.ic.ac.-uk/info.html.
  56. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions // SIAM J. Comput. 9 (1980) P.846−855.
  57. 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.
  58. Bischoff E., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1995. P. 84.
  59. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem // Quaterly Journal of the Belgian, French and Italian Operations Research Societies 2002. P. 45−51.
  60. 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. P. 34−35.
  61. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing // CS270 Project Report, Spring 1999. P.56−62.
  62. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins // SIAM J. Algebraic Discrete Meth. 3 (1982) P. 66−76.
  63. Coffman E., Garey M., Jchonson D. Approximation algorithms for bin-packing-an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P. eds) Berlin etal. 1984. P. 89−94.
  64. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life. 1999. Vol.5. No.3. pp. 137−172.
  65. Dorigo M., Gambardella L.M. Ant Colonies for the traveling salesman problem// IRIDIA, Technical Report 1996. P. 3.
  66. 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.
  67. Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing // Annotated Bibliographies in Combinatorial Optimization, edited by M. DeH'Amico, F. MafFioli and S.Martello. John Wiley&Sons. 1997. P.393−412.
  68. Dykhoff H. A typology of cutting and packing problems // Evropean Journal of Operational research. 1990. Vol. 44. P. 145−159.
  69. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990.44(2).
  70. 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. P. 251−259.
  71. Folkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing // Evolutionary Algorithms in Management Applications. Berlin. 1995. P. 167−182.
  72. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998.2(1). P. 5−30.,
  73. H., Wascher G. (1997) Simulated annealing for order spread minimization sequencing cutting patterns // European Journal of Operational Research. 1998.110. P. 272−281.
  74. Garey M.R., Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness // San-Francisco, Freemau. 1979. P. 321−338.
  75. 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.
  76. Gilmore P., Gomory R. Multistage cutting stock problem of two and more dimensions// Operat.Res. 1965.13(1). P.94−120.
  77. Gilmore P., Gomory R. The theory and computation of knapsack functions. //Oper. Res. 1966. V.14. P.1045−1075.
  78. Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research 9(1961), pp. 849−859.
  79. Glover F. Tabu search and adaptive memory programming advances, applications and challenges // Interfaces in Computer Science and Operations Research. 1996. P. 1−75.
  80. Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. // EJOR 128.2001. P. 34−57.
  81. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle Packing Problem With General Spatial Costs // MIC'2001 4th Metaheuristics International conference. P. 471−476.
  82. Jhonson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. V. 3. N4.1974. P.299−325.
  83. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing. Science. v220 (1983), pp 671−680.
  84. Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001, Porto, 2001. P. 619−624. Работа поддержана РФФИ: проект 01−01−510.
  85. Lirov Y., edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modelling. 1995.16(1).
  86. 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.
  87. 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.
  88. Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems. // Discrete Applied Mathematics 123.2002. P. 379 -396.
  89. Loris Faina. An application of simulated annealing to the cutting stock problem// European Journal of Operational Research. 1999.114. P. 532−556.
  90. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. // INFOR. 1994. 32(3).
  91. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems // INFOR. 1994. 32(4).
  92. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. // YOHN WILEY&SONS. Chichester. 1990.
  93. Martynov V. Geometrical objects regular placement onto a stock sheet or strip // Pesquisa Operacional, Vol. 19, No.2. SP — BRAZIL, Institute Nacional de Pesquisas Espaciais, dezembro de 1999. P.211−222.
  94. 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.
  95. Morabito R, Arenales M. An AND/OR graph approach to the container loading problem // International Transactions in Operational Research 1 (1994) 5973.
  96. Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems)/ The International Scientific Collection. 1997. Ufa. Russia.
  97. Mukhacheva Е.А., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V. 3. N4. P. 463−476.
  98. 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.
  99. 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. Pp.829−832.
  100. Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res. Proc. 1991, Springer-Verlag, Berlin Heidelberg, 439−444.
  101. Scheithauer G., Terno Y. Muller A., Belov G. Solveng one-dimensional cutting stock problems exactly with a cutting plane algorithm. // Journal of the Operational Research Society. 2001. 52. H. 1390−1401.
  102. 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.
  103. Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa 1997. P. 261−270.
  104. Stutzle T., Hoos H.H. MAX-MIN Ant System // Preprint submitted to Elsiever Science, 1999.
  105. Takahashi T. A New Encoding Scheme for Rectangle Packing Problem // Graduate School of Science and Technology. Niigata University. IEEE. 2000. P.175−178.
  106. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.215p.
  107. 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.
  108. Wang P., Valenzeva L. Data set generation for rectangular placement problems // European Journal of Operational Research. 2001.134(2). P.378−391.
  109. Wang P., Wascher G., edit, {it Special issue: Cutting Packing Problems} Europen Journal of Operational research. 141 (2002).
  110. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999.19(2).
Заполнить форму текущей работой

Заказал и сдал!