автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Идентификация и синтез интеллектуальных NP-полных систем

На правах рукописи

Же

Марков Виталий Николаевич

ИДЕНТИФИКАЦИЯ И СИНТЕЗ ИНТЕЛЛЕКТУАЛЬНЫХ ОТ-ПОЛНЫХ СИСТЕМ

Специальность 05 13 01 - «Системный анализ, управление и обработка информации (информационные и технические системы)»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

□□3174626

Краснодар - 2007

003174626

Работа выполнена в Кубанском государственном технологическом университете

Научный консультант: доктор технических наук, профессор

Ключко Владимир Игнатьевич, Кубанский государственный технологический университет

Официальные оппоненты, доктор технических наук, профессор

Плахотнюк Александр Николаевич,

Кубанский государственный технологический университет,

доктор физико-математических наук, профессор Чижиков Владимир Иванович, Кубанский государственный университет,

доктор технических наук, доцент Финько Олег Анатольевич, Краснодарский военный институт имени генер.зла армии Штеменко С М Ведущая организация ОАО КБ «Селена»

Защита состоится «14» ноября 2007 года в 14 00 на заседании диссертационного совета Д 212 100 04 в Кубанском государственный технологический университете по адресу. 350072, г Краснодар, ул Московская, 2, конференц-зал

С диссертацией можно ознакомиться в библиотеке Кубанского государственного технологического университета Автореферат разослан Г" веТЛ^Я-2007 г

Ученый секретарь диссертационного совета, канд техн наук, доцент

А В Власенко

СОКРАЩЕНИЯ И ОБОЗНАЧЕНИЯ

НМТ - недетерминированная машина Тьюринга, NP-полные задачи -задачи, решаемые за полиномиальное время на НМТ, ПЗ - класс NP-полных задач, допускающих приближенное решение, ИС - интеллектуальная система, БЗ - база знаний, СГО - статистический глобальный оптимум, ФСС — факториальная система счисления, ФФЦ - факториальная форма цепи, 2DCSP (2 dimensional cutting stock problem) - проблема двухмерного гильотинного раскроя, 2DBPP (2 dimensional bin packing problem) - проблема двухмерной негильотинной упаковки, нестинг - проблема оптимальной упаковки-вложения плоских фигур произвольной формы, ©(/) -класс функций с одинаковым ростом сложности /, П(/) - класс функций, растущих не медленнее/, 0(f) - класс функций, растущих не быстрее/, R* -

множество неотрицательных дейс гвигельных чисел, Z+ - множество целых

неотрицательных чисел, N - множество натуральных чисел, deg v - степень

вершины графа, Г{/?,а) -гамма-функция от и с произвольным нижним пределом интегрирования а > 0, i//(z) - логарифмическая производная гамма-функции, - наименьшее целое число > а

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

вом, а также проектирование в области электроники и архитектуры и др

С одной стороны для решения ЫР-полных задач дискретной оптимизации с произвольной размерностью исходных данных в настоящее время не существует методов получения точного решения за время, ограниченное техническими условиями функционирования информационной системы или продолжительностью технологических операций Поэтому суть современных методов заключается в выборе лучшего варианта при проверке чрезвычайно узкого подмножества всех возможных альтернатив в надежде на то, что ошибка найденного решения не слишком велика и решение будет субоптимальным При этом величина ошибки приближённого решения принципиально не определяема Сформированные к настоящему времени направления исследований в этой области имеют ряд особенностей I) Методы динамического программирования, основанные на принципе локальной оптимальности Беллмана, не содержат обоснованных критериев локализации субоптимальных решении в пространстве поиска 2) Существующие методы управления поиском в пространстве решений (имитация отжига, муравьиная колония, генетичес кие алгоритмы и др ) в разной мере используют математическую конструкцию цепей Маркова и сводятся к описанию состояния вычислительной модели уравнениями Колмогорова При этом поиск эвристик и метаэвристик ограничения перебора не формализован, является своего рода искусством и определяется творческими способностями и талантом исполнителя 3) Вероятностные методы не гарантируют стабильность решения по причине возможного отказа или заведомо усредненного результата

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

то, что выявленные закономерности сохраняются в задачах с большой размерностью исходных данных, использовать найденные эвристики в практике решения №-полных задач с произвольной размерностью

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

Цель: оптимизация потребления ресурсов на основе разработки специальной теории синтеза интеллектуальных систем дискретной оптимизации

Задачи:

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

2 Введение метрики в пространство поиска решений и экспериментальное исследование распределения оптимальных решений

3 Идентификация свойств пространства поиска и разработка методов эффективного поиска субоптимальных решений на основе расширения окрестности статистического глобального оптимума (СГО) с минимальными вычислительными затратами

4 Разработка основ теории синтеза интеллектуальных ЫР-полных систем

5 Разработка методов синтеза прикладных интеллектуальных полных систем и конструкторов решений задач 20С8Р, 20ВРР и нестинга

6 Оценивание эффективности использования интеллектуальных К'Р-полных систем по технико-экономическим показаУелям

Методы исследования В диссертации использованы методы системного анализа, дискретной оптимизации, теории автоматов и вычислений, теории вероятностей и математической статистики, теории чисел, теории графов, теории множеств, а также многосортные алгебры и исчисление предикатов

Объект исследования дискретные системы оптимизации потребления ресурсов

Предмет исследования оптимальный поиск субоптимальных решений в пространстве состояний дискретных систем

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

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

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

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

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

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

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

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

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

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

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

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

Интеллектуальная система оптимального раскроя плоских материалов (ДСП, ДВП, МДФ, фанера, ст екло и др ) со сквозным резом внедрена в г Краснодаре в компании "СБС", ООО ПКП "БАКАУТ" и мебельных предприятиях Краснодарского края.

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

пая форма цепи, ведущая к статистическому глобальному оптимуму, соответствует принципу оптимальности Беллмана,

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

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

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

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

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

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

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

Публикации. Результаты диссертации опубликованы в 21 работе, из них шесть в ведущих периодических изданиях, рекомендованных ВАК РФ, четыре статьи в сборниках трудов ВУЗов, 11 работ в сборниках трудов международных симпозиумов и конференций

Структура и объём диссертации. Диссертация состоит из введения, шести глав, заключения и приложений Общий объем работы 370 страниц Основная часть диссертации содержит 322 страницы машинописного текста, в том числе 51 рисунок и 16 таблиц Список использованных источников включает 242 наименования Приложения приведены на 48 страницах

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

В первом разделе главы описан функционал g(z) ,Ж R+, определенный на множестве ,М произвольных структур, задаваемых семейством уравнений z Показано, что функционал g(z) упорядочивает „U в такую последовательность Структур (Z|,Z2, ,z„ , z,„), что g(z\) > g(z2) > > g(z,) > > g(zm) Определены условия принадлежности NP-задачи с размерностью п исходных данных х и функционалом g(z) классу ПЗ

• \.J/\ = Q(f"), где f- константа или полином от п

• Исходное множество не упорядочено по g(z)

• Постановка ПЗ требует нахождение в „//такого zopl е {zi, z,„, z,}, для которого выполняется один из соответствующих критериев {mm g(Z|), max g(z,„), min (g(z,)-go)}

Для большинства прикладных ПЗ форма представления решения z не определена условием задачи и ее нахождение, как правило, является самостоятельной задачей обоснования и синтеза структур z е. U в виде семейства в общем случае рекурсивных уравнений z, = К(х, Zj)

Во втором разделе первой главы проведен анализ методов решения ПЗ рассмотрены основы методов динамического программирования, метод имитации отжига и муравьиной колонии, генетические алгоритмы, жадные алгоритмы, методы Монте-Карло, Лас-Вегас, Шервудские Ре)уль-

таты анализа сводятся к еледующе му

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

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

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

Дополнительно рассмотрены специальные методы оптимизации раскроя-упаковки, основу которых заложил Канторович Л В и Залгаллер В А и в нашей стране развили Кочетов Ю А , Норенков И П , Мухачева Э А , Романовский ИВ и др По резутьтатам анализа приведены частные направления дальнейших исследований

1 Исследование закономерностей распределения субоптимальных решений в пространстве поиска с метрикой структур карт раскроя

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

3 Глубоко исследованы методы поиска оптимального решения, однако требуется оптимизация самого процесса поиска по критерию минимальной вычислительной сложности

4 Разработан огромный пласт эвристик и метаэвристнк ограничения поиска, однако недостаточно внимания уделено вопросам автоматизации получения эвристик

5 Не определены свойства пространства поиска, что препятствует разработке общих методов решения задачи раскроя-упаковки, как ¡адачи класса ПЗ

В третьем разделе первой главы осуществлена формализация ПЗ Исходные данные представлены графом G = (V, E/v„ d), где V- множество вершин-ресурсов v, произвольной природы с вектором параметров Р, = (pi,pi, ,pd) определенных на R+, = п E/v, - фактор-множество ребер, инцидентных каждой v,

Форма решения z представлена на основе меченого упорядоченного дерева Lot, введенного в 2000 г Т Takahasi, и приведенного в работе к рекурсивной структуре z = К(п, г), где конструктор К - семейство уравнений {К], К2, ,К,}, описывающих отображение Пх.Ж——удовлетворяющее условию С, П - носитель структуры, роль которого играет множество цепей к на гргфе G, используемых Касьяновым В Н и Евстигнеевым В А для анализа свойств графов Для заданной пары (n,k) множество П„а ={л"| л(п,к) = (V|, v2, ,v„v,+i, , v*), 0 < к< п+\} является деревом цепей на графе G с фиктивной корневой вершиной и0, смежной ко всем остальным вершинам графа Описаны свойства Y[„k

a) Степень вершин подчиняется неравенству deg v, < и-/+1 (1 1)

I i и'

b) Верхняя оценка числа цепей ж(п,к) на дереве !Г!„ А<- (1 2)

