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

• Воробьева, Ирина Александровна
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Воробьева, Ирина Александровна

Введение

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

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

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

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

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

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

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

Глава 2: Об учете случайного времени обслуживания терминалов при эксплуатации в СТС

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Traversal Scheduling)

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

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

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

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

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

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

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

4.4.1 Проверочная серия для LLAP и LLAN.

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Исследование методов и разработка алгоритмов и программных средств планирования обслуживания терминалов распределенных компьютерных систем»

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

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

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

Важнейшим требованием, предъявляемым к РКС. является ее отказоустойчивость и высокая рабочая готовность. Его выполнение обеспечивают методы и средства оперативного планирования (ОП), концепция развития которого в последнее десятилетие формулируется как «планирование для достижения нулевого уровня отказов» [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]. В стохастических задачах оптимизации параметры могут выражаться через вероятностные соотношения. Трудности в разработке методов решения связаны в таких задачах со сложностью нахождения законов распределения случайных величин, проверки устойчивости и достоверности законов, если они получены на основе ограниченного объема статистических данных, дающих разные законы распределения при незначительных изменениях в исходной информации. Задачи оптимизации в условиях неопределенности (или задачи с неполной информацией) характеризуются тем, что их случайные параметры не могут быть получены заранее. Если задача предполагает динамические условия работы модели (так называемые диспетчерские задачи), то приемлемые алгоритмы решения найти удается, однако, как только требуется хоть какое-то прогнозирование или планирование ситуации (например, задачи, изучаемые в теории расписаний), поиск точных решений чисто алгоритмическим путем становится крайне труден. В этом классе есть рекомендации комплексного подхода к поиску решений [9], однако они не позволяют синтезировать конструктивные алгоритмы, так как уже первая рекомендация: «определение множества условий, характеризующих модель, и формирование на их основе множества оптимизационных задач, с той или иной адекватностью описывающих объект» приводит к решению 2п оптимизационных задач, где п - число параметров неопределенности.

Задачи I (II) относятся к классу детерминированных, наиболее близкой (но не точной) известной математической формулировкой которых можно считать задачу нескольких коммивояжеров (ЗНК) [73, 74]. Ввод в детерминированные задачи таких параметров, как надежность работы устройства сети и загрузка дорог, переводят их в класс стохастических и задач с неполной информацией, а значительное количество параметров и ограничений, возникающих в реальных задачах ОП, делает большинство существующих алгоритмов либо неприменимыми, либо плохо адаптируемыми к их решению. Поэтому на практике описанные задачи часто решаются приближенно, без алгоритмической поддержки на основе экспертных оценок, и именно они снижают эффективность ОП в РКС, а поиск их алгоритмического и программного решений становится особенно актуальным для сетей большой размерности. ТУР-трудная задача коммивояснсера(ЗК) является вырожденным случаем ЗНК и не имеет полиномиальных алгоритмов поиска точных решений, становясь неразрешимой уже для сетей с числом узлов больше 13, а типичная РКС может состоять из нескольких тысяч объектов, поэтому поиск решений родственных ЗНК задач планирования обходов в РКС в работе проводится среди приближенных и эвристических методов. Выделим из них два наиболее подходящих для задач, основанных на ЗНК.

Метод Кларка-Райта2 [69] до сих пор является самым популярным эвристическим итерационным методом решения задачи доставки грузов из одного РЦ множеству получателей. Она относится к распределительным задачам, в которых основным является распределение ресурсов по требуемым для выполнения работам с математической формулировкой: определить максимальное или минимальное значение целевой функции при сокра

2Был разработан двумя британскими учеными Г. Кларком и Дж.В. Райтом, опубликован в 1963 г. щении объема ресурсов и потребности на них (минимум затрат, максимум эффекта) [40]. Если ресурсов не хватает, то осуществляется их переброски с одной на другую работы таким образом, чтобы показатель эффективности оставался оптимальным. Это выражается или в достижении общего дохода, или в сокращении затрат (в нашем случае — это выбор оптимального маршрута обхода узлов сети). В основу метода положено вычисление матрицы километровых расстояний и выигрышей, он способен решать только детерминированную задачу оптимизации.

