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

ИЫ4616674

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

ЯНКОВ Игорь Александрович

ОПЕРАТИВНОЕ ПОСТРОЕНИЕ РАСПИСАНИЙ С ДРЕВОВИДНОЙ СТРУКТУРОЙ ТРЕБОВАНИЙ

Специальности:

05.13.01 - Системный анализ, управление и обработка информации 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени

кандидата технических наук

~ 9 ЛЕН 2010

ПЕНЗА 2010

004616674

Работа выполнена на кафедре «Математическое обеспечение применение ЭВМ» в Пензенском государственном университете.

Научные руководители:

Официальные оппоненты:

Ведущая организация:

кандидат технических наук, профессор Шашков Борис Дмитриевич кандидат технических наук, доцент Шибанов Сергей Владимирович доктор технических наук, профессор Лебедев Виктор Борисович; кандидат технических наук, доцент Дрождин Владимир Викторович Институт Проблем Управления Сложными Системами РАН (г.Самара)

Защита состоится ъ 2010 г. в /4 час. на заседай:

диссертационного совета Д.212.186.04 при Пензенском государственнс университете (440026, г. Пенза, ул. Красная, 40, корпус 1)

С диссертацией можно ознакомиться в библиотеке Пензенско! государственного университета. Автореферат размещен на сайте луту.рг^и.г

Автореферат разослан « /¿^» _2010 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

В.В. Смогуно

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

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

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

Автоматизированные системы построения и управления расписаниями могут отличаться:

1) уровнем оперативности - некоторые системы подготавливают расписание заранее, другие строят и перестраивают его в процессе исполнения;

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

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

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

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

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

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

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

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

Именно поэтому проблема разработки адекватных моделе расписаний с древовидной структурой, а также эффективных алгоритмо их построения и перестроения является чрезвычайно актуальной значимой. Исследованиям сложной структуры расписаний и алгоритмо их построения посвящены работы: Норенкова И.П., Пртуцкого М.Х., Власова B.C., Костенкова В.А.. Вместе с тем особенности и проблематик генерации расписаний с древовидной структурой в настоящее время слаб' освещены в научно-технической литературе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-Система автоматического планирования «Астерикс» разработана компанией ООО НПК «Маджента Девелопмент» г. Самара. Данная система внедрена и используется британским отделением международной компании по сдаче автомобилей в аренду AVIS.

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

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

Основные положения диссертационной работы, выносимые на защиту.

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

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

анализ пространства возможных решений и выбор наиболее подходяи их вариантов.

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

4. Программный комплекс построения расписаний для rent-a-i компаний, предназначенный для начального построения и оперативне перестроения расписаний водителей и автомобилей в процес выполнения заказов.

Апробация работы. Основные положения и результаты рабо' докладывались на:

-Международной конференции HoloMAS 2009, г. Линц, Австр 2009 г.;

-Международной конференции «Новые информационш технологии и системы», Пенза: ПГУ, 2009;

-Международном симпозиуме «Надежность и качество», Пенз ПГУ, 2009-2010;

-Всероссийской суперкомпьютерной конференции «Научнь сервис в сети Интернет: масштабируемость, параллельност эффективность» г. Новороссийск, 2009 г.;

-Девятой международной конференции «Высокопроизводительнь параллельные вычисления на кластерных системах» г. Владимир, 2009 г.;

-Всероссийской молодежной выставке-конкурсе прикладны исследований, изобретений и инноваций, г. Саратов, 2009 г.

-Всероссийской конференции «Технологии Microsoft в теории практике программирования», г. Нижний Новгород 2010.

Публикации. По теме диссертации опубликованы 15 печатны работ, 2 из которых в изданиях из перечня ВАК. Список публикаци приведен в разделе Литература.

Личный вклад автора. Основные результаты данной работы был. получены в ходе разработки системы автоматического планировани «Астерикс», проводимой ООО НПК «Маджента Девелопмент». Автор; принадлежат исследование расписаний с древовидной структуро]

требований, определение их формальной модели, нотации представления, а также разработка алгоритма построения и перестроения таких расписаний. В соавторстве со Скобелевым П.О. и Шибановым C.B. была предложена мультиагентная архитектура планирования расписаний и определены основные направления описания экспериментальной части работы.

Характеристика работы. Диссертационная работа содержит 198 страниц основного текста, 3 приложения, 75 рисунков, 12 таблиц и список использованной литературы из 194 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