1 (п — ку

c) Верхняя оценка числа всех вершин дерева до глубины к,0<к<п+1 [П„А|*</ (Г(я -m-V(n-k,\))-n е (Г(и,0)-Г(и,1)), (1 3)

' " {n-k-iy

JO

где Г{n,a) = je~'t"~,dt, и при к - п

|Пя4|"=и«е-ие(Г(л,0)-Г(л,1)),

(14)

для больших л указана приближенная оценка |Пя4| ~ п[е

Функция веса к П —> Я цепи я(п,к) задана выражением

п к

к

Кя) = ку + 2>(е,,+1),

(15)

а

где q(v) = \\р, - вес вершины и м^) - вес ребра, определенные на ку

икЕ- экспертные коэффициенты, характеризующие ПЗ

В диссертации показано, что значением функционала g(z) является суммарный вес носителя структуры g{г) = ,), независимо от исполь-

I

зуемого конструктора К Выдвинута гипотеза о том, что распределение оптимальных по весу структур а определяется распределением в пространстве П„ь оптимальных по весу носителей 7Г, которые составляют структуру г

Произведена редукция пространства поиска цепей к подпространству П* л сП,(, которое содержит цепи л е П* к с наибольшей вероятностью того, что их вес /¡(тс*) минимален во всем пространстве П„ к

где л' е П„ к \ П* к Для фиксированной пары {К, С) ПЗ сведена к поиску цепи с минимальным весом и минимальными вычислительными затратами А(л-*)= Пип (Кл,У), (17)

РЩ= шш Шл,)) И(л') = шш Шл,))

(1.6)

(1 8)

где рл(7г,_ь 7i,) - вычислительная сложность получения цепи тг, из цепи л,_и получаемая как сумма вычислительных затрат на переходы из концевой вершины цепи тс,.| в концевую Берлину цепи п,

Для пятерки (и, к, щ, я, h{ir) I произведена классификация частных задач поиска оптимальных цепей на группы задач, инвариантных к носителю П„ к структур решений z

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

Во второй главе «Недетерминированные NP-полные системы» приведены идентификаторы NP-полных систем и построена модель потребления ресурсов В первом разделе второй главы в качестве идентификаторов NP-полных систем приведены общие структурные и функциональные признаки дискретных автоматов с памятью, специализированных для поиска состояния, переменные которого минимизируют целевую функцию (17)

1 Граф переходов состояний системы является деревом Г1„ обладающим структурными свойствами (1 l)-i 1 4)

2 Система содержит к дискретных однотипных комбинационных устройств, вычисляющих переменные состояния

3 Память состояний системы представляет собой стек с фиксированной глубиной к < п, который обслуживается стековыми операциями

4 Порождение цепей осуществляется известными операциями недетерминированного присоединения & Г1„,->П„,+| вершины ущ, выбираемой из выколотой окрестности N(v,)\i\(n,i), и детерминированного усечения ret П„, —> П„, | цепи

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

в терминах дискретной ЫР-полной системы и даны характеристики вычислительной сложности

В основу функционирования недетерминированной системы положен известный метод непрерывной оптимизации решения Процесс построения цепей к(п,к) еП,( из элементов й реализуется пошаговым управлением дискретной системой Состояние системы представлено тройкой = ((Т10, I — длина цепи, 7 - ранг вершины последнего

просмотренного потомка — состояния 5<,+1>, при отсутствии потомков ] = О Ст'] - состояние графа после исключения г ресурсов определяется рекурсивным соотношением С^ = и,.\}

Потребление ресурса и,+\ осуществляется операцией присоединения 7г(и,г+1) = п{п,1) & у,+1 и переводом ¡{1) —» 5<1+|) системы из состояния = я(п,1),у) в состояние = (С"+,), л(«,/+1), 0) При этом в стеке сохраняется состояние с модифицированным индексом потомка 5<') = (Ст'\ л(п,1), г+1) Возврат ресурса и, из цепи я(и,г) в граф С осуществляется операцией усечения цепи я(л,ь1) = ге1(я(л,/)), выталкиванием из стека состояния £('"|> = (С*'"1', л(п,1- 1),у) и переводом 5(|)—системы из состояния в состояние 5(И) с модифицированным индексом потомка ¿»1) = (&П\ я(Л,/-1), ;)

Приведены описания состояний системы

• Исходное состояние с пустой цепью (по включению или сбросу) С/0' = О, л(и,0) = ()

• Текущее состояния 5(|) Сг'} = }, л(и,/) = (уь у2, , V,.], V,)

• Конечное состояние а1*' (Ук) = }, л(п,к) = (уь у2, , уа)

• Предельное состояние для полной цепи к = п С*"'= {м„},

Л(П,П) = (У|, , У„Л, V,,)

Состояние — (<У°\ п(/7,г),у) для произвольного графа С"' может содержать ряд цепей из П„, Для явного различения состояний 5(|> = (Сг-'\ тг„(;7,/),/) и = (С*0, Я/,(«,/),_/) введен индекс состояния

s„U) = nm(n,i),j), где m = 1,2, ,|П„,| Система имеет обновляемую память текущего решения sik), содержащую цепь с наилучшим весом Функционирование системы прекращается при достижении состояния sjk) = ((jk\ лт{п,к), i), m = |п* При этом память системы будет содержать

цепь л\п,к) с весом, удовлетворяющим целевым функциям (1 7)~0 8) и ограничениям С, а структура решения буде г иметь вид z = K(x (п,к))

Предложено измерять вычислительную сложность поиска оптимального решения в единицах измерения вычислительной сложности перехода As = su) -» .r,+l) Показано, что сложность такого перехода 6(п) Для оценки эффективности алгоритмов рассмотрен известный показатель - удельная вычислительная сложность F(n,k), определенный в работе отношением количества Ns состояний s{,) системы, в кот орых она находилась при порождении всех цепей тС(п,к) из множества П(, к к количеству этих цепей

F{n,k) = Ah (2 1)

Приведены оценки величины F{n, к) Fmà\{n,k) = k

Характеристики функционирования недетерминированных NP-полных систем сформулированы в вице теорем

Лемма 2.1 С ростом к количество состояний системы N% растет быстрее, чем |П„ J

Теорема 2.1 Минимальная удельная вычислительная сложность F{n,k) произвольного алгоритма при порождении всех п(п,к) е П„*

F(n,k)<e (2 3)

Следствие 2.1 Управление порядком просмотра цепей п\п.к) е П*1;( в алгоритме "сначала вглубь", а также при лексикографическом переборе

является наиболее эффективным по критерию минимальной удельной сложности

Следствие 2.2 Управление порядком просмотра цепей к(п,к") в вероятностных методах поиска является наименее эффективным по критерию минимальной удельной сложности и равна F(n,k) = к.

Следствие 2.3 Приближенная оценка удельной вычислительной сложности при больших значениях ппк,к<п

Пп,к)«2е—-(Г(»-*,0)-Г(и-*,1)) (2 4)

(п-к-1)

Следствие 2.4 Вычислительная сложность поиска оптимальной цепи в области П* х лежит в пределах е < F(n,k) < к

Теорема 2.2 Вычислительная сложность оптимального поиска в области П* к hm F(n,k)^>e (2 5)

п к—мс

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

В третьей главе «Аппарат факториальных форм цепей» введена метрика в пространстве поиска В первом разделе третьей главы введено ранжирование упорядоченной окрестности ZV*(v,) - N(v,) \ %(n,i) вершины v„ посредством отображения его в равномощное упорядоченное множество рангов Уг = {г,, г2, ,/-„_|}, К с Z+ Аналогом данной окрестности являет-

ся окрестность в виде совокупности соседних состояний, введенная F Glover при разработке метода поиска с запретами и используемая Ерма-ченко А И , Усмановой А Р и Кочетовым Ю А для решения задач гильотинного раскроя Доказана теорема об обратимости ранжирования V<r> V* Введено понятие ранжированной цепи п(п, к) = (ri, r2, , r„ , гк) О < г, < n-i, как цепи, представленной рангами вершин последовательности v2, , v„ , vk) Ранжированные цепи позволяют абстрагироваться от весов q{v) и w(e) и исследовать влияние только рангов г на вес цепи к(л).

Задано детерминированное управление переходом s^—г'+] NP-полной системы на основе ранга перехода г,+1.

Во втором разделе третьей главы доказаны теоремы о единственности представления индекса т произвольной цепи пт в факториальной системе счисления (ФСС)

Лемма 3.1 Ранги цепи пт(п, п) = (г\, г2, , г„ , г„) явчяются коэффициентами ФСС с основанием (и—г)1

А = г,(п- 'У+г2(п-2)'+ +r„_t V, (3 1)

где п - число вершин исходного графа G, г, - ранг перехода, г - номер перехода

Теорема 3.2 Всем цепям irjn,k) - (гь г2, , гк.\) ран кированного дерева можно сопоставить единственное число т в ФСС

т = («-/)' (3 2)

Следствие 3.1 Отображение множества ранжированных цепей П,„, во множество jw | т = £ rt (п - /)'j является взаимно однозначным

Следствие 3.2 Индекс цепи п,„(п,к) = (ru i2, , г„ 0 с максимальными рангами г, определяется выражением >пт„ = -1

Следствие 3.3 В случае неполноты исходного графа G всем цепям кт(п,к) = (г|, /:, ,ik) ранжированного пространства поиска можно сопос-

тавить единственный индекс т в ФСС

Ранжированные цепи кт(п, к) = (ri, гг, , гк) на основе (3 2) представляются в виде чисел ФСС /= rti2 гк, названных факториапьной формой цепи (ФФЦ), г, -разряды ФФЦ

В третьем разделе третьей главы определена алгебра (М/, Z), ФФЦ на носителе М/= {/= г, r2 .г, г, | 0< г, < n-i v 0 > г, > i-n} с операциями Z = {+,-,л,Н} сложения, разности, поразрядного сравнения слева и выделения индекса старшего ненулевого разряда соответственно Определены свойства операций, формулы для определения расстояния между двумя ФФЦ и расчета вычислительны к затрат на переход между двумя произвольными состояниями системы Введена функция ф суммирования разрядов ФФЦ

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

В четвертой главе «Основы теории синтеза интеллектуальных NP-полных систем» предложена структура NP-полной системы, исследованы статистические закономерности распределения оптимальных решений в пространстве поиска и определены его свойства

В первом разделе четвертой главы описана структура NP-полной системы (рисунок 4 1), характерной особенностью которой является наличие генератора рангов и генератора ранжированных цепей Генератор рангов на основе операций алгебры ФФЦ осуществляет построение разрядов ri гг >"к, удовлетворяющих условию, накладываемому на оценку веса ранжированной цепи, что и определяет новизну предлагаемой системы Генератор цепей осуществляет построение ранжированных цепей я, удовлетворяющих условию h(n) < /г(и'), где я' - минимальная по весу цепь на данном шаге решения, хранимая в регистре. Конструктор К преобразует

цепь п' в структуру г, удовлетворяющую ограничениям С

Рисунок 4 1 - Структурная схема ЫР-полной системы

На рисунке 4 2 изображена структурная схема генератора цепей, содержащая к комбинационных устройств, выполняющих операцию ,<.'<?/(у„ У"\ г,+1, С), которая по рангу г,+\ определяег удовлетворяющую условиям С смежную к V, вершину у,+1 и усеченное множество = И'^у,}, а также операцию & поэлементного построй ния цепи п(п^)

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