При ряде допущений нашу задачу можно свести к транспортной задаче в матричной форме, относящейся к классу задач линейного программирования3. Наибольший интерес представляет применение эвристического алгоритма имитации отжига (Simulated annealing)4 [67] к ее решению [23]. Это общий алгоритмический метод решения задачи глобальной оптимизации [31, 30], который является одним из методов Монте-Карло0. В работе [54] описан метод поэтапного решения (МПР): сначала кластеризация (алгоритм, основанный на выборе транзитивно-ближайших сообщений), затем маршрутизация в ЗК (алгоритм имитации отжига). Метод МПР не рассчитан на решение задачи для нескольких коммивояжеров одновременно. Предложенный нами в работе подход лишен недостатков обоих описанных методов, он позволяет адаптировать алгоритмы под все упомянутые выше типы задач планирования обходов в РКС. Доказано, что наши алгоритмы имеют оценки сложности на порядок лучше, чем указанный метод МПР. Рассмотрим проблемы, в которых еще могут найти применение алгоритмы, решающие модифицированные задачи I (II).

3Для решения задачи наиболее известны методы северо-западного угла, минимального элемента и метод потенциалов [36].

4Другое название алгоритма — алгоритм Н. Метрополиса.

5Общее название группы численных методов, основанных на получении большого числа реализаций стохастического процесса, который формируется таким образом, чтобы его вероятностные характеристики совпали с аналогичными величинами решаемой задачи [66].

Необходимость составления регулярных краткосрочных планов с возможным приоритетом обслуживания узлов вводят задачи I (II) в класс задач упорядочивания (задачи теории расписаний). Здесь могут применяться генетические алгоритмы [22, 70], относящиеся к эвристическим алгоритмам поиска решения задач оптимизации путем случайного подбора с использованием механизмов, аналогичных биологической эволюции. Нередко при составлении расписаний применяются и алгоритмы случайного поиска, когда среди множества решений, полученных при помощи так называемых быстрых приближенных алгоритмов, находящих любое допустимое решение, «запоминается» лучшее решение. Например, подобный подход применялся при составлении расписаний для Аэрофлота [51].

В одной из своих конкретных практических постановок задачи I (II) могут быть выведены в класс динамических задач диспетчеризации, причем на двух типах объектов сети: транспортных6 и стационарных (терминалов). Тогда алгоритмы решения задач I (II) могут стать частью автоматической системы управления (АСУ). На основании нижеизложенного в соответствии со статьей [53], выделим два основных требования, которые были предъявлены нами к решающим алгоритмам.

Диспетчерское управление и сбор данных (SCADA, Supervisory Control And Data Acquisition) является основным и в настоящее время остается наиболее перспективным методом автоматизированного управления сложными динамическими системами (процессами). Главная тенденция развития в современных сетях удаленных терминалов — увеличение скорости обработки информации и повышение интеллектуальных возможностей терминалов. Последние строятся на основе микропроцессорной техники, работают под управлением операционных систем реального времени, объединя

6 С начала 90-х годов в США начались интенсивные исследования и разработки в области создания автоматизированных систем управления наземным транспортом ATMS (Advanced Traffic Management System) [53]. ются в сеть непосредственно или через сеть взаимодействуют с интеллектуальными электронными датчиками объекта управления и компьютерами верхнего уровня. В SCADA-системах требование работы в жестком реальном времени относится, как правило, только к удаленным терминалам, в то время как в диспетчерских пунктах управление событиями (объектами) происходит в режиме квазиреального7 времени. Для нас это означает, что алгоритм, решающий задачу, может быть использован экспертами и в квазиреальном времени, если будет достаточно быстрым. Например, если алгоритм в состоянии отработать в пределах получаса (требуемое время определяется конкретной технической задачей или эвристическими соображениями). он может применяться не только для планирования обхода ТС «на завтра», но и для быстрой коррекции уже составленного плана в случае поступления корректирующей информации (например, сигнал терминала) — достаточно дать на вход актуальные данные.

Основная тенденция развития технических средств SCADA — миграция в сторону систем с открытой архитектурой, позволяющей независимо выбирать компоненты системы от различных производителей; в результате — расширение функциональных возможностей, облегчение обслуживания и снижение стоимости. Несмотря на продолжающиеся споры специалистов по системам управления на тему «что лучше: UNIX или Windows?», во многих сегментах рынка выбор однозначно сделан в пользу последней. Решающими для быстрого роста популярности Windows стала открытая архитектура и эффективные средства разработки приложений, что позволило многочисленным фирмам-разработчикам создавать программные продукты для решения широкого спектра задач. Программный комплекс, разработанный в рамках диссертационной работы, написан в среде Visual С++ в

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

