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

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

Воробьева Ирина Александровна

Г

ИССЛЕДОВАНИЕ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ ПЛАНИРОВАНИЯ ОБ С ЛУ ЖИВ АНИЯ ТЕРМИНАЛОВ РАСПРЕДЕЛЕННЫХ КОМПЬЮТЕРНЫХ СИСТЕМ

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

АВТОРЕФЕРАТ

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

1 1 МАЙ 2012

Москва - 2012

005043691

005043691

Работа выполнена на кафедре математического моделирования ФГБОУ ВПО «НИУ «МЭИ».

Научный руководитель: кандидат физико-математических наук, доцент

Мещанинов Дмитрий Германович

Официальные оппоненты: Кутепов Виталий Павлович,

доктор технических наук, профессор, НИУ МЭИ, проф. каф. "Прикладная математика"

Хакимуллин Евгений Робертович, кандидат физико-математических наук, доцент, МИЭМ, проф. каф. "Исследование операций"

Ведущая организация: Факультет вычислительной

математики и кибернетики МГУ имени М.В. Ломоносова

Защита состоится 08 июня 2012 г. в 16- 00 на заседании диссертационного совета Д 212.157.01 при НИУ МЭИ по адресу:

Москва, ул. Красноказарменная, д. 17 в ауд. Г- 306.

С диссертацией можно ознакомиться в библиотеке НИУ МЭИ.

Автореферат разослан ^¿^ __2012 г.

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

диссертационного совета Д 212.157.01, кандидат технических наук, доцент '

Фомина Марина Владимировна

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

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

Рассматриваются автономные компьютеризированные объекты, в которых компьютер выполняет роль специализированного встраиваемого управляющего ядра; последнее является одновременно средством автоматизации управляемых объектов и средством обмена информацией в объединяющей их системе. Основой согласованного функционирования этих объектов является их объединение в локальную сеть с централизованным управлением и территориально-распределенным администрированием. Область размещения устройств сети: территория предприятия, город, регион. Подобные сетевые объединения относятся к классу распределенных компьютерных систем (РКС). Их примерами могут служить: сети телекоммуникационного оборудования; производственные сети станков с ЧПУ; системы контроля и управления доступом, видеонаблюдения в системах безопасности; сети по предоставлению банковских, информационных, торговых услуг и др.

Важнейшим требованием, предъявляемым к РКС, является ее отказоустойчивость и высокая рабочая готовность. Его выполнение обеспечивают методы и средства оперативного планирования (ОП), концепция развития которого в последнее десятилетие формулируется как «планирование для достижения нулевого уровня отказов»1 и предполагает тесное взаимодействие следующих этапов работы: 1) сбор информации; 2) анализ статистических данных; 3) прогнозирование необходимых работ и формирование требований о содержании и параметрах этих работ; 4) поиск последовательности работ, отвечающей сформированным требованиям, возможно с оптимизацией такой последовательности по определенным критериям.

Мы рассматриваем именно последний этап ОП. Серьезный вклад в развитие систем ОП, а также исследование проблем оптимизации и возникающих трудностей в поиске их решений внесли работы Л.В.Канторовича, Дж.Б.Данцига, Р.Гомори, А.Лэнда, Дж.Литтла, Р.Беллмана, С.М.Джонсона. На текущий момент уровень развития математических и программно-алгоритмических методов реализации различных этапов ОП сильно отличается, а неразвитость любого из взаимодействующих этапов снижает эффективность всего процесса оперативного планирования. Наша работа призвана повысить качество четвертого этапа. Поиск и оптимизация последовательности работ проводится нами на примере частного случая РКС — сети терминалов самообслуживания (СТС), обладающей специфическими чертами, например, в СТС возникают жестко регламентируемые нормативными актами и требованиями безопасности задачи инкассирования, а условия работы узлов сети предусматривают взаимодействие с человеком (клиентом), что отражается в параметрах и условиях задач ОП. Разработанные нами мето-

1 Иванов А., Токаренко Р. Планирование ремонтов: выбор оптимального пути// "Директор информационной службы". - Л>2. - 2009. - С.З.

ды планирования обслуживания СТС обобщаются и на произвольные РКС.

Решается задача составления плана оптимального обхода РКС несколькими обслуживающими бригадами. Есть множество узлов сети и множество бригад (я — число бригад), обслуживающих сеть. Обслуживание заключается в предоставлении однотипной услуги: поставка расходных компонентов узла, доставка (сбор) товара, техническое обслуживание узлов и т.п. Услуга имеет условную стоимость (не обязательно денежный эквивалент, зависит от конкретной практической задачи). Задан произвольный набор N узлов сети (подсеть с числом п узлов), который необходимо обслужить за отведенное время Тра5- Каждый узел г имеет характеристику — время его обслуживания Т;. В сети выделен узел — распределительный центр (РЦ) и для всех г,.; задано время Су проезда от узла г к узлу ], Су ф оо. Бригады обслуживают сеть циклично: начинают в РЦ, обходят часть узлов из набора N и возвращаются в РЦ — это один цикл обхода (подсети) бригадой; обслуженные узлы повторно не обслуживаются. За время Гра£ бригада может совершить несколько циклов обхода. Условие завершения цикла состоит в превышении временного лимита Граб или лимита г на суммарную стоимость услуги.

Задача состоит в поиске путей обхода (или построении плана обхода) заданных п узлов в бригадами с учетом ограничивающих характеристик Тра£ и г. При этом желательно минимизировать накладные расходы, например, транспортные, зависящие от суммарного времени работы всех бригад, необходимого на обслуживание узлов из набора N. Величины в, Трад и г назовем ресурсами сети. Отличие по типу обслуживания РКС: обслуживание внутренними силами производства (ресурс в ограничен максимальным числом собственных бригад штата сотрудников); и обслуживание силами сторонних организаций (ресурс я можно считать неограниченным, но требующим минимизации накладных расходов). Тип обслуживания РКС определяет принципиально разные проблемы производственных потребностей, решаемые средствами ОП (стоимость работ, скорость их выполнения, сбалансированная загрузка штата, экспертная оценка штатной комплектации), поэтому в работе выделены два типа задач планирования обходов РКС: планирование с ограниченным ресурсом в (обозначим такую задачу через 3-1) и планирование, где в не ограничено (обозначим 3*-1). Задача 3*-1 всегда будет иметь решение (не обязательно оптимальное), а задача 3-1 может оказаться неразрешимой уже на уровне поиска любого допустимого решения. Тогда представляет интерес, разрешима ли 3-1, если один из ресурсов не ограничен. Например, если ей г фиксировании, а Траб — не ограничено, можно решать модифицированную задачу 3-1 с оптимизацией одного из ресурсов при фиксированных значениях остальных ресурсов.

В практических задачах время, затрачиваемое на обслуживание узла, может быть случайной величиной. Допустим, что неисправность устройства г из набора К, обнаруженная уже в процессе его обслуживания, устранима за фиксированное время Трем силами бригады. Тогда общее время обслуживания составит: + 7рем, с прогнозируемой каким-либо способом вероятностью Л,- неисправности узла г или Т;, с вероятностью 1 — Л,-, если узел г исправен. Подобная ситуация возникает, например, в СТС, когда вероят-