ж, минимален Р|(/) = и функция отношения веса Ьтт наилегчайшей це-

1 " 11тт

пи к случайному весу цепи И(ж,) /?,(/) = — V———, где /У - общее количе-

N /?(л", )J

ство проведенных опытов, п, - число опь.тов, в которых вес цепи л, мини-

Га

мален, Максимальная дисперсия в эксперименте О —^ <0,025

Рисунок 4 2 - Структурная схема генератора ранжированных цепей

Выявлены свойства пространства поиска, основные из которых приведены ниже

1. Функция вероятности оптимальных групп 1]ф ФФЦ с равной суммой разрядов {иф\ф(/) = § фты} ПРИ п,к-> <ю аппроксимируется распределением Пуассона Р{ф) = сф— Достоверность выбранной функции под-

ф<

тверждается уменьшением среднего квадратического отклонения от с = 0,002 при п = 5 до ст = 0,0004 при /7=15

2 Случайная функция оптимальных значений рангов г, р каждом /-том разряде ФФЦ аппроксимируется геометрическим распределением

= $(1 - зу Достоверность выбранной функции подтверждается уменьшением среднего квадратического отклонения аппроксимации для п= 15 от ст = 0,004 при / = 1 до а = 0,000008 при / = 9

3 Принцип локальной оптимальности Беллмана ведет к статистически наилучшему решению Р12(/) = шах с ФФЦ /= 0,02 0* и при п,к —> со вероятность Р\ 20) -> 0

4 Субоптимальные решения локально равноудалены и их частота убывает по мере удаления от глобального статистического оптимума

5 Расстояние от ФФЦ/ до глобального статистического оптимума пропорционально сумме разрядов ФФЦ f-jо ~ $f)

6 Для задач с фиксированным к приращение Af = (n r2 А г, rk) в г-м разряде ФФЦ пропорционально индексу г-ro разряда Af ~ i

7 Для задач с произвольным к приращение Af, = (rt r2 А г, п) в г-м разряде ФФЦ пропорционально дополнению разряда до п Af, ~ n-t

Свойство №2 подтверждает тип окрестности экспоненциальной мощности, предложенный Кочетовым К) А и Усмановой А Р Свойство №7 уточняет характер окрестности локального оптимума в задаче поиска сумм подмножеств, решаемой при раскрое-упаковке N Soma и Р Toth, а также Валеевой А Ф при разработке алгоритмов динамического перебора На основании найденных закономерностей развиты и разработаны методы построения окрестностей СГО

1) Вероятностный метод построения ФФЦ в окрестности СГО на основе к датчиков случайных чисел с геометрическим распределением весовых коэффициентов для каждого разряда ФФЦ Данный метод уточняет и развивает вероятностную схему Усмановой А Р

2) Метод рекуррентного построения ФФЦ/ в окрестности СГО П, в общем случае с неубывающим целочисленным шагом

п ,={/„/\/, =/. +Гд/(01ь где Aft) полином отДО

3) Метод построения ФФЦ в окрестности СГО П2 с фиксированной верхней границей Ф суммы разрядов ФФЦ П2 = {f \ ф(]]) < Ф} Для случая строго равенства П2 = {f \ tj>(f,) = Ф} предложенный метод разделяет все пространство поиска на непересекающиеся области и этим подобен чередующимся окрестностям, введенным Кочетовым 10 А, Младеновичем Н и Хансеном П

На рисунке 4 3 привеДена функция вероятности цепей л(5,5) имею-

щих наименьший вес при разных стратегиях просмотра цепей. На рисунке 4.4 изображена случайная функция отношения среднего заданного веса йц к весу цепи я;(10,£) произвольной длины к от индекса цепи i в задаче о поиске сумм подмножеств |А(л,-) - Aol min. рассматриваемую N. Soma и P. Toth как вспомогательную задачу поиска критической детали в фазе предварительной подготовки к генерации раскроя.

pi

0,25 0,2 0,15 0.1 0,05 О

Л-- _4_г1=2 —»—[-1=3

1

\ ,

в)

Рисунок 4.3 - Функция вероятности Р\ при просмотре цепей а) в лексикографическом порядке; б) в порядке чередования окрестностей с Ф = 0 .. 6; в) по убыванию Р\

а)

б)

Р2 0,96 0,92 0.88 0,84 0.8

i 1 N

50 100 150

Рисунок 4.4 — Случайная функция Я2(г) при просмотре цепей а) в лексикографическом порядке; 6) в порядке возрастания суммы рангов ф= 0,1,.../; в) по убыванию Р2

На рисунке 4.5 приведены результаты сравнительных испытаний метода построения ФФЦ окрестности СГО с верхними границами Ф=1, Ф = 2, Ф = 3 и методов Шермана-Рейтера и Лина, специализированных для

поиска цепи с минимальным весом h{7t) = w(e,) Принята величина

нижней границы hmm = (е/)> гДе wr(e,) - вес ребра ранга г,

h, 55

35

25

—К— Теор оценка __| -*-Ф=2 | —Q—Шерман ФИ Ф=3 Лин

* и | *_> .. t „ --1--

20

40

60

инцидентного вершине V, Построение ФФЦ окрестности СГО с Ф=1, содержащая п+\ цепей, превосходит результаты, полученные методами Шермана-Рейтера и Лина по весу И,(п,п+1), в 1,5-2 раза С ростом размерности ис-120 п ходных данных эффективность метода построения ФФЦ с фиксированной суммой разрядов воз-

Рисунок 4 5 - Сравнение методов по весу цепи /:,{«,«+1)

растает

Третий раздел четвертой главы посвящен разработке метода расширения ранжированной окрестности статистического оптимума, роль которого играет цепь с/= 0, т е цепь, полученная по принципу локальной оптимальности Беллмана Введена функция оценки веса ранжированной цепи от ее рангов и индексов

hr(7T(n,k)) = t—И

(4 1)

, = |И-/ + 1

где 0 < г, < п-1 Данный метод является расширением метода "ветвей и границ" для случая ранжированного пространства поиска и установленной оценки веса ранжированной цепи (4 1) Суть метода заключается в построении окрестности СГО П°„к, содержащей в лексикографическом порядке только те цепи %{п,к), вес которых не превышает априорно заданного порога И„{я(п,к))

П^, = \с(п,к) | )/{ж{п,к)) < А0'(я-(я,Л))}. (4 2)

где й^ш(;г(и,А:)) < И^(тг(п,к)) < к Лексикографический порядок минимизирует вычислительные затраты при построении цепей окрестности Найдено точное значение нижнего порога

кгтт (гг(и, к)) ---- у/{п +1) - ц/{п - к +1),

где 1//(г) = — 1пГ(г), С - постоянная Эйлера-Маскерони,

и найдены приближенные оценки нижнего порога

/С Ог(и,*)) « , Утт {л{п,п))* 1п(и +1) + С

п - к +1

Для Ьд(л(п,к)) = Игтт(п,к) + АИг и среднего приращения

лГг к-у/(п + \) + у/{п-к + \) ,

дй =--/>'

(п-ку

введена оценка величины кг0{л{п,к)) при известном количестве д проверяемых цепей

ЬЦя(п,к)) = И^\)-Ип-к + 1)Ня-1) —'Яп + 1) + Ч'{п-к + \) {п_к)х

п'

а также при известной доле с1 проверяемых цепей

Иц{я(п,к)) = й к + {\-с1) ц/(п ++ ь/{п-к +1)

В диссертации показано, что отношение количества цепей окрестности П° к количеству цепей тс°еП°, удовлетворяющих (1 6), то есть л°еП , подчиняется равенству

И

1ип т—----1-^ = 1

На рисунке 4 6 приведена функция вероятности оптимальных цепей в пространстве поиска задачи, описанной для рисунка 4 3, и упорядоченных согласно (4 2), Ига{5,5)- Игтт +АЬ', Ьгтт — вес ранжированной цепи с /= 0 На рисунке 4 7 приведена функция вероятности оптимальных цепей в задаче, описанной для рисунка 4 4, но упорядоченных согласно (4 2),

/?о (Ю,&) = Игтт- А Аг, 4,9. На рисунке 4.8 показаны результаты срав-

нительных испытаний метода расширения ранжированной окрестности статистического оптимума при д = п, 5и, 10« и методов Шермана-Рейтера и Лина по значению весовой функции А(и,и~1).

Рисунок - 4.6 Функция вероятности Р\ в окрестности СГО при а) А/г = 0,5; б) ДА = 0,8; в) ДА = 1

А

-|нта х-0.21— — -

0 5 10 15 20 ( б)

0 15 30 45 I а) 0) в)

Рисунок 4.7 - Функция вероятности Р2 в окрестности СГО при а) ДА = -0,1; б) ДА = -0,2; в) ДА = -0,3

20 40 60 80 100 120 п

Рисунок 4.8 - Сравнение методов по значению А(л,л+1)