ОС Windows, что позволяет использовать его практически на любом стандартном ПК и отвечает второму требованию к системам управления процессами. Модульная структура программного комплекса и наличие гибкого интерфейса позволят встраивать его в различные системы оперативного планирования производства (ОПП), где диспетчерские службы выполняют роль нижнего производственного звена управления. В задачи систем ОПП входят, например, такие функции как расчет ограничений и резервов производственных мощностей, расчет режимов работы производственных мощностей для достижения планового задания, формирование режимных заданий для производственно-диспетчерских служб [26].

Рассмотрим, какие системы ОПП существуют на современном этапе и с какими трудностями сталкиваются разработчики при решении задач планирования, однако сначала изложим краткую историю проблемы ОПП, освещенную в [63]. «Новую» историю решения задач по оптимальному планированию в производстве принято исчислять от 1939 г.: тогда монография Л.В.Канторовича «Математические методы организации и планирования производства» положила начало научным методам в планировании и организации производства на основе зарождающегося тогда направления экономической математики8. Через десять лет появление первых вычислительных машин значительно стимулировало развитие работ в области математической экономики, организации и планирования производства. Были разработаны эффективный метод решения целочисленных задач (Р.Гомори), метод ветвей и границ (А.Лэнд, В.Дойг и Дж.Литтл), метод динамического программирования (Р.Беллман) и др. Все эти методы поиска оптимума находили применение в различных областях экономики и производства. В 1954 г. С.М.Джонсон опубликовал задачу планирования

8Американский ученый Дж.Б.Данциг в 1947 г. пришел к аналогичным результатам идеи численного решения задач оптимизации, названного симплекс-методом. технологических операций на станках, которая показала, что составление расписания уже для трех станков относится к классу задач, трудноразрешимых за приемлемое время (класс ЖР-трудных задач), однако практические задачи характеризуются тем, что трудность их решения не может избавить от необходимости поиска решения. В результате строятся приближенные методы нахождения решений.

На рынке IT существует несколько разновидностей «систем управления предприятиями и процессами», которые в настоящее время отвечают за планирование работ на производстве - это системы классов ERP9. MRPII10, APS11 и MES12. В работах [62, 61, 20] Е.Б. Фролова13 и P.P. Загидуллина рассмотрены недостатки систем стандартов ERP, MRP и MRPII. Основная причина неспособности этих систем оперативно составлять детализированные планы и отслеживать все изменения, происходящие в рамках предприятия состоит в том, что задачи составления расписаний относятся к классу AP-трудных задач. Системы же MES используют децентрализованный подход к управлению, а именно: на первом уровне с помощью системы ERP решаются стратегические задачи — управление ресурсами, укрупненное планирование; на нижнем уровне управления находятся SCADA-системы, отвечающие за функции автоматизации управления и контроля выполнения технологических процессов;

ERP-система формирует объемные планы для цехов; с помощью сессий MES-системы каждый цех формирует детализи

9 Enterprise Resource Planning была предложена компанией GartnerGroup в начале 90-х годов.

10Manufactory Resource Planning управление ресурсами предприятия.

11 Advanced Planning and Scheduling системы синхронного оптимизационного планирования производства.

12Manufacturing Execution Systems или исполнительная производственная система.

13Разаработчик MES-системы «ФОБОС». рованные расписания (это уровень детализированного, оперативно-календарного планирования).

Основной характеристикой алгоритмов в МЕЭ является понятие «частный критерий» — критерий, отражающий какую-либо одну особенность при построении расписания, например, минимизация времени переналадок, минимум транспортных операций и др14. Пусть необходимо выбрать одно из множества решений X из области допустимых значений, где каждое выбранное решение оценивается совокупностью критериев . . , Д., различающихся своими коэффициентами относительной важности (1,., к). Критерии д = 1,. к. — это частные, или локальные, критерии, они образуют интегральный, или векторный, критерий оптимальности ^ = {/д}. Коэффициенты образуют вектор важности и каждый локальный критерий характеризует некоторую локальную цель принимаемого решения [62]. При оптимизации расписаний в МЕБ-системах с помощью векторных критериев чаще всего используется методика поиска оптимума на Парето-множествах10 [47]. Ориентируясь на вышеизложенное, мы строили алгоритмы, способные по определенному пользователем параметру искать один частный критерий оптимума среди некоторого заданного набора, что в совокупности с требованием «быстроты» нахождения решения обеспечивает способность интегрировать при необходимости частные оптимумы в векторные с приоритетом.

