Оперативное построение расписаний с древовидной структурой требований

Образование и науки | Эта статья также находится в списках: , , , , , , , , , , , , , , , , , | Постоянная ссылка

ЯНКОВ

Игорь Александрович

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

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

05.13.01 – Системный анализ, управление и обработка информации

05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

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

ПЕНЗА 2010

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

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

кандидат технических наук, профессор Шашков Борис Дмитриевич

кандидат технических наук, доцент Шибанов Сергей Владимирович

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

доктор технических наук, профессор

Лебедев Виктор Борисович;

кандидат технических наук, доцент

Дрождин Владимир Викторович

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

Институт Проблем Управления Сложными Системами РАН (г. Самара)

Защита состоится « 23 » декабря 2010 г. в _14_ час. на заседании диссертационного совета Д.212.186.04 при Пензенском государственном университете (440026, г. Пенза, ул. Красная, 40, корпус 1)

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

Автореферат разослан «____» __________________ 2010 г.

Ученый секретарь

диссертационного совета,

д. т.н., профессор

В. В. Смогунов

ОБщая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Имеется конечное множество требований N={1;2;…;n} и конечное множество ресурсов R={1;2…;r}. Будем считать, что процесс обслуживания каждого требования состоит только из одной стадии и может быть осуществлен только одним ресурсом, допускается только непрерывная обработка требования. При этом каждому требованию сопоставляется некоторое множество ресурсов , такое, что непосредственно само требование i должно быть обслужено любым из ресурсов , но не более чем одним одновременно.

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

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

Таким образом, расписание можно представить в виде совокупности кусочно-постоянных функций , каждая из которых задана на интервале и принимает значения 0,1,…,r. Если , то в момент ресурс m обслуживает требование i. Если , то в момент требование i не обслуживается.

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

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

С целью повышения наглядности на рисунке каждая операция помечена дополнительным набором индексов требований и задач, а также признаком последовательности (“B” задача из списка элемента верхнего уровня i, “A” – из). Например, операция “2B1” реализует первую задачу из списка B2, а “2B1B1” – первую задачу из списка .

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

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

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

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

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

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

Древовидную структуру связей между задачами удобно представлять в виде маркированного ориентированного дерева GT = (T, P), где T – множество задач; P= – множество дуг; B – множество дуг, отражающих подчиненность задач слева; A – множество дуг, отражающих подчиненность задач справа. Корнем такого дерева является главная задача, которая отражает основной процесс обслуживания требования.

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

1. Правило “создание подчиненной задачи” createTask(r, x, y).

2. Правило “отмена подчиненной задачи” cancelTask(r, x, y)

Для приведенных правил – различные вершины графа GT, .

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

Таким образом, если задано множество операций O= {1; 2;…; On}, то для каждой задачи однозначно задается пара операций множества O.

, где – операция-потребитель для задачи i;– операция-исполнитель для задачи i.

При этом одна и та же операция o, может входить в пары разных задач: или .

Удобной моделью, позволяющей описать связи между задачами и операциями, является граф GL = (T, O, L), где T – множество задач; O – множество операций; L= – множество ребер, описывающих связи между операциями и задачами; R – множество ребер, отражающих связь задач с их операциями-исполнителями; D – множество ребер, отражающих связь задач с их операциями-потребителями.

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

1. Правило “создание операций задачи” createOperations(x, y, z, d, r);

2. Правило “перепланирование задачи” rescheduleOpertaions(x, y, z, d, r);

3. Правило “отмена задачи” cancelOperations(x, y, z, d, r).

Для приведенных правил , – вершины графа GL; , – ребра графа GL.

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

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

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

1. Правило “добавление операции” add(x, y, z, c1, c2, c3)

2. Правило “удаление операции” delete(x, y, z, c1, c2, c3)

Для приведенных правил – вершины графа GO; – дуги графа GO.

Для эффективного использования графов GT, GL, GO как моделей для преобразования расписаний объединим их в один смешанный граф G= (T, O, P, L, C), комплексно описывающий все связи расписания.

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

1. Правило “планирование задачи” schedule(x) (рисунок 2) представляет собой последовательное применение правил createOperations(x, y, z, d, r), add(y, c1, c2), add(z, c3, c4), createTask(u1, x, v1) и createTask(u2, x, v2);

2. Правило “отмена задачи” cancel(x);

3. Правило “перепланирование задачи” reschedule(x).

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

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

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

Задача составления расписания обслуживания множества требований N={n1,n2,..,nk} состоит в определении множества S={S1,S2,..,Sm} расписаний ресурсов. Для каждого ресурса задается последовательность Si=(ti1, ti2, ti3, …, tin) состоящая из задач, которые данный ресурс должен выполнять.

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