обслуживания каждого требования.

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

Все это обуславливает необходимость разработки нового тш расписаний с древовидной структурой требований. Допустим пер< выполнением или после выполнения работы требуется осуществи' мероприятия по подготовке ресурса к работе. Классическим примеро может являться процесс переналадки станка перед/после операщ выполнения требований. В этом случае необходимо вести учет расписан! дополнительного ресурса, который будет осуществлять подготовь (переналадку) основного ресурса. Т.е. фактически необходимо создават новую задачу, подчиненную главному требованию, и осуществлять £ планирование, размещая операцию подготовки в расписани дополнительного ресурса. Но если рассматривать дополнительную задач по подготовке основного ресурса как идентичную главному требовании то можно утверждать, что в процессе ее планирования также возможн создание новой дополнительной задачи. В итоге каждое требование може создавать дерево подчиненных задач.

Имеется конечное множество требований Ы={1;2; ...;п} и конечно множество ресурсов Л={1;2...;г}. Будем считать, что продес обслуживания каждого требования состоит только из одной стадии 1 может быть осуществлен только одним ресурсом, допускается толью непрерывная обработка требования. При этом каждому требованию / е N сопоставляется некоторое множество ресурсов Л, с: Л, такое, что непосредственно само требование г должно быть обслужено любым из ресурсов те!!,, но не более чем одним одновременно.

Для описания дополнительных действий вводится понятие задачи, как единицы дополнительной работы для подготовки ресурса к выполнению требования. Каждая задача будет соответствовать одному из типов задач из множества Т = /7/2...;т}. При этом каждому типу задачи

i e T сопоставляется некоторое множество ресурсов Aci?, такое, что только ресурсом из множества R¡ может быть выполнена данная задача.

Таким образом, для каждого требования / е N задается своя, специфическая для этого требования, последовательность типов задач В' = (TÍ,T¿,...,T¿t), где T¡ е Т,\ <j<b¡, которая означает, что задача типа Т1-

должна быть выполнена перед выполнением требования i основным ресурсом. Таким же образом необходимо задать последовательность типов задач Л'= (7,1',Г2',...,Г0'), где T¡ е Т,1 < j < а,, которая должна быть выполнена после выполнения требования / основным ресурсом. Кроме того, такие же последовательности можно задавать не только для требований, но и для каждого типа задачи из множества Т. Т.е. можно определять В' = (7|',Г2',...,Г4') и А' = (7j',r2',...,ro') для /еГ, Но в этом

случае должно выполняться правило i£A',i£B',ieT, т.е. в списках дополнительных задач для данной задачи не может оказаться она сама.

Таким образом, расписание можно представить в виде s -{s1(t),s2(t),...,sn(í)} совокупности кусочно-постоянных функций Sjit), z е N, каждая из которых задана на интервале 0 < t < со и принимает значения 0,1,...,г. Если si(í')=m, то в момент f ресурс m обслуживает требование /. Если s¡(t') = 0, то в момент требование i не обслуживается.

i

1 2 Ресурс 3 - | |-1 | |-1

ИВ11 I I2B1I I Ресурс 2 - I-1 | 1-i 1

1B1B-Í Ьв IB-í 1А1 ¡ ' '

Ресурс 1 - -1 С-1-1 I I

I I I I I I

I_I_I_I_I_I_^

0123456789t

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

На рисунке 1 приведен график расписания s¡{t),i е N и дерево задач обслуживания требований N = { 1,2} ресурсами R={1,2,3} и типами задач Т = {Т\,Т2,ТЗ}. Все длительности операций равны единице.

В' = (Г2),А' = (Г\),В2 = (12),А2 = О, В72 = (ТЗ),Ап = (),Ви = (), Ат,=0,В"=0А"=0, R1 ={3},^J ={3},ДГ1 ={1},RT2={2},RT3 ={1}

11

С целью повышения наглядности на рисунке каждая операц помечена дополнительным набором индексов требований и задач, а так: признаком последовательности ("В" задача из списка В' элемек верхнего уровня /, "А" - изА'). Например, операция "2В1" реализу первую задачу из списка В2, а "2В1В1" - первую задачу из списка Втг.

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

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

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

- описывать внутренние связи между задачами;

- описывать отношения типа операция-задача;

- описывать последовательность выполнения операций.

Древовидную структуру связей между задачами удобн

