Введение к работе
Актуальность работы. Диссертационная работа посвящена проектированию, реализации, настройке и экспериментальному испытанию программно-алгоритмического комплекса, предназначенного для автоматизации оперативного планирования в сложных системах, которые состоят из объектов, функционирующих в автономном режиме и нуждающихся в обслуживании в произвольные моменты реального времени.
Рассматриваются автономные компьютеризированные объекты, в которых компьютер выполняет роль специализированного встраиваемого управляющего ядра; последнее является одновременно средством автоматизации управляемых объектов и средством обмена информацией в объединяющей их системе. Основой согласованного функционирования этих объектов является их объединение в локальную сеть с централизованным управлением и территориально-распределенным администрированием. Область размещения устройств сети: территория предприятия, город, регион. Подобные сетевые объединения относятся к классу распределенных компьютерных систем (РКС). Их примерами могут служить: сети телекоммуникационного оборудования; производственные сети станков с ЧПУ; системы контроля и управления доступом, видеонаблюдения в системах безопасности; сети по предоставлению банковских, информационных, торговых услуг и др.
Важнейшим требованием, предъявляемым к РКС, является ее отказоустойчивость и высокая рабочая готовность. Его выполнение обеспечивают методы и средства оперативного планирования (ОП), концепция развития которого в последнее десятилетие формулируется как «планирование для достижения нулевого уровня отказов»1 и предполагает тесное взаимодействие следующих этапов работы: 1) сбор информации; 2) анализ статистических данных; 3) прогнозирование необходимых работ и формирование требований о содержании и параметрах этих работ; 4) поиск последовательности работ, отвечающей сформированным требованиям, возможно с оптимизацией такой последовательности по определенным критериям.
Мы рассматриваем именно последний этап ОП. Серьезный вклад в развитие систем ОП, а также исследование проблем оптимизации и возникающих трудностей в поиске их решений внесли работы Л.В.Канторовича, Дж.Б.Данцига, Р.Гомори, А.Лэнда, Дж.Литтла, Р.Беллмана, С.М.Джонсона. На текущий момент уровень развития математических и программно-алгоритмических методов реализации различных этапов ОП сильно отличается, а неразвитость любого из взаимодействующих этапов снижает эффективность всего процесса оперативного планирования. Наша работа призвана повысить качество четвертого этапа. Поиск и оптимизация последовательности работ проводится нами на примере частного случая РКС — сети терминалов самообслуживания (СТС), обладающей специфическими чертами, например, в СТС возникают жестко регламентируемые нормативными актами и требованиями безопасности задачи инкассирования, а условия работы узлов сети предусматривают взаимодействие с человеком (клиентом), что отражается в параметрах и условиях задач ОП. Разработанные нами мето-
1 Иванов А., Токаренко Р. Планирование ремонтов: выбор оптимального пути// "Директор информационной службы". - №2. - 2009. - С.З.
ды планирования обслуживания СТС обобщаются и на произвольные РКС. Решается задача составления плана оптимального обхода РКС несколькими обслуживающими бригадами. Есть множество узлов сети и множество бригад (s — число бригад), обслуживающих сеть. Обслуживание заключается в предоставлении однотипной услуги: поставка расходных компонентов узла, доставка (сбор) товара, техническое обслуживание узлов и т.п. Услуга имеет условную стоимость (не обязательно денежный эквивалент, зависит от конкретной практической задачи). Задан произвольный набор N узлов сети (подсеть с числом п узлов), который необходимо обслужить за отведенное время Т . Каждый узел і имеет характеристику — время его обслуживания Т{. В сети выделен узел — распределительный центр (РЦ) и для всех г, j задано время с^ проезда от узла і к узлу j, Cij ^ оо. Бригады обслуживают сеть циклично: начинают в РЦ, обходят часть узлов из набора N и возвращаются в РЦ — это один цикл обхода (подсети) бригадой; обслуженные узлы повторно не обслуживаются. За время Т.'^ бригада может совершить
несколько циклов обхода. Условие завершения цикла состоит в превышении временного лимита Т ^ или лимита г на суммарную стоимость услуги.
Задача состоит в поиске путей обхода (или построении плана обхода) заданных п узлов s бригадами с учетом ограничивающих характеристик Т.'^
и г. При этом желательно минимизировать накладные расходы, например, транспортные, зависящие от суммарного времени работы всех бригад, необходимого на обслуживание узлов из набора N. Величины s, 71 5 и г назовем
ресурсами сети. Отличие по типу обслуживания РКС: обслуживание внутренними силами производства (ресурс s ограничен максимальным числом собственных бригад штата сотрудников); и обслуживание силами сторонних организаций (ресурс s можно считать неограниченным, но требующим минимизации накладных расходов). Тип обслуживания РКС определяет принципиально разные проблемы производственных потребностей, решаемые средствами ОП (стоимость работ, скорость их выполнения, сбалансированная загрузка штата, экспертная оценка штатной комплектации), поэтому в работе выделены два типа задач планирования обходов РКС: планирование с ограниченным ресурсом s (обозначим такую задачу через 3-1) и планирование, где s не ограничено (обозначим 3*-1). Задача 3*-1 всегда будет иметь решение (не обязательно оптимальное), а задача 3-1 может оказаться неразрешимой уже на уровне поиска любого допустимого решения. Тогда представляет интерес, разрешима ли 3-1, если один из ресурсов не ограничен. Например, если s и г фиксированны, а Т ^ — не ограничено, можно
решать модифицированную задачу 3-1 с оптимизацией одного из ресурсов при фиксированных значениях остальных ресурсов.
В практических задачах время, затрачиваемое на обслуживание узла, может быть случайной величиной. Допустим, что неисправность устройствам из набора N, обнаруженная уже в процессе его обслуживания, устранима за фиксированное время Трем силами бригады. Тогда общее время обслуживания составит: Т{ + Трем, с прогнозируемой каким-либо способом вероятностью hi неисправности узла і или Ті, с вероятностью 1 — hi, если узел і исправен. Подобная ситуация возникает, например, в СТС, когда вероят-
ность hi вычисляется на основании данных о предполагаемом числе обращений клиентов к устройству. Образуется новая задача, связанная с проблемой учета прогнозируемых состояний случайных величин при предварительном планировании обслуживания РКС — планирование обходов РКС с учетом случайного времени обслуживания узлов (обозначим ее 3-2, если s ограничено, и 3*-2, если s не ограничено). В ряде практических задач возникает неопределенность в величине Qj, — например, если нужно учитывать степень загрузки дорог в РКС, локализованных в городах, при предварительном планировании обходов сети. Образуется новая задача составления планов обхода РКС с учетом переменного трафика (обозначим ее 3-3, если s ограничено, и 3*-3, если s не ограничено). Величинас^- при предварительном планировании является не предопределенной константой, а неизвестной переменной величиной, зависящей от предполагаемого трафика на пути из і в j. При этом величина интенсивности трафика зависит от ряда факторов (времени суток, участка пути, погодных условий, аварий и др.) и не имеет точного аналитического описания, так как учесть все факторы воздействия на трафик крайне сложно. Таким образом, решение задачи связано с прогнозированием в условиях неполной информации и эмпирическим определением функции описания Су. В диссертации рассмотрены все перечисленные задачи, предложены методы и алгоритмы их решения.
Задачи 3-1 (3*-1) относятся к классу детерминированных, наиболее близкой (но не точной) известной математической формулировкой которых можно считать задачу нескольких коммивояжеров (ЗНК)2. Ввод в детерминированные задачи таких параметров, как надежность работы устройства сети и загрузка дорог, переводят их в класс стохастических (3-2, 3*-2) и задач с неполной информацией (3-3, 3*-3), где поиск решений наиболее затруднен, а значительное количество параметров и ограничений, возникающих в реальных задачах ОП, делает большинство существующих алгоритмов либо неприменимыми, либо плохо адаптируемыми к их решению. Поэтому на практике описанные задачи часто решаются приближенно, без алгоритмической поддержки на основе экспертных оценок, и именно они снижают эффективность ОП в РКС, а поиск их алгоритмического и программного решений становится особенно актуальным для сетей большой размерности.
TVP-трудная задача коммивояжера(ЗК) является вырожденным случаем ЗНК и не имеет полиномиальных алгоритмов поиска точных решений, становясь неразрешимой уже для сетей с числом узлов больше 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 Распределительная транспортная задача по доставке грузов из одного центра множеству получателей состоит в следующем: определить максимум (минимум) целевой функции при сокращении объема ресурсов и потребности на них.
детерминированную задачу оптимизации. При решении сходных задач применяется также метод поэтапного решения (МПР): сначала кластеризация (алгоритм, основанный на выборе транзитивно-ближайших сообщений), затем маршрутизация в ЗК (эвристический алгоритм имитации отжига, или алгоритм Н.Метрополиса). Этот метод не рассчитан на решение задачи для нескольких коммивояжеров одновременно. Предложенный в работе подход лишен недостатков обоих описанных методов, он позволяет адаптировать алгоритмы под все упомянутые выше типы задач планирования обходов в РКС. Доказано, что наши алгоритмы имеют оценки сложности на порядок лучше, чем указанный метод МПР.
Для расширения возможностей компьютерных систем и поддержки задач планирования в РКС в условиях неполной, противоречивой и пересматриваемой информации предлагаемые программно-алгоритмические решения должны быть реализованы с учетом современного состояния рынка информационных технологий5 и ориентироваться на максимально широкий спектр обслуживаемых РКС относительно их технической оснащенности, площади распределения и числа узлов сети, а также уровня развития программного обеспечения (ПО) и специфики эксплуатации. Поэтому при выборе методов построения алгоритмов и их реализации в разработанном программном комплексе соблюден ряд важных требований: алгоритмическая простота и гибкость — для обеспечения возможности адаптации к специфике технических требований РКС; полиномиальная сложность алгоритмов — для обеспечения возможности составления краткосрочных планов и планирования в режиме квазиреального времени даже для сетей из нескольких тысяч объектов; минимальные требования к ресурсам, необходимым для работы ПО, и поддержание свойств открытых систем — для обеспечения интегрируемости ПО в сложные программные продукты, решающие комплексные задачи управления процессами в сетях.
Целью работы является построение моделей, алгоритмов и программных средств для составления оптимальных планов обслуживания РКС.
Отличительной особенностью работы являются постановка и решение задачи обхода сетевых устройств несколькими исполнительными бригадами одновременно, а также учет неопределенных и случайных параметров, требований распределенности системы и минимизации ресурсов, необходимых для функционирования ПО. Основные задачи, решаемые в диссертации:
Построение и обоснование математической модели с целью решения практической задачи оптимального планирования работ относительно времени обхода терминалов сети и с учетом параметров ограничений обхода РКС. Выбор методов решения для двух типов задач: с ограниченным и неограниченным ресурсами обхода.
Модификации детерминированной задачи оптимального обхода сетей и методов ее решения с учетом случайного фактора — времени обслужи-
4Смирнов М.И., Хайруллин Р.З.Математические модели, используемые в системе оптимизации доставки товаров автотранспортом «Диспетчер» - М.: ИПМ им. М.В.Келдыша РАН, 2002.
5 Сейчас на рынке IT существует несколько основных разновидностей систем управления предприятиями и процессами: ERP (Enterprise Resource Planning), MRP (Manufactory Resource Planning), APS (Advanced Planning and Scheduling) и MES (Manufacturing Execution Systems).
вания терминалов сети и фактора неопределенности — степени загрузки транспортных путей. Математическая формулировка новых задач: стохастической и с неполной информацией.
Алгоритмическая и программная реализация методов решения сформулированных задач оптимального обхода сетей.
Разработка программного комплекса, позволяющего эффективно применять и сравнивать предложенные алгоритмы планирования оптимальных обходов сетей, варьировать исходные параметры задач. Реализация, наряду с исполнительскими, функций анализа и самотестирования, возможность выбора наиболее эффективных алгоритмов для конкретных вариантов обслуживаемых компьютерных сетей.
Определение средствами математического моделирования реальных значений рабочих величин и возможных ограничений для применения предложенных методов решений.
Обеспечение мобильного (портативные ПК) и внутрисистемного (открытая архитектура) применения комплекса в задачах диспетчеризации и оперативного планирования, а также поддержки систем АСУ и ОПП, использующих многокритериальную оптимизацию.
Методы исследования. Аналитический и алгоритмический аппарат дискретной математики, теории графов, теории сложности вычислений, теории вероятностей и математической статистики, численные методы аппроксимации функций, технологии разработки и тестирования программных средств, методы объектно-ориентированного программирования.
Научная новизна работы заключается в создании единой методики, позволяющей построить семейство быстрых эвристических алгоритмов планирования обхода РКС несколькими бригадами с дополнительными условиями неопределенности временных затрат пребывания в узлах и перемещения между узлами сети. Предложенный метод разработан на основе приближенного алгоритма Кристофидеса (АК), решающего ЗК. Такой подход обеспечивает гибкость при поиске решения в задачах составления оптимальных планов обслуживания РКС различного назначения. В отличие от известных эвристических методов, решающих ЗНК, предложенный подход позволяет вводить в исходную задачу дополнительные параметры неопределенности, не требуя качественного пересмотра решения и построения полностью новых алгоритмов, а также позволяет строить алгоритмы как с последовательным выделением ресурса (выделение новой бригады при исчерпании возможностей предыдущей) так и с параллельным распределением ресурсов (построение решения для всех бригад одновременно). Новыми в диссертации являются:
Семейство эвристических полиномиальных алгоритмов, основанных на модификациях АК и решающих следующие задачи: детерминированные задачи обхода РКС с ограниченным и неограниченным числом бригад; задачу обхода РКС с ограниченным числом бригад и учетом случайного времени обслуживания терминалов; задачу обхода РКС с ограниченным числом бригад и учетом степени загрузки дорог. Алгоритмы имеют оценки сложности на порядок лучше, чем метод МПР.
Метод учета случайности времени обслуживания терминалов сети на
основе вывода закона распределения случайной величины, который позволил решить стохастическую задачу оптимизации без ухудшения вычислительной сложности алгоритмов относительно базового6.
Метод учета загрузки дорог, базирующийся на кусочно-линейной аппроксимации функций, и реализованный на его основе полиномиальный алгоритм вычисления времени обхода цикла с учетом влияния коэффициента загрузки дорог. Предложенный метод позволил сохранить ресурсную эффективность алгоритма, решающего задачу обхода РКС с учетом загрузки дорог, без увеличения вычислительной сложности относительно базового.
Метод автоматической генерации приближенной структурно-параметрической модели сети, позволяющий проводить эффективную оценку разрешимости задачи при эксплуатации различных РКС. Универсальная относительно количества целевых функций, типа критерия и алгоритма планирования процедура минимизации по частному критерию.
Достоверность результатов подтверждается строгим математическим и логическим выводом основных используемых соотношений, а также модельными примерами, результатами компьютерных процедурно-статистических экспериментов и автоматических тестов.
Практическая значимость работы. Предложенные в работе алгоритмические решения позволяют широкому спектру пользователей с различным уровнем технической оснащенности решать такие задачи построения обходов сетевых устройств в сетях большой размерности, которые до настоящего времени обычно решались только с привлечением сил экспертов. Применение разработанных алгоритмов LLA, ULLA и LLA_P-Rnd7 планирования обходов РКС на реальных данных практической задачи обходов сети терминалов Райффайзенбанка, обслуживающих Москву и Московскую область в 2012 г., позволило сократить число бригад обхода до 50% в сравнении с планами, составляемыми экспертами. Разработанный на объектном языке высокого уровня C++ программный комплекс TNTS (Terminal Networks Traversal Scheduling) имеет модульную структуру и ориентирован на открытые архитектуры как компьютерных систем, так и их ПО, что делает доступным встраивание его функциональных компонент в другие проекты. Этому способствует выбор внутреннего способа хранения данных, а также способ чтения/записи для внешних данных: для хранения данных использовались стандартные контейнеры библиотеки STL, для чтения/записи данных использовался потоковый ввод/вывод языка СН—Ь При выборе способа построения базового алгоритма (БА), решающего детерминированную задачу планирования обходов сетей, предусматривалась возможность его расширения введением в исходную задачу новых параметров, не обязательно детерминированных. Эффективность и оправданность выбранного подхода была продемонстрирована успешной реализацией двух новых алгоритмов на базе БА: с введением случайного параметра и параметра неопределенности. Проведенное тестирование временных характеристик эффективности доступа к хранимой информации позволило исключить из рассмотрения вариан-
е Алгоритм, решающий детерминированную задачу обхода РКС с ограниченным числом бригад. 7LLA — решает задачу 3-1; ULLA — задачу 3*-1; LLA_P-Rnd — задачу 3-2.
ты с избыточной чувствительностью к аппаратным ресурсам, выбрать наиболее универсальные методы, обеспечить допустимость размера решаемых задач в диапазоне от десятка до нескольких тысяч устройств. Использование средств автоматизации программирования позволило определить числовые характеристики практического применения алгоритмов, выработать корректировки их программных реализаций для повышения качества планирования. В TNTS предусмотрены средства наладки, тестирования и моделирования, что позволяет решать широкий спектр задач (например, принятие решений о комплектовании служб оперативного обслуживания персоналом, транспортом, расходным материалом, выработке начальных нормативов выполнения работ) по одной лишь предварительной информации о составе и территориальной распределенности СТС. Скорость выполнения алгоритмов и реализация универсальной функции оптимизации по частному критерию в TNTS позволят интегрировать TNTS в современные IT-системы (SCADA, MES). Результаты диссертации внедрены в производственную деятельность ООО «Эрумпо» для повышения эффективности планирования обхода множества сайтов тендерных площадок для сбора информации от заказчиков и позволили оптимизировать этот процесс, а также использованы в учебном процессе кафедры математического моделирования НИУ МЭИ по курсам «Дискретная математика», «Дополнительные главы дискретной математики», «Математические методы в экономике», что подтверждено соответствующими актами.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных научно-технических конференциях «Информационные средства и технологии» (2007, 2011 гг.), «Радиоэлектроника, электротехника и энергетика» (2007, 2008, 2010 гг.), на международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании' 2009» (Одесса, 2009 г.), на 5-й международной научно-практической конференции, посвященной 50-летию Сибирского государственного аэрокосмического института (Красноярск, 2010 г.), на 10-й международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010 г.) и на семинаре «Дискретные математические модели» НИУ МЭИ (Москва, 2012 г.). Результаты диссертационной работы изложены в 10 публикациях, из которых две — статьи в профильных журналах, рекомендованных ВАК РФ к защите кандидатских диссертаций, и 8 докладов на международных конференциях.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка, словаря терминов и сокращений и приложений. Общий объем диссертации занимает 251 машинописных страниц, содержит 11 рисунков, 30 таблиц и 3 приложения. Список литературы включает 74 источника.