ность hi вычисляется на основании данных о предполагаемом числе обращений клиентов к устройству. Образуется новая задача, связанная с проблемой учета прогнозируемых состояний случайных величин при предварительном планировании обслуживания РКС — планирование обходов РКС с учетом случайного времени обслуживания узлов (обозначим ее 3-2, если s ограничено, и 3*-2, если s не ограничено). В ряде практических задач возникает неопределенность в величине су, — например, если нужно учитывать степень загрузки дорог в РКС, локализованных в городах, при предварительном планировании обходов сети. Образуется новая задача составления планов обхода РКС с учетом переменного трафика (обозначим ее 3-3, если s ограничено, и 3*-3, если s не ограничено). Величина Су при предварительном планировании является не предопределенной константой, а неизвестной переменной величиной, зависящей от предполагаемого трафика на пути из i в j. При этом величина интенсивности трафика зависит от ряда факторов (времени суток, участка пути, погодных условий, аварий и др.) и не имеет точного аналитического описания, так как учесть все факторы воздействия на трафик крайне сложно. Таким образом, решение задачи связано с прогнозированием в условиях неполной информации и эмпирическим определением функции описания с^. В диссертации рассмотрены все перечисленные задачи, предложены методы и алгоритмы их решения.

Задачи 3-1 (3*-1) относятся к классу детерминированных, наиболее близкой (но не точной) известной математической формулировкой которых можно считать задачу нескольких коммивояжеров (3HKf. Ввод в детерминированные задачи таких параметров, как надежность работы устройства сети и загрузка дорог, переводят их в класс стохастических (3-2, 3*-2) и задач с неполной информацией (3-3, 3*-3), где поиск решений наиболее затруднен, а значительное количество параметров и ограничений, возникающих в реальных задачах ОП, делает большинство существующих алгоритмов либо неприменимыми, либо плохо адаптируемыми к их решению. Поэтому на практике описанные задачи часто решаются приближенно, без алгоритмической поддержки на основе экспертных оценок, и именно они снижают эффективность ОП в РКС, а поиск их алгоритмического и программного решений становится особенно актуальным для сетей большой размерности.

Л^Р-трудная задача коммивояжера(ЗК) является вырожденным случаем ЗНК и не имеет полиномиальных алгоритмов поиска точных решений, становясь неразрешимой уже для сетей с числом узлов больше 13, а типичная РКС может состоять из нескольких тысяч объектов, поэтому поиск решений родственных ЗНК задач планирования обходов в РКС в работе проводится среди известных приближенных и эвристических методов. Выделим из них два наиболее подходящих для задач, основанных на ЗНК. Метод Кларка-Райта является эвристическим итерационным методом решения задачи доставки грузов3. В его основу положено вычисление матрицы километровых расстояний и выигрышей, он способен решать только

2Hong S., Manfred W. Padberg A Note on the Symmertric Multiple Traveling Salesman Problem with Fixed Charges// Operations Research. - 25(5). - 1977. - p. 871.

3Распределительная транспортная задача по доставке грузов из одного центра множеству получателей состоит в следующем: определить максимум (минимум) целевой функции при сокращении объема ресурсов и потребности на них.

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

Для расширения возможностей компьютерных систем и поддержки задач планирования в PKG в условиях неполной, противоречивой и пересматриваемой информации предлагаемые программно-алгоритмические решения должны быть реализованы с учетом современного состояния рынка информационных технологий5 и ориентироваться на максимально широкий спектр обслуживаемых РКС относительно их технической оснащенности, площади распределения и числа узлов сети, а также уровня развития программного обеспечения (ПО) и специфики эксплуатации. Поэтому при выборе методов построения алгоритмов и их реализации в разработанном программном комплексе соблюден ряд важных требований: алгоритмическая простота и гибкость — для обеспечения возможности адаптации к специфике технических требований РКС; полиномиальная сложность алгоритмов — для обеспечения возможности составления краткосрочных планов и планирования в режиме квазиреального времени даже для сетей из нескольких тысяч объектов; минимальные требования к ресурсам, необходимым для работы ПО, и поддержание свойств открытых систем — для обеспечения интегрируемости ПО в сложные программные продукты, решающие комплексные задачи управления процессами в сетях.

Целью работы является построение моделей, алгоритмов и программных средств для составления оптимальных планов обслуживания РКС.

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

1. Построение и обоснование математической модели с целью решения практической задачи оптимального планирования работ относительно времени обхода терминалов сети и с учетом параметров ограничений обхода РКС. Выбор методов решения для двух типов задач: с ограниченным и неограниченным ресурсами обхода.

2. Модификации детерминированной задачи оптимального обхода сетей и методов ее решения с учетом случайного фактора — времени обслужи-

4Смирнов М.И., Хайруллин Р.3. Математические модели, используемые в системе оптимизации доставки товаров автотранспортом *Диспетчер* - М.: ИПМ им. М.В.Келдыша РАН, 2002.

5 Сейчас на рынке IT существует несколько основных разновидностей систем управления предприятиями и процессами: ERP (Enterprise Resource Planning), MRP (Manufactory Resource Planning), APS (Advanced Planning and Scheduling) и MES (Manufacturing Execution Systems).

вания терминалов сети и фактора неопределенности — степени загрузки транспортных путей. Математическая формулировка новых задач: стохастической и с неполной информацией.

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

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

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

6. Обеспечение мобильного (портативные ПК) и внутрисистемного (открытая архитектура) применения комплекса в задачах диспетчеризации и оперативного планирования, а также поддержки систем АСУ и ОПП, использующих многокритериальную оптимизацию.

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

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

Новыми в диссертации являются:

1. Семейство эвристических полиномиальных алгоритмов, основанных на модификациях АК и решающих следующие задачи: детерминированные задачи обхода РКС с ограниченным и неограниченным числом бригад; задачу обхода РКС с ограниченным числом бригад и учетом случайного времени обслуживания терминалов; задачу обхода РКС с ограниченным числом бригад и учетом степени загрузки дорог. Алгоритмы имеют оценки сложности на порядок лучше, чем метод МПР.

2. Метод учета случайности времени обслуживания терминалов сети на

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

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

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

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

Практическая значимость работы. Предложенные в работе алгоритмические решения позволяют широкому спектру пользователей с различным уровнем технической оснащенности решать такие задачи построения обходов сетевых устройств в сетях большой размерности, которые до настоящего времени обычно решались только с привлечением сил экспертов. Применение разработанных алгоритмов LLA, ULLA и LLA_P-Rna7 планирования обходов РКС на реальных данных практической задачи обходов сети терминалов Райффайзенбанка, обслуживающих Москву и Московскую область в 2012 г., позволило сократить число бригад обхода до 50% в сравнении с планами, составляемыми экспертами. Разработанный на объектном языке высокого уровня С++ программный комплекс TNTS (Terminal Networks Traversal Scheduling) имеет модульную структуру и ориентирован на открытые архитектуры как компьютерных систем, так и их ПО, что делает доступным встраивание его функциональных компонент в другие проекты. Этому способствует выбор внутреннего способа хранения данных, а также способ чтения/записи для внешних данных: для хранения данных использовались стандартные контейнеры библиотеки STL, для чтения/записи данных использовался потоковый ввод/вывод языка С++. При выборе способа построения базового алгоритма (БА), решающего детерминированную задачу планирования обходов сетей, предусматривалась возможность его расширения введением в исходную задачу новых параметров, не обязательно детерминированных. Эффективность и оправданность выбранного подхода была продемонстрирована успешной реализацией двух новых алгоритмов на базе БА: с введением случайного параметра и параметра неопределенности. Проведенное тестирование временных характеристик эффективности доступа к хранимой информации позволило исключить из рассмотрения вариан-

»Алгоритм, решающий детерминированную задачу обхода РКС с ограниченным числом бригад.

'LLA - решает задачу 3-1; ULLA - задачу ЗМ; LLA_P-Rnd - задачу 3-2.

ты с избыточной чувствительностью к аппаратным ресурсам, выбрать наиболее универсальные методы, обеспечить допустимость размера решаемых задач в диапазоне от десятка до нескольких тысяч устройств. Использование средств автоматизации программирования позволило определить числовые характеристики практического применения алгоритмов, выработать корректировки их программных реализаций для повышения качества планирования. В ТИТБ предусмотрены средства наладки, тестирования и моделирования, что позволяет решать широкий спектр задач (например, принятие решений о комплектовании служб оперативного обслуживания персоналом, транспортом, расходным материалом, выработке начальных нормативов выполнения работ) по одной лишь предварительной информации о составе и территориальной распределенности СТС. Скорость выполнения алгоритмов и реализация универсальной функции оптимизации по частному критерию в ТИТЭ позволят интегрировать ТМТЕ> в современные 1Т-системы (БСАБА, МЕЯ). Результаты диссертации внедрены в производственную деятельность ООО «Эрумпо» для повышения эффективности планирования обхода множества сайтов тендерных площадок для сбора информации от заказчиков и позволили оптимизировать этот процесс, а также использованы в учебном процессе кафедры математического моделирования НИУ МЭИ по курсам «Дискретная математика», «Дополнительные главы дискретной математики», «Математические методы в экономике», что подтверждено соответствующими актами.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных научно-технических конференциях «Информационные средства и технологии» (2007, 2011 гг.), «Радиоэлектроника, электротехника и энергетика» (2007, 2008, 2010 гг.), на международной научно-практической конференции «Современные проблемы и пути их решения в науке> транспорте, производстве и образовании' 2009» (Одесса, 2009 г.), на 5-й международной научно-практической конференции, посвященной 50-летию Сибирского государственного аэрокосмического института (Красноярск, 2010 г.), на 10-й международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010 г.) и на семинаре «Дискретные математические модели» НИУ МЭИ (Москва, 2012 г.). Результаты диссертационной работы изложены в 10 публикациях, из которых две — статьи в профильных журналах, рекомендованных ВАК РФ к защите кандидатских диссертаций, и 8 докладов на международных конференциях.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка, словаря терминов и сокращений и приложений. Общий объем диссертации занимает 251 машинописных страниц, содержит 11 рисунков, 30 таблиц и 3 приложения. Список литературы включает 74 источника.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении определена актуальность темы работы, формулируются задачи исследования диссертации, раскрывается научная новизна и практическая значимость полученных результатов, приведены сведения об апробации и внедрении работы.

. Глава 1 посвящена анализу практических предпосылок исследования, уточнению детерминированной задачи планирования обходов в РКС несколькими коммивояжерами. Выделены два основных ее типа, возникающие в РКС: с ограниченным и неограниченным числом £ бригад (3-1 и 3*-1, соответственно); сформулированы их математические постановки, основанные на теоретико-графовом подходе, описаны методы и алгоритмы их решения. Произведено сравнение предложенных методов с уже существующими.

Анализ практической задачи с целью уточнения и формализации ее постановки проведен на примере СТС8, обладающей всеми признаками и общими параметрами РКС. Предложена математическая модель РКС в виде полного взвешенного орграфа Е), в котором заданы веса су ребер и веса Т{ вершин. Произвольный набор N задан в виде подмножества вершин V С V, |У*| = п, а выделенная вершина РЦ обозначена щ, у1 € V. Время одного цикла обхода бригады равно сумме весов всех его ребер и вершин. Таких циклов у бригады при планировании обхода РКС может быть несколько. Время обхода РКС равно сумме времен циклов всех я бригад. Приведем математические формулировки задач. Ограничивающие характеристики задач 3-1 (3*-1) (Траб - рабочее время обслуживания РКС иг — суммарная стоимость однотипной услуги цикла обхода бригады) учтены в правиле ограничения циклов обхода бригад. Условная стоимость услуги принята равной единице и является естественной оценкой максимального числа и> узлов в цикле обхода бригады — и) = г. Такое допущение применимо во многих РКС (в частности, в большинстве СТС), где используются однотипные устройства, машины сопровождения бригад имеют одинаковую грузо/-вместимость, объем груза, требуемого для обслуживания узлов, одинаков. Правило ограничения циклов обхода (для одной бригады):