Особенностью использования разработанных методов является постепенное улучшение текущего субопт имального решения, что позволяет завершать поиск либо по времени, либо по количеству/доле просмотренных цепей, либо по достижению заданного порога целевой функции (1 7), либо по завершению построения окрестности СГО П° 4, удовлетворяющей (4 2) В заключение четвертой главы сделан вывод о том, что разработанные методы с помощью алгебраических преобразований над разрядами ФФЦ г, г,+1 позволяют задавать детерминированные ранжированные переходы ———ИР-полной системы, в результате чего последняя приобретает свойства ИС характерные для оракула НМТ

В пятой главе «Методы синтеза прикладных интеллектуальных ЫР-полных систем» приведены специализированные методы для решения задач раскроя-упаковки Исходные данные представлены в виде множества материалов М= [т | т={Ь,IV,К)}, где Ь - длина, Ж - ширина, К - количество листов с параметрами IV, множестве! деталей 0={с1, \ с!=с1{х,у,ог,к), х<Ь,

у<\¥, ог= 0,1, ¿еМ, «=1„. ,«}, где л: - длина, у - ширина, ог - ориентация

ог — 0 - разрешение поворотов, ог — 1 — запрет поворотов, к - количество деталей с параметрами х,у,г, и - ассортимент деталей Явные условия непересечения деталей на карте раскроя замещены такой структурой К представления карт раскроя, которая исклю^ ает подобные коллизии

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

X У,

г,=-1т2>">'-1). • (5 1)

а 1 ,

К

е-1 ,

e'W-^-l), (5 2)

где Я, - площадь г-го остатка, £= Ы¥(\ - г]), Л — коэффициент чувстви-

1

тельности к соотношению плошади материала и площади деталей, 0<Я<1, 0<^<1, 0<к<1, 0<г<1 Целевая функция (1 7) при этом принимает вид функционала

п-\

/г(М,ДД) = шах^(ог7, +/к,+ут )+ шах т„, (5 3)

где сх,р,у- экспертные коэффициенты приоритетов

Во втором разделе пятой главы разработан метод автоматической адаптации экспертных коэффициентов аф,у к исходным данным М и й Данный метод основан на преобразовании (вх —> (аф,у) показателей крупности деталей в и их разнообразия £ в тройку аг,Д/

а(в,& = в?-0 +1, ß(e,Z)=-et + 0, где /(*,£) = -0,5 +

0 = -

* = ylnf ^(VlOVO^W,) + , ' М I cr(I.ff')

0< 6>< 1 ГТри CTjnax(*,J7) — c(L,W) справедливо

0<£< 1

В третьем разделе пятой главы расширен мегод повышения многообразия решений на основе использования семейства эвристик выбора очередного детали Q Для вектора параметров Р=(л,>>) множество Q построено экспертным путем и содержит помимо известных эвристик с одной координатой - {NFDL, FFDL, BFDL}, веденных A Loch, S Mari ello и D Vigo, ряд эвристик, расширяющих q(y) до множества весовых функций П = {maxívy), max(.x+v), (xI71IX vmin), (rimn jw), max(\ + ln.y)}

Сделано заключение о том, что в задачах поиска оптимальных структур кат раскроя рассмотренные методы являются метаэвристиками, повы-

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

В шестой главе «Синтез прикладных NP-полных систем» рассмотрены конструкторы структур карт раскроя, а также разработаны ИС для решения типовых задач раскроя-упаковки В первом разделе шестой главы описан конструктор карт раскроя для задачи гильотинного раскроя

(2DCSP), представляемый композицией ® иерархических структур k¡(X,Y),

i

i - уровень иерархии, j 6 {hor, ver} - ориентация реза, разделяющего структуры Отличием предлагаемого конструктора от рекурсивного метода с неявным перебором фрагментов карт, разработанного Ермаченко А И и Сиразетдиновым Т М, является то, что разрешенные структуры задаются семейством экспертно перечисляемых нерекурсивных уравнений, а также то, что полная карта раскроя строится не один раз, а столько, сколько уравнений k0(L,W) на верхнем уровне иерархии Верхний уровень иерархии задает многообразие карт раскроя, в виде семейства композиций ® из« конструкторов горизонтальных и вертикальных слоев кг, введенных Мухаче-вой Э А , располагаемых в экспертно задаваемой последовательности, при этом прямоугольный остаток (L-IX, W-H.Y) заполняется либо всеми горизонтальными слоями ®kx{L~Y^X,W-^Y), либо всеми вертикальными

hor

слоями ®kx{L~Y,X,W-YJ)

\ег

\k0{L,W) = ®,{к2(.X, Y))® к,(L - XXta., W -£ Yhor), j 1

' к, (L, W) = ®„ (k2 (X, Y)) ® (L - £ Xver, W - £ Yhnr), j '

k0(L,W) = £

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

т

к2(иУ) = ®к2(Х,Г), ]

т

где ®кг{Х,У) -т-арная композиция доменов кг(Х,Т), ограниченная пара)

метрами Ь и ¡V родительской структуры кг{Ь,\У) Домен к^{Х,У) - элемент структуры слоя, ограниченный двумя координатами Нижний уровень иерархии занимают терминальные домены к4(Х,У) - элементы множества Д которые и задают разметку карты раскроя координатами деталей к4(Х,У)п = с1(х,у,к\ при к>\,Х>кх, У>у, к4(Х,У)п = с1(х,у,к), при к>\,Х>х, Г>ку, НХ,У)а = е,

где О - критерии выбора терминальных доменов

В работе оценена вычислительная сложность построения одного варианта карты раскроя 20СБР, содержащей п деталей

F(n,í,M,Д,S)*!(e-l) — -Я М5,

где Г - арность доменов, М- количество вариантов конструкторов доменов, К - количество вариантов конструкторов слоев, 5 - среднее число доменов в слое Разработана структурная схема интеллектуальной ЫР-полной системы для решения 20СБР (рисунок 6 1), воплотившая как универсальный аппарат ранжированных цепей, так и специализированные для ортогонального раскроя методы оптимизации по структурным показателям, адаптации к исходным данным и многообразия эвристических весовых функций П

Многопроходный режим функционирования ИС, определяемый набором различных четверок (аф,у,Х), позволяет использовать параллельные языки и вычислительные системы Номенклатура и количество исходных данных не имеют принципиальных методологических ограничений и зависят только от ресурсов ЭВМ. ИС обладает новыми функциональными свойствами вариативность последней карты раскроя, произвольное направление первого реза, учет недоступных зон Последнее свойство явля-

ется важным при внедрении ИС на предприятиях с ограниченной рабочей зоной перемещения материала вокруг станков

БД ресурсов

Блок адаптации к исходным данным

hr(m) 3.

i 1

Г-» Генератор ФФЦ Параметры

Б ток структурных показателей

и управления

1— о 1 1

Конструктор структур ---

1

Пе ременные состояния f,_к, Стек Вычислитель V—1 состояний целевой функции <Ъ>т

Рисунок 6 1 — Структурная схема ИС ортогонального раскроя

Реализованная в среде Visual-Prolog 5 2 ИС оптимизации 2DCSP эксплуатируется на ряде предприятий мебельной промышленности Краснодарского края (компания СБС, ООО ГЖП БАКАУТ) с 2000 г Достигаемый коэффициент использования ресурсов на отдельных картах раскроя rj» 97%, относительный полезный эффект в сравнении с существующими многочисленными системами оптимизации 2DCSP на мелко и среднесерийном производстве при большом ассортименте деталей Л/7,фог < 3%, относительный полезный эффект г. сравнении с ручным кроем Д>7р>чн ~ -2 - 11% в зависимости от размерности исходных данных

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

m(L,W) = {dot(l„w,) | /0 = 0,1, > /,_„/тал = £,vvmm = 0,и>1гах = Щ, ^ ^ Q{L, W) = {corner, | corner, = (dot(l,, w,), dot(lni, w,), dot, (/,+1, w,+1))},

где m(L,W) - упорядоченное множество координат угловых точек dot(l,w) ортогональной ломаной линии Q(L,\V) текущего реза, corner, — элемент ломаной линии Q{L,W) Данная модель расширяет многообразие форм раскраиваемого материала, так как с произвольной степенью точности аппроксимирует криволинейные трапеции ломаной Q, что позволяет рас-

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

1) Правила, определяющие различные стратегии раскроя с помощью троек весовых коэффициентов (a,ß /)„ каждая из которых определяет решение z, с кортежем (г]„к„т,)

2) Правила, определяющие многообразие 7} вариантов раскроя z:J материалов и остатков путем декомпозиции дерева поиска на страты Г= sup {Tj \ Т = {Г,*1, Г2*2, ,Т'', } } j - поддеревья поиска, ограниченные

max( F)

по глубине к, ветвями

3) Правила Н,к, служащие для заполнения калдой страты Тк = sup ,#*} и определенных на множестве Q критериев вы-

тах(У-)

бора деталей

4) Эвристики Л = {тах(У), тах(Т), max(L-X^.ax.,)} выбора домена размещения k(X,Y) Эвристики Л расширяют известную безуровневую стратегию "нижний-левый" тах(У), проанализированную В Baker, J Coffman и R, Rivest, эвристиками "максимально широкий" тахДО и группой эвристик соединения правых смежных доменов (max(L-XmavI), тах(1-Л'тах.2), max(L-Xmav,)} Домен k(X,Y) - прямоугольник (Y,Y), определенный в модели (6 1) в виде суммы j смежных элементов corner с размерами

j

Х = "£Ы„ y = mm(w„w1+1, ,w,) i

5) Эвристики P={PuPj, ,Pj), задающие правила выбора направления прижима детали (д\)>) в домене Loc(X,Y) и операцию отсечения детали cut

6) Операция сглаживания линии ре ¡a smooth QxD->Q В случае, когда все фрагменты меньше любой детали в массиве D, линия реза переходит в конечную форму m= \ Jot(L,0)}, что является признаком достижения терминальной вершины дерева поиска карты раскроя

В работе приведена оценка вычислительной сложности решения задачи 2DBPP

F( К', к', и, F) = и log« 4 ктк'{К 'F - F +1) « и log и + kmk'K'F,

и

где к' = —удвоенное количество деталей, обусловленное их ловоро-

/=1