Актуальность диссертационной работы определяется следующим: выбором практически востребованных задач; несовершенством существующих решений поставленной задачи на современном этапе; ориентацией на ис

14В противовес этим критериям существуют интегральные критерии, например, минимум всех непроизводительных времен, минимум стоимости выполненного расписания и др. [25].

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

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

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

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

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

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

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

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

Методы исследования

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

Достоверность научных результатов

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

Научная новизна

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

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

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

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

3. Метод учета загрузки дорог, базирующийся на кусочно-линейной ап

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

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

Практическая значимость работы

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

17LLA — решает задачу I; ULLA — задачу II; LLAP-Rnd — задачу I с дополнительным случайным параметром. систем, так и их ПО. что делает доступным встраивание его функциональных компонент в другие проекты. Этому способствует выбор внутреннего способа хранения данных, а также способ чтения/ записи для внешних данных: для хранения данных использовались стандартные контейнеры библиотеки STL, для чтения/записи данных использовался потоковый ввод/вывод языка С--. При выборе способа построения базового алгоритма (БА), решающего детерминированную задачу обходов сетей, предусматривалась возможность его расширения введением в исходную задачу новых параметров, не обязательно детерминированных. Эффективность и оправданность выбранного подхода была продемонстрирована успешной реализацией двух новых алгоритмов на базе БА: с введением случайного параметра и параметра неопределенности. Проведенное тестирование временных характеристик эффективности доступа к хранимой информации позволило исключить из рассмотрения варианты с избыточной чувствительностью к аппаратным ресурсам, выбрать наиболее универсальные методы, обеспечить допустимость размера решаемых задач в диапазоне от десятка до нескольких тысяч устройств. Использование средств автоматизации программирования позволило определить важные числовые характеристики практического применения алгоритмов; выработать дополнительные процедуры корректировки программных реализаций алгоритмов, существенно повысившие качество планирования. В TNTS предусмотрены средства наладки, тестирования и моделирования, что позволяет решать широкий спектр задач (например, принятие решений о комплектовании служб оперативного обслуживания персоналом, транспортом, расходным материалом, выработке начальных нормативов выполнения работ) по одной лишь предварительной информации о составе и территориальной распределенности СТС. Скорость выполнения алгоритмов и реализация универсальной функции оптимизации по частному критерию в TNTS позволят интегрировать TNTS в современные IT-системы (SCADA. MES).

Реализация результатов

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

Апробация работы

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

• на 13-й междунар. науч.-техн. конф. студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, 2007 г.)

• на 15-й междунар. науч.-техн. конф. «Информационные средства и технологии» (Москва, 2007 г.)

• на 14-й междунар. науч.-техн. конф. студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, 2008 г.)

• на междунар. науч.-практ. конф. «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании' 2009» (Одесса, 2009 г.)

• на 16-й междунар. науч.-техн. конф. студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, 2010 г.)

• на 5-й междунар. науч.-практ. конф. поев. 50-летию СГАУ. 75-летию образования Красноярского края (Красноярск, '2010 г.)

• на 10-й МНТК «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010 г.)

• на 19-й междунар. науч.-техн. конф. «Информационные средства и технологии» (Москва, 2011 г.)

Публикации

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

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

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

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

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

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

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

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

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

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

Личный вклад автора в совместные работы [3, 4, 9, 10]:

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

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

9] Автору принадлежит ввод в задачу планирования практических факторов, влекущих к неопределенностям в решении оптимизационных задач. Формулирование задач в рамках неопределенностей: стохастической и неопределенности, связанной с недостатком информации. Предъявлены алгоритмы по решению задачи планирования при неопределенности второго рода, подсчитаны оценки его сложности.

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

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы (74 источника), словаря терминов и приложений. СОДЕРЖАНИЕ РАБОТЫ

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Воробьева, Ирина Александровна

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

1. Программно реализованы алгоритмы АФ-I и АФ-П, а также две процедуры для решения «задачи учета» при помощи аппроксимации Пуассона и нормальной аппроксимации. Процедура на базе аппроксимации Пуассона реализована в двух вариантах исполнения: базовой и с дополнительной процедурой принятия решений способом рандомизации.

2. Алгоритмы и процедуры встроены в разработанный на базе среды визуального программирования Visual С--программный комплекс

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

