Математическое обеспечение интеллектуальных систем декомпозиции объектов с невозобновляемыми ресурсами тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Ковель, Иван Владимирович

• Ковель, Иван Владимирович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Ковель, Иван Владимирович

ВВЕДЕНИЕ.

1 АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ ПОТРЕБЛЕНИЯ РЕСУРСОВ.

1.1 Характеристика вычислительной сложности.

1.2 Классы труднорсшасмых задач

1.3 Анализ общих методов приближенного решения.

1.4 Анализ специальных методов оптимизации раскроя-упаковки.

Выводы по главе

2 ПОС ТАНОВКА ЗАДАЧИ СТОХАСТИЧЕСКОГО ПОИСКА В ПРОСТРАНСТВЕ PAÍ ЖИРОВАННЫХ PEI ПЕНИЙ.

2.1 Исходные данные.

2.2 Представление решения ММрудпой задачи потребления ресурсов.

2.3 Пространство поиска цепей.

2.4 Стохастические ранжированные цепи.

2.5 Постановка задачи вероятностного поиска оптимального потребления ресурсов.

2.6 Частные задачи поиска оптимальных цепей.J.

Выводы по главе 2.

3 МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СТОХАСТИЧЕСКОЙ ИНТЕЛ-ЛЕКУ ТАЛЬМОЙ сиси <;мы.

3.1 Недетерминированные интеллектуальные системы.

3.1.1 Операции модификации цепей.

3.1.2 Структура и правила работы недетерминированных интеллектуальных систем.

3.2 Функционирование недетерминированных интеллектуальных систем

3.2.1 Модель потребления ресурсов с регистром памяти состояния.

3.2.2 Генератор стохастических ранжированных цепей.

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

3.2.4 Характеристики вычислительной сложности алгоритмов поиска решений на модели недетерминированной интеллектуальной системы.

Выводы по главе

4 СТРУКТУРА СТОХАСТИЧЕСКОЙ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ

4.1 Функционирование интеллектуальной системы в режиме анализа решений

4.2 Функционирование стохастической интеллектуальной систем в режиме синтеза решений.

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

4.4 Исследование распределений весов решений в зависимости от рангов локальных решений.

4.5 Определение параметров распределения рангов субоптимальных решений.:.

4.6 Оценка эффективности функционирования стохастической интеллектуальной системы.

4.7 Реализация прикладной интеллектуальной системы ортогонального раскроя со сквозным резом.

Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Математическое обеспечение интеллектуальных систем декомпозиции объектов с невозобновляемыми ресурсами»

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

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

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

1) Методы динамического программирования, основанные па принципе локальной оптимальности Бсллмана, пс содержат научно обоснованных критериев локализации субоптимальных решений в пространстве поиска МРС-задач.

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