том, К' =2K+kR - удвоенное количество листов материала, обусловленное их поворотом, и число производственных остатков kR, F — число карт раскроя Коэффициент kNB=ka кТ g кн к, кп кр характеризует ширину поиска на дереве решений. ка — число проходов, кт — количество вариантов конструкторов листа материала, g - среднее число конструкторов на листе материала (зависит от конкретных исходных данных), кн — количество правил заполнения страт, kL - количество правил выбора доменов, кп - количество правил выбора детали для домена, кР - количество правил прижима детали в домене В реализованной ИС kNB в 4 104

На рисунке 6 2 изображена структурная схема БЗ, соответствующая структуре и свойствам пространства поиска задачи 2DBPP Реализованная в среде Visual-Prolog 5 2 ИС оптимизации упаковки деталей из природных минералов эксплуатируется на предприятии «Хозяйка медной горы» г Краснодара с 2006 г Коэффициент использования ресурсов на отдельных картах раскроя в зависимости от ассортимента деталей rj ~ 98%, относительный полезный эффект в сравнении с существующими системами оптимизации 2DBPP на мелкосерийном производстве Дт7прог< 1,5%, относительный полезный эффект в сравнении с ручным кроем Д/7РУчн ~ -1 -9% в зависимости от размерности исходных данных

В третьем разделе шестой главы процесс нестинга сведен к композиции двух преобразований D -> К <> К -* Ка Первое есть преобразование D —> К исходного множества D деталей произвольной формы во множество пакетов К = {ку{х\,у\J(\), к2(х2^2,К2), , к,{х„у„К,)} прямоугольной формы

Рисунок 6 2- Структурная схема БЗ

Пакет к(х,у,К-р) - рекурсивное представление подмножества деталей, занимающих прямоугольную локальную область Pxv карты раскроя с размерами х,у, родителем которой является деталь d(x,y, Р), Р - полигон, описывающий конгур детали, К- - множество дочерних пакетов и дета-

лей, размещенных во множестве локальных областей Р = {P¡,P2, ,Р,} родительской детали, которые дополняют полигон Р до прямоугольного полигона Рху, то есть для них выполняется объединение Рх = Р U Р

Преобразование К—> Ко применягтся как при упаковке карты раскроя в целом, так и при упаковке локальной области Pt отдельной детали Оно осуществляется последовательным сведением кривой текущего реза Q(L, W) карты раскроя или кривой реза Q(l, w) локальной области в соответствующие отрезки Q(L, 0) или Q(l, 0) операциями алгебры на множестве точек dot(l, w) и деталей d{x, у, Р) и one рациями Y разности Р = Рх \Р и

объединения Р, „ = Р U Р на множестве полигонов

Ограничением принятой модели гвляется условие описания формы раскраиваемого материала и Р, всех деталей в виде криволинейных трапеций, описанных ортогональной ломаной линией Q{L, W) Допущением принятой модели является представление произвольных криволинейных фигур описывающими их полигонами

ИС для решения задачи нестинга имеет структурную схему и реализацию подобную 2DBPP с дополнительными операциями Т разности и объединения полигонов на четвертом уровне иерархии БЗ Реализованная в среде Visual-Prolog 5 2 ИС нестинга деталей из природных минералов эксплуатируется на предприятии "Хозяйка медной горы" г Краснодара с 2006 г Коэффициент использования ресурсов в зависимости от ассортимента деталей r¡~ 87-94%, приведенный полезный эффект в сравнении с ручным кроем Д/7ручн «-4 - 8% в зависимости от размерности исходных данных Достоинством ИС нестинга является возможность использования режущего оборудование как с прямолинейным, так и с криволинейным резом ("water-jet"), а также дополнительные функции выбора профилей и технологических операций с учетом допусков оборудования

Полученные результаты позволяют сделать вывод о решении важной

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

В заключение диссертации приведены основные результаты и выводы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

ским законом распределения значений разрядов

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

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

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

5 Структурные характеристики <арт раскроя, учитывающие размеры составляющих элементов, перераспределяют оценки карт раскроя таким образом, что позволяют обходить локальные оптимумы, при этом кортежи экспертных коэффициентов, определяющих приоритеты структурных и неструктурных показателей карт раскроя, повышают многообразие карт раскроя и з целом повышают коэффициент раскроя-упаковки 9 Для задачи двухмерного гильотинного раскроя введенные конструкторы структур карт раскроя на ранжированных цепях повышают коэффициент раскроя на отдельных картах до величины г] « 97% для исходных наборов деталей большого ассортимента, и дают превышение среднего коэффициента раскроя по сравнению с существующими методами решения 20С8Рдо Д/7<3%

10 Для задач двухмерной негильотинной упаковки принятая модель раскраиваемого материала и введенные конструкторы структур карт упаковки повышают коэффициент упаковки на отдельных картах до величины r¡« 98, при широком ассортименте деталей, и дают превышение среднего коэффициента раскроя по сравнению с существующими методами решения задачи 2DBPP до Дг;< 1,5%

11 Сведение задачи несгинга к задаче негильотинной упаковки криволинейных трапеций позволяет использовать карты раскроя криволинейных фигур на отечественных предприятиях, которые не оборудованы режущим инструментом типа water-jet с произвольным резом

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

4 Марков В. Н. Редукция порождающего графа в NP-проблемах // Известия вузов Сев-Кавк регион Техн науки 2004 Спец выпуск - с 51-53

5 Ключ ко В. И., Марков В. И. Решение NP-проблем в алгебре компактных контейнеров // Известия вузов Сев -Кавк регион Техн науки 2005 Приложение №2 - с 54-58 (Марковым В Н определена алгебра компактных контейнеров для управления поиском решения /VP-полных задач)

6 Марков В. Н. Оптимизация линейных контейнеров // Известия вузов

Сев -Кавк регион Техн науки 2005 Приложение №3 - с 5-9

7 Ключ ко В. И., Марков В. Н. Субоптимальные решения NP- задач за полиномиальное время // Информатика и управление Труды КубГТУ Том XXV Краснодар 2005 - с 153-156 (Марковым В H приведено обоснование использования алгебры компактных контейнеров для управления поиском решения в пространстве состоя'гай с полиномиальной зависимостью времени решения NP-задач от их размерности)

8 Марков В. Н. Распределение индексов функции выбора в оптимальных циклах Гамильтона // Информатика и управление Труды КубГТУ Том XXV Краснодар 2005 -с 176-178

9 Марков В. Н. Оценка вычислите 1ьной сложности вершинного обхода графа // Информатика и управление Труды КубГТУ Том XXV Краснодар

2005 -с 129-130

10 Марков В. Н. Синтез NP-полных систем//Информатика Математика Моделирование Методика Сборник трудов ИНЭП. Краснодар 2007 -с 29-39

11 Markov V. The intellectual system for orthogonal cutting-packing // VIP-ALC'06 — Proceedings of the First Visual Prolog Applications and Language Conference Faro-Portugal. 2006 P 34-41 URL http//www visualprolog com/conference2006/speakers-subjects htm

12 Марков В. H. Гильотинный раскрой с использованием технологии баз знаний // Высокие технологии, фундаментальные и прикладные исследования, образование Сборник трудов II международной НПК Том 4 СПб

2006 -с 302-304

13 Марков В. Н. Порождение эвристик для приближенного решения NP-трудных задач // Высокие технологии, фундаментальные и прикладные исследования, образование Сборник трудов II международной НПК Том 4 СПб 2006 -с 44-45

14 Марков В. Н. Оценка применения ранжированных цепей дня приближенного решения NP-трудных задач // Высокие технологии, фундамен-

тальные и прикладные исследования, образование Сборник трудов II международной НПК Том 4 СПб 2006 - с 45-47

15 Марков В. Н. Архитектура интеллектуальных систем для решения NP-трудных задач с ресурсами /'/ ИнтеллектуалЕ.ные системы Труды седьмого международного симпозиума Москва 2006 - с 423-427

16 Марков В. Н. Эвристический поиск в пространстве решений NP-трудных задач // Интеллектуальные системы Труды седьмого международного симпозиума Москва 2006 - с 427-431

17 Марков В. Н. Синтез интеллектуальных NP-полных систем // Исследование, разработка и применение высоких технологий в промышленности Сборник трудов III международной НПК Санкт-Петербург 2007 -с 247-248

18 Марков В. Н. Ранжирование решений NP-полных задач методом обратных приращений // Исследование, разработка и применение высоких технологий в промышленности Сборник трудов III международной НПК Санкт-Петербург 2007 - с 249-250

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

20 Марков В. Н. Экспертная систсма негильотинного раскроя-упаковки // Кибернетика и высокие технолоши XXI века Сборнит докладов VIII Международной конференции Воронеж 2007 - с 123-133

21 Ващенко И. В., Марков В. Н. Идентификация NP-полных систем // Современные информационные технологии Сборник научных трудов НТК Пенза 2007 - с 88-93 (Марковым В Н выполнена общая постановка задачи, приведена формальная идентификация NP-полной системы как дискретной системы потребления ресурсов со стековой памятью состояний, а также приведена детерминированная модель дискретной системы потребления ресурсов на основе генератора ранжированных цепей)

Подписано в печатьо-г.^о ЬопГг. Зак № Тираж уод

Типография КубГТУ, 350053 Коасчодар, Старокубанская, 88/-1

ВВЕДЕНИЕ.

1. ОБЩАЯ ПОСТАНОВКА ПРИКЛАДНЫХ NP-ПОЛНЫХ ЗАДАЧ С

НЕЯВНОЙ ФОРМОЙ ПРЕДСТАВЛЕНИЯ РЕШЕНИЯ.

1.1. Класс NP-полных задач, допускающих приближённое решение.

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

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

1.2. Анализ методов решения NP-полных задач.

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

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

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

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

1.3.2 Представление решения NP-трудной задачи потребления ресурсов

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

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

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

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

2 НЕДЕТЕРМИНИРОВАННЫЕ NP-ПОЛНЫЕ СИСТЕМЫ.

2.1 Идентификаторы недетерминированных NP-полных систем.

2.1.1 Алгебра цепей.

2.1.2 Идентификаторы недетерминированных NP-полных систем.