Таким образом, расписание будет более предпочтительным, чем если , где .

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

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

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

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

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

1)  частное изменение целевой функции, , где i – ресурс, на который запланировалась задача j, ;

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

В результате планирования одной задачи значение целевой функции увеличивается на величину , где j – планируемая задача. При этом она включает в себя приращение целевой функции как результат размещения операций не только задачи j, но и всех ее подчиненных задач. Для того чтобы выбрать вариант планирования задачи j с наименьшим суммарным приращением, необходимо рассмотреть все возможные комбинации размещения задачи j и всех ее возможных подчиненных задач. Число таких вариантов в среднем составляет , где l – среднее число подзадач для каждой задачи, m – средняя глубина поддерева, ni – количество ресурсов, способных выполнить задачу i. Очевидно, что для предметных областей, где возможны глубокие деревья задач, алгоритм, использующий простой перебор вариантов, будет демонстрировать неприемлемую зависимость времени работы от размерности входных данных. Для решения этой проблемы было предложено использование метода ветвей и границ, позволяющего исключать из рассмотрения ветки дерева с заведомо неперспективными приращениями целевой функции.

Будем называть предварительной стоимостью размещения задачи (averageCost) величину приращения целевой функции, происходящего в результате планирования только данной задачи. В то время как точная цена размещения задачи (marginalCost), будет включать в себя стоимости размещения самой задачи и всех подчиненных ей задач. Тогда процесс отыскания точной цены наиболее оптимального планирования задачи будет осуществляться следующим образом. На основе предварительной цены размещения всех ресурсов данного типа формируется список с лучшими вариантами (опциями) отсортированными по предварительной стоимости размещения. Далее происходит опрос всех ресурсов на предмет выявления точной цены размещения, начиная с самой предварительно лучшей опции. Процесс останавливается, если на каком-либо этапе текущее значение точной цены будет меньше, чем предварительная цена следующей опции. Т. е. если , где , averageCosti – предварительная цена размещения, marginalCosti – точная цена размещения, – число элементов в списке опций.

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

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

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

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

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

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

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

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

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

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

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

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

Основные результаты работы

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

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

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

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

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

6.  A Multi-agent Scheduler for rent-a-car Companies / 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 компаний / И. А. Янков, С. В. Шибанов, Б. Д. Шашков // Труды 8-ой Международной конференции «Новые информационные технологии и системы», Пенза: ПГУ, 2009. – Ч. 2. – C.126-134.

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

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

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

11.  Янков, И. А. Автоматическое построение и оперативное управления сильносвязанными расписаниями в условиях быстро изменяющейся внешней среды / И. А. Янков, С. В. Шибанов // Всероссийская молодежная выставка-конкурс прикладных исследований, изобретений и инноваций: Сборник материалов (27–28 октября 2009 г., г. Саратов). – Саратов: Изд-во Сарат. Ун-та, 2009. – С. 96. ISBN 978-5-292-03950-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.  Янков, И. А. Практическое применение модели расписаний с древовидной иерархической структурой для планирования ресурсов rent-a-car / И. А. Янков, С. В. Шибанов, Б. Д. Шашков // Надежность и качество: Труды международ. симпозиума, Т. I. – Пенза, Информац.-изд. центр Пенз. гос. ун-та, 2010. – С. 297-300.

Подписано в печать 11 ноября 2010 г.

Формат 60´84/16. Бумага офсетная. Печать оперативная.

Объем 1 п. л. Тираж 100 экз. Заказ № 1908

443011 г. Самара, ул. Академика Павлова,1

Отпечатано в УОП СамГУ



Архивы pandia.ru
Алфавит: АБВГДЕЗИКЛМНОПРСТУФЦЧШЭ Я

Новости и разделы


Авто
История · Термины
Бытовая техника
Климатическая · Кухонная
Бизнес и финансы
Инвестиции · Недвижимость
Все для дома и дачи
Дача, сад, огород · Интерьер · Кулинария
Дети
Беременность · Прочие материалы
Животные и растения
Компьютеры
Интернет · IP-телефония · Webmasters
Красота и здоровье
Народные рецепты
Новости и события
Общество · Политика · Финансы
Образование и науки
Право · Математика · Экономика
Техника и технологии
Авиация · Военное дело · Металлургия
Производство и промышленность
Cвязь · Машиностроение · Транспорт
Страны мира
Азия · Америка · Африка · Европа
Религия и духовные практики
Секты · Сонники
Словари и справочники
Бизнес · БСЕ · Этимологические · Языковые
Строительство и ремонт
Материалы · Ремонт · Сантехника