1. Каждый цикл обхода содержит не более г вершин.

2. Суммарное время Т^ум всех циклов обхода бригады; не превышает Траб. 3-1. Задача с ограниченным числом в бригад.

1. На полном графе в(У,Е), V — множество вершин, Е — множество ребер, заданы: неотрицательные веса всех ребер и всех вершин; правило ограничения циклов для фиксированного числа э ^ 1 бригад.

2. Задано подмножество V* С V и рассматривается порожденный V* подграф С*(У*,Е*).

3. Все циклы начинаются в заданной вершине г>ь она является единственной общей вершиной всех циклов.

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

3*-1. Задача с неограниченным числом в бригад отличается от 3-1 в п.4: найти минимальное число я бригад, требующихся для обхода вершин графа С.

Разработаны эвристические алгоритмы: алгоритм решения задачи 3-1 (далее АФ-1) и алгоритм решения задачи 3*-1 (АФ-11). В основу обоих

8СТС — частный случай РКС, поэтому везде, где заведомо допустимо обобщение на любой тип РКС, будет упомянуто РКС.

алгоритмов положены методы обхода графа в глубину для построения специального цикла алгоритма по списку вершин (так называемый цикл предварительной оценки, ЦПО), ближайшего соседа для построения минимального остовного дерева и алгоритм АК решения ЗК. Схематически оба алгоритма можно разбить на две части, которые рекурсивно повторяются для каждого узла сети: 1) поиск узлов РКС — «кандидатов» на включение в ЦПО; 2) принятие решения о включении узлов в ЦПО и контроль соответствия цикла ограничивающим его параметрам. Такой подход позволил успешно вводить в исходные задачи 3-1(3*-1) дополнительные факторы влияния на результат планирования без ухудшения оценки вычислительной сложности алгоритмов, решающих модифицированные задачи. Произведено сравнение алгоритмов с методами Кларка-Райта и МПР к решению задач, родственных ЗНК, в рамках которого доказана оценка сложности для этапа кластеризации в методе МПР: О Размер д задач 3-1(3*-1) равен Доказано, что сложность АФ-1 и АФ-Н полиномиальна относительно размера задач и составляет О