2.2 Идентификация недетерминированных NP-полных систем.

2.2.1 Модель потребления ресурсов со стековой памятью состояний.

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

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

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

3 АППАРАТ ФАКТОРИАЛЬНЫХ ФОРМ ЦЕПЕЙ.

3.1 Ранжированные цепи.

3.1.1 Ранжирование окрестности концевой вершины цепи.

3.1.2 Ранжирование окрестности состояния дискретной системы.

3.1.3 Ранжирование цепей.

3.1.4 Ранжированный граф переходов дискретной системы.

3.2 Факториальная форма представления цепей.

3.2.1 Арифметизация ранжированных цепей с переменным количеством разрядов.

3.2.2 Факториальная форма цепей.

3.2.3 Восстановление ФФЦ цепей по индексу.

3.3 Алгебра ранжированных цепей.

3.3.1 Алгебра факториальных форм ранжированных цепей.

3.3.2 Метрика пространство поиска.

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

4 ОСНОВЫ ТЕОРИИ СИНТЕЗА ИНТЕЛЛЕКТУАЛЬНЫХ NP-ПОЛНЫХ

СИСТЕМ.

4.1 Синтез структуры интеллектуальных NP-полных систем.

4.1.1 Режим анализа решений ПЗ.

4.1.2 Режим синтеза решений ПЗ.

4.2 Анализ решений ПЗ.

4.2.1 Исследование распределений весов решений.

4.2.2 Свойства пространства поиска.

4.2.3 Методы построения окрестностей СГО

4.3 Метод расширения ранжированной окрестности статистического глобального оптимума.

4.3.1 Приведённое приращение весовой функции.

4.3.2 Оценка весовой функции.

4.3.3 Расширение ранжированной окрестности СГО.

4.3.4 Оценка состояний дискретной системы по уравнениям состояний Колмогорова.

4.3.5 Оценка эффективности метода расширения ранжированной окрестности

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

5 МЕТОДЫ СИНТЕЗА ПРИКЛАДНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ NP-ПОЛНЫХ СИСТЕМ.

5.1 Метод оптимизации по структурным показателям.

5.2 Метод адаптации весовых коэффициентов к исходным данным.

5.3 Метод повышения многообразия решений.

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

6 СИНТЕЗ ПРИКЛАДНЫХ NP-ПОЛНЫХ СИСТЕМ.

6.1 Синтез интеллектуальных NP-полных систем ортогонального гильотинного раскроя-упаковки.

6.1.1 Послойные схемы.

6.1.2 Доменные схемы.

6.1.3 Оценка вычислительной сложности.

6.1.4 Реализация интеллектуальной системы 2DCSP.

6.2 Синтез интеллектуальных NP-полных систем ортогонального негильотинного раскроя-упаковки.

6.2.1 Модель раскраиваемого материала.

6.2.2 Иерархия правил базы знаний.

6.2.3 Оценка вычислительной сложности.

6.2.4 Реализация интеллектуальной системы 2DBPP.

6.3 Синтез интеллектуальных NP-полных систем криволинейного раскроя 285 Выводы по главе 6.

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

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

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

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

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

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

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

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

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

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

2. Введение метрики в пространство поиска решений и экспериментальное исследование распределения оптимальных решений.

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

4. Разработка основ теории синтеза интеллектуальных NP-полных систем.

5. Разработка методов синтеза прикладных интеллектуальных NP-полных систем и конструкторов структур решений задач ортогонального (2DCSP,

2DBPP) и криволинейного раскроя-упаковки.

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

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

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

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

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

В диссертационной работе впервые:

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

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

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

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

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

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

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

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

Интеллектуальная система оптимизации ортогонального гильотинного раскроя, эксплуатируемая с 2000 г. на ряде предприятий мебельной промышленности Краснодарского края (компания СБС, ООО ПКП БАКАУТ), позволяет использовать ресурсы с коэффициентом rj < 97% на отдельных картах раскроя. При этом относительный полезный эффект в сравнении с существующими многочисленными аналогами на мелко и среднесерийном производстве Лт7прог^З%, относительный полезный эффект в сравнении с ручным кроем Л?7ручн м -2 -ь 11% в зависимости от размерности исходных данных. Время кроя сокращено в десятки раз по сравнению с ручным кроем. Кроме этого в качестве полезного эффекта можно считать сокращение персонала и, как следствие, экономию фонда заработной платы.

Интеллектуальная система оптимизации ортогональной негильотинной упаковки и упаковки криволинейных деталей из природных минералов, эксплуатируемая 2006 г. на предприятии «Хозяйка медной горы» г. Краснодара, позволяет использовать ресурсы с коэффициентом rj < 87-^98% на отдельных картах раскроя в зависимости от ассортимента деталей. При этом относительный полезный эффект в сравнении с существующими аналогами на мелкосерийном производстве Л77прог< 1,5%, относительный полезный эффект в сравнении с ручным кроем А г]ручн « -4 -г- 9% в зависимости от размерности исходных данных. Время кроя сокращено в десятки раз по сравнению с ручным кроем. На защиту выносятся следующие основные положения:

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

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

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

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

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

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

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

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

Результаты исследований докладывались и обсуждались на международных симпозиумах и конференциях, в том числе за рубежом. Результаты диссертации опубликованы в 21 работе, из них шесть в ведущих периодических изданиях, рекомендованных ВАК РФ, четыре статьи в сборниках трудов ВУЗов, 11 работ в сборниках трудов международных симпозиумов и конференций.

Диссертация выполнена на кафедре вычислительной техники и автомата

17 зированных систем управления (ВТ и АСУ) ГОУ ВПО "Кубанский государственный технологический университет" (КубГТУ).

Автор выражает признательность своему научному консультанту профессору В.И. Ключко и всему коллективу кафедры ВТ и АСУ за доброжелательность и участие в обсуждении вопросов, возникших в ходе исследований, технологам компании "СБС", ООО "БАКАУТ" и коллективу ИП "Хозяйка медной горы" за обсуждение практических вопросов выявления эвристик оптимального ручного раскроя, директору ООО "Пролог Девелопмент Сентер СПб" В А. Юх-тенко за обсуждение практических вопросов разработки промышленных экспертных систем, а также директору фирмы Prolog Development Center Лео Йен-сену и техническому директору ВА. Юхтенко за свободное предоставление лицензионных систем программирования Visual Prolog 5.2 и Visual Prolog 7.0.

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

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

В задаче двухмерной негильотинной упаковки (2DBPP) модель раскраиваемого материала представлена криволинейной трапецией, которая описывается ортогональной ломаной линией реза, конструкторы решений представлены в виде страт - множества цепей фиксированной длины, многообразие выбора доменов и размещаемых деталей обеспечено статистически обоснованной границей ранжированной окрестности локального оптимума, что в целом позволяет увеличить многообразие субоптимальных упаковок и за счёт этого повысить коэффициент упаковки на А г/< 1,5%.

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

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

293

ЗАКЛЮЧЕНИЕ

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

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

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

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

Аппроксимация случайной функции разрядов ФФЦ позволяет на основе NP-полных систем реализовать вероятностный перебор цепей п(п,к) посредством к независимых датчиков случайных чисел с научно обоснованным для данной задачи геометрическим законом распределения значений разрядов.

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

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

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

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

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

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

Для задачи двухмерного гильотинного раскроя введённые конструкторы структур карт раскроя, основанные на иерархии послойных и доменных схем на ранжированных цепях повышают коэффициента раскроя на отдельных картах до величины rj« 97% для исходных наборов деталей с большим ассортиментом, и дают превышение среднего коэффициента раскроя по сравнению с существующими методами решения 2DCSP до Л 77 < 3%.

Для задач двухмерной негильотинной упаковки принятая модель раскраиваемого материала и введённые конструкторы структур карт упаковки повышают коэффициент упаковки на отдельных картах до величины 77» 98 и дают превышение среднего коэффициента раскроя по сравнению с существующими методами решения 2DBPP до Л 77 < 1,5%.

Сведение задачи криволинейного раскроя к композиции двух преобразований: исходного множества деталей во множество прямоугольных пакетов и последнего в карты раскроя на основе технологии двухмерной негильотинной упаковки позволяет использовать карты раскроя криволинейных фигур на тех отечественных предприятиях, которые не оборудованы режущим инструментом типа water-jet с произвольной линией реза.

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

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

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

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

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

3. Алгоритмы и программы решения задач на графах и сетях / Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Новосибирск: Наука. СО, 1990. -515 с.

4. Александров Е.А. Основы теории эвристических решений. М.: Наука, 1975.-291 с.

5. Амелькин В.А. Методы нумерационного кодирования. Новосибирск: Наука, 1986.- 155 с.

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

7. Анисимов А.В. Об оптимальной упаковке деревьев // Кибернетика. 1976. №3.-с. 89-91.

8. Анисимов А.В., Карпенко И.В., Крижановский В.В. Представление упорядоченных деревьев // Кибернетика. 1980. №3. с. 29-34.

9. Арбиб М. Алгебраическая теория автоматов. М.: Статистика, 1975. - 312 с.

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

11. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: Наука, 1989. - 159 с.

12. Басакер Р., Саата Т. Конечные графы и сети. М.: Наука, 1974.

13. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач. Учеб. пос. / Под ред. Я.Е. Львовича. — Воронеж: ВГТУ, 1995. — 96 с.

14. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. -М.: Наука, 1997, 368 с.

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

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

17. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. Для вузов / Под ред. Зарубина B.C., Крищенко А.П. 2-е изд., стер. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 744 с.

18. Бендат Дж., Пирсол А. Прикладной анализ случайных данных. М.: Мир, 1989.-287 с.

19. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. М.: Мир, 1990. - 560 с.

20. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. 13-е изд., испр. - М.: Наука, Гл. ред. физ.-мат. лит., 1986. - 544 с.

21. Будущее искусственного интеллекта: Сборник / АН СССР; Ред. сост. К.Е.

22. Левитин, Д.А. Поспелов М.: Наука, 1991. - 301 с.

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

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

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

26. Ван дер Варден. Б.Л. Алгебра. Пер. с нем. М.: Наука, 1979. - 624 с.

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

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

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

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