3. Возможности расширения (встраивания в системы, переносимости на другие платформы) комплекса обеспечиваются: текстовым форматом файлов описания объекта и вывода результатов; векторным форматом "\УМР"для контекстно-независимого вывода результата моделирования РКС; разработанными контейнерными классами основных объектов «алгоритм», «план», «сеть», «модель» и средствами библиотеки STL; механизмами абстракции с сохранением стандарта языка ANSI/ISO.

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

5. Разработаны средства генерирования исходных файлов (на основании свойств «предельной теоремы» общей теории вероятностей) и их визуального отображения.

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

7. Реализованы методы обеспечения тестирования и наладки ТИТБ (подбор квантили, статистическая оценка точности выполнения плана).

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

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

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

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

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

2. Рассмотреть возможности динамического (диспетчерского) обслуживания РКС, которые не имеют столь строгих ограничений по регламенту обслуживания, как СТС с банкоматами.

3. Алгоритмически реализовать другие, уже предложенные в первой главе, подходы к решению задач оптимального планирования с предварительной кластеризацией области обхода. Особый интерес представляет возможность применения к задаче диссертации алгоритмов из аппарата нечетких множеств, £"М-алгоритм, алгоритм ^-средних на этапе кластеризации и алгоритм имитации отжига на этапе составления маршрутов.

4. В Т1МТ8 необходимо доработать ввод-вывод информации с целью ее наиболее удобного использования, например, требуется большая информативность файла результата планирования: запись исходных параметров планирования, сортировка бригад в описании обхода, возможно, визуальное отображение плана обхода на «карте РКС».

Заключение

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Воробьева, Ирина Александровна, 2012 год

1. Амосов A.A. Вычислительные методы для инженеров/ A.A. Амосов, Ю.А. Дубинский, Н.В. Копченова. М.: Высш. шк., 1994. - 544 с.

2. Аникеич A.A. Сменно-суточное планирование работы грузовых автомобилей на ЭВМ./ A.A. Аникеич, A.B. Грибов, С.С. Сурии М.: Транспорт, 1976. - 152 с.

3. Асатрян С.Р. Использование технологий «клиент-сервер» для организации управления производством/ С.Р. Асатрян, A.B. Ващило, Ю.Г. Коган и др.]. // САПР и Графика. 1999, - №11.:- С. 30-34.

4. Баранов Г. Дисковые накопители информации/ Г. Баранов. // Компьютеры Днепропетровска. 1998., - №19.

5. Бертсекас Д. Сети передачи данных/ Д. Бертсекас, Р. Галлагер. -М.: Мир, 1989. 544 с.

6. Блехерман М.Х. Гибкие производственные системы. Организационно экономические аспекты/ М.Х. Блехерман - М.: Экономика, 1988.

7. Болынев JI.H. Таблицы математической статистики./ Л.Н. Большее, Смирнов H.B. М.: Наука, 1983. - 416 с.

8. Воробьева И.А. Алгоритм планирования массовых инкассации в сетях с переменным трафиком/ И.А. Воробьева. //' XVI Между нар. науч.-техн. конф. «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА»: тез. докл./ МЭИ М., 2010. - Т.1. - С. 324-326.

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

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

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

12. Гараева Ю. Российские mes-системы или как вернуть производству оптимизм/ Ю. Гараева, Р. Загидуллин, Сун Кай Цин. // САПР и графика. 2005., - №11.

13. Гарматюк С. Современные десктоппые процессоры архитектуры, х86: обилие принципы работы (х86 CPU FAQ 1.0) Электронный ресурс]/ С. Граматюк. Электрон, журн. «iXBT.com», 2006. - URL: http://www.ixbt.com/cpu/x86-cpu-faq-2006.shtml.

14. Гладков JI.A. Генетические алгоритмы/ Л.А. Гладков, В.В. Курей-чик, В.М. Куреичик. М.: ФИЗМАТЛИТ, 2006. - 320 с.

15. Горбатов В.А. Логическое управление распределенными системами/ В.А. Горбатов, М.И. Смирнов, И.С. Хлытчиев. М.: Энергоатомиз-дат, 1991.

16. Горицкий Ю.А. Введение в теорию вероятностей/ Ю.А. Горицкий// под ред. Д.Г. Мещанинова. М.: Изд-во МЭИ, 2005. - 80 с.

