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

Введение.

Глава 1. Проблемы раскроя и упаковки.

Определение и дуальность понятий раскроя и упаковки.

Классификация задач раскроя.

Регулярная и нерегулярная упаковка.

Упаковка полосы и прямоугольника.

Практические аспекты.

NP-полнота проблем раскроя и упаковки.

Алгоритмы и их сложность.

NP-полнота задачи.

Выводы.

Глава 2. Генетические алгоритмы.

Эволюционные вычисления.

Эволюционные алгоритмы.

Формализация генетического алгоритма.

Оценка эффективности генетического алгоритма.

Основная теорема о генетических алгоритмах.

Применение генетических алгоритмов.

Комбинирование методов.

Вопросы разработки и использования.

Достоинства и недостатки.

Выводы.

Глава 3. Решение задачи раскроя полубесконечной полосы.

Задача прямоугольного раскроя.

Содержательная постановка задачи.

Математическая постановка задачи.

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

Блок - структуры упаковок.

Блочный декодер.

Задача круглого раскроя.

Содержательная постановка задачи.

Математическая постановка задачи.

Методы решения задачи круглого раскроя.

Структура края круглой упаковки.

Краевой декодер.

Другие задачи плоского раскроя.

Практическая задача раскроя листов.

Задача нерегулярного раскроя.

Перспективы развития метода.

Выводы.

Глава 4. Вычислительный эксперимент.

Программное обеспечение.

Общая характеристика результатов.

Прямоугольный раскрой.

Круглый раскрой.

Показатели качества раскроя.

Прямоугольный раскрой.

Круглый раскрой.

Оценка сложности алгоритма.

Показатель качества генетического алгоритма.

Другие оценки.

Выводы.

Глава 5. Область применения метода.

Технологии раскроя материалов.

Лазерная промышленность в России.

Устройство лазерных установок.

Примеры программного обеспечения.

Выводы.

Актуальность темы исследования

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

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

Необходимость разработки рациональных методов раскроя обоснована еще в 40-х годах XX века. В СССР первые разработки принадлежат академику JI.B. Канторовичу. На сегодняшний день существует множество алгоритмов, созданных для решения подобных задач. В то же время практически нет универсальных разработок, которые позволили бы решать различные (в рамках некоторого класса) задачи раскроя на основе одного и того же метода.

Последние несколько лет ряд металлургических и машиностроительных предприятий впервые приобрели или заменяют морально и физически устаревшую технику, осуществляющую лазерный раскрой листового металла (в том числе, Западно-сибирский металлургический комбинат (г. Новокузнецк), Курганский автобусный завод, «Химконцентрат» (г. Новосибирск), «ЭлСиб» (г. Новосибирск), Тверской вагоностроительный завод) и другие. Установки для лазерной резки на некоторых предприятиях имеются уже десятилетие, но только в настоящее время руководство получает возможность модернизировать процесс производства.

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

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

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

Цель работы и решаемые задачи

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

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

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

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

Основные защищаемые положения

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

- показала, что асимптотическая сходимость алгоритма сохраняется при смене декодера;

- позволяет предположить, что разработанный алгоритм решения NP-полной задачи имеет полиномиальную сложность.

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

3. При помощи разработанных алгоритмов:

- решена задача прямоугольного раскроя полубесконечной полосы;

- поставлена и решена задача круглого раскроя полубесконечной полосы;

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

- разработано соответствующее программное обеспечение.

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

Научная новизна

• Поставлена и решена малоизученная задача круглого раскроя; разработан оригинальный «краевой» декодер для использования в предложенном генетическом алгоритме; основная идея декодера носит общий характер и применима для упаковки предметов других несложных геометрических форм;

• поставлена и решена практическая задача раскроя набора листов на прямоугольные детали с осуществлением предварительного раскроя листов на крупные заготовки; для решения задачи разработана модификация предложенного генетического алгоритма и блочного декодера;

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

Обоснованность научных положений и выводов

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

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

На основе сформулированного метода разработано математическое и программное обеспечение, реализующее эффективный алгоритм решения задач оптимизации плоского раскроя различных прямоугольных, либо различных круглых деталей. Данное программное обеспечение можно использовать: для решения практических промышленных задач (например, в НИЛ ППДиУ МГИСиС); как обучающее и демонстрационное средство для проведения практических занятий и лабораторных работ (например, на кафедре обработки металлов давлением МГИСиС); как базовый проект для разработки нового программного обеспечения для решения других задач плоского раскроя.

Реализация результатов

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

В НИЛ ППДиУ МГИСиС часто встает задача рационализации карты раскроя прямоугольных листов на прямоугольные предметы. Задача осложняется тем, что размер листов, как правило, превышает размер рабочего поля резки лазера. В связи с этим требуется осуществлять предварительный раскрой листов на крупные заготовки.