Рассмотрены варианты обеих задач (с предложением алгоритмических схем их решения), возникающие при вводе дополнительных факторов учета (различная грузовместимость машин, требование реакции на ситуацию выхода из строя одной из машин) или дополнительных параметров описания РКС (изменения, позволяющие расширить спектр учитываемых при планировании характеристик, например, приоритет обслуживания узла РКС). Дополнительные параметры определены и учтены при формировании классов объектов описания РКС в программном комплексе Т№ГЗ. Предлагаются модификации внутреннего алгоритма АК и условий локального оптимального выбора на основе предварительной кластеризации области обхода с классификацией вариантов географического расположения узлов РКС на ней.

В Главе 2 рассматриваются задачи 3-2(3*-2) — планирование обходов в СТС с учетом случайного времени обслуживания терминалов, которые образуются из задач 3-1(3*-1) усилением ограничительных характеристик планирования — переводом детерминированных величинТ* в разряд случайных т¡. Так как выполнение плана обхода за является одним из требований задач 3-1(3*-1), а влияющие на это время величины ц случайны, мы можем обеспечить выполнение составленного плана только с какой-то вероятностью Рдоп- При известном алгоритме решения задачи 3-1(3*-1) для решения 3-2(3*-2) достаточно: ввести временную корректировку в алгоритм планирования обхода СТС с учетом случайной составляющей времени обслуживания так, чтобы обеспечить выполнение плана с заданным уровнем доверия Рдоп- Предлагаемые нами методы одинаковы для обеих задач 3-2(3*-2), поэтому далее, для краткости, будем писать просто 3-2. Если требуемый уровень доверия Рдоп будет обеспечен в каждом цикле обхода каждой бригады, то и весь план будет составлен с заданным Рдоп- Это значит, что математическая формулировка задачи 3-2 отличается от формулировки 3-1 изменением одного ограничительного условия на максимальное число узлов в правиле ограничения циклов обхода бригады: 1. Каждый цикл обхода содержит не более г вершин.

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

где Гра6 — рабочего времени у бригады при заданном рабочем времени

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

цикле бригады, при котором выполняется вероятностное условие

Р + т0 * граб| > (1)

Обозначим такую подзадачу через 3-4. Алгоритмически решение задачи 3-4 не зависит от применяемого алгоритма решения 3-1(3*-1), а успешное решение задачи 3-2 полностью зависит от того, сможем ли мы совместить оба алгоритма (решения 3-4 и 3-1). Ниже предложена схема сведения проблемы 3-4 к решению математической задачи нахождения закона распределения суммы случайных величин и основанных на нем процедур учета случайного времени в 3-4: с аппроксимацией Пуассона (П-АП) и с нормальной аппроксимацией (П-НА) суммы случайных величин.

В СТС г* - случайное время обслуживания терминала г формируется при помощи характеристик: р — вероятность неисправности терминала при одном клиентском обращении, щ — статистически предполагаемое количество клиентских обращений к терминалу г, и вычисляется по формуле

