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

• Янков, Игорь Александрович
• кандидат технических наук
• 2010

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

Введение.

Глава 1. Анализ современных моделей, методов и средств построения расписании.

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

1.1.1 Анализ существующих систем автоматического планирования.^

1.1.2 Специфика предметных областей с древовидной структурой обслуживания требований.^

1.2 Теоретические основы построения расписаний.^

1.2.1 Одностадийные расписания.

1.2.2 Многостадийные расписания.

1.2.3 Анализ современных методов построения расписаний.

1.3 Расписания с древовидной структурой связей.

1.4 Выводы по главе 1.

Глава 2. Модель и методы оперативного построения и перестроения расписаний с древовидной структурой требований.

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

2.1.1 Требования к модели и ее предназначение.

2.1.2 Представление модели расписания в виде смешанного графа.

2.1.3 Операции над графом расписания: создание, отмена, перепланирование задачи.

2.1.4 Принципы построения дерева задач (ветвление задач).

2.2 Алгоритм построения расписаний с древовидной структурой связей.

2.2.1 Постановка задачи.

2.2.2 Формирование целевой функции.

2.2.3 Общая схема построения расписаний.

4.3.2 Целевая функция и ее компоненты.

4.3.3 Логика агентского взаимодействия.

4.4 Особенности архитектуры и программной реализации комплекса построения расписании.

4.5 Экспериментальная оценка эффективности программного комплекса на основе тестовой эксплуатации системы планирования компанией AVIS UK.

4.5.1 Условия проведения тестовой эксплуатации.

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

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

Введение диссертации (часть автореферата) на тему «Оперативное построение расписаний с древовидной структурой требований»

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

В настоящее время для построения и управления расписаниями все чаще применяются автоматические и автоматизированные системы. Они применяются в самых различных сферах нашей жизни, и уже невозможно представить себе, как человечество может управлять множеством технических и организационных комплексов^ без автоматического планирования их деятельности. Транспортная логистика грузовых и пассажирских перевозок на всех видах транспорта [20,32,138,150], планирование взаимодействия поставщиков в единых технологических циклах [177], управление работой административных и образовательных учреждений, составление сложных сетевых планов большого числа взаимодействующих предприятий [54,67]'- вот лишь небольшой перечень задач, которые эффективно решаются средствами автоматизированного планирования и управления.

Некоторые такие системы подготавливают расписание заранее, другие строят и перестраивают его в процессе исполнения. Одни системы генерируют расписания на несколько лет вперед, другие - на несколько ближайших часов [109]. Существуют системы реального времени, от надежности работы которых зависят технологические процессы. Существуют вспомогательные системы поддержки принятия решений, которые лишь помогают человеку строить и проверять расписания [149]. Однако практически всегда основной целью систем" автоматического построения расписаний является посторенние оптимальных расписаний, а также контроль их исполнения.

Если расписания в тех или иных предметных областях описываются широко-распространенными моделями, то для построения расписаний можно использовать глубоко проработанный и апробированный аппарат теории расписаний. Однородным и неоднородным, многостадийным и одностадийным моделям расписаний посвящены работы Джонсона С.М.[ 154], Танаееа B.C. [8485], Конвея Р.В. [42], Коффмана Э.Г. [49].

Если же структура расписания предметной области имеет нетривиальный и8ерархический характер, если уже попытки формализовать и определить множество возможных вариантов расписаний вызывают сложности, то применение, классического аппарата теории расписаний ограничено, а во многих случаях и: невозможно; Тогда перед проектированием любых средств автоматического построения расписаний необходимо изучить его структуру и предложить, способы, ее формального описания [101]. Именно такое описание позволит строить и перестраивать расписания с учетом всех внутренних, причинно-следственных; связей,' обуславливающих наличие тех или иных операций, элементов^ блоков.расписаний.

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

К предметным, областям,. для- которых с: одной; стороны важен учет внутренней структуры расписания,,, а с другой стороны возможность их динамического построения^ и перестроения, можно отнести . планирование .ресурсов для компаний по прокату автомобилей (rent-a-car);[109],.планирование сложных технологических процессов; в условиях большого5 количества задач и ресурсов, планирование: загрузки и разгрузки крупнотоннажных контейнеровозов в. портах- планирование связанных распределенных репликаций .и т.д. . , . .

