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

• Марков, Виталий Николаевич
• доктор технических наук
• 2007

Оглавление диссертации доктор технических наук Марков, Виталий Николаевич

ВВЕДЕНИЕ.

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-полных задач, допускающих приближённое решение. Представителями указанного класса задач являются задачи оптимизации ортогонального и криволинейного раскроя-упаковки, распределения персонала, перевозок, размещения предприятий, управления производством, а также проектирование в области электроники и архитектуры.

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

Список литературы диссертационного исследования доктор технических наук Марков, Виталий Николаевич, 2007 год

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