Ti + Трем, с вероятностью hh ^^ hi = 1 - (1 - pp.

Ti, с вероятностью 1 — hi

Заменой г* = 7;+Трем где Ej — бинарная случайная величина, равная 1 с вероятностью hi, если устройство неисправно, и 0, если исправно, проблема поиска решения задачи 3-4 свелась к нахождению закона распределения

771

суммы случайных величин £i = Em9 после приведения (1) к виду

Т* , - C{m) m

Р {Ет < К{т)} > Рдоп, где К{т) = ра°-, С(т) = £ (сц + Ti). (2)

•'рем i=1

Существуют теоремы сходимости к известным распределениям, на основании которых в работе предложены два способа (П-АП и П-НА) решения задачи 3-4, применение которых зависит от параметров 3-4. Если все вероятности hi достаточно малы, т.е. выполнено неравенство

т т

(3)

1=1 ¡=1

то по теореме о редких событиях величина Ет распределена приближенно

93нак "="имеет смысл «равно по определению».

по закону Пуассона с параметром ат — МЕт, а условие (2) преобразуется в

[А'(т)1 ;

S(m) = Y, ~fe~arn ^ РД°П' где Целая часть А:(ш). (4)

¿=1 г'

Если неравенство (3) не выполняется, предложен другой подход. В работе доказано, что дисперсия каждой величины Si в задаче 3-2 ограничена и в силу центральной предельной теоремы Ет распределена приближенно по нормальному закону. Условие (2) принимает вид:

К(т) > МЕт + Ф-1(Рдоп)^5^, (5)

где Ф_1(Рдоп) = <5рдоп — эт0 квантиль порядка Рдоп стандартного нормального распределения.

Рассмотрено поведение величин S(m), К(т) и ат с ростом т, на основании чего процедуры учета случайного времени обслуживания терминалов в задаче 3-4 свелись к проверке условия (4) в П-АП и (5) в П-НА. На этапе принятия решения о включении терминала в цикл обхода бригады на очередном шаге т -Ь 1 при нарушении условия (4) или (5) завершается формирование обхода с исключением (т + 1)-го терминала из плана обхода.

Для экспериментальной проверки пригодности П-АП (П-НА) в решении задачи 3-2 выбраны практически достоверные данные частной проблемы — планирования массовых инкассации в СТС10. Этапы проверки:

1. Статистическая оценка и разбиение исходных диапазонов входных данных задачи 3-2 по типу, допустимости и качеству аппроксимации Ет предложенными законами: Пуассона и нормальным.

2. Проверка работоспособности П-АП и П-НА моделированием на различных входных данных задачи 3-4. В результате выявлена проблема, не проявившаяся на первоначальных этапах работы: недостижимость заданной точности выполнения плана Рдоп в обеих процедурах.

3. Теоретический анализ и проверка повторным моделированием предложенных решений проблемы: предварительный подбор квантилей в П-НА и введение способа рандомизации для П-АП.

4. Тестирование программной реализации алгоритмов решения задачи 3-2, основанных на встраивании в АФ-I процедур П-АП (П-НА). Вероятность hi неисправности терминала г является случайной величиной как функция от случайной величины щ. В экспериментальных проверках предполагается, что все щ независимы и одинаково распределены: п; ~ TZ[nL\nR\ для всех i. Вычислена полная вероятность события «терминал г неисправен»: Р {г, = 1} = МЫ = ц. Показано, что она не зависит от г, а значит экспериментальное распределение Efn ~ Вг(т, /л). Найдено ана-

{i-p)nL-(i-p)nR+1 . 1 литическое представление для /г. ц = i--p{nR-nL+i)—' 1 ~ ' —>rn-

Статистически оценены диапазоны параметров т и hi, зависимого от 71 j. Критерий качества приближения определяется в работе как AFmax =

max |.Рл(г) - (г)|, где FE3, FA — функции распределения для законов

и аппроксимирующего соответственно. Приближение считается хорошим, ес-

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

ли ДРтах ^ 0.1 для нормального закона и ДРтах < 0.0511 для закона Пуассона. Составлены таблицы допустимых для применения обеих аппроксимаций диапазонов величин [?л£;тл] и [пь;пл] с указанием соответствующих значений ц и диапазонов колебания ДРтах на различных фиксированных т из отрезков [ш1; тя]. Весь диапазон возможных в задаче значений тип, получил разделение на области с хорошим качеством приближения, области, где на отдельных участках сравнительных гистограмм наблюдается превышение нормы по ДРтаХ: и области, приводящие суммы Ет к неизвестному типу распределения. На этапе моделирования задачи 3-4 были исследованы все указанные области.

Этап моделирования задачи 3-4 и ее решения с помощью П-АП (П-НА) заключался в формировании процедуры построения одного цикла обхода терминалов сети Л^исп = 1000 раз с табличной квантилью <2рдоп Длял/"(0, 1) из условия принятия решений (5) для П-НА и без квантили и условием принятия решений (4) для П-АП. Экспериментальный уровень доверия Рдоп вычисляется по формуле Рд0П = 1 - Число ошибок Л^ш находит-

ся с помощью предварительно сформированного массива из е^ имитирующего наличие или отсутствие неисправностей в устройствах: если истинное время Тист для построенного на основании условия принятия решений цикла превышало Т^^, формировался флаг ошибки. Были выявлены проблемы, не позволяющие в отдельных случаях добиться приемлемой близости Рдоп — Рдоп (погрешность Рдоп не должна превышать 0.05) на входных данных с хорошим качеством приближения. Проведенный анализ позволил предложить следующее решение проблем.

Для применения П-НА необходима проверка условия (сц + Т,)/Трем ^ 1 для всех г,сети. В случае его нарушения недопустимо использовать известные квантили <2рдоп распределения ЛА(0,1); необходимо осуществлять предварительный подбор квантилей для каждой индивидуальной задачи 3-2. Это является недостатком П-НА, но подобный подход позволяет получать Рдоп с погрешностью не выше 0.0075. Для преодоления трудностей в П-АП предложено ввести дополнительную процедуру рандомизации. Ее смысл заключается в том, что когда в П-АП выполняются неравенства 5(ттг + 1) < Рдоп < 5(т) с вероятностью д, в цикл обхода включается т устройств, в противном случае (тп + 1) устройство. Вероятность q вычисляется по формуле q = 5(т)-5[т+1) • Последующее тестирование программных реализаций решения задачи 3-2, основанных на «П-АП с дополнительной рандомизацией», позволило получать Рдоп с погрешностью не выше 0.05.

Моделирование, проведенное в тех областях тп и щ, где не было достигнуто хорошее качество приближения или не было найдено простого приближения для Ет, показало существенное увеличение величины погрешности Рдоп* вдвое для П-АП и втрое для П-НА. Автор рекомендует использовать предложенные решения на таких данных только в случаях, когда задачи не

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

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

По результатам проведенного в главе 2 анализа была составлена сводная таблица зависимости применяемой процедуры аппроксимации от входных данных 3-2. Выработаны методики решения 3-2 в произвольных СТС, подтвержденные программными реализациями модификаций алгоритма АФ-1. Методики могут быть перенесены на любую РКС, имеющую необходимые данные для прогнозирования возможной неисправности узлов сети.

В Главе 3 рассматриваются задачи 3-3(3*-3) — составления планов обхода РКС с учетом переменного трафика па дорогах, которые образуются из задач 3-1(3*-1) переводом детерминированных величин времени су проезда от узла г к узлу 3 в разряд переменных величин, зависящих от предполагаемого трафика на пути из г в j. Сложность задачи связана с определением подходящей эмпирической функции описания зависимости су от трафика и учета ее изменяемого состояния в зависимости от времени включения в расписание планируемого обхода РКС. Рассмотрены практические основания возникновения задачи, проанализированы возможности учета трафика и существующие алгоритмы, выработаны требования к ресурсной эффективности алгоритмов, подтвержденные экспериментально. Задача формализована, предложен способ се решения.

Пусть АТ3о — время прохождения пути во длины й8о — скорость на этом пути, #яо = 1ва/АТ8о. По результатам анализа факторов влияния на ЛТ5о и выработке требований к ресурсам, подтвержденных серией тестов определения быстродействия на различных объемах и типах памяти, введена функция, характеризующая влияние на АТео: коэффициент загрузки дорог = Ка{£), зависящий от времени суток и выбранного пути. Пусть V® — средняя скорость движения транспорта на пути во при отсутствии затруднений (К3о{1) = 1), тогда влияние коэффициента на ее изменение при К30(1) > 1 введем при помощи формулы

V0

Время ДТ8о прохождения пути во находится из формулы

М 2(>0= / йп (() М, где (ТА + ЛТ,а) е [ТА, Тв]. (7)

^ТЛ

Функция загрузки дорог для данной СТС на каждом ребре 8} сети задана собственной функцией от одного непрерывного аргумента I. Количество функций ограничено числом ребер графа, причем сами функции не являются известными параметрами задачи. На входе задачи вместо аналитического задания функций Кц{£) имеются значения

функции К™6{и)

с неравномерным шагом аргумента^-, = К„}{1 ¿). Задачи 3-1 (3*-1),. в которых веса ребер исходного графа Е), характеризующие время проезда между узлами при коэффициенте загрузки дорог равном единице, усилены вышеописанными табличными данными о значениях коэффициента и обозначены, соответственно, 3-3 (3*-3).

Пусть для данного пути йо таблично задан коэффициент загрузки дорог К™6(/\и) на каждом интервале разбиения Р30 = {Р?° = Д£;}, г = 1,..., д,

суточного интервала [Тд, Тв] (в общем случае q г q(sо)) в виде ступенчатой функции Kjga^(t), к которой применяется метод кусочно-линейной аппроксимации по средним точкам с коэффициентами а, и 6j.

Исходное разбиение заменяется разбиением Р;^ = {(Pm )«}Li = {[Та — Pmo.JV]; [PmuPm2]\ •••; [Pm^2,Pm,^ = ТВ}}, Где pm = ((pi+i - Pi)/2) + ри 1 = l,...,q - 2, pmo = TA и = Тв с кусочно-линейной функцией k*0(i),

непрерывной на интервале [Та,Тв] и гладкой на интервалах разбиения Р^. Тогда K*o(t) на [ртщ-иРгт], i — 1 >•••,? — представляет из себя линейную функцию fi(t) = di ■ t + b{, где а; ф aj и fy ф i ф j, в общем случае, а коэффициенты а,, 6; € К получаются решением (</ — 1) систем уравнений. Ранее ввели учет влияния KSo(t), считая KSo(t) непрерывной и гладкой на всем интервале \Га,Тв], через формулы (6), (7).

Пусть /¿(pm,.,,?,,*) s тогда формула (7) преобразуется к виду

f vso(t) dt =t/°0-JTa

и искомое время Т®0 прохождения пути so с учетом загрузки K*0(t) произвольной точки начала движения Тьед € [Pmj_i>.Pm,-] вычисляется по формуле

TS0 = (Тъед + |) • exp , где Tbeg,TSo € [р^,^.], j = 1,-,q - 1.

Если TSo > pmj, применяется рекуррентная схема вычислений.

На основании приведенных теоретических расчетов и описанного в главе 1 алгоритма АФ-I предложены два новых алгоритма: эвристический алгоритм решения 3-3 (далее АФТ-I) и алгоритм вычисления времени обхода цикла с учетом влияния коэффициента загрузки дорог (кусочно-линейная аппроксимация) (далее ТЦО_КЛА). ТЦО_КЛА используется в АФТ-I для решения частной подзадачи подобно тому, как используются П-АП и П-НА в решении 3-2. Доказано, что сложность ТЦО_КЛА составляет О (z • q), где г — число ребер цикла, q — число интервалов на [Га, Тв]', сложность АФТ-I составляет О (q • | . Размер g задачи 3-3 равен q • \V\, поэтому сложность АФТ-I относительно размера задачи составляет О (<?3), т.е. она полиномиальна, причем степень полинома не высока, равна 3.

Предложенный подход к решению 3-3 (3*-3) применим к любой РКС и наиболее актуален в РКС, локализованных в городах. В работе также указан способ введения уникальных параметров разбиения qs. суточного интервала для каждого ребра графа G (против единого параметра q), что потребует удвоения объема памяти для хранения данных. Это не влияет на скорость доступа к данным, однако позволяет повысить точность планирования.

Глава 4 содержит описание программного комплекса TNTS и серии тестов, проведенных с его помощью, для алгоритмов: LLA, ULLA, LLA_P-St, LLA_P-Rnd и LLA_N 12, реализованных на основании материала глав 1 и 2. Рассматриваются результаты практического испытания предложенной

13LLA — решение задачи 3-1; ULLA — решение задачи 3*1: LLA_P-St, LLA_P-Rnd — решение задачи 3-2 методом аппроксимации Пуассона в стандартном исполнении (St) и с процедурой рандомизации принятия решений (Rnd); LLA_N — решение задачи 3*-2 методом нормальной аппроксимации.

Гг

dt

t art + bj

методики и разработанного программного обеспечения.

Описание TNTS включает: его назначение, функциональное наполнение, интерфейс, команды управления и способы доступа к ним, а также форматы хранения объектов (графов) в TNTS, файлов описания РКС и результата планирования. Описание стандартной СТС (матрицы весов ребер и вершин, вектор числа клиентских обращений) реализуется в объектах базового класса «Base Graph». Предусмотрены дополнительные параметры описания РКС: матрицы приоритетов обслуживания ребер, вершин, специально организованная матрица хранения кратчайших путей между всеми вершинами. Эти параметры могут присутствовать в РКС в различных комбинациях. Для таких РКС создано семь дочерних классов класса «Base Graph» по принципу множественного «ромбовидного» полиморфного наследования. Файл описания РКС состоит из числовой информации с допустимыми разделителями в текстовом формате. Основная информация текстового файла результата: время выполнения алгоритма, статистическая информация для режима тестирования вероятностных алгоритмов, список циклов обхода с дополнительной информацией о номере бригады, времени выполнения цикла и флаге, отображающем причину завершения формирования цикла обхода.

Интерфейс расширенных функций TNTS реализован в виде соответствующих диалоговых окон. Диалоговое окно моделирования РКС с двумя типами распределения узлов в прямоугольной области: равномерным (тип RDP) и нормальным распределением некоторого числа узлов относительно нескольких центров с произвольными радиусами (Rx, Ry) разброса распределения (тип NDP). Тип RDP характеризует региональные силыюразреженные, а NDP — городские РКС. Тип NDP формируется методом генерации случайной величины, основанном на предельной теореме

где aj ~ 7£[0; 1]. Для случайной величины 7 = Rx-(3 выполняется D(Rx-/3) = Rx2 • Т)(/3) = Rx2, а значит 7 ~ Л/"(0, Rx2), т.е. сг = R^. Из известных данных для нормально распределенных величин и правила трех (двух) сигмп имеем: Р {-2RX «С 7 ^ 2Д*} = 0.95 и Р {-ЗД* «С 7 < 3Я*} = 0.975. В заданный радиус Rx попадут не все точки, но большая их часть с высокой вероятностью. Разработан алгоритм генерации узлов РКС с типом NDP с задаваемыми параметрами.

Установки параметров планирования (формирование объекта класса «планирование») определяют тип решаемой задачи и формируются в специальном диалоговом окне, содержащем указание назначения и допустимых диапазонов рабочих величин. Разработана универсальная процедура оптимизации по частному критерию. TNTS может осуществлять оптимизацию по критериям: число бригад, грузовместимость машин, рабочее время бригад алгоритмами планирования LLA, LLA_P-St, LLA_P-Rnd и LLA_N. Возможно расширение числа и типов критериев, числа используемых алгоритмов. Алгоритмы планирования должны отвечать требованиям: иметь тип, определенный в TNTS как typedef int(*pFF) (const boolfe) и поддержи-

13 "В результате испытания случайной величины ее значение практически достоверно окажется в интервале * математическое ожидание ±3<т>п.

вать класс «алгоритм», определенный и описанный в TNTS. Таким образом, все алгоритмы в TNTS могут функционировать в двух режимах (при этом каждое допустимое решение всегда ищется на основании минимизации времени в циклах обхода РКС): 1) поиск допустимого решения задачи при всех фиксированных параметрах (или частных критериях) планирования; 2) поиск оптимального частного критерия при остальных фиксированных. Заметим, что в обоих режимах возможна ситуация, когда решение не будет найдено. Исключение составляет алгоритм ULLA — он всегда ищет оптимальный частный критерий (число бригад) и всегда находит решение, так как по условию задачи 3*-1 число бригад не ограничено.

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