3) Вероятностные алгоритмы (Монте-Карло, Лас-Вегас, Шсрвудские) не гарантируют стабильность решения 1\[РС-задач по причине возможного отказа или заведомо усреднённого результата.

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

Таким образом, диссертационная работа посвящена актуальным вопросам разработки структуры и правил функционирования интеллектуальной системы декомпозиции объектов на основе статистически определённой функции вероятности рангов локальных решений. Такой подход позволяет решать прикладные НРС-задачи оптимального потребления ресурсов путём выборки только субоптимальных по вероятности решений из окрестности глобального оптимума (ГО).

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

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

1. Провести анализ методов оптимизации потребления ресурсов.

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

3. Разработать генератор стохастических ранжированных решений ЫРС-задач на основе генераторов псевдослучайных рангов локальных решений.

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

5. Разработать методику определения диапазонов генерации рангов.

6. Оцепить эффективность использования интеллектуальной системы.

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

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

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

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

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

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

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

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

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

- Методика определения диапазонов генерации рангов. Вероятность того, что последний ранг цепи равен единице, является нижней границей для вероятностей остальных рангов, что определяет верхнюю границу генерации рангов.

Теоретические положения работы внедрены в ООО "Бакаут" при разработке интеллектуальной системы оптимизации раскроя-упаковки плоских изделий мебельной промышленности. г'

Достоверность и обоснованность полученных результатов основывается па промышленной эксплуатации прикладной интеллектуальной системы ортогонального раскроя-упаковки па предприятии г. Краснодара ООО "Бакаут", а также компьютерными экспериментами по сравнению результатов решения ряда ЫРС-задач разработанной интеллектуальной системой и специализированными для этих задач методами.

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

ВАК РФ, 12 работ в сборниках трудов международных и Всероссийских конференций.

Диссертация выполнена на кафедре вычислительной техники и автоматизированных систем управления (ВТ и АСУ) ГОУ ВПО "Кубанский государственный технологический университет" (КубГТУ). Диссертация состоит из введения, четырёх разделов, заключения, списка использованных источников из 103 наименований и приложений, содержит 153 страницы машинописного текста и включает 21 рисуиок и 6 таблиц.

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

Выводы по главе 4

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

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

127

ЗАКЛЮЧЕНИЕ

1. В диссертации проведён сравнительный анализ общих методов решения ЫРС-задач дискретной оптимизации, а также специальных методов оптимизации раскроя-упаковки. На основании анализа сделан вывод о том^ что перспективный путь решения М^С-задач оптимизации раскроя-упаковки — использование зависимости оценки веса субоптимальных решений от рангов локальных решений. Это позволяет обоснованно сократить дерево поиска решений.

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

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

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

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

5. Произведена оценка эффективности использования стохастической иителлск 1 уальпой системы.

Для задачи двухмерного гильотинного раскроя введено рекурсивное описание схемы карт раскроя с использованием ранжированных цепей, что повысило коэффициент раскроя до величины ц « 97% для исходных наборов деталей с большим ассортиментом на одинаковых заготовках, и привело к превышению: среднего коэффициента раскроя по сравнению с существующими методами решения задач 2ПС8Р до А /; и 1,5% па отдельных листах.

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

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

Список литературы диссертационного исследования кандидат технических наук Ковель, Иван Владимирович, 2010 год

1. Адамснко А.Н., Кучуков A.M. Логическое программирование и Visual Prolog. СПб.: БХВ-Петербург, 2003. - 992 с.

2. Акимов O.E. Дискретная математика: логика, группы, графы — 2-е .изд., доп. М.: Лаборатория базовых знаний, 2003. - 376 с.

3. Андерсон Джеймс А. Дискретная математика-и комбинаторика: Пер. с англ. — М. : Издательский дом «Вильяме», 2003. — 960 с.1

4. Ахо А., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 276 с.

5. Беллмаи Р. Динамическое программирование. М.: ИЛ, 1960. - 412 с.

6. Беллмап Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. — 565 с.

7. Валсева А.Ф. Применение конструктивных эвристик в задачах раскроя упаковки // Информационные технологии. 2006. №11. Приложение. 24 с.

8. Валсева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки //Информационные технологии'. 2005. №10. с. 36-43.

9. Валесва А.Ф., Гаресв И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизированный метод динамического перебора с усечением // Информационные технологии. 2003. №10. Приложение. — 24 с.

10. Ващспко И.В. Марков В.Н. Идентификация NP-полпых систем // СовреIменпые информационные технологии: Сборник статей международной НТК.

11. Выпуск 5. Пенза. 2007. с. 103-107. '

12. Вептцсль Е.С. Исследование операций. — М.: Сов. Радио, 1972. — 362 с.

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

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

15. Власспко A.B., Марков В.Н. Интеллектуальная NPC-систсма // Перспективы науки. 2010. №1(03). с.55-60.

16. Власспко A.B., Марков В.Н. Метод построения окрестности глобального оптимума NPC-задач на ранжированном дереве поиска решения // Программные продукты и системы. 2010. №1(89). с.6-10. ?.'

17. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб.: Питер, 2001. - 384 с.

18. Гаврилова Т.А., Чсрвинская K.P. Извлечение и структурирование знаний для экспертных систем. — М.: Радио и связь, 1992. — 199 с.

19. Гашков С.Б., Чубариков В.Н. Арифметика. Алгоритмы. Сложность вычислений. 2-е изд., перераб. — М.: Высш. шк., 2000. 320 с.

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

21. Гончаров E.H. Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследоваиие операций. 1999. Сер. 2. Т. 6. №1. с. 12-32.

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

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

24. Дистсль Р. Теория графов. Новосибирск: Изд-во ИМ СО РАН, 2002.

25. Евстигнеев В.Л. О некоторых свойствах локальных алгоритмов на графах // Комбинаторно-алгебраические методы в прикладной математике. — Горький, 1983.-е. 72-105.

26. Гвсшгиеев В.Л. Применение теории графов в программировании. — М.: Паука, 1985. — 352 с.

27. Евстигнеев В.Л., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: Паука, 1994.

28. Искусственный интеллект: В 3 кн. Кп. 1. Системы общения и экспертные системы: Справочник. / Под ред. Попова Э.В. М.: Радио и связь, 1990. - 464 с.

29. Искусственный интеллект: В З.кн. Кн. 2. Модели и методы: Справочник. / Под ред. Поспелова Д.Л. М.: Радио и связь, 1990. — 304 с.

30. Искусственный интеллект: В 3 кн. Кп. 3. Программные и аппаратные средства: Справочник / Под ред. Захарова В.Н., Хорошевского В.Ф. М.: Радио и связь, 1990.-368 с.

31. Исследования по прикладной теории графов / Под ред. Л.С. Алексеева. -Новосибирск: Наука, 1986.

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

33. Касьянов В.П., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. 1104 с.

34. Ковель И.В. Интеллектуальная система раскроя-упаковки с ранжированным управлением шириной поиска // Сборник трудов V Всероссийской научной конференции. «Информационные технологии в промышленности» Пиж. Новгород. 2008. с. 422-424

35. Ковель И.В., Марков В.Н. Метод адаптации весовых коэффициентов к исходным данным в задачах раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 105-110.

36. Ковель И.В. Синтез базы знаний прикладной интеллектуальной системы непшьотишюго раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 111 -113.

37. Ковель И.В. Вероятностный способ перебора ранжированных решений задачи раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 192-193.

38. Ковсль И.13. Кшочко В.И., Марков В.II. Интеллектуальная система для приближённого решения прикладных КРС-задач // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 194-199.

39. Ковсль И.В. Управление шириной поиска в ранжированном пространстве решений // Сборник трудов 7 Международной иаучио-ирактической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. с.399-400.

40. Ковель И.В. Проблемный подход в преподавании дисциплины «Структуры и алгоритмы обработки данных» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». КубГТУ. 2009.

41. Ковсль И.В. Интеллектуальная система с ранжированным деревом решений // Сборник трудов 8 Международной паучпо-практичсской конференции

42. Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. — с.241-242

43. Ковель И.В. Вероя тностный метод построения окрестности статистического глобального оптимума ЫРС-задач // Интеллектуальные технологии. 2010. №2 -с. 38-41.

44. Ковель И.В. Проблемный подход в преподавании дисциплины «Системы искусственного интеллекта» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Куб! ТУ. 2010.

45. Юпочко В.И., Марков В.Н. Решение ЫР-проблем в алгебре компактных контейнеров // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2005. Приложение №2. с. 54-58.

46. Юпочко В.И., Марков В.Н. Субоптимальные решения ЫР-задач за полиномиальное время // Информатика и управление: Труды КубГТУ. Том XXV. Краснодар. 2005. с. 153-156.

47. Кокотов В.З. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии. 1998. №11. с. 16-21.

48. Колмогоров А.П. Основные понятия теории вероятностей. М.: Паука, 1974.-371 с.

49. Кори Г, Корн Т. Справочник по математике (для научных работников и инженеров). Определения, теоремы, формулы. 6-е из/1., стер. СПб.: Издательство «Лань», 2003. - 832 е.

50. Кочетов Ю., Младепович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Сер. 2. 2003. Т. 10. №1. с. 11-43.

51. Кочетов Ю., Усмаиова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // XII Байкальская международная конференция. Иркутск. 2001. с. 22-27.

52. Лорьср Ж.-Л. Системы искусственного интеллекта: Пер. с франц. М.: Мир, 1991. - 568 с.

53. Люгср Дж.Ф. Искусственный интеллект: Стратегии и методы решения сложных проблем. 4-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2003.- 864 с.

54. Макконслл Дж. Основы современных алгоритмов. 2-е дополненное издание: Пер. с англ. -М.: Техносфера, 2004. 368 с.

55. Малпас Дж. Реляционный язык Пролог и его применение: Пер с англ. — М.: Паука, Гл. ред. физ.-мат. лит., 1990. —464 с.

56. Марков В.П. База знаний для негильотипиого раскроя-упаковки // Информационные технологии. 2007. №4. с. 17-23.

57. Марков В.Ы. Идентификация интеллектуальных NP-гюлных систем // Кибернетика и высокие технологии XXI века: Сборник трудов VIII Международной конференции. Воронеж. 2007. с. 114-122.

58. Марков В.Н. Принципы построения экспертной системы гильотинного раскроя // Информационные технологии. 2005. №4. с. 53-57.

59. Марков В.Н. Способ порождения эвристик для решения NP-трудных задач // Информационные технологии. 2006. №6. с. 21-25.

60. Молокова О.С., Уварова Т.Г. Методология анализа предметных знаний // Новости искусственного интеллекта. 1992. №3. с. 11-60.

61. Мухачева A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. №3. с. 27-32.

62. Мухачева A.C., Чиглинцев A.B., Смагип М.А., Мухачева Э.А. Задачи двумерной упаковки: развитие генетических алгоритмов па базе смешанных процедур локального поиска оптимального решения // Информационные технологии. Приложение. 2001. №9.-24 с.

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

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

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

66. Мухачева Э.Л., Ермаченко Л.И., Сиразетдипов Т.М., Усманова А.Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. №6. с. 25-31.

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

68. Мухачева A.C., Курелеиков С.Х., Смагин М.А., Ширгазии P.P. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. 2002. №10. с. 26-3 1.

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

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

71. Мухачева ЭЛ., Мухачева A.C., Чиглшщсв A.B. Генетический алгоритм блочной структуры в задачах двумерной упаковки. // Информационные технологии. 1999. №11. с. 13-18.

72. Мухачева A.C., Ширгазии P.P. Задачи упаковки прямоугольников: рандомизированная эвристика па базе двойственной схемы локального поиска оптимума // Информационные технологии. 2003. №5. с. 18-23.

73. Осуга С. Обработка знаний: Пер. с япоп. — М.: Мир, 1989. — 293 с.

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

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

76. Поспелов Д.Л. Ситуационное управление. Теория и практика. М.: Наука, 1986.-284 с.

77. Построение экспертных систем: Пер. с англ. / Цод ред.Ф. Хсйеса-Рота, Д. Уотсрмапа, Д. Лсната. М.: Мир, 1987. - 441 с.

78. Приобретение знаний / Осуга С., Саэки Ю., Судзуки X. и др.: Пер. с япоп. -М.: Мир, 1990.-304 с.

79. Рейнгольд Э. Нивергельт Ю. Део Н. Комбинаторные алгоритмы: теория и практика. М.: Мир, 1980.

80. Свами М.П., Тхуласираман К. Графы, сети и алгоритмы: Пер. с аигл. — М.: Мир, 1984.-454 с.

81. Слиссико Д.О. Сложпостные задачи теории вычислений // Успехи мат. Паук. 1981. - Т. 36. № 6. - с. 21-103.

82. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: — Пер. с англ. М.: Мир, 1990. - 235 с.

83. Taxa Х.А. Введение в исследование операций, 6-е изд.: М.: Издательский дом «Вильяме», 2001. - 912 с.

84. Толковый словарь по искусственному интеллекту / Аверкии Л.Н., Гаазе-Рапопорт М.Г., Поспелов Д.Л. М.: Радио и связь, 1992. — 256 с.

85. Уотермси Д. Руководство по экспертным системам: Пер. с англ. М.: Мир, 1989.-388 с.

86. Усманова А.Р. Вероятностные жадные эвристики для задачи упаковки в контейнеры. Спб: ОПТИМ-2001. с. 141-146.

87. Усманова Л.Р. Экспоненциальная окрестность решений для задачи упаковки в контейнеры//Информационные технологии. 2005. №6. с. 48-51.

88. Хопкрофт Д.Э., MoiBaira Р., Ульман Д.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.: — М.: Издательский дом «Вильяме», 2002. 528 с.

89. Чистяков В .П. Курс теории вероятностей. М.: Высш. школа, 1982. - 356 с.

90. Шайтхауэр Г., Мухачсва Л.С. Белов Г.П., Мухачсва Э.Л. Планирование одномерного раскроя материала различной длины на базе непрерывной релаксации и метода отсекающих плоскостей. // Информационные технологии. 2004. №1. с. 28-35.

91. Ясницкий JI.H. Введение в искусственный интеллект: Учеб. пособие для студ. вузов. М.: Издательский центр «Академия», 2005. — 176 с.

92. Belov G. Л branch-and price algorithm for one-and-two dimensional two-stage cutting (stock) problems // Technical report MATH-NM-03-03. Dresden University. 2003. url: http://www.math.tu-drcsden.de/~capad

93. Dorigo M. Ant Algorithms for Discrete Optimization, 1999. url: http://citeseer.nj.nec.con/420280.html

94. DykhofflL A typology of cutting and packing problems // European Journal of Operational Research. 1990. Vol. 141. P. 274-294.

95. Hopper E., Turton B. An empirical investigation of mcta-heuristic and heuristic algorithms for a 2D packing problem // EJOR. 2001. Vol. 128. P. 34-57.

96. Kendal 1G. Simulated Annealing, 2002.iurl: http://www.cs.nott.ac.ul<y~gxk/aim/notes/simulatedannealing.doc

97. Eiu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles // EJOR. 1999. Vol. 112. P. 413-420.

98. Eodi Д., Martcllo S., Vigo D. Heuristic and mcta-heuristic approaches for a class of two-dimensional bin packing problems Algorithms // INFORMS J. Comput. 1999. Vol. 11. P. 345-357.

99. Luke B.T. Simulated Annealing Cooling Schedule, 2001. url: http://membcrs.aol.com/btlukc/simanfl.htm

100. Shaffer II. Practical Guide to Genetic Algorithms, 1993. http://chemdiv-www.nrl.navy.mil/6110/6112/sensors/chemomctrics/practga.html142