31. Воинов А., Гаврилова Т. Инженерия знаний и психосемантика: Об одном подходе к выявлению глубинных знаний // Известия РАН. Техническая кибернетика. 1994. №5. с. 5-13.

32. Волков A.M., Ломнев B.C. Классификация способов извлечения опыта экспертов // Известия АН СССР. Техническая кибернетика. 1989. №5. с. 34-45.

33. Выявление экспертных знаний / Ларичев О.И., Мечитов А.И. Мошкович Е.И. и др. М.: Наука, 1989.

34. Гаврилова Т.А., Красовская М.Р. О концептуальном анализе знаний при разработке экспертных систем // Гибридные интеллектуальные системы. Ростов/н/Д. 1991. с. 110-113.

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

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

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

38. Гельфонд А.О. Исчисление конечных разностей. М.: Наука, 1967. - 288 с.

39. Гильберт Д., Бернайс П. Основания математики. Теория доказательств. -М.: Наука, Гл. ред. физ.-мат. лит., 1982. 652 с.

40. Гимади Э.Х., Залюбовский В.В. Задачи упаковки в контейнеры: асимптотически точный подход // Изв. Вузов. Математика. 1997. №2. с. 25-33.

41. Гимади Э.Х., Залюбовский В.В., Шарыгин П.И. Задачи упаковки в полосу: асимптотически точный подход // Изв. Вузов. Математика. 1997. №12. с. 34-44.

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

43. Глушков В.М. Введение в кибернетику. Киев.: Изд-во Акад. Наук УССР,1964.-324 с.

44. Глушков В.М. Кибернетика, вычислительная техника, информатика: Избр. тр.: В 3 т. Т. 1. / АН УССР, Ин-т кибернетики им. В.М. Глушкова. Киев: Наук, думка, 1990.-261 с.

45. Глушков В.М. Кибернетика и её применение в народном хозяйстве: Избр. тр.: В 3 т. Т. 3. / АН УССР, Ин-т кибернетики им. В.М. Глушкова. Киев: Наук, думка, 1990.-261 с.

46. Годунов С.К., Рябенький B.C. Разностные схемы. М.: Наука, 1977. - 251 с.

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

48. Горбатов В.А. Фундаментальные основы дискретной математики: информационная математика. М.: Наука, 1999. - 544 с.

49. Городецкий В.И., Грушинский М.С. Хабалов А.В. Многоагентные системы // Новости искусственного интеллекта. 1988. №2. с. 32-38.

50. Гульден Я.П., Джексон Д. Перечислительная комбинаторика: Пер. с англ. -М.: Наука, 1990.-502 с.

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

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

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

54. Дынкин Е.Б. Юшкевич. А.А. Теоремы и задачи о процессах Маркова. М.: Наука, 1967. - 186 с.

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

56. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985.-352 с.

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

58. Житников В.П., Филиппова А.С. Задача прямоугольной упаковки в полубесконечную полосу: поиск решений в окрестности локальной нижней границы // Информационные технологии. 2007. № 5. с. 55-61.

59. Завада А.П., Кожевникова Г.П. К анализу алгоритмов над деревьями. Векторные коды. Генерация случайных структур и характеристика дерева // Кибернетика. 1984. - с. 12-18.

60. Зарипов Р.Х. Машинный поиск вариантов при моделировании творческого процесса. М.: Наука. 1983.

61. Зыков А.А. Основы теории графов. М.: Наука, 1987. - 380 с.

62. Ильин В.В. Теория познания. Эпистемология. М.: Издательство МГУ, 1974. - 136 с.

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

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

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

66. Искусственный интеллект: применение в интегрированных производственных системах / Э. Кьюсиак, К.Т. Яп, У.М. Чау и др.: Пер. с англ. М.: Машиностроение, 1991. - 539 с.

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

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

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

70. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970. - 499 с.

71. Клир Дж. Системология. Автоматизация решения системных задач. Пер. с англ. М.: Радио и связь, 1990. - 544 с.

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

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

74. Кожарский JT.A. Экспертные системы интеллектуальное ядро ЭВМ пятого поколения. - М.: Знание, 1984 - 64 с.

75. Кожевникова Г.П. Структуры данных и проектирование эффективной вычислительной среды. Львов: Выща шк., 1986.

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

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

78. Комбинаторно-алгебраические и вероятностные методы дискретного анализа: Межвуз. сб. науч. тр. Горький: ГГУ, 1989. - 155 с.

79. Коов М.И., Мацкин М.Б., Тыугу Э.Х. Интеграция концептуальных и экспертных знаний в САПР // Известия АН СССР. Техническая кибернетика. 1988. №5. с. 108-118.

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

81. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. -384 с.

82. Кофман А. Методы и модели исследования операций. М.: Мир, 1966.401 с.

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

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

85. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. -М.: Мир, 1978.-432 с.

86. Кук Д., Бейз Г. Компьютерная математика. М.: Наука ,1990.

87. Куратовский Л., Мостовский А. Теория множеств. М.: Мир, 1970.

88. Левин Р., Дранг Д., Эделсон Б. Практическое введение в технологию искусственного интеллекта и экспертных систем с иллюстрациями на Бейсике. М.: Финансы и статистика, 1990. - 239 с.

89. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. М.: Наука, 1990.

90. Лернер Э.Ю., Фазылов В.Р. Функция гильотинного размещения для наборапрямоугольников // Исследования по прикладной математике. Казань: Унипресс, 1999. Вып. 21. с. 187-196.

91. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

92. Логический подход к искусственному интеллекту: от классической логики к логическому программированию / А. Тей, П. Грибомон, Ж. Луи и др.: Пер. с франц. М.: Мир, 1990. - 432 с.

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

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

95. Магрупов Т.М. Графы, сети, алгоритмы и их приложения. АН УзССР, Ин-т кибернетики с ВЦ УзНПО «Кибернетика» Ташкент: Фан, 1990, 120 с.

96. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. М.: Мир, 1981.-394 с.

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

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

99. Марков В.Н. Архитектура интеллектуальных систем для решения NP-трудных задач с ресурсами ii Интеллектуальные системы: Труды седьмого международного симпозиума. Москва. 2006. с. 423-427.

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

101. Марков В.Н. Гильотинный раскрой с использованием технологии баз знаний // Высокие технологии, фундаментальные и прикладные исследования, образование: Сборник трудов II международной НПК. Том 4. Санкт-Петербург. 2006. с. 302-304.

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

103. Марков В.Н. Оптимизация линейных контейнеров // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2005. Приложение №3. с. 5-9.

104. Марков В.Н. Оценка вычислительной сложности вершинного обхода графа // Информатика и управление: Труды КубГТУ. Том XXV. Краснодар. 2005. с. 129-130.

105. Марков В.Н. Оценка применения ранжированных цепей для приближённого решения NP-трудных задач // Высокие технологии, фундаментальные и прикладные исследования, образование: Сборник трудов II международной НПК. Том 4. Санкт-Петербург. 2006. с. 45-47.

106. Марков В.Н. Порождение эвристик для приближённого решения NP-трудных задач // Высокие технологии, фундаментальные и прикладные исследования, образование: Сборник трудов II международной НПК. Том 4. Санкт-Петербург. 2006. с. 44-45.

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

108. Марков В.Н. Ранжирование решений NP-полных задач методом обратных приращений // Исследование, разработка и применение высоких технологий в промышленности: Сборник трудов III международной НПК. Том 5. Санкт-Петербург. 2007. с. 249-250.

109. Марков В.Н. Распределение индексов функции выбора в оптимальных циклах Гамильтона // Информатика и управление: Труды КубГТУ. Том XXV. Краснодар. 2005. с. 176-178.

110. Марков В.Н. Редукция порождающего графа в NP-проблемах // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2004. Спецвыпуск, с. 51-53.

111. Марков В.Н. Синтез интеллектуальных NP-полных систем // Исследование, разработка и применение высоких технологий в промышленности: Сборник трудов III международной НПК. Том 5. Санкт-Петербург. 2007. с. 247-248.

112. Марков В.Н. Синтез NP-полных систем // Информатика. Математика. Моделирование. Методика: Сборник трудов ИНЭП. Краснодар. 2007. с. 29-39.

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

114. Марков В.Н. Эвристический поиск в пространстве решений NP-трудных задач // Интеллектуальные системы: Труды седьмого международного симпозиума. Москва. 2006. с. 427-431.

115. Марков В.Н. Экспертная система негильотинного раскроя-упаковки //

116. Кибернетика и высокие технологии XXI века: Сборник трудов VIII Международной конференции. Воронеж. 2007. с. 123-133.

117. Математическое моделирование и дискретная оптимизация: Сб. ст. / АН СССР, ВЦ М.: ВЦ АН СССР, 1988. 93 с.

118. Методы дискретного анализа в теории графов и сложности. Новосибирск: Ин-т математики, 1992. - 122 с.

119. Месарович М. Основания общей теории систем. / Общая теория систем Сб. науч. тр.: Пер с англ. М.: Мир, 1996.

120. Месарович М., Такахара Я. Общая теория систем: математические основы. М.: Мир, 1978.

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

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

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

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

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

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

127. Мухачева Э.А., Валеева А.Ф., Филиппова А.С., Поляковский С.Ю. Задача двумерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума// Информационные технологии. 2006. №4. с. 45-52.

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

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

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

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

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

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

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

135. Мухачева Э.А., Назаров Д. А., Филиппова А.С., Чиглинцев А.В. Проектирование прямоугольных упаковок на базе развития технологии блочных структур // Информационные технологии. 2007. №1. с. 20-29.

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

137. Оре О. Теория графов. М.: Наука, 1968.

138. Осипов Г.С. Информационные технологии, основанные на знаниях // Новости искусственного интеллекта. 1993. №1. с. 7-41.

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

140. Нейман Ю. Теория вероятностей и математическая статистика: Пер. с англ. -М.: Мир, 1968.

141. Нечаев В.И. Числовые системы. М.: Просвещение ,1975. - 199 с.

142. Нивергельт Ю.,Фаррар Дж., Рейнгольд Э. Машинный подход к решению математических задач. М.: Мир, 1977.

143. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь, 1985.

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

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

146. Панюкова Т.А. Синтез программ управления процессом раскроя // Обозрение прикладной и промышленной математики. Т. 8. Вып. 2. / Под ред. Прохорова. М.: Науч. Изд-во «ТВП», 2001. - 664 с.

147. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. М.: Мир, 1985. - 512 с.

148. Перепелица В.А. Многокритериальные задачи теории графов. Алгоритмический подход. Киев: УМКВО, 1989. - 66 с.

149. Перспективы развития вычислительной техники: В 11 кн.: Справ. Пособие/ Под ред. Ю.М. Смирнова. Кн. 2. Интеллектуализация ЭВМ / Кузин Е.С., Ройтман А.И., Фоминых И.Б., Хахалин Г.К. М.: Высш. шк., 1989. - 159 с.

150. Плоткин Б.И., Гринглаз Л.Я., Гварамия А.А. Элементы алгебраической теории автоматов. -М.: Высш. шк., 1994. 191 с.

151. Попков В.К. Представление деревьев. Новосибирск, 1981. — 26 с. -(Препринт / АН СССР, СО, ВЦ; №242)

152. Попов Э.В., Фоминых И.Б., Кисель Е.Б., Шапот М.Д. Статические и динамические экспертные системы. М.: Финансы и статистика, 1996.

153. Последовательный метод решения экстремальных комбинаторных задач -Новосибирск: Наука, СО, 1991. 143 с.

154. Поспелов Г.С. Искусственный интеллект основа новой информационной технологии. / АН СССР. - М.: Наука, 1988. - 278 с.

155. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. М.: Радио и связь, 1989.

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

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

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

159. Проблемы обработки знаний / Сб. науч. тр.: Под ред. В.М. Пономарева. -АН СССР Ленинград ЛИИАН, 1989. -155 с/

160. Пугачёв B.C. Теория вероятностей и математическая статистика. М.: Наука, 1979.-311 с.

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

162. Риордан Дж. Введение в комбинаторный анализ. М.: Изд-во иностр. лит., 1963.

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

164. Романовский И.В. Дискретный анализ. 2-е изд., исправ. СПб.: Нев. Диалект, 2000. - 240 с.

165. Рубашкин В.Ш. Представление и анализ смысла в интеллектуальных информационных системах. -М.: Наука, 1989. 189 с.

166. Рыбников К.А. Введение в комбинаторный анализ. М.: Изд-во МГУ, 1972.- 178 с.

167. Самарский А.А. Теория разностных схем. М.: Наука, 1977. - 208 с.

168. Сачков В.Н. Вероятностные методы в комбинаторном анализе. М.: Наука, 1978.-287 с.

169. Сачков В.Н. Комбинаторные методы дискретной математики. — М.: Наука, 1977.-314 с.

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

171. Сергеев В.М. Когнитивные модели в исследовании мышления: структура и онтология знания // Интеллектуальные процессы и их моделирование. М.: Наука, 1987. с. 179-195.

172. Системы управления базами данных и знаний: Справ, изд. / А.Н. Наумов, A.M. Вендров, В.К. Иванов и др. Под ред. А.Н. Наумова. М.: Финансы и статистика, 1991. - 352 с.

173. Скорняков JI.A. Элементы теории структур. М.: Наука, 1970.

174. Слейгл Дж. Искусственный интеллект. М.: Мир, 1973.

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

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

177. Татт У.Т. Теория графов: Пер. с англ. М.: Мир, 1988. - 424 с.

178. Таунсенд К., Фохт Д. Проектирование и программная реализация ЭС на ПЭВМ: Пер. с англ. М.: Финансы и статистика, 1990. - 320 с.

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

180. Теория графов. Покрытия, укладки, турниры. Сб. пер. Под ред. В.Б. Алексеева и др. М.: Мир, 1974. - 223 с.

181. Теория графов: Тематический сб. / АН УССР Киев: Ин-т математики, 1977.-216 с.

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

183. Тыугу Э.Х. Концептуальное программирование. М.: Наука, 1984. - 256 с.

184. Уилкс T.JI. Математическая статистика. М.: Наука, 1967. - 522 с.

185. У ил сон Р. Введение в теорию графов. М.: Мир, 1988.

186. Уинстон П. Искусственный интеллект. М.: Мир, 1980.

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

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

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

190. Уэно X., Исидзука М. Представление и использование знаний: Пер. с япон. -М.: Мир, 1989.-313 с.

191. Хант Э. Искусственный интеллект. М.: Мир, 1978.

192. Харари Ф. Теория графов. М.: Мир, 1973.

193. Филиппова А.С. Задача двумерной упаковки в полубесконечную полосу: численный эксперимент с алгоритмами локального поиска и с декодерами блочной структуры // Информационные технологии. 2005. №6. с.32-47.

194. Филиппова А.С. Задача ортогональной упаковки в полубесконечную полосу: численный эксперимент с безотходными задачами Е.Норрег // Информационные технологии. 2005. №6. с. 32-47.

195. Филиппова А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур // Информационные технологии. 2006. №6. Приложение. 32 с.

196. Филиппова А.С. Проблемы кодирования прямоугольных упаковок: краткий обзор современных технологий // Информационные технологии. 2005. №6. с. 32-47.

197. Форсайт Ф. Экспертные системы. Принципы работы и примеры. М.: Радио и связь, 1987. - 384 с.

198. Хант Д. Искусственный интеллект. М.Мир, 1986.

199. Хоггер К. Введение в логическое программирование. М.: Мир, 1988.

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

201. Цой Э.В., Юдин А.Д., Юдин Д.Б. Задачи пополнения и синтеза знаний // Автоматика и телемеханика. 1994. №7. с. 47-51.

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

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

204. Шенк Р. Обработка концептуальной информации. Пер. с англ. М.: Энергия, 1980.-360 с.

205. Экспертные системы. Принципы работы и примеры: Пер. с англ. / А. Брукинг, П. Джонс, Ф. Кокс и др. М.: Радио и связь, 1987 - 224 с.

206. ЭВМ пятого поколения: Концепции, проблемы, перспективы / Под ред. Мото-ока: Пер. с англ. М.: Финансы и статистика, 1984. - 110 с.

207. Элти Дж., Кумбс М. Экспертные системы: концепции и примеры: Пер. с англ. -М.: Финансы и статистика, 1987. 191 с.

208. Эндрю А. Искусственный интеллект. М.: Мир, 1985. - 591 с.

209. Юдин А.Д., Юдин Д.Б. Пополнение и синтез знаний в задачах теориипринятия решений // Изв. РАН. Техническая кибернетика. 1992. №5. с.31-35.

210. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. -431 с.

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

212. Belov G. A 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-dresden.de/~capad

213. Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock length // European Journal of Operational Research. 2002. Vol. 44. P. 145-149.

214. Bentley J. L., Friedman J. H. Fast algorithms for constructing minimal spanning trees in coordinate spaces // IEEE Trans. Computers. 1978. - Vol. C-27. T. 2. - P. 97-105.

215. Berman C.L. Ordered binary decision diagrams and circuit structure // The international Conference of Computer Design. IEEE, New York, 1989. - P. 392-395.

216. Beyer Т., Hedetniemi S.M. Constant time generation of rooted trees // SIAM J. Computing. 1980. - Vol. 9, N. 4. - P. 706-712.

217. Burns R. N., Haff С. E. A ranking problem in graphs // Proc. Of the 5th Southwest Conf. on Combinatorics, Graph Theory and Computing. 1974. - P. 461-470.

218. Chin F., Houck D. Algorithm for updating minimum spanning trees // J. Com-put. System Sci. 1978. - Vol. 16. - P. 333-334.

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

220. Dorigo M. The ant system: Optimization by a Colony of Cooperating Agents // IEEE Transactions on Systems, Man and Cybernetics. Part B26,(l):l - 13, 1996.

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

222. Er M. C. Enumerating ordered trees lexicographically // Comput. J. 1985. -Vol. 28, N. 5. - P. 274-294.

223. Gabow H. N. A good algorithm for smallest spanning trees with a degree constraint // Networks. 1978. - Vol. 8. - P. 201-208.

224. Gabow H. N. Two algorithms for generating weighted spanning trees in order // SIAM J. Computing. 1977. - Vol. 6. - P. 139-150.

225. Gabow H. N., Myers E. W. Finding all spanning trees of directed and undirected graphs // SIAM J. Computing. 1978. - Vol. 7. - P. 280-287.

226. Garbe R. Tree-width and path -width of comparability graphs of interval orders // Lecture Notes Сотр. Sci. Springer-Verlag. - 1995. - Vol. 903. - P. 26-27.

227. Gutin G. exponential neighborhood local search for the traveling salesman problem // Comput. Oper. Res. 1999. Vol. 26. P. 313-320.

228. Hifi M. Exact algorithms for the guillotine stop cutting/packing problem // Сотр. and Oper. Res. 1998. N. 25. P. 925-940.

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

230. Jayakumar R., Thulasiram K. Analysis of a spanning tree enumeration algorithm // Combinatorics and Graph Theory. Lect. Notes in Math. Springer-Verl., 1980. -N. 833.-P. 284-289.

231. KendallG. Simulated Annealing, 2002. url: http://www.cs.nott.ac.uk/~gxk/aim/notes/simulatedannealing.doc

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

233. Lodi A., Martello S., Vigo D. Heuristic and meta-heuristic approaches for a class of two-dimensional bin packing problems Algorithms // INFORMS J. Comput. 1999. Vol. 11. P. 345-357.

234. Luke B.T. Simulated Annealing Cooling Schedule, 2001. url: http://members.aol.com/btluke/simanfl .htm

235. Pisinger D. Heuristics for the container loading problem // European Journal of Operational Research. 2002. Vol. 141. P. 383-392.

236. Shaffer R. Practical Guide to Genetic Algorithms, 1993. http://chemdiv-www.nrl.navy.mi1/6110/6112/sensors/chemometrics/practga.html

237. Spinrad J. Dimension and algorithms // Lecture Notes Сотр. Sci. 1994. - Vol. 831.-P. 33-52.323