17. Горшков А.Ф. Компьютерное моделирование менеджмента/ А.Ф. Горшков, Б.В. Евтеев, В.А. Коршунов и др.] // под общ. ред. Н.П. Тихомирова. М.: Издательство «Экзамен», 2004.

18. Гребнев С. Интегрированные системы управления непрерывным производством: оптимальный синтез./' С. Гребнев. // «Connect! Мир Связи». 2008., - т.28J Гук М.Ю. Аппаратные средства IBM PC. Энциклопедия/ М.Ю. Тук.- 3-е изд. Спб.: Питер, 2008. - 1072 с.

19. Гук М.Ю. Интерфейсы устройств хранения ATA. SCSI и другие. Энциклопедия/ М.Ю. Гук. Спб.: Питер, 2007. - 448 с.

20. Джонс М.Т. Программирование искуственного интеллекта в приложениях/ М. Т. Джонс. М.: ДМК-пресс., 2004.

21. Елкин Д. Искусственный интеллект. Алгоритм имитации отжига Электронный ресурс[/ Д. Елкин7 А. Тяхти/ СПбГУ ИТ-МО СПб. - проект «Computer Algorithm Tutor», 2008. - URL: http://rain.ifmo.ru/cat.

22. Золотарев B.M. Современная теория суммирования независимых случайных величин/ В.М. Золотарев. М.: Наука, 1986.

23. Иванов А. Планирование ремонтов: выбор оптимального пути/ А. Иванов7 Р. Токаренко //Директор информационной службы. 2009.,- №2.:- С. 3. URL: http://www.osp.ru/cio/2009/02/7135198.

24. Иванов Б.Н. Дискретная математика. Алгоритмы и программы/ Б.Н. Иванов. М.: Лаборатория базовых знаний, 2002.- 288 с.

25. Интеллектуальный детектор транспорта «Трафик-Монитор» Электронный ресурс]/ Сайт на базе ПО «Элбитек» (№ свидетельства Роспатента 2001610504)- патент на промышленный образец № 52161 от 16.02.2003г. - 2004. - URL: http://www.imsrosprom.com.

26. Конюховский П.В. Математические методы исследования операций в экономике/ П.В. Конюховский. СПб.: Питер, 2002. - 208 с.

27. Кормен Т. Алгоритмы: построение и анализ./ Т. Кормен, Ч. Лейзер-сон, Р. Ривест. М.: МЦНМО, 2001.

28. Кофман А. Введение в теорию нечетких множеств/ А. Кофман. -М.: Радио и связь, 1982.

29. Левит Б.Ю. Нелинейные сетевые транспортные задачи./ Б.Ю. Левит, В.Н. Лившиц. М.: Транспорт, 1972. - 144 с.

30. Математические методы и модели в принятии решений Электронный ресурс]/статьи редакции. Radiomaster.ru, 2009 - URL: http://www.radiomaster.ru/articles/view/143.

31. Минаев Ю.Н. Стабильность экономико-математических моделей оптимизации/ Ю.Н. Минаев. М.: Статистика, 1980. - 103 с.

32. Миротин Л.Б. Интегрированная логистика накопительно-распределительных комплексов (склады, транспортные узлы, терминалы) / Л.Б. Миротин, А.Г. Некрасов, Е.Ю. Куликова и др.]. М.: ЭКЗАМЕН, 2003. - 448 с.

33. Михалевич B.C. Методы исследования оптимизации в дискретных сетевых задачах оптимального распределения ресурсов/ В. С. Михалевич, А.И. Кукса. М.: Наука, 1983. - 208 с.

34. Мониторинг автотранспорта путь к снижению производственных затрат. // ИНФОРМОСТ. - 2007, - №2(50).:- С. 34-35.

35. Навигационная аппаратура ОАО «Ижевский радиозавод».//ИНФОРМОСТ. 2008., - №2(55).:- С. 10-11.

36. Новиков Ф.А. Дискретная математика для программистов/ Ф.А. Новиков. СПб.: Питер, 2004. - 364 с.

37. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход/В.Д. Ногин. М.: ФИЗМАТЛИТ, 2002. - 144 с.

38. О технологии Machine 2 Machine для профессионалов Электронный ресурс]. Офиц. сайт компании «М2М Телематика» (торговая марка BusinessNavigator®), 2002. - URL: http://www.m2m-t.ru/technology.

39. Паклин Н. Алгоритмы кластеризации на службе Data Mining Электронный ресурс]/ Н. Паклин. BaseGroup Labs, 2006 - URL: http://www.basegroup.ru/clustarization/datamining.htm.

