Оптимизация процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограничений тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Файзрахманов, Ришат Илшатович

• Файзрахманов, Ришат Илшатович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Файзрахманов, Ришат Илшатович

Оглавление.

Введение.

1 Анализ проблемы процесса раскроя промышленного материала по критерию минимизации потерь с учетом технологических ограничений.

1.1 Актуальность исследуемой проблемы.

1.2 Анализ существующих технологий раскройно-заготовительных работ

1.3 Классификация и анализ методов решения задач раскроя.

1.4 Цель и задачи исследования.

Выводы по первой главе.

2 Модели и методы решения задач раскроя промышленного материала при наличии технологических ограничений и методы ее решения.

2.1 Математические модели задач раскроя.

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

2.3 Пример работы процедуры размещения.

Выводы по второй главе.

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

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

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

3.3 Пример работы алгоритма муравьиной колонии, основанной на популяции

Выводы по третьей главе.

Глава 4. Оценка эффективности алгоритмов и методов оптимизации процесса раскроя при наличии технологических ограничений на базе численных экспериментов.

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

4.2. Определение влияния параметров алгоритма на качество решений.

4.3 Исследование эффективности предложенных методов и алгоритмов.

Выводы по четвертой главе.

Введение диссертации (часть автореферата) на тему «Оптимизация процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограничений»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна результатов диссертационного исследования:

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

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

3. Модифицированный алгоритм муравьиной колонии, основанный на процедурах генетического алгоритма и осуществляющий обмен информацией о построенных картах раскроя, для решения задачи раскроя листового и рулонного материалов на заготовки различных геометрических форм при наличии технологических ограничений характерных для реального производства, который использует: a) интервальное ограничение для параметра, показывающего частоту выбора фрагмента решения во избежания ранней стагнации; b) принцип «элитного муравья» для сохранения лучшего решения.

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

Практическую значимость имеют следующие результаты.

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

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

Апробирование результатов в виде методики повышения эффективности управления раскроем листового промышленного материала при производстве заготовок и рабочего прототипа программного обеспечения для оптимизации процесса раскроя на этапе технологической подготовки производства осуществлено на предприятии ХТЦ УАИ, Уфа. Применение разработанного программного обеспечения позволяет повысить эффективность использования материала на 6-8%.

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

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

Работа выполнялась при частичной поддержке грантов Российского фонда фундаментальных исследований (РФФИ), проекты 09-07-09254-мобз и 10-07-91 ЗЗО-ННиО-а, ИФ ВК 03 10 ХК.

Апробация работы и публикации

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

1. IV Республиканская студенческая научно-практическая конференция «Научное и экологическое обеспечение современных технологий», УГАЭС, Уфа, 2007;

2. Международная конференция "Компьютерные науки и информационные технологии" (С81Т), Уфа, 2007-2010;

3. Зимняя школа для аспирантов и молодых ученых, Уфа, 2008-2010;

4. I Всероссийская молодежная научная конференция "Молодежь и наука на севере", Сыктывкар, 2008;

5. IV Всероссийская конференция "Проблемы оптимизации и экономические приложения", Омск, 2009;

6. Российская конференция "Дискретная оптимизация и исследование операций"' (00011-2010), Республика Алтай, 2010;

7. Международная конференция «Инновационные информационные технологии: Теория и Практика», Дрезден, 2010.

Публикации. По теме диссертации опубликовано 13 работ выполненных по теме диссертации при непосредственном участии автора: 9 статей, в том 8 числе 2 в рецензируемом журнале ВАК и 7 статей в сборниках трудов конференции, 4 тезиса в сборниках конференций.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 139 страницах машинописного текста, кроме того содержит 61 рисунок и 13 таблиц. Библиографический список включает 112 наименования и занимает 9 страниц.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Файзрахманов, Ришат Илшатович

Выводы по четвертой главе

1. Разработано программное обеспечение для решения задачи оптимизации процесса раскроя промышленных материалов по критерию минимума материальных потерь. В программном обеспечении реализованы: a) метод размещение круглых и прямоугольных предметов в заданную область АВЬР+\ b) предложенный алгоритм АСОЭА для решения поставленной задачи.

2. Проведенный численный эксперимент по оценке влияние параметров алгоритма на целевую функцию показал: a) не существует оптимальных параметров для всех классов задач. Выбор параметров зависит от размерности задачи, типа раскраиваемых заготовок и величины разброса размеров заготовок; b) для задач малой размерности и с большим разбросом размеров заготовок существенное влияние на качество получаемого решения оказывает коэффициент влияния эвристической информации. В этом случае рекомендуется принимать значение коэффициента влияния эвристической информации в 2 раза больше коэффициента влияния уровня феромона; I c) для задач большой размерности, в которых разброс размеров заготовок относительно мал, существенное влияние на качество получаемого решения оказывает коэффициент влияния уровня феромона. В этом случае рекомендуется принимать значение коэффициента влияния уровня феромона больше коэффициента влияния уровня эвристической информации.

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

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