Проведена проверочная серия тестов для LLA_P и LLÄ_N с оценкой точности, построенной на базе статистического подхода и «правила трех сигм», представлены данные с фактическими уровнями доверия для алгоритмов LLA_P-St,LLA_P-Rnd, сопровождаемые оценками полученного качества приближения к заданному уровню доверия. Проверка алгоритма LLA_N подтвердила выводы, полученные на этапе моделирования процедуры — правильно подобранная квантиль обеспечивает соответствие фактически достигаемой точности заданному уровню Рдоп- Сравнительное тестирование LLA_P-St и LLA_P-Rnd, подтвердило, что введение дополнительной процедуры рандомизации в процедуру Пуассона существенно приближает фактическую точность выполнения плана к заданной.

Следующая серия тестов осуществляет сравнение по показателям минимального числа s бригад обхода и времени t выполнения алгоритма оптимального по s планирования, относительно таких характеристик как: тип алгоритма, допустимый уровень точности решения, число узлов РКС и тип распределения узлов на плоскости. Сравниваются алгоритмы LLA, LLA_P и LLA N. По времени выполнения нет явных отличий для LLA, LLA_P и LLA_N на РКС, сопоставимых по числу узлов. Тип распределения узлов не влияет на время работы алгоритмов. При уменьшении Рдоп результаты оптимизации по числу бригад для алгоритмов LLA_P и LLÄ_N стремятся к результатам LLA, а разница между результатами LLA_P-St и LLA_P-Rnd увеличивается, что соответствует результатам предварительного этапа тестирования. Доказаны следующие оценки сложности для алгоритмов, решающих 3-2: О (V|3) для алгоритма LLA_N и О + Граб • |F|2) для алгоритмов LLA_P-St, LLA_P-Rnd, где \V\ — число узлов сети, Tpag — заданный параметр задачи. Размер д задачи 3-2 равен Траg ■ |V|, а значит оценки для алгоритмов LLA_N, LLA_P-St и LLA_P-Rnd являются полиномиальными относительно размера задачи.

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