40. Прохоров Ю.В. Вероятность и математическая статистика. Энциклопедия./ авт. ст. В.Ю. Королев// гл. ред. Ю.В. Прохоров. М.: Изд-во «Большая Российская Энциклопедия», 1999. - С. 364, 523-524.

41. Романовский И.В. Дискретный анализ/ И.В. Романовский Спб.: Невский диалект, 2000. - 240 с.

42. Системы диспетчерского управления и контроля транспортных средств на базе технологий спутниковой навигации Электронный ресурс[. ИНФОРМОСТ, 2004. - URL: http://www.informost.ru/ss/03/s4.htm.

43. Системы диспетчерского управления и сбора данных (scada-системы). // Мир компьютерной автоматизации (МКА). 1999., - №3.

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

45. Смирнов М.И. Свидетельство об официальной регистрации программы для ЭВМ/ М.И. Смирнов, Р.З. Хайруллин, Т.И. Кожахмедов,

46. A.A. Павлов (Россия). № 2001611583 от 22.11.2001. - Выдано Российским агентством по патентам и товарным знакам (РОСПАТЕНТ). 2001.

47. Страуструп Б. Язык программирования Сч-+/ Б. Страуструп. 3-е изд./Пер. с англ. - Спб.: Невский диалект, М.: Изд-во БИНОМ, 1999. - 991 с.

48. Танаев B.C. Теория расписаний. Одностадийные системы./ B.C. Та-наев, B.C. Гордон, Я.М. Шафранский. М.: Наука, 1984. - 384 с.

49. Фишберн Питер С. Теория полезности для принятия решений/ П. С. Фишберн. М.: Наука., 1978. - 352 с.

50. Фридман A.A. Исследования по дискретной оптимизации/ Сб. статей под ред. A.A. Фридмана. М.: Наука, 1976. - 448 с.

51. Фролов А.Б. Прикладные задачи дискретной математики и сложность алгоритмов/ A.B. Фролов, А.Е. Андреев, A.A. Болотов, К.В. Коляда. М.: Изд-во МЭИ, 1997. - 312 с.

52. Фролов Е.Б. MES-системы. Критерии, которые мы выбираем Электронный ресурс]/ Е.Б. Фролов, P.P. Загидуллин. Электрон, журн. ERPNEWS, 2007. - URL: http://erpnews.ru/doc2690.html.

53. Фролов Е.Б. MES-системы, как они есть или эволюция систем планирования производства. Часть I Электронный ресурс]/ Е.Б. Фролов, P.P. Загидуллии, Электрон, журн. ERPNEWS, 2007. URL: http: / / erpnews. ru / doc2 59 2. html.

54. Чернышев С.В. Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах большой размерности: автореф. дис. канд. техн. наук/ С.В. Чернышев, НИУ «ВШЭ» Москва, 2011. - 22 с.

55. Чистяков В.П. Курс теории вероятностей/ В.П. Чистяков. М.: Агар, 1996. - 256 с.

56. Ясницкий JI.H. Введение в искусственный интеллект/ JI.H. Ясниц-кий. М.: Академия, 2005.

57. Anderson L.H. Metropolis, monte carlo, and the maniac/ Herbert L. Anderson. // LOS ALAMOS SCIENCE Fall 1986., - pp. 96-108.

58. Cherkassky B.V. Buckets, heaps, lists, and monotone priority queues/ B.V. Cherkassky, A.V. Goldberg, C. Silverstein. // SIAM Journal on Computing. 1999., - №28:- pp. 1326-1346.

59. Clarke G. Scheduling of vehicles from a central depot to a number of delivery points/ G. Clarke, J.W. Right. // Operations Research 1963., -Ml:- pp. 568-581.

60. Clement R.P. Genetic algorithms and bus-driver scheduling./ R.P. Clement, A. Wren. //International Conference for Computer-Aided Transport Scheduling/ Lisbon, Portugal., 1993.

61. Denardo E.V. Shortest-route methods: 1.reaching, pruning, and buckets/ E.V. Denardo, B.L. Fox. // Operations Research. 1979., - №27:- pp. 161-186.

62. Dijkstra E.V. A note on two problems in connection with graphs E.V. Dijkstra. // Numerische Math. 1959., №1:- pp. 269-271.