5. Проведенные эксперименты на реальных данных показали, что разработанные методы и алгоритмы позволяют повысить эффективность использования материала на 6-8%.

Заключение

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

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

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

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

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

5. Разработан рабочий вариант программного обеспечения на основе предложенных методов, алгоритмов и математического обеспечения оптимизации процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограничений. Анализ результатов численных экспериментов показал их эффективность. На его основе было выявлено, что разработанные методы и алгоритмы позволяют повысить эффективность использования материала на 6-8%. Для пяти примеров задачи размещения круглых и прямоугольных предметов в полубесконечную область получены новые улучшенные значения целевой функции.

Список литературы диссертационного исследования кандидат технических наук Файзрахманов, Ришат Илшатович, 2011 год

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

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

3. Валеева А.Ф., Аглиуллин М.Н. Алгоритм муравьиной колонии для задач двухмерной упаковки: результаты вычислительного эксперимента II Труды XIII Байкальской международной школы-семинара. Иркутск, Байкал. -2005. - Т.1. - С. 429-434.

4. Валеева А.Ф., Файзрахманов Р.И. Применение конструктивной метаэвристики «Муравьиная колония» к задаче гильотинного прямоугольногораскроя II Вестник Башкирского государственного университета. Уфа:Бгу -2007.-Т. 12, №3,-с. 12-15.

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

6. Гамберг В.Я., Липовецкий А.И., Петунин A.A. Автоматизация проектирования раскройных карт в условиях индивидуального производства II Кузнечно-штамповочное производство. — 1982. — №3 — с.26-27.

7. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи.- М.: Мир. 1982. - 416 с.

8. Ермаченко А.И., Сиразетдинов Т.М. Метод поиска с запретами для решения задач прямоугольного гильотинного раскроя. II Дискретный анализ и исследование операций: сб. трудов всерос. конф. Новосибирск: НГТУ. - 2002. -с. 230.

9. Канторович JI.B., Заллгаллер В.А. Расчет рационального раскроя материалов — С.-П.: Лениздат. — 1951.

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

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

12. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане II Автоматика и телемеханика. № 3.-2004.-с. 80-88.

13. Лореш М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. Омск: ОмГУ. - 2006. — 19 с.

14. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки II Дискретный анализ и исследование операций': Материалы российской конференции. Новосибирск. -2002г.-с. 80-87.

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

16. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование II Новосибирск: Наука СО. 1987. - 272 с.

17. Мухачева Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката II Оптимизация: Сб. науч. трудов СО АН СССР. 1978. - Вып. 22. - с. 83-93.

18. Мухачева Э.А., Валеева А.Ф., Картак В.М., Мухачева A.C. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур/1 Информационные технологии. Приложение. 2004. - №5. - 31 с.

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

20. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Усманова А.Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя II Информационные технологии. — 2001. — №6. — С. 25-31. Работа поддержана РФФИ: проект 99-01-00947, 01-01-00510.

21. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя II Информационные технологии. 2000. - №9. с. - 15-22. Работа поддержана РФФИ: проект 99-01-00947.

22. Мухачева Э.А., Мухачева A.C., Белов Г.Н. Метод последовательногоуточнения оценок: алгоритм и численный эксперимент для задачи одномерного132раскроя // Информационные технологии. 2000 - №2. — с. - 11-17. Работа поддержана РФФИ: проект 99-01-00947.

23. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. И Информационные технологии. — 1999г. — №1, С. 27.

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

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

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

27. Руднев A.C. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу II Дискретный анализ и исследование операций.-2009.-Т. 16 -No. 4.-е. 61 -86.

28. Руднев A.C. Задачи двумерной прямоугольной упаковки в контейнеры с запрещенными областями II Магистерская диссертация. — 2006. — 120с.

29. Скобцов Ю. А. К вопросу о применении метаэвристик в решении задач рационального раскроя и упаковки II Вюник Хмельницького нацюнального ушверситету. — 2008. — Т. 1, № 4. — с. 205—217.

30. Усманова А. Вероятностные жадные эвристики для задачи упаковки в контейнеры. II С.Петербург: ОПТИМ 2001. - с. 141-146. Работа поддержана РФФИ: проекты 99-01-00947, 01-01-00510.

31. Файзрахманов Р.И. Конструктивный вероятностный алгоритм для размещения кругов и прямоугольников II Вестник Уфимского государственного авиационного технического университета. Уфа: УГАТУ. — 2010. — Т. 14, №4 (39).-с. 132-138.

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

33. Aurts E., Lenstra J., edit. Local Search in Combinatorial Optimization. II John Wiley&Sons. 1996. - p. 10-15.

34. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions II SIAM J. Comput. 9 - 1980 - P.846-855.

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

36. Bischoff E., Wascher G., edit. Special issue: Cutting and Packing II European Journal of Operational Research. 1995. - p. 84.

37. Bonabeau E., Dorigo M., Theraulaz G. From Natural to Artificial Swarm Intelligence II Oxford University Press. 1999.

38. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem II Quaterly Journal of the Belgian, French and Italian Operations Research Societies 2002.-p. 45-51.

39. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison II ACM Computing Surveys. 35(3) -2003 — p. 268-308.

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

41. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins II SIAM J. Algebraic Discrete Meth. 3 (1982) - p. 66-76.134

42. Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis, Dipartimento di Electrónica, Politécnico di Milano, IT. 1992 (in Italian).

43. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization II Artificial Life, 1999. V.5(2). - P.137-172.

44. Dorigo M., Gambardella L.M. Ant Colonies for the traveling salesman problem. II IRIDIA, Technical Report 1996. P. 3.

45. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem II IEEE Transactions on Evolutionary Computation, 1(1). 1997. - p. 53-66.

46. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process //Report1 TR-91-016. Milan: Politécnico di Milano, 1991.

47. Dorigo M., Maniezzo V., Colorny A. The Ant system: Optimization by a colony of cooperating agents II IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 1996. P. 29-41.

48. Dorigo M., Stutzle T. Ant Colony Optimization //MIT Press. 2004.

49. Dykhoff H. A typology of cutting and packing problems I I Evropean Journal of Operational research. 1990. Vol. 44. - p. 145-159.

50. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing II European Journal of Operational Research. 1990. - 44(2).

51. Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing// Annotated Bibliographies in Combinatorial Optimization, edited by M.Dell'Amico, F.Maffioli and S.Martello. John Wiley&Sons. 1997. - p.393-412.

52. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing II Journal of Heuristics. 1998. - 2(1). - p. 5-30.

53. 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.

54. Forster H., Wascher G. (1997) Simulated annealing for order spread minimization sequencing cutting patterns. II European Journal of Operational Research. 1998. - №110. - p. 272-281.

55. Garey M.R., Johnson D.S. Computers and Intractability: A guide to the Theory of NP-Completeness II San-Francisco, Freemau. 1979. - p. 321-338.

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

57. Gilmore P., Gomory R. The theory and computation of knapsack functions.// Oper, Res. 1966. -V. 14. - p. 1045-1075.

58. Gilmore P.C., Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem II Operations Research 9(1961). — p. 849-859.

59. Glover F. Tabu search and adaptive memory programming advances, applications and challenges. II Interfaces in Computer Science and Operations Research. 1996. - p. 1-75.

60. Hifi M., M'Hallah R. A dynamic adaptive local search algorithm for the circular packing problem II European Journal of Operational Research №183(2007) -p. 1280-1294.

61. Hifi M., M'Hallah R. Approximate algorithms for constrained circular cutting problems II Computers & Opertations Research- 31(2004) p. 675-694.

62. Hifi M., M'Hallah R. A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes. //International Transaction in Operational Research. 2003. - №10. - p. 195-216

63. Hopper E., Turtun B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem //EJOR. — 2001. — №128. P. 34-57.136

64. Huang W. Q., Li Y., Aked H., Li. C. M. Greedy algorithms for packing unequal circles into a rectangular container II European Journal of Operational Research. 2005. - №56. - P.539-548.

65. 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

66. Kallrath. Cutting circles and polygons from area-minimizing rectangles. //Journal of Global Optimization. 2009. - №43. - P. 299-328.

67. Lirov Y., edit. Special issue: Geometric Resource Allocation I I Mathematical and Computer Modelling. 1995. - 16(1).

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

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

70. Loris Faina. An application of simulated annealing to the cutting stock problem. II European Journal of Operational Research. 1999. - 114. - P. 532-556

71. Lin S. Computer solutions of the traveling salesman problem II Bell System Journal. 1965. - V. 44 -P. 2245-2269.

72. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. II European Journal of Operation Research. — 1999. -112.-p. 413-420.

73. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. IIINFOR. 1994. - 32(3).

74. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems 11 INFOR. 1994. - 32(4).

75. 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.

76. Morabito M., Arenales M. An AND/OR graph approach to the container loading problem II International Transactions in Operational Research 1 (1994) 5973.

77. Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems) / The International Scientific Collection. -1997.-Ufa.-Russia.

78. Sakanushi К., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pasific Conference on Circuits and systems. 2000. - p. 829-832.

79. Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. II Oper. Res. Proc. 1991. - Springer-Verlag: Berlin Heidelberg, - p. 439-444.

80. Schwerin P., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP II International Transactions in Operational Research. 1997. — 4. -p.337-389.

81. Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes II Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa- 1997. - p. 261-270.

82. Stoyan Y.G., Yaskov G.N. A mathematical model and solution for the problem of placing various-sized into a strip //European Journal of Operational Research. 2004. - №156. - P.590-600.

83. Stoyan Y.G., Yaskov G.N. Mathematical model and solution of optimization problem of placement of rectangles and circles taking into accountspecial constraints II International Transaction in Operational Research. 1998, №5(1). - p.45-57.

84. Stutzle T., Hoos H.H. MAX-MIN Ant System. II Preprint submitted to Elsiever Science. 1999.

85. Terao J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. — 1987.

86. Yanasse H., edit. Special issue: Cutting and Packing Problems!I Pesquisa Operacional. 1999. - 19(2).

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