Основные особенности реализации TNTS: унифицированный интерфейс и полиморфная реализация структур данных для хранения объектов (графов) описания РКС, обладающих дополнительными (одиночными или смешанными) признаками, с использованием множественного «ромбовидного» наследования; специально организованная динамическая структура «умного указателя»14 для единого доступа к объектам разных наследующих классов; полиморфная реализация процедуры чтения данных из файла при помощи виртуальной функции базового класса; средства расширения (встраивания в системы, переносимости на другие платформы) комплекса, обеспеченные разработанными контейнерными классами основных объектов («алгоритм», «план», «сеть», «модель») и средствами библиотеки STL, механизмами абстракции с сохранением стандарта языка С++ ANSI/ISO. В Заключении подведены итоги проведенной работы. Приложения содержат иллюстрации к разделу об экспериментальном определении пригодности аппроксимаций Пуассона и нормальной, файлы заголовков программного комплекса TNTS и иллюстрации моделирования РКС в нем, пример работы алгоритма АФ-I, копии актов о внедрении.

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

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

2. Построены математические модели РКС на языке взвешенных графов, даны постановки различных вариантов оптимизационных задач обхода вершин графов.

3. Обоснован выбор математических методов, наиболее приемлемых для работы с построенными моделями.

4. Предложены алгоритмы планирования работ в РКС, основанные на выбранных методах, осуществлена их программная реализация.

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

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

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

8. Предложены методы и реализованы средства обеспечения взаимодействия TNTS с пользователем и другими программными продуктами: пользовательский интерфейс со средствами визуализации модели и процесса обслуживания РКС, средства автоматической модификации и настройки, направленные на наиболее эффективное применение программного продукта, учет особенностей конкретной анализируемой сети.

"Термин объектно-ориеитированного программирования (Б.Страуструп, Язык программирования С++, 3 изд., с.337).

9. Экспериментально доказана и проверена адекватность построенных математических методов и эффективность основанных на них алгоритмов и программных средств реальным техническим системам.

ОСНОВНЫЕ ПУБЛИКАЦИИ

1. Воробьева И.А., Горицкий Ю.А. Об учете случайного времени обслуживания при эксплуатации сетей терминалов // Вестник МЭИ, - №6, - М., 2007. - С.57—64.

2. Воробьева И.А. Математические модели задач планирования и координации массовых инкассаций в сетях терминалов самообслуживания.// Вестник МЭИ, - №6, - М., 2006. - С.10-19.

3. Воробьева И.А., Мещанинов Д.Г. Процедура нормальной аппроксимации в задаче учета случайного времени обслуживания // 19-я Междунар. науч.-техн. конф. «Информационные средства и технологии»: 18-20.10.2011 г., сб.тр./ МЭИ - М.,2011. - Т.З. - С. 185-193.

4. Воробьева И.А., Мещанинов Д.Г. Алгоритмы краткосрочного планирования обходов сетей с переменным трафиком и случайным временем обслуживания // X Междунар. науч.-практ. конф. «Исследование, разработка и применение высоких технологий в промышленности»: 09-11.12.2010, тез. док л./СПб НЦ РАН - Спб.,2010. - Т.З. - С. 72-73.

5. Воробьева И.А. Прогноз времени обхода цикла сети с учетом переменного коэффициента загрузки дорог // Логистика и экономика регионов: матер. V Междунар. науч.-практ. конф., посвящ. 50-летию Сиб. гос. аэрокосмич. ун-та, 75-летию образования Краснояр. края: 4-5.02.2010 г./ СГАУ - Красноярск, 2010. - Т.2. - С. 476-478.

6. Воробьева И.А. Алгоритм планирования массовых инкассаций в сетях с переменным трафиком // XVI Междунар. науч.-техн. конф. студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: тез. докл./ МЭИ - М.,2010. - Т.1. - С. 324-326

7. Воробьева И.А. Об учете переменного трафика в задаче планирования обходов для сети терминалов // Междунар. науч.-практ. конф. «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании' 2009»: 21-28.12.2009 г., сб. науч. тр./ УкрНИИМФ - Одесса,2009. -Т.22. - С.30-31.

8. Воробьева И.А. Экспериментальные испытания алгоритмов планирования обходов сетей терминалов самообслуживания // XIV Междунар. науч.-техн конф. студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: тез. докл./ МЭИ - М.,2008. - Т.1. - С. 268-269

9. Воробьева И.А., Горицкий Ю.А. Исследование вопроса учета времени обслуживания терминалов в алгоритме планирования инкассаций сетей с денежным потоком.// 15-я МНТК «Информационные средства и технологии» 16-18.10.2007 г, сб.тр./МЭИ - М.,2007. - Т.З. - С.117-120.

10. Воробьева И.А. Поиск приближенных решений задач планирования массовых инкассаций в сетях терминалов самообслуживания // XIII Междунар. науч.-техн. конф. студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: тез. докл./ МЭИ - М.,2008. - T.l. - С.327

Подписано в печать 4$, ^ & г Зак. ¡JfQ Тир. ЮО П.л. Полиграфический центр МЭИ Красноказарменная ул., д. 13

61 12-5/3821

ФГБОУ ВПО «НИУ «МЭИ»

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

Воробьева Ирина Александровна

ИССЛЕДОВАНИЕ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ ПЛАНИРОВАНИЯ ОБСЛУЖИВАНИЯ ТЕРМИНАЛОВ РАСПРЕДЕЛЕННЫХ КОМПЬЮТЕРНЫХ СИСТЕМ

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

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

Научный руководитель кандидат физ.-мат. наук доцент Д.Г. Мещанинов

Москва - 2012

ОГЛАВЛЕНИЕ

Введение ..................................................................................................5

Глава 1: Задачи планирования и координации массовых обходов в компьютерных сетях ..........................................................31

1.1 Анализ практической задачи. Уточнение постановки задачи 31

1.2 Математические модели двух задач на языке теории графов 40

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

1.4 Другие способы решения задач планирования..................55

1.5 Преимущество алгоритмов АФ-1 и АФ-Н........................61

Выводы по первой главе..........................................65

Глава 2: Об учете случайного времени обслуживания

терминалов при эксплуатации в СТС ........................................67

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

2.2 Определение распределения случайного параметра задачи (аппроксимации: нормальная и Пуассона)......................72

2.3 Экспериментальное определение пригодности приближений . 82

2.3.1 Общее описание экспериментальной методики .... 82

2.3.2 Нормальная аппроксимация: проверка диапазонов . . 87

2.3.3 Нормальная аппроксимация: моделирование процедуры 92

2.3.4 Аппроксимация Пуассона: проверка диапазонов ... 96

2.3.5 Аппроксимация Пуассона: моделирование процедуры 101

Выводы по второй главе..........................................109

Глава 3: Задача планирования обходов устройств в сетях с

непостоянной загрузкой ....................................................................110

3.1 Практические основания возникновения задачи. Постановка задачи..............................................................110

3.2 Теоретическое обоснование способа решения задачи.....129

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

3.4 Алгоритм вычисления времени обхода цикла с учетом

влияния коэффициента загрузки дорог........................142

Выводы по третьей главе........................................151

Глава 4: Программный комплекс TNTS (Terminal Networks

Traversal Scheduling) ..........................................................................152

4.1 Краткое описание программного комплекса TNTS......152

4.2 Форматы данных в TNTS........................................159

4.3 Диалоговые окна, расширенное описание функционала . . . 167

4.3.1 Окно моделирования СТС................................167

4.3.2 Окно установки параметров планирования......176

4.3.3 Организация подбора оптимального решения по заданному параметру....................178