Именно поэтому задача разработки; адекватных моделей расписаний с древовидной структурой и эффективных алгоритмов их построения, и перестроения/; является чрезвычайно актуальной и значимой. Исследованиям сложной структуры расписаний и алгоритмов их построения и посвящены работы: . Норенкова И.П. [62-65], Пргшуцкого MX. [7,68-70], Власова B.C. [69,188]; Костенкова В.А. [47, 48]. Вместе с тем особенности и проблематика генерации расписаний с древовидной; структурой в настоящее время слабо освещены, в научно-технической литературе.

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

2.2.4 Применение метода ветвей и границ.70

2.2.5 Временные окна планирования задач и механизмы оценки их нарушений.72

2.2.6 Стратегии расчета взаимного влияния планирования задач.76

2.3 Анализ сложности алгоритма построения расписаний.85

2.4 Выводы по главе 2.8(5

Глава 3. Мультиагентная архитектура программного комплекса построения Я расписании с древовидной структурой связей.00

3.1 Программное окружение комплекса построения расписаний.88

3.2 Требования к архитектуре программного комплекса построения

Q1 расписании с древовидном структурой связей.yL

3.3 Мультиагентный подход диспетчеризации активностей планирования

93 задач.

3.3.1 Общая схема функционирования мультиагентной архитектуры.93

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

3.4 Событийная модель обработки требований. Ю2

3.5 Мультиагентная проактивность.

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

Глава 4. Реализация и экспериментальная оценка эффективности программного комплекса автоматического построения расписаний для предметной области сдачи автомобилей в аренду (rent-a-car).1

4.1 Описание предметной области с точки зрения построения расписаний.Ю9

4.2 Требования к комплексу автоматического построения расписаний для rent-a-car компаний.Ш

4.3 Использование предложенных моделей и методов для построения расписания в rent-a-car предметной области.

4.3.1 Схема ветвления, типы задач и ресурсов.

115

116 обслуживание множества требований, структура которых имеет древовидный характер. Данная работа направлена на изучение природы расписаний для предметных областей с древовидной структурой обслуживания требований, выявление их общих характеристик и описание обобщенной формы, позволяющей осуществлять- процесс построения и перестроения, таких расписаний.Именно поэтому в качестве предмета' исследования»была выбрана < модель расписаний" с древовидной- структурой требований, а также методы и средства-построения таких расписаний.

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

Поставленная цель была решена с помощью разработки модели' расписаний, с древовидной структурой! требований, однозначно определяющей закономерности существования внутренних связей расписания, а также с помощью разработки, метода построения и перестроения таких расписаний [97,101-103].

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

1. Исследование особенностей, расписаний в предметных областях с явно выраженной древовидной структурой обслуживания-требований для выявления их наиболее общих черт и определения теоретической модели таких расписаний.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Система, автоматического планирования «Астерикс» внедрена и используется британским отделением международной rent-a-car компании AVIS [109];

- Информационная система распределенных репликаций разработана и; используется в Губернском Баке «Тарханы», а также в компании-операторе приема коммунальных услуг «Электронный Платеж».

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

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

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

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

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

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

В* качестве такой модели было предложено и обосновано использование смешанного граф (Т, О, Р, Ь, С), комплексно описывающего все внутренние связи расписания. Вершинами такого графа являются операции и задачи, а дуги отражают причинно-следственные и временные связи процесса обслуживания I требований.

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

1. Планирование задачи

2. Отмена задачи

3. Перепланирование задачи

Применение такого подхода позволяет эффективно описывать множество возможных вариантов расписания обслуживания одного требования и задавать правила перехода от одного варианта к другому.

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

1. Возможность адаптивного управления качеством расписания за счет гибкого задания критериев оптимальности и учета большого числа факторов.

2. Способность строить расписания для большого числа задач и ресурсов' за счет полиномиальной зависимости вычислительной сложности алгоритма.

3. Возможность инкрементального (избирательного) планирования, обеспечиваемая раздельным планированием каждого требования.

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

5. Способность изменять расписания в режиме реального времени, достигаемая за счет использования формализованного процесса перестроения плана» (в каждый момент времени расписание остается актуальным и допустимым).

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

ГЛАВА 3. МУЛЬТИАГЕНТНАЯ АРХИТЕКТУРА ПРОГРАММНОГО КОМПЛЕКСА ПОСТРОЕНИЯ РАСПИСАНИЙ. С ДРЕВОВИДНОЙ СТРУКТУРОЙ СВЯЗЕЙ.

3.1 Программное окружение комплекса построения расписаний

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

Рисунок 3.1. Типовая схема системы автоматического планирования и построения расписаний.

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. На основе предложенных моделей, - алгоритмов и архитектуры был разработан*, и реализован программный комплекс построения расписаний ресурсов rent-a-car компаний. Комплекс предназначен для функционирования-в, системе автоматического построения расписаний в качестве основного программного' средства оперативного* планирования. Он был реализован на языке Java 6.0 с использованием клиент-серверных технологий J2EE, и мультиагентных средств МАЕ. !

5. Проведено исследование эффективности использования разработанного программного комплекса в процессе его тестовой эксплуатации на четырех станциях британского отделения rent-a-car компании AVIS. Исследование проводилось на основе сравнения результатов, автоматического и ручного способа построения расписаний.'' Оно продемонстрировало значительное возрастание показателей эффективности работы станций и использования ресурсов (на 17%-25%) и подчеркнуло преимущества использования предложенных автоматических средств планирования в данной предметной области.

Дальнейшие исследования по рассматриваемой проблеме целесообразно производить в следующих направлениях:

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

2. Поиск более эффективных эвристик определения стоимости перепланирования задачи.

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

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

159

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

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

2. Аксенов В.А. Полиномиальный алгоритм приближенного решения одной задачи теории расписаний // Управляемые системы. Новосибирск: Изд-во математики, 1988. С. 8—11.

3. Аттетков A.B., Галкин С.В., Зарубин B.C. Методы оптимизации: Учеб. для студ. втузов.-М.: Изд-во МГТУ, 2001.

4. Бабушкин А.И., Башта А.Л., Белов И.С. Построение календарного плана для многомаршрутной* задачи трех станков // Автоматика и Телемеханика N7, 1976. С 154-158.

5. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Методкомбинирования эвристик для решения комбинаторных задач упорядочения иjраспределения ресурсов. //Информационные технологии. Москва, N2, 1997. С.29-32.

6. Белов И.С., Столин Я.Н. Алгоритм в одномаршрутной задаче календарного, планирования. В кн.: Математическая экономика и функциональный анализ. М.: Наука, 1974. С. 248—257.

7. Берж К. Теория графов и ее применения. М.: Издательство иностранной литературы, 1962.10: Бигель Дж. Управление производством, количественный подход. Мир, М 1973.

8. Брюхов /Д.О., Задорожный В.И., Калиниченко. Л.А., Курошев М.Ю., Шумилов С.С. Интероперабельные информационные системы: архитектуры^ технологии; '//СУБД, 1995, №4.- С. 45. ':" ; . ;

9. Вирт Н. Алгоритмы и структуры данных: Пер. с, англ. М.: Мир; -1989. -360 с., ил. '• ' • ' .

10. Виттих В.А. Эволюционное управление сложными системами // Известия Самар.науч. центра РАН;2000. Т. 2. - № 1. - С. 53-65,

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

12. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб: Питер, 2001. - 368 е.: ил. (Серия «Библиотека программиста»).

13. Гладков Л. А.,!Курейчик.В; В., Курейчик В. М. Генетические алгоритмы:: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. С. 320. — ISBN 5-92210510-8

14. Самара, 2006 Самара: СНЦ РАН, 2006

15. Гончаров Е. Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискрет, анализ и исслед. операций. Сер. 2. 1998. Т. 5,№ 1.С. 19-39.

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

17. Гимади Э.Х., Глебов Н.И. дискретные экстремальные задачи принятия решений. Учебное пособие //Новосибирск: НГУ, 1991.

18. Гимади Э.Х., Глебов Н.И., Перепелипа В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука, 1975.-Вып. 31. с. 35-42.

19. Громов Сергей. Возможности использования ERP-системы для поддержки-оперативного планирования производства // СЮ, №9; сентябрь 2006.

20. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание", информатики: Пер. с англ. М.: Мир, 1998. - 703 е., ил.

21. Губенко И.О. Приложение "АВТОРасписание" (http://www.mmis.ru/Default.aspx?tabid=59).

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

23. Дейт, К. Дж. Введение в системы баз данных.: Пер. с англ. 6-е изд. — К.: Диалектика, 1998. - 784 е.: ил. - Парал. тит. англ.

24. Душин Б.И. Алгоритм для 2-маршрутной задачи Джонсона // Кибернетика. 1988. N3. с. 53-58.

25. Душин Б.И. Алгоритм для р-маршрутной задачи Джонсона // Кибернетика. 1989. N2. С. 119-122.

26. Золотарев Вадим. Система управления маршрутами и составления расписаний ROMAN// Connect! Мир Связи 2009, N3.

27. Каширских К.Н., Поттс К.Н., Севастьянов* С.В. Улучшенный алгоритм решения, двухмашинной задачи flow shop« с неодновременным поступлением работ//Дискретный анализ и исследование операций. 1997. Т. 4, N 1. с. 13-32;

28. Кнут, Дональд, Эрвин. Искусство программирования, том I. Основные, алгоритмы;, 3-е изд.: Пер: с англ.: Уч-. пос.- М.: Издательский дом «Вильямс», 2000- — 720'с;: ил.-Парал. тит.англ. ,

29. Кнут, Дональд,. Эрвин.' Искусство iфограммирования, том 2. Получисленные алгоритмы, З'-е-изд.: Пер. с англ.: Уч. пос. М.: Издательский, дом «Вильяме», 2000. - 832 е.: ил. - Парал. тит. англ.

30. Кнут, Дональд, Эрвин. Искусство программирования, том 3. Сортировка и поиск, 2-е'изд.: Пёр. с англ:: Уч. пос. —М.: Издательский дом «Вильяме»^ 2000. 832 е.: ил. — Парал. тит. англ.

31. Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер, Теория расписаний. М., Наука, 1975г. \ . '

32. Кононов А. В. О расписаниях рабрт на одной машине с длительностями, нелинейно зависящими от времени;// Дискрет, анализ и исслед. операций. 1995: Т. 2,№ 1.С. 21-35.

33. Кононов А. В. Комбинаторная сложность составления расписаний для работ с простым линейным ростом длительностей // Дискрет, анализ и исслед, операций. 1996. Т. 3, № 2. С. 15-32.

34. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М., Наука, 1969 г.

35. Корбут A.A. Сигал И.Х., Финкелыптейн Ю.Ю. Гибридные методы в дискретном программировании // Изв. АН СССР. Техн. кибернет. 1988. - N 1. -С. 65 - 77.

36. Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование, 2002., N 3, С.64-80.

37. Костенко В.А., Винокуров A.B. Локально-оптимальные алгоритмы построения расписаний, основанные на использовании сетей Хопфилда // Программирование, 2003., №4.

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

39. Кофман А., Введение в прикладную комбинаторику. М., Наука, 1975 г.

40. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 1999.

41. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы и анализ / Пер. с англ. под ред. А. Шеня. М.: МЦНМО, 2002. - 960 е.: 263 ил.

42. Кустов А.И. Автоматизированная информационная система составления и оптимизации расписания // Информационные1 технологии моделирования и управления 2006, №6(31)

43. Лафоре Р. Объектно-ориентированное программирование в С++. Классика

44. Computer Science. 4-е изд. СПб.: Питер, 2003. - 928 е.: ил.

45. Мельников О. Н:, Шафранский Я. М. Параметрическая задача теории расписаний // Кибернетика. 1979; № 3; С. 53-57.

46. Мину Mi Математическое программирование; М^ Наука, 1990i . •58; 'Мирёцкий И§ ЮГ Синтез*; оптимальных . расписаний! для . систем последовательного типа //. Известия"5РА№;.Теорйяш< си стемы. у правления. 2002, №1.С. 77-85. , . ' . • /• . '

47. Мирецкий; И.Ю;, Щербаков М.А. Матричные модели?и методы в; теории^ расписаний: Монография; Пенза: Изд.-во Пенз. гос; ун-та, 2003. 260 с.

48. Мирецкий И. Ю. S-оптимальные решения задачи М станков // Известия? РАЖ Теория и системы-управления., 2004, №=1. С'. 110—Г19г

49. Норенков И.П. Генетические алгоритмы решения проектных иг логистических задач // Информационные технологии. 2000. - №9 64. Норенков И.П. Эвристика и их, комбинации в генетических методах дискретной оптимизации // Информационные технологии. - 1999. - №1

50. Норенков И.П. Генетические методы структурного синтеза проектных решений // Информационные технологии. 1998. - № 1

51. Паретооптимальные решенияшногокритериальных задач: Подиновский В; В., Ногин В. Д. М; :Наука.: Главная редакция: • физико-математической литературы, 1982. - 256 с.

52. Попов Г.А. Формализация* задачи составления расписания в высшем учебном заведении//.Вестник АЕТУ -2006, N! (30):

53. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах. Журнал Автоматика п.телемеханика. Москва. 1996, №2, с.24-29. • ■•'•■■■■■'■

54. Прилуцкий М.Х., Власов B.C. Метод комбинирования эвристических алгоритмов для конвейерных задач теории расписаний // Исследовано в России.5 2007. С. 901-905.

55. Прилуцкий М.Х., Кумагина Е.А. Задачи распределения; разнородных-ресурсов в сетевых канонических структурах// Перспективные информационные технологии и интеллектуальные системы. 2000. №4, стр. 4652.

56. Рузинкевич М., Цикоцки А. Определение и выполнение потоков транзакций: Часть Г. //СУБД, 1995, №2.- С.18.

57. Рузинкевич Mi, Цикоцки А. Определение и выполнение потоков транзакций: Часть 2. //СУБД, 1995, №4.- С. 18.

58. Рыжиков-Ю.И. Теория » очередей и управление запасами. // «Питер» Санкт-Петербург 2001.

59. Севастьянов C.B. Приближенные алгоритмы в задачах Джонсона и суммирования векторов // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1980. С. 64-73. (Тр./ АН СССР: Сиб. отд-ние. Ин-т математики. Вып. 20.)

60. Севастьянов C.B. О" связи задачи календарного распределения с одной задачей на единичном кубе // Методы дискретного анализа. Новосибирск: ИздIво Ин-та математики, 1980. С. 93-103. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 35.)

61. Севастьянов C.B. О задаче календарного распределения // 5 Всесоюз. конф. по проблемам теор. кибернетики. Тез. докл. Новосибирск, 1980. с. 92-93.

62. Севастьянов C.B. О приближенном решении задачи Джонсона // 5 Всесоюз. конф. по проблемам теор. кибернетики. Тез. докл. Новосибирск, 1980. с. 93-95.

63. Седжвик Роберт. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ./Роберт Седжвик. СПб: ООО «ДиаСофтЮП», 2003. - 1136 с.

64. Смелянский P.JI. Модель функционирования распределенных вычислительных систем// Вестн. Моск. Ун-та. сер 15, Вычисл. Матем. и

65. Кибернетика. 1990, No. 3, стр. 3-21.

66. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование // М.: Физматлит, 2002. 240 с.

67. Страуструп Б. Язык: программирования С++, 3-е изд./Пер. с англ. СИб.; Mi: «Невский Диалект» - «Издательство*БИНОМ», 1999'. - 991 с. ил.

68. Стулов Александр ; Особенности построения? информационных; хранилищ: //Открытые системы, 2003; №4- С. 76.83: Таиаев В.Cl, Шкурба В.В., Введение в теорию расписаний. М., Паука, 1975.

69. Танаев В. С, Гордон В. С, Шафранскпй Я. М. Теория; расписаний. Одностадийные системы.МС: Наука; 1984. •

70. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. Mi: Наука, 1989.

71. Тарасов В Б. От многоагентпых систем к интеллектуальным организациям:' философия, психология, информатика.,- М.: Эдиториал УРСС, 2002

72. Фаулер М. Рефакторинг: улучшение существующего кода. — ГТер: с англ.-СПб: Символ-Плюс, 2003. 432 е., ил.

73. Финкельштейн Ю.Ю. Метод отсечения и ветвления для- решения задач целочисленного линейного программирования // Изв. АН СССР. Техн. кибернет. 1971. N 4. - С. 34 - 38. ■ :

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

75. Шахбазян К.В., Гушкина Т.А., Сохраненая B.C., Товкач JI.M." Эксперимент по реализации алгорифмов? диспетчеризации длямногопроцессорных систем: — Управляющие системы и машины, 1975, № 3, 8485. ^

76. Янков И:А., Скобелев*П:0., Шибанов С.В., Шашков Б.Д. Мультиагентный подход к планированию, и распределению ресурсов в динамических гетерогенных; системах'// Динамика гетерогенных структур: Сб. тр. Пенза:

77. Инф.-изд ц. Пенз. ГУ, 2009: Вып 1. - е.22-37.. г |

78. Янков И.А., Шибанов; G.B., Шашков Б.Д., Разработка мультиагентного планировщика для RentACar компаний // Труды 8-ой Международной конференции; «Новые информационные; технологии: m системы», Пенза: ПРУ, 2009.-Ч. 2.-с. 126-134. . . ' , .

79. Янков1. И:А., Шибанов. C.B., Шашков Б.Д. Модель расписаний; с; древовидной структурошсвязей // Программные; продукты и системы. — № 1. М. 2010.-С. 77-79: • ;

80. Янков И.А Общая схема построения расписаний с иерархической» древовидной структурой связей //Альманах современной науки и образования. Тамбов: Ерамота, 2010№ 3 (34): в>2-хч. Ч: 1 : ISSN 1993-5552: стр.*.64-66;. ' .

81. Янков И.А., Шибанов C.B. Система автоматического построения расписаний для rent-a-car компаний //Технологии,Microsoft в теории и практике программирования Труды международного- симпозиума, Нижний Новгород 2010.-е. 407-410.

82. Янков И.А., Шибанов C.B., Шашков Практическое, применение модели расписаний с древовидной иерархической; структурой для планирования* ресурсов rent-a-car // Надежность и качество: Труды, международного: симпозиума, Пенза 2010. с. 297-300. Л

83. Aarts Е. H. L., Korst J. H. M. Simulated- annealing // Local search incombinatorial optimization. Chichester: John Wiley & Sons, 1997. P. 91-120.

84. Ahuja, R., O. Ergun, J. Orlin, and A. Punnen. "A Survey of Very Large-Scale Neighborhood Search Techniques." Technical report, Department of Industrial & Systems Engineering, University of Florida, Gainesville,FL 32611, 1999

85. Balas, E. andN. Simonetti. "LinearTime Dynamic-Programming Algorithms for NewClasses of Restricted TSPs: A Computational Study." INFORMS Journal* on Computing 13(1), 2001, 56-75.

86. Battitr R., Protasi M. Reactive local'search for maximum clique4// Proc. of Workshop on Algorithm Engineering, 1997. P. 74-82.

87. Bean, J.C., and J.R. Birge, "Match-Up Real-Time Scheduling", Technical Report No. 85-22, University of Michigan, Department of Industrial and OperationsEngineering, June, 1985.

88. Biefeld, E. and L. Cooper, "Operations Mission Planner: Final Report", Jet Propulsion Laboratory, Tech. Report 90116, March; 1990.

89. Burke, P:, and-P. Prosser, "A Distributed-Asynchronous System for Predictive and' Reactive Scheduling", Tech. Report AISL42, Dept. of Computer Science, University of Strathclyde, 1989.

90. Boese K. D., Kahng A. B., Muddu.S. A new adaptive multi-start technique for combinatorial global optimizations // Oper. Res. Lett. 1994. V. 16, N 2. P. 101-113.

91. Bonavear E., Dorigo M: Swarm Intelligence: from Natural to Artificial Systems.— Oxford University Press, 1999.— 307 p.

92. Browne S., Yechiali U. Scheduling deteriorating jobs on a single processor // Oper. Res. 1990. V. 38, N 3. P. 495-498.

93. Carlier J. The one-machine sequencing problem // European J. of Oper. Res. -1982. V11,N 1.-P.42-47.

94. Cesta A., Oddi A. and Smith S. A Constraint-Based Method for Project

95. Scheduling with Time Windows. Tech. Report CMU-RI-TR-00-34, Robotics Institute, Carnegie Mellon University, February, 2000:

96. Chen B.v Potts- C.N., Woeginge rG. J. A review of machine- scheduling: complexity, algorithms and approximability // Handbook of combinatorial optimization:.V. 3: Boston::;Kluwer Acad; Publ:, 1998^ P: 21—1691

97. Coffman E.G. A> survey of.mathematical1 results in, flow-time scheduling for computer:systems. - LectaresNotestiDbmputeir-Scivl'^Si ' .

98. Collinot, A., C, LePape, and G; Pinoteau; "SONIA: A\ Knowledge- Based SchedMng System", Aj1:ificial-ntelli~genceinfEngineerihg; 2 (2), 1988, pp. 86-94. • .125. • ' , : . ■ * . '.;, ."■'■■ ' ' : , ' • ' . .

99. Congram; R:, C:.Potts, and. S: van de Velde:, "AnTterated^iDynasearch Algorithm; for the Single-MachinedTotaF. WeigHtedi Tardiness.'.Scedulihgf.Broblemi"" INFORMS: Journal: on Computing 14(1'),' 2002: P; 52^67. .

100. Corne D., Dorigo M., Glover F. New Ideas-in Optimization.- McGravHill, 1999:

101. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for GEU Summer University Course «Complex System».-— Budapest,. Central European University, 2001.-—P. 1-38.

102. Eastman W.L., Even S. Isaacs I. M. Bounds for the optimal scheduling of jobs on processors. Manag. Sci., 1964, 11, № 2, 268-279:

103. Faigle U., Kern \V. Some convergence results for probabilistic tabu search // ORSA J. Comput: 1992. V. 4, N 4. P. 32-37. .

104. Fernandez E.B1, Buspell B: Bounds on the number of processors and time for171multiprocessor optimal shedules. IEEE Trans.Comput., 1973, C-22, № 8, 745-754.

105. Fisher K., Chaib-draa B. A Simulation Approach, Based on Negotiation and Cooperation between Agents: A Case Study. In IEEE Transactions On Systems, Man, And Cybernetics- Part; C:; Applications And Reviews, No.4!,.November 1999s .

106. Fox, MIS;-, "Constraiht-DirectediSearch::A,Case Study in:Job Shop-Scheduling",. . PhD? Thesis, Dept: of Computer, Science, Carnegie Mellon :University, .1983 :

107. Fox, MiS., andl S:F. Smith,- "ISIS:: A Knowledge-Based^ System^ for Factory Scheduling", Expert Systems,; 1 (%July, 1984, pp.,25-49: \ ' • " :'

108. Goldberg D. E. Genetic* Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA. 1989; 412 pages. \

109. Gonzalez T., Sahni S. Flowshop and: jobshop schedules: complexity and approximation //Oper. Res. 1978. V. 26, N l/P. 36-52.

110. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H:G: Optimization andi approximation in deterministic sequencing and scheduling: a: survey// Ann. Discrete Math.- 1979,-V. 5.-P. 287 326.

111. Graham; R.L. Bounds on multiprocessing timing anomalies.- SI AM J. Appl:

112. Math., 1969, 17, № 2, 416-429.

113. Handbook of Scheduling:. Algorithms, Models and; Performance Analysis. Edited by J. Y-T. Leung // Chapman & Hall / CRC Computer and Information Science5Series. 2004.

114. Helman P., Bernard M.E. Moret, and ' Henry D. Shapiro., An Exact Characterization; of Greedy , Structures. / Department of Computer Science, University ofNcw Mexico^ 1993.

115. Held M., Karp R.M. A dynamic programming approach to sequencing problems. J.Soc.lndustr. and Appl.Math., 1962,IO, Ife 1, 196-210.

116. Hertz A., Taillard E.,.de Werra D. Tabu search / / Local search in combinatorial optimization. Chichester:. John*/Wiley& Sons; 1997. P. 121-136;

117. Himoff, J., Skobelev, P., Wooldridge, M. MAGENTA Technology: Multi-Agent Systems for Industrial Logistics The Fourth International Joint Conference on. Autonomous Agents and Multi Agent Systems. July 2005. .

118. Jackson J.R. Scheduling a.production-line^^minimize maximunr^ardiness//'Los Angeles,.CA: University of California,. 1955-Manag; Sci. Res. Proj. Res. Rep. N 43:

119. Johnson S.M. Optimal two- and three-stage production- schedules with setup times included// Naval Res. Logistics Quat.- 1954 V. l. P: 61 - 68.

120. Jackson J: R. Scheduling a production line, to minimize maximum tardiness. Research Report 43. Management Science Res. Proj., University of California, 1955.

121. Karp R. M., Miller R.E. Properties of a model for parallel computations determinacy, termination, queneing. SIAM J.Appl.Math.,-1966, 14, № 6, 1390-MIL

122. Kaufman. M/T. An almost-optimal algorithm for the assembly line scheduling, problem. IEEE Trans. Comput., 1974, N-II, 10-50.

123. Lawler E. L., Lenstra Jt K., Rinnooy Kan A. Hi G;, Shmoys D. Bl Scquensing .andv scheduling: algorithms and;; complexity. Centrum-, voor Wiskundeen Infonnatica

124. Report BS-R8909, 1989. . 1165 . Levin V. Il, Miretskii I. Yu. Optimal scheduling of jobs in conveyor systems //

125. Automat Remote Controll 1996.: V. 57. № '6. Part: 11 P.\ 773-7931 (Translated^ from:.1. Russian) ' .'.,.166? LePape, C. and S.F. Smithy "Management of Temporal.Constraints for- Factory

126. Scheduling", TechnicallReport TR-eMU-RI-87-13, The Robotics Institute; Carnegie:

127. Mellon:University, June; 1987. ;

128. Metaheuristic Optimization: Via Memory .and? Evolution:: Tabu Search' and: Scatter Search. Edited by Cesar Rego and Bahrain Alidaee. // Kluwer* Academic Publishers / Operational Research & Computer Science Series — Boston-London,

129. Minton, SI, M.D. Johnston, A.B. Phillips and P: Laird, "Solving Large Scale Constraint Satisfaction and Scheduling Problems Using, a Heuristic Repair Method",

130. Proceedings AAAI-90, Boston, July, 1990.

131. Russian Optical Cable Maker : increases visibility with Preactor (http://www.preactor.com/Case-Study/Casc-Studies/ZAO-SOiCK.aspx)

132. Rzevski G., Skobelev P. Managing a Virtual Environment. Patent'Application; No. 0202527.8, 2003.

133. Rzevski G.A., Skobelev P.O. Emergent Intelligence in Large Scale Multi-Agent Systems Education and Information Technologies Journal, Issue 2, Volume 1, 2007.

134. Rzevski G.A., Skobelev P.O., Andreev V.V. Magenta Toolkit: A Set of Multi-' Agent Tools for Developing Adaptive- Real-Time Applicátions Proceedings of International Conference of.' Multi-Agent and. Holónic Systems (HoloMAS 2007) -Germany, June 2007.

135. Safavi, A. and S.F. Smith, "A Heuristic Search Approach to Planning and

136. Scheduling, of Software Projects",, in Advances; in Articial Intelligence: Natural Language; and Knowledge-Based Systems, (ed.) M. Golumbic, Springer-Verlag Publishers,, 1990b

137. Scharge. L. ¡Solving Resource-Constrained. Network. Problems by Implicit Enumeration:;Non-Preemptive:Case //©per:'.Res: 1970.,-V18; - P: 263' -:278i

138. ShuttleSelect System at Port of Tauranga . Powered by Preactor (http://www.prcactor.coni/Case-Study/Case-Studies/Port-of-Tauranga.aspx) '

139. Stefan,Vos. Meta-heuristics: The state of the. Art. // Local* Search for Planning and Scheduling. Edited by A. Nareyek // ECAI 2000 Workshop, Germany, August 21, 2000 // Springer-Verlag, Germany, 2001.

140. Tcha D. W., Lee Bi-B A branch-and-bound algorithm for the multilevel uncapacitated!facility; location-problem*/ / European J. ©per: Res. 1984. V.: 18;.№ 1. Pi 35-43. ■■ • , •• ' ■ .■• • :- ' ■ ;

141. Toth, P. and D.Vigo. 0:- "Fast Local Search Algorithms for the; Handicapped; Persons Transportation*Problem.""In Iv. ©srnamandiJC. Kelly (edsi)j.Meta-Heuristics:,, Theory & Application, chapter 41. Boston: Kluwer Academic, 1996. pp. 677 690.

142. Vittikhi V.AJ, Skobelev P:©r Thermulti-agent models? of interaction irr demands .resource-networks-. // AutomaticalandiTelemechanica 2003;,.-№1. — pps K77-185;

143. Власов B:C. Задачи упорядочения и распределения«: ресурсов при изготовлении изделий микроэлектрониого производства // ИНФОРМАТИКА И СИСТЕМЫ УПРАВЛЕНИЯ. Москва, N 1,2010. с.63-69. ".

144. Richard Puddephatt. Gist increase fleet utilisation and reduce transportation costs and carbon footprint using Magenta's Dynamic Scheduling System (http://magenta-technology.com/web/guest/gist-press-release)

145. Woeginger G. J. Scheduling with time-dependent execution times // Inform.Process. Lett. 1995. V. 54, N 3. P. 155-156.

146. Zweben, M., M. Deale, and R. Gargan, "Anytime Rescheduling", Proceedings 1990 DARPA Workshop on Innovative Approaches to Planning, Scheduling and Control, (ed.) K.P. Sycara, Morgan Kaufmann Publishers, 1990.

147. Verena Kantere, Aris Tsois. Using ECA Rules to Implement Mobile Query Agents for Fast-Evolving Pure P2P Networks. Proc. of 4th Int. Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 2004), June, 19-23, 2004, New York, USA.