Предложенный метод был модифицирован в соответствии накладываемыми технологическими ограничениями. Разработанное программное обеспечение принято в эксплуатацию и используется для повышения экономичности лазерного раскроя плоских металлических материалов (нержавеющей, конструкционной, инструментальной, броневой марок сталей). При этом в процессе раскроя обеспечивается экономия материала на 3-16%, а также достигается повышение производительности работы лазерной установки типа «ТЛУ-1000».

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

Основные положения диссертации докладывались на 57-ой научно-технической конференции студентов и аспирантов МГИСиС в 2002 году, на Всероссийской конференции «Высокопроизводительные вычисления и технологии» в 2003 году, на I и II Международных конференциях «Параллельные вычисления и задачи управления» в 2001 и 2004 годах.

Публикации

Содержание диссертации отражено в 4 печатных работах [47,48,49,50]. Кроме того, опубликовано еще 2 работы, посвященных решению NP-полных проблем с использованием генетических алгоритмов [45,46].

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

Работа состоит из введения, пяти глав и заключения. Первые две главы носят обзорный характер. В Главе 1 подробно анализируется современное состояние проблем раскроя и упаковки, Глава 2 посвящена методу стохастической оптимизации - генетическим алгоритмам.

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

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

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

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

- показала, что асимптотическая сходимость алгоритма сохраняется при смене декодера;

- позволяет предположить, что разработанный алгоритм решения NP-полной задачи имеет полиномиальную сложность.

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

3. При помощи разработанных алгоритмов:

- решена задача прямоугольного раскроя полубесконечной полосы;

- поставлена и решена задача круглого раскроя полубесконечной полосы;

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

- разработано соответствующее программное обеспечение.

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

Заключение

1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 288 с.

2. Балакин В.П., Мартынов А.И., Тер-Акопов Р.С. Теория и технология процессов штамповки. М.: МИСиС, 1996. -122 с.

3. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988. - 128 с.

4. Бурковский B.JL, Харченко Р.А., Цапин А.Н. Исследование эффективности эволюционных вычислений в задачах оптимизации в электроэнергетике. // Системы управления и информационные технологии, 2003. №1-2. С.63-67.

5. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

6. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов. // Приложение к журналу «Информационные технологии», 2000. № 12. 25 с.

7. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1988. 208 с.

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

9. Волкова В.Н., Денисов А.А. Основы теории систем и системного анализа. СПб.: СПбГТУ, 1998.-510 с.

10. Габасов P.P., Кириллов Ф.М. Методы оптимизации. Минск: БГУ, 1975. И.ГупалА.М. Стохастические методы решения негладких экстремальных задач.

11. Киев: Наукова думка, 1979. 151 с.

12. Дегтярев Ю.И. Системный анализ и исследование операций. М.: Высшая школа, 1996.-335 с.

13. Джонс М. Тим Программирование искусственного интеллекта в приложениях. -М.: ДМК Пресс, 2004. 312 с.

14. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003. - 432 с.

15. Ермольев Ю.М. Методы стохастического программирования. М.: Наука, 1976.239 с.

16. Задачи статистической оптимизации. Под ред. JI.A. Растригина. Рига: Зинатне, 1971.-230 с.

17. Заде Jl.А. Основы нового подхода к анализу сложных систем и процессов принятия решений. // В кн. Математика сегодня. М.: Знание, 1974. С. 5-49.

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

19. Кафаров В.В., Дорохов И.Н., Марков Е.П. Системный анализ процессов химической технологии. М.: Наука, 1986. - 359 с.

20. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.-368 с.

21. Кормен Т., ЛейзерсонЧ., РивестР. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.-960 с.

22. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 1980. - 280 с.

23. Куприянов М.С., Матвиенко Н.И. Генетические алгоритмы и их реализации в системах реального времени. // Информационные технологии, 2001. № 1. С. 17-21.

24. Курейчик В.М. Генетические алгоритмы. Состояние, проблемы, перспективы. // Известия академии наук. Теория и системы управления, 1999. №1. С. 144-160.

25. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование. // Известия академии наук. Теория и системы управления, 2002. № 1. С. 127-137.

26. Ларичев О.И. Наука и искусство принятия решений. М.: Наука, 1979. - 200 с.

27. Липницкий А. А. Применение генетических алгоритмов к задаче о размещении прямоугольников. // Кибернетика и системный анализ, 2002. №6. С. 180-184.

28. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. Раздел: Сложные задачи комбинаторной оптимизации. М.: Наука, 1990. - 272 с.

29. Норенков И.П., Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации. // Информационные технологии, 1999. № 2. С. 2-7.

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

31. Макаров И.М., Виноградская Т.М. и др. Теория выбора и принятия решений. М.: Наука, 1982. - 328 с.

32. Математические методы в исследовании операций. Сборник под ред. Моисеева Н.Н., Краснощекова П.С. М.: Изд-во Московского университета, 1981. - 192 с.

33. Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, 1981.488 с.

34. Мухачева А.С., Мухачева Э.А. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя. // Информационные технологии, 2002. №6. С.25-30.

35. Мухачева А.С., Чиглинцев А.В. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя. // Информационные технологии, 2001. №3. С.27-31.