4.4 Сравнительное тестирование алгоритмов...........182

4.4.1 Проверочная серия для LLA_P и LLA_N.......183

4.4.2 Сравнительные тесты для алгоритмов LLA, LLA_P

и LLA_N.........................188

4.4.3 Сравнительные тесты для алгоритмов LLA и ULLA . 193

4.4.4 Сравнение результатов алгоритмов и экспертных решений ........................................198

4.5 Особенности реализации TNTS.................202

Выводы по четвертой главе...................204

Направления дальнейших исследований ................. 206

Заключение ............................................................................................207

Список литературы ............................................................................209

Словарь терминов и сокращений ................................................219

Приложение 1. Иллюстрации к разделу 2.3 о тестировании пригодности вероятностных процедур ................... 223

Приложение 2. Программный комплекс TNTS: иллюстрации к тестам. Пример работы алгоритма АФ-1 .......... 241

Приложение 3. Акты о внедрении результатов диссертационной работы............................................. 250

Введение

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

Актуальность проблемы

Рассмотрим автономные компьютеризированные объекты, в которых

компьютер выполняет роль специализированного встраиваемого управляющего ядра, а последнее является одновременно средством автоматизации управляемых объектов и средством обмена информацией в объединяющей их системе. Основой согласованного функционирования этих объектов является их объединение в локальную сеть с централизованным управлением и территориально-распределенным администрированием. Область размещения устройств сети может варьироваться: территория предприятия, город, регион. Подобные сетевые объединения относятся к классу РКС. Их примерами могут служить: сети телекоммуникационного оборудования; производственные сети станков с ЧПУ; системы контроля и управления доступом, видеонаблюдения в системах безопасности; сети по предоставлению банковских, информационных, торговых услуг и др.

Важнейшим требованием, предъявляемым к РКС. является ее отказоустойчивость и высокая рабочая готовность. Его выполнение обеспечивают методы и средства оперативного планирования (ОП), концепция развития которого в последнее десятилетие формулируется как «планирование для достижения нулевого уровня отказов» [33] и предполагает тесное взаимодействие следующих этапов работы:

1. сбор информации;

2. анализ статистических данных;

3. прогнозирование необходимых работ и формирование требований о содержании и параметрах этих работ;

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

Мы рассматриваем именно последний этап ОП. На текущий момент уро-

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

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

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

Рассмотрим частную задачу планирования сервисного обслуживания для банковской сети, являющейся характерным примером сети удаленных терминалов самообслуживания (ТС), обеспеченной МВК. Опишем процесс сервисного обслуживания на примере инкассации банкоматов сети. В последнее десятилетие в практику ведущих мировых банков были введены системы централизованного мониторинга расходуемых ресурсов ТС, лучшие из которых (например, Gasper Vantage компании NSR) позволяют заранее выделять те ТС, которые вскоре могут потребовать сервисного обслуживания; и так называемые системы управления наличностью, позволяющие для отдельно взятого ТС рассчитать оптимальную загрузку на следующий инкассационный цикл, используя статистику его прошлой работы за длительный период. Применение МВК может дать хорошие результаты; например, в Альфа-Банке (имеющем около полутора тысяч банкоматов по России, из них несколько сотен в Москве) показатель работоспособности банкоматов достигал в 2006 году 99,2%х. Однако эффект применения МВК до сих пор продолжает ограничиваться прогнозированием множества требующих обслуживания ТС, загрузки и состава работ на каждом из них, оставляя без алгоритмической поддержки решение задач планиро-

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

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

Решается задача составления плана оптимального обхода РКС несколькими обслуживающими бригадами. Есть множество узлов сети и множество бригад (s — число бригад), обслуживающих сеть. Обслуживание заключается в предоставлении однотипной услуги: поставка расходных компонентов узла, доставка (сбор) товара, техническое обслуживание узлов и т.п. Услуга имеет условную стоимость (не обязательно денежный эквивалент, зависит от конкретной практической задачи). Задан произвольный набор N узлов сети (подсеть с числом п узлов), который необходимо обслужить за отведенное время TDag. Каждый узел г имеет характеристику

— время его обслуживания Т). В сети выделен узел — распределительный центр (РЦ) и для всех г.] задано время проезда от узла г к узлу ], гб'у ф оо. Бригады обслуживают сеть циклично: начинают в РЦ. обходят часть узлов из набора N и возвращаются в РЦ — это один цикл обхода, (подсети) бригадой; обслуженные узлы повторно не обслуживаются. За время ■^раб бригада может совершить несколько циклов обхода. Условие завершения цикла состоит в превышении временного лимита или лимита Z на суммарную стоимость услуги.

Задача состоит в поиске путей обхода (или построении плана обхода) заданных п узлов в бригадами с учетом ограничивающих характеристик Тра^ и При этом желательно минимизировать накладные расходы, например, транспортные, зависящие от суммарного времени работы всех бригад, необходимого на обслуживание узлов из набора N. Величины в, и назовем ресурсами сети. Важно принципиальное отличие по типу обслуживания РКС: обслуживание внутренними силами производства (ресурс й ограничен максимальным числом собственных бригад штата сотрудников); и обслуживание силами сторонних организаций (ресурс й можно считать неограниченным, но требующим минимизации накладных расходов). Тип обслуживания РКС определяет принципиально разные проблемы производственных потребностей, решаемые средствами ОП (стоимость работ, скорость их выполнения, сбалансированная загрузка штата, экспертная оценка штатной комплектации), поэтому в работе выделены два типа задач планирования обходов РКС: планирование с ограниченным ресурсом 5 (обозначим такую задачу через I) и планирование, где в не ограничено (обозначим II). Задача II всегда будет иметь решение (не обязательно оптимальное), а задача I может оказаться неразрешимой уже на уровне поиска любого допустимого решения. Тогда представляет интерес, разрешима ли

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

В практических задачах время, затрачиваемое на обслуживание узла, может быть случайной величиной. Допустим, что неисправность устройства г из набора 14, обнаруженная уже в процессе его обслуживания, устранима за фиксированное время Трем силами бригады. Тогда общее время обслуживания составит: Тг + Трем, с прогнозируемой каким-либо способом вероятностью К1 неисправности узла г или 7], с вероятностью 1 — Кг1 если узел г исправен. Подобная ситуация возникает, например, в СТО, когда вероятность вычисляется на основании данных о предполагаемом числе обращений клиентов к устройству. Образуется новая задача, связанная с проблемой учета прогнозируемых состояний случайных величин при предварительном планировании обслуживания РКС — планирование обходов РКС с учетом случайного времени обслуживания узлов (с ограниченным и неограниченным ресурсом й). В ряде практических задач возникает неопределенность в величине Юу, — например, если нужно учитывать степень загрузки дорог в РКС, локализованных в городах, при предварительном планировании обходов сети. Образуется новая задача составления планов обхода РКС с учетом переменного трафика (с ограниченным и неограниченным ресурсом й). Величина и>у при предварительном планировании является не предопределенной константой, а неизвестной переменной величиной, зависящей от предполагаемого трафика на пути из г в j. При этом величина интенсивности трафика зависит от ряда факторов (времени суток, участка пути, погодных условий, аварий и др.) и не имеет точного аналитического описания, так как учесть все факторы

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

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