63. Hong S. A Note on the Simmertric Multiple Traveling Salesman Problem with Fixed Charges/ S. Hong, Manfred W. Padberg. // Operations Research: (Sep. Oct.) - 1977., - Vol. 25, No. 5:- pp. 871-874.

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

65. АК — алгоритм Кристофидеса: приближенный алгоритм, решающий ЗК за полиномиальное время, с известной оценкой полученного решения.

66. АФТ-1, АФТ-П — алгоритмы построения обхода вершин графа фиксированным числом бригад и неограниченным числом бригад, соответственно (решение задачи Т-1(Т-П).

67. Б А — базовый алгоритм (здесь, алгоритм АФ-1, для которого все остальные решающие алгоритмы: АФ-П, АФТ-1, АФТ-П, а также алгоритмы решения задачи учета, являются его модификациями).

68. ВК, МВК — вычислительный комплекс; ВК удаленного контроля состояния, или мониторинговый ВК.

69. ЗК — задача коммивояжера: поиск на полном взвешенном неориентированном графе минимального по весу гамильтонова цикла обхода вершин. Гамильтонов цикл — цикл, содержащий каждую вершину графа ровно один раз.

70. Задача 1(11) — детерминированная задача планирования инкассации, сформулированная на языке теории графов (основная задача диссертации: I — с ограничением на ресурс обхода, II — без ограничения на ресурс обхода).

71. Задача Т-1(Т-11) — задача планирования обходов в сетях с учетом трафика, сформулированная на языке теории графов с ограничением на ресурс обхода (без ограничения на ресурс обхода).

72. Задача учета — задача учета дополнительного увеличения времени на обход СТС за счет случайного события: случайной неисправности терминала в сети (времени на ее устранение).

73. Клиентское обращение — одно обращение клиента к устройству сети на прием-выдачу (товар, деньги).

74. МОД — минимальное остовное дерево.

75. МПР — метод поэтапного решения: сначала кластеризация, затем маршрутизация в ЗК.

76. ОЗУ, ОЗУ ПК — оперативно запоминающее устройство (оперативная память) персонального компьютера.

77. ОП(ОПП) — оперативное планирование (производства).

78. ПК, ППК — персональный компьютер; портативный ПК.

79. РЦ —- распределительный центр.

80. РКС — распределенная компьютерная сеть.

81. СТС — сеть терминалов самообслуживания.

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

83. Терминал самообслуживания — любое устройство самостоятельного обслуживания клиентов, требующее регулярного сервисного обслуживания (инкассирования), например, банкомат, платежный терминал, автомат по продаже мелких товаров (талонов, газет и др.).

84. Типовая загрузка (банкомата) — количество денежных листов в банкомате либо любом устройстве принимающем (выдающем) денежные средства.

85. ТЦО(КЛА) — алгоритм вычисления времени обхода цикла с учетом влияния коэффициента загрузки дорог (кусочно-линейная аппроксимация).

86. ТЬА — программная реализация алгоритма АФ-1.

87. ЬЬА Р — программная реализация процедуры аппроксимации Пуассона решения задачи учета (включает два алгоритма LLAP-St и 1ХАР-Ипс!).

88. ХХА ЛГ — программная реализация процедуры нормальной аппроксимации решения задачи учета.

89. MCAD (Mathcad) ----- система компьютерной алгебры из класса систем автоматизированного проектирования (http: / / www.ptc.com/prodiicts/ mathcad).

90. MES — Manufacturing Execution Systems (исполнительная производственная система).

91. NDP — Normal Distribution of Points (тип распределения узлов CTC на плоскости).

92. RDP — Random Distribution of Points (тип распределения узлов CTC на плоскости).

93. SCAD А — Supervisory Control And Data Acquisition (диспетчерское управление и сбор данных).

94. Statistica — Программный пакет для статистического анализа (www.statsoft.ru).

95. STL — Standard Template Library (стандартная библиотека шаблонов) языка программирования С——.

96. TNTS — Terminals Networks Traversal Scheduling (планирование обхода CTC). ULLA — программная реализация алгоритма АФ-II.

97. UltraATA, Serial ATA, USB, Fire Wire, Ethernet — интерфейсы передачи данных в различных электронных носителях.

98. Visual С+Ч---Microsoft Visual Studio, среда визуального программирования (http://www.microsoft.com/visualstudio/ru-ru).

99. WMF — универсальный формат векторных графических файлов для Windows приложений (разработан Microsoft, является неотъемлемой частью Windows).