представлять в виде маркированного ориентированного дерева = (Г, Р где Т- множество задач; Р=А^В - множество дуг; В - множество ду] отражающих подчиненность задач слева; А ~ множество дуг, отражающи подчиненность задач справа. Корнем такого дерева является главна задача, которая отражает основной процесс обслуживания требования.

К основным правилам преобразования дерева задач относятся:

1. Правило "создание подчиненной задачи" сгеШеТа8к(г, х, у).

2. Правило "отмена подчиненной задачи" сапсе1Тазк(г, х, у)

Для приведенных правилх,у^Т - различные вершины графа О; г еВиА.

Каждая дополнительная задача, созданная для подготовки основного ресурса, может задействовать сразу два ресурса: подготавливаемый ресурс (ресурс-потребитель) и ресурс, выполняющий дополнительную задачу по

12

подготовке основного (ресурс-исполнитель). При этом в расписании каждого из ресурсов создается по одной операции.

Таким образом, если задано множество операций 0= {1; 2;...; 0„}, то для каждой задачи / е Т однозначно задается пара операций множества О. V/:<о;о.^ >; / е Г;о.^еО, где о.^- операция-потребитель для

задачи /; о - операция-исполнитель для задачи /. (V

При этом одна и та же операция о, может входить в пары разных задач: <о,о,г> и <(¡¡¿,0 >;о,огос, еО;/,/еГ или <о!г,о> и <о,о)д>\о,огоЛ еО;!,/еГ.

Удобной моделью, позволяющей описать связи между задачами и операциями, является граф Сь = (Т, О, Ь), где Т - множество задач; О -множество операций; - множество ребер, описывающих связи

между операциями и задачами; Я - множество ребер, отражающих связь задач с их операциями-исполнителями; £> - множество ребер, отражающих связь задач с их операциями-потребителями.

К основным правилам преобразования графа С/ относят:

1. Правило "создание операций задачи" сгешеОрегаНот(х, у, г, й, г);

2. Правило "перепланирование задачи" ге8скес1и1еОрег1ают(х, у, г, А,

г);

3. Правило "отмена задачи" сапсеЮрегаИот(х, у, г, А, г).

Для приведенных правил хеТ, у.г е О- вершины графа Си г е Я, й е £>- ребра графа (7/..

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

Каждая дуга (о!,о2) показывает порядок выполнения операций, т.е. после выполнения операции <?; ресурс должен приступить к выполнению операции

К основным правилам преобразования графа Со относят:

1. Правило "добавление операции" ас1с1(х, у, 2, С], с2, с3)

2. Правило "удаление операции" АеШе(х, у, г, сь с2, с3)

Для приведенных правил х, у,г € О- вершины графа С0;

с,,с2,с3 € С-дуги графа <30.

Для эффективного использования графов Ст, (?£., С?0 как моделей для

преобразования расписаний объединим их в один смешанный граф (?= (Т, О, Р, Ь, С), комплексно описывающий все связи расписания.

Тогда основными правилами преобразования модели являются:

1. Правило "планирование задачи" $скес1ик(х) (рисунок 2) представляет собой последовательное применение правил сгеа1еОрега(1от(х, у, 2, с1, г), адй(у, с!: с2), аМ(г, с3, с4), сгеМеТаяЦии х, V,) и сгеа(еТазк(и2, х, у2)]

2. Правило "отмена задачи" сапсе1(х);

3. Правило "перепланирование задачи" ге5скес1и1е(х).

С

G

О

- schedule (х)

U,/ \\U2

о-

V2

Рисунок 2. Применение правила "планирование задачи"

G'

G'

Рисунок 3. Примеры последовательного применения правила "планирование задачи"

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

Задача составления расписания обслуживания множества требований N={nj,n2,..,nic} состоит в определении множества S={Sj,S2,..,S„,} расписаний ресурсов. Для каждого ресурса ieR задается последовательность St=(tu, ti2, ti3, ..., tin) состоящая из задач, которые

данный ресурс должен выполнять.

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

Таким образом, расписание 5' будет более предпочтительным, чем если ЛЛ^ОГ), где р = + ++

;еЛ' _/еА' /€/? /еЛ

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

1) планирование задачи;

2) создание подчиненных задач согласно схеме ветвления и результатам планирования задачи;

3) инициирование последовательного планирования подчиненных задач.

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