36. Мухачева Э.А., Валеева А.Ф. Метод динамического перебора в задаче двумерной упаковки. // Информационные технологии, 2000. №5. С.30-36.

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

38. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя. // Информационные технологии, 2000. №9. С. 15-20.

39. Мухачева Э.А., Мухачева А.С. Метод перестройки для решения задач прямоугольной упаковки. // Информационные технологии, 2000. №4. С.30-36.

40. Мухачева Э.А., Мухачева А.С., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя. // Информационные технологии, 2000. №2. С. 11-17.

41. Мухачева Э.А., Мухачева А.С., Чиглинцев А.В. Генетический алгоритм блочной структуры в задачах двумерной упаковки. // Информационные технологии, 1999. №11. С. 1318.

42. Немировский А.С., ЮдинД.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. - 197 с.

43. Николаев А.И., Брук В.М. Системотехника методы и приложения. М.: Машиностроение, 1985. - 199 с.

44. Подлазов B.C., Подлазова А.В. Обеспечение наращиваемости многопроцессорных систем с общей памятью с использованием многокольцевых некоммутируемых систем связи. Ч Труды Международной конференции «Параллельные вычисления и задачи управления

45. РАСО'2001)», Том V («Программное и аппаратное обеспечение»), Москва, ИПУ РАН, 2001. С.165-181.

46. Подлазова А.В. Генетические алгоритмы в задачах плоского регулярного раскроя // Труды II Международной конференции «Параллельные вычисления и задачи управления (РАСО'2004)». М.: ИПУ РАН, 2004г. С.284-316.

47. Подлазова А.В. Генетические алгоритмы: происхождение, сущность, применение // Сборник научных трудов «Экономика, информационные технологии и управление в металлургии». М.: изд-во МИСиС «Учеба», 2004г. С.122-128.

48. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 238 с.

49. Проблемы случайного поиска. Задачи оптимизации и адаптации. Под ред. JI.A. Растригина. Рига: Зинатне, 1988. - 209 с.

50. Растригин J1.A. Системы экстремального управления. М.: Наука, 1974. - 248 с.

51. Редько В.Г. Эволюционная кибернетика. М.: Наука, 2001. - 159 с.

52. Реклейтис Г., Рейвиндран А., РэгсделК. Оптимизация в технике. Книга 1. М.: Мир, 1986.-350 с.

53. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. Книга 2. М.: Мир, 1986.-320 с.

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

55. Росс Клемент. Генетические алгоритмы: почему они работают? Когда их применять? // Компьютерра, 1999. № 11. С. 20-23.

56. Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы М.: Горячая линия — Телеком, 2004. - 452 с.

57. Рыков А.С. Методы деформируемых конфигураций. М.: Физматлит, 1993.216 с.

58. Рыков А.С. Методы системного анализа: оптимизация. — М.: Экономика, 1999.256 с.

59. Рыков А.С. Системный анализ и исследование операций. Методы поисковой оптимизации. Методы управляемого прямого поиска. М.: МИСиС, 1990.

60. Рыков А.С., Оразбаев Б.Б. Системный анализ и исследование операций. М.: МИСиС, 1995.

61. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985. - 384 с.

62. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1980. - 276 с.

63. Стецюра Г.Г. Эволюционные методы в задачах управления, выбора, оптимизации. // Приборы и системы управления, 1998. № 3. С. 54-62.

64. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения геометрических объектов. Киев: Наукова думка, 1976. - 247 с.

65. Сухарев А.Г. Об оптимальных стратегиях поиска экстремума. // Журнал вычислительной математики и математической физики, 1971. №4. С. 910-924.

66. Сухарев А.Г. Оптимальный поиск экстремума. М.: Изд-во Московского Университета, 1975. - 334 с.

67. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.-328 с.

68. Танаев B.C., ШкурбаВ.В. Введение в теорию расписаний. М.: Наука, 1975.256 с.

69. Теория и применение случайного поиска. Под ред. J1.A. Растригина. Рига: Зинатне, 1969. - 305 с.

70. Теория расписаний и вычислительные машины, под. ред. Коффмана Э.Г. М.: Наука, 1984. - 332 с.

71. Dyckoff Н. Topology of cutting and packing problems. // European Journal of Operational Research, 1990. №44. P.145-159.

72. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. -Addison-Wesley, Reading, M.A., 1989. 412 p.

73. Heckmann R., Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry. // Annals of Operations Research, 1995. №57. P. 103-133.

74. Hinxman A.I. The trim loss and assortment problems. // European Journal of Operational Research, 1980. №5. P. 8-18.

75. Holland J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, University of Michigan, Ann Arbor, 1975.

76. Hopper H., Turton B.C.H. A review of the application of meta-heuristic algorithms to 2D strip packing problems. // Artificial Intelligence Review, 2001. №16. P. 257-285.

77. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementation. // Operation Research, 1990. №19. P. 983-998.

78. ZadehL.A. Soft computing and Fuzzy Logic. // Software Engineering Journal, 1994.11.