Введение к работе
Актуальность темы. С понятием расписания каждый человек знакомится с самого начала осознанной жизни. Расписания движения самолетов и поездов, распорядки работы магазинов и учреждений, производственные планы на смену, неделю, квартал. Еще совсем недавно такие расписания строились вручную.
В настоящее время для построения и управления расписаниями все чаще применяются автоматические и автоматизированные системы. Транспортная логистика, планирование взаимодействия поставщиков в единых технологических циклах, управление работой административных и образовательных учреждений - вот лишь небольшой перечень предметных областей, в которых задачи построения расписаний эффективно решаются средствами автоматизированного планирования и управления.
Автоматизированные системы построения и управления расписаниями могут отличаться:
1) уровнем оперативности - некоторые системы подготавливают
расписание заранее, другие строят и перестраивают его в процессе
исполнения;
2) периодом работы расписаний - одни системы генерируют
расписания на несколько лет вперед, другие - на несколько ближайших
часов;
3) уровнем автоматизации - существуют как полностью
автоматизированные системы реального времени, так и вспомогательные
системы поддержки принятия решений.
Однако практически всегда основной целью систем автоматического и автоматизированного построения расписаний является построение оптимальных расписаний и управление процессом их исполнения.
Если расписания в тех или иных предметных областях описываются широко распространенными моделями, то для построения расписаний можно использовать глубоко проработанный и апробированный аппарат теории расписаний. Однородным и неоднородным, многостадийным и одностадийным моделям расписаний посвящены работы Джонсона СМ., Танаева B.C., Шкурбы В.В., Коффмана Э.Г.
Если же структура расписания предметной области имеет нетривиальный иерархический характер, если уже попытки формализовать и определить множество возможных вариантов
расписаний вызывают сложности, то применение классического аппара теории расписаний ограничено, а во многих случаях и невозможно. каждом таком случае приходится дополнительно исследовать структу расписания и разрабатывать способы его формального описания. Имен] формальное описание затем позволит строить и перестраивать расписан! с учетом всех внутренних, причинно-следственных связе обуславливающих наличие тех или иных операций, элементов, блою расписаний.
Кроме того, зачастую требуется не просто генерировать своднь план для множества ресурсов в пакетном режиме, но и инкременталы перестраивать итоговое расписание согласно данным о ходе ei выполнения с учетом информации об изменении внешних услови Например, если в ходе выполнения расписания один из ресурсов вышел і строя, то расписание всех остальных ресурсов должно бьп скорректировано так, чтобы минимизировать воздействие данної события на качество всего расписания.
Примерами задач, в которых имеется сложная древовидна структура расписаний и необходимо динамическое построение оперативное перестроение расписаний, являются планирование ресурсе для транспортных компаний, планирование сложных технологически процессов, планирование загрузки и разгрузки крупнотоннажны контейнеровозов в портах, планирование связанных распределенны репликаций в информационных системах и многие другие.
Именно поэтому проблема разработки адекватных моделе расписаний с древовидной структурой, а также эффективных алгоритмо их построения и перестроения является чрезвычайно актуальной значимой. Исследованиям сложной структуры расписаний и алгоритмо их построения посвящены работы: Норенкова И.П., Прилуцкого М.Х., Власова B.C., Костенкова В.А.. Вместе с тем особенности и проблематик генерации расписаний с древовидной структурой в настоящее время слаб' освещены в научно-технической литературе.
Указанные выше обстоятельства обуславливают выбор в качеств объекта исследования процессов построения расписаний для технологических, транспортных и организационных систем, в основ' которых лежит обслуживание множества требований, структура которых имеет древовидный характер. Данная работа направлена на изучение природы расписаний для предметных областей с древовидной структурой
обслуживания требований, выявление их общих характеристик и описание обобщенной формы, позволяющей осуществлять процесс построения и перестроения таких расписаний. Именно поэтому в качестве предмета исследования была выбрана модель расписаний с древовидной структурой требований, а также методы и средства построения таких расписаний.
Цель работы - формализация моделей и разработка алгоритмов построения и перестроения расписаний с древовидной структурой требований для последующего создания программных средств автоматического и автоматизированного управления расписаниями.
Задачи исследования. Для достижения поставленной цели необходимо решение следующих задач:
-
Исследование особенностей расписаний в предметных областях с явно выраженной древовидной структурой обслуживания требований для выявления их наиболее общих черт и определения теоретической модели таких расписаний.
-
Разработка нотации представления расписаний реального масштаба времени, позволяющей не только строить и перестраивать расписания, но и верифицировать расписания различных предметных областей на соответствие предложенным моделям.
-
Разработка алгоритма эвристического поиска расписаний с древовидной структурой требований, позволяющего эффективно находить допустимые решения в условиях большой размерности сети заказов и ресурсов.
-
Проектирование обобщенной архитектуры взаимодействия основных участников процесса построения расписаний (задач и ресурсов), позволяющей распределять и изолировать логику планирования для повышения надежности и масштабируемости.
-
Апробация предложенных подходов путем разработки и реализации программного комплекса построения и динамического управления расписаниями, позволяющего автоматизировать процесс генерации и контроля исполнения плана в одной из подходящих предметных областей.
-
Оценка эффективности предложенных моделей и алгоритмов на основе исследования результатов использования разработанного программного комплекса в процессе его эксплуатации.
Методы исследования данной работы основаны на методах теор множеств и теории расписаний. Для описания моделей и нотац расписаний использовалась теория графов. Оценка сложное предлагаемых алгоритмов осуществлялась на основе теории сложное вычислений. При разработке архитектуры программного комплек построения расписаний применялся мультиагентный подход.
Научная новизна работы состоит в следующем:
-
Определен тип расписаний с древовидной структуре характеризуемый иерархической декомпозицией процесса обслуживай требований, порядком взаимодействия ресурсов, а также наличие внутренних причинно-следственных связей между различньт элементами расписаний.
-
Предложено и обосновано использование смешанных графов виде моделей таких расписаний для их начального построения последующего перестроения. Применение такого подхода позволж задать множество локальных структурных вариантов расписаш обслуживания одного требования и описать правила перехода от одної варианта к другому, тем самым формализовав процесс изменения шш так, чтобы в любой момент времени он оставался актуальным допустимым.
-
Разработан эвристический алгоритм генерации расписаний древовидной структурой связей, основанный на применении метол ветвей и границ в ходе построения дерева задач обслуживания каждог требования. Данный алгоритм позволяет перемещаться по множеств допустимых вариантов расписания в поиске наиболее эффективног решения, определяемого на основе гибко задаваемых критерие оптимальности.
-
Предложена мультиагентная архитектура системы построени расписаний, предназначенная для диспетчеризации активностей ресурсо и задач с целью повышения надежности, масштабируемости і расширяемости средств автоматического построения расписаний за сче' эффективного распределения логики планирования, механизмов поиска соответствия задача-ресурс и т.д.
Практическая значимость работы заключается в следующем: 1. Результаты исследований модели расписаний с древовидной структурой, а также алгоритмов их построения нашли практическое применение при разработке средств построения расписаний для группы
предметных областей, где важен учет древовидной природы расписания.
-
Предложена обобщенная архитектура систем автоматического построения расписаний, включающая средства получения данных о заказах и ресурсах, генерации расписаний, контроля их исполнения. Данная архитектура может быть использована для разработки систем автоматического планирования расписаний в широком спектре предметных областей.
-
Разработан программный комплекс построения расписаний водителей и машин для компаний, предоставляющих услуги по прокату и доставке автомобилей.
Реализация результатов работы. Основные результаты работы были использованы при разработке следующих программных систем:
-Система автоматического планирования «Астерикс» разработана компанией ООО НПК «Маджента Девелопмент» г. Самара. Данная система внедрена и используется британским отделением международной компании по сдаче автомобилей в аренду AVIS.
-Информационная система распределенных репликаций разработана и используется в Губернском Баке «Тарханы», а также в компании-операторе приема коммунальных услуг «Электронный Платеж».
Достоверность и обоснованность основных научных и практических результатов исследования диссертационной работы подтверждается: применением апробированного математического аппарата; получением оправданных, наглядных и интуитивно-убедительных результатов; экспериментальными данными тестовой эксплуатации разработанных программных средств, демонстрирующими высокую эффективность предложенных моделей и методов.
Основные положения диссертационной работы, выносимые на защиту.
-
Формальная модель расписаний с древовидной структурой связей, задаваемая в виде графа, вершинами которого, являются операции и задачи, а дуги отражают причинно-следственные и временные связи процесса обслуживания требований, а также правила преобразования данной модели как набор операций над графом, позволяющий описать процесс изменения расписаний.
-
Алгоритм построения и перестроения расписаний с древовидной структурой, позволяющий, учитывая внутреннюю структуру расписания и гибко заданные критерии оптимальности, обеспечить эвристический
анализ пространства возможных решений и выбор наиболее подходяи их вариантов.
-
Мультиагентная архитектура диспетчеризации активное ресурсов и задач, позволяющая рассмотреть процесс построеі расписаний как целенаправленное и координированное взаимодейсті ресурсов и задач с целью обеспечения надежной изоляции лоп принятия решений на каждом уровне планирования. Такой под> позволяет разрабатывать масштабируемые и расширяемые программн решения.
-
Программный комплекс построения расписаний для rent-a-i компаний, предназначенный для начального построения и оперативне перестроения расписаний водителей и автомобилей в процес выполнения заказов.
Апробация работы. Основные положения и результаты рабо' докладывались на:
-Международной конференции HoloMAS 2009, г. Линц, Австр 2009 г.;
-Международной конференции «Новые информационні технологии и системы», Пенза: ПГУ, 2009;
-Международном симпозиуме «Надежность и качество», Пенз ПГУ, 2009-2010;
-Всероссийской суперкомпьютерной конференции «Научнь сервис в сети Интернет: масштабируемость, параллельност эффективность» г. Новороссийск, 2009 г.;
-Девятой международной конференции «Высокопроизводительнь параллельные вычисления на кластерных системах» г. Владимир, 2009 г.;
-Всероссийской молодежной выставке-конкурсе прикладны исследований, изобретений и инноваций, г. Саратов, 2009 г.
-Всероссийской конференции «Технологии Microsoft в теории практике программирования», г. Нижний Новгород 2010.
Публикации. По теме диссертации опубликованы 15 печатны работ, 2 из которых в изданиях из перечня ВАК. Список публикаци приведен в разделе Литература.
Личный вклад автора. Основные результаты данной работы был. получены в ходе разработки системы автоматического планировани «Астерикс», проводимой ООО НПК «Маджента Девелопмент». Автор; принадлежат исследование расписаний с древовидной структуро)
требований, определение их формальной модели, нотации представления, а также разработка алгоритма построения и перестроения таких расписаний. В соавторстве со Скобелевым П.О. и Шибановым СВ. была предложена мультиагентная архитектура планирования расписаний и определены основные направления описания экспериментальной части работы.
Характеристика работы. Диссертационная работа содержит 198 страниц основного текста, 3 приложения, 75 рисунков, 12 таблиц и список использованной литературы из 194 наименований.