1) частное изменение целевой функции, ДР = + + + АГ\, > гДе ' ~ ресурс, на который запланировалась задача¡' е Я,} е N;

2) влияние текущего планирования на уже размещенные в расписании ресурсов задачи.

В результате планирования одной задачи значение целевой функции

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

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

г

задач. Число таких вариантов в среднем составляет Г1 ni, где / - среднее

1=1

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

Будем называть предварительной стоимостью размещения задачи (averageCosí) величину приращения целевой функции, происходящего в результате планирования только данной задачи. В то время как точная цена размещения задачи (таг&па1Соз{), будет включать в себя стоимости размещения самой задачи и всех подчиненных ей задач. Тогда процесс отыскания точной цены наиболее оптимального планирования задачи будет осуществляться следующим образом. На основе предварительной цены размещения всех ресурсов данного типа формируется список с лучшими вариантами (опциями) отсортированными по предварительной стоимости размещения. Далее происходит опрос всех ресурсов на предмет выявления точной цены размещения, начиная с самой предварительно лучшей опции. Процесс останавливается, если на каком-либо этапе текущее значение точной цены будет меньше, чем предварительная цена следующей опции. Т.е. если тащша/Сс^г, <аче^еСойм, где / = (Гт), ауе^еСоз(, - предварительная цена размещения, marginalCost¡ - точная цена размещения, т - число элементов в списке опций.

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

планирование не остается ни одного элемента.

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

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

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

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

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

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

Программный комплекс был реализован на языке Java 6.0 как набор серверных EJB компонент, обеспечивающих оперативное построение и

перестроение расписаний в рамках системы автоматического планирования ресурсов rent-a-car компании. Разработка комплекса осуществлялась с использованием клиент-серверных технологий J2EE, и мультиагентных средств МАЕ. Разработанный программный комплекс включает в себя: подсистему начальной обработки внешних событий, модуль учета критериев оптимальности, комплекс программ планирования и перепланирования задач, модуль проактивного улучшения расписания.

Протокол 1

Протокол 2

Агент задачи,!

Поступление ^

задачи на

планирование

Актуализация

задачи

Агент ресурса

^Запрос предварительной.

лтоимости *

[Агент ресурса;

Запроса на расчет __ «виртуального контракта»

Формирование предварительной цены размещений

(_Пр^дварительна^ цена размещения

Формирование списка лучших опций

Запрос «виртуального "" контрактаТ """ ^

ret) Формирование «виртуального контракта» планирования задачи(Пр.2)

. ^Ви£туальный^ __ контракт»

Выбор лучшего «виртуального контракта»

«Виртуальный контракт» на планирование задачи

X

Агент, задачи

Расчет «виртуального контракта»

Формирование цены размещения задачи

Определение цены перепланирования размещенных в расписании ресурса задач

Создание дополнительных подзадач

I Запроснапланирование^ "" подзадачи ^

I ref )

Планирование подэадачи(Пр.1)

. «Виртуальный контракт» ~ планирования подзадачи

Корректировка подзадач

Объединение «виртуальных контрактов»

Итоговый «виртуальный контракт» на планирование

Рисунок 4. Протоколы взаимодействия агентов задач и ресурсов

Также было проведено исследование основных результатов использования разработанной системы. Они были получены в ходе ее тестовой эксплуатации на четырех станция rent-a-car компании AVIS UK в восточной Англии в течение одной недели (02.11.2009-08.11,2009). За это время было обслужено 490 заказов. Для доставки автомобилей

привлекалось 37 водителей. За время тестовой эксплуатации было обработано 9332 события.

При этом основной показатель эффективности использования рабочего времени водителей "ОСОБ" составил 4.44 выполненных работ в день, а показатель простоя парка автомобилей "ОС81аск" достиг значении 24.27 часов. Эти значения на 17% и 25% соответственно лучше, чем показатели, получаемые в результате ручного построения расписания для данной предметной области. Это объясняется тем, что разработанная система позволяет учитывать существенно большее число факторов в процессе построения расписаний и оперировать значительно большим числом ресурсов и задач. Кроме того автоматизация процесса планирования расписаний приводит к повышению надежности функционирования и устойчивости бизнес процессов за счет возможности оперативного перестроения расписаний в ходе его исполнения.

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ В ИЗДАНИЯХ, РЕКОМЕНДОВАННЫХ ВАК РФ

1. Янков, И.А. Нотация представления сильносвязанных расписаний реального времени с учетом внутренней метаинформации / И.А. Янков, С.В. Шибанов, Б.Д. Шашков // Известия Высших Учебных Заведений. Поволжский Регион. Технические Науки. - 2009. - № 4. - С. 26-37.

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

ПУБЛИКАЦИИ В ДРУГИХ ИЗДАНИЯХ

3. Янков, И. А. Сервисно-компонентная модель web-приложения на основе опыта разработки системы "Электронный платеж" / И. А. Янков, С. В. Шибанов // Научный сервис в сети Интернет: технологии параллельного программирования: Труды Всероссийской суперкомпьютерной конференции (18-23 сентября 2006г., г. Новороссийск). - М.: Изд-во МГУ, 2006. С. 234-236.

4. Янков, И. А. Многоуровневая расширяемая система как средство создания единого информационного пространства ВУЗа / И. А. Янков, С. В. Шибанов // Математические методы в технике и технологиях: Сб. труд. XX международной конференции. Т. 10. - Ростов-на-Дону: Донской гос. техн. ун-т, 2007. - С. 297-300

5. Мультиагентный подход к планированию и распределению ресурсов в динамических гетерогенных системах / И.А. Янков, П.О. Скобелев, C.B. Шибанов, Б.Д. Шашков // Динамика гетерогенных структур: Сб. тр. - Пенза: Инф.-изд.ц. Пенз. ГУ, 2009. - Вып. 1. - С. 22-37.

6. A Multi-agent Scheduler for rent-a-car Companies Applications / S. Andeev, G.A. Rzevski, P. Shveikin, P.O. Skobelev, I.A. Yankov // Proceedings of International Conference of Multi-Agent and Holonic Systems (HoloMAS 2009) - Linz, Austria, September 2009. P. 305-314. ISBN 978-3-642-03666-8

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

8. Янков, И.А. Методика атоматизированного построения и динамического управления сильносвязанным расписанием с учетом внутренней метаинформации / И.А. Янков, C.B. Шибанов // Надежность и качество: Труды международного симпозиума. - Пенза: Инф.-изд.ц. Пенз. ГУ, 2009.-IT.-С. 214-218.

9. Янков, И. А. Параллельная обработка событий при построении и динамическом управлении сильносвязанными расписаниями / И. А. Янков, Б. Д. Шашков, С. В. Шибанов // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009г., г. Новороссийск). -М.: Изд-во МГУ, 2009. - С. 33-35. ISBN 978-5-21105697-8

10. Янков, И. А. Методика распределенного построения расписаний для систем обслуживания с древовидной структурой связей между операциями / И. А. Янков, С. В. Шибанов // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы Девятой международной конференции-семинара (23 ноября 2009 г., г. Владимир). - Владимир.: Изд-во ВГУ, 2009. - С. 424427. ISBN 978-5-89368-958-7

11. Янков, И. А. Автоматическое построение и оперативное управления сильносвязанными расписаниями в условиях быстро изменяющейся внешней среды / И. А. Янков, С. В. Шибанов // Всероссийская молодежная выставка-конкурс прикладных исследований, изобретений и инноваций: Сборник материалов (27-28 октября 2009 г.,

г.Саратов). - Саратов: Изд-во Сарат. Ун-та, 2009. - С. 96. ISBN 978-5-29203950-1

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

13. Янков, И.А. Архитектура системы построения и управления расписаниями с иерархической, древовидной структурой связей / И. А. Янков П Инновации и традиции науки и образования:материады Всероссийской научно-методической конференции. Часть 1. - Сыктывкар: Изд-во Сыктывкарского гос. ун-та, 2010. - С. 130-133.

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

15. Янков, И.А. Практическое применение модели расписаний с древовидной иерархической структурой для планирования ресурсов renta-car / И.А. Янков, С.В. Шибанов, Б.Д. Шашков // Надежность и качество: Труды международ, симпозиума, Т. I. - Пенза, Информац.-изд. центр Пенз. гос. ун-та, 2010. - С. 297-300.

Подписано в печать 11 ноября 2010 г. Формат 60x84/16. Бумага офсетная. Печать оперативная. Объем 1 п.л. Тираж 100 экз. Заказ № 1908 443011 г.Самара, ул. Академика Павлова, 1 Отпечатано в УОП СамГУ

Введение.

Глава 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

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.