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

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

Никулина Екатерина Юрьевна

МОДЕЛИ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ВРЕМЕННЫХ ХАРАКТЕРИСТИК ИНФОРМАЦИОННЫХ СИСТЕМ ОРГАНОВ ВНУТРЕННИХ ДЕЛ

Специальность 05 13 18 - «Математическое моделирование, численные методы и

комплексы программ»

АВТОРЕФЕРАТ

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

1 16

Воронеж - 2008

003445116

Диссертация выполнена на кафедре высшей математики Воронежского института МВД России

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

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

Защита диссертации состоится 17 сентября 2008 года в 13 00 часов в ауд № 213 на заседании диссертационного совета Д203 004 01 по защите докторских и кандидатских диссертаций при Воронежском институте МВД России по адресу 394065, г Воронеж, проспект Патриотов, 53

С диссертацией можно ознакомиться в библиотеке Воронежского института МВД России

С текстом автореферата можно ознакомиться на официальном сайте Воронежского института МВД России www vimvd ru в разделе «Наука» - «Работа диссертационных советов» - «Д 203 004 01»

Автореферат разослан 11 июля 2008 года

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

Меньших Валерий Владимирович

Официальные оппоненты: доктор технических наук, доцент

Авсентьев Олег Сергеевич

кандидат технических наук, Курченкова Татьяна Викторовна

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

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

Актуальность темы Одной из главных задач Министерства внутренних дел Российской Федерации является повышение эффективности обработки информации в информационных системах с учетом технических возможностей на современном этапе развития В связи с этим в МВД России принята концепция создания «Единой информационно-телекоммуникационной системы органов внутренних дел» на 20052008 годы, в рамках которой предполагается переход к использованию принципиально новых информационных систем, способных обеспечивать все возрастающие потребности пользователей

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

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

Диссертация выполнена на кафедре высшей математики Воронежского института МВД России в соответствии с одним из научных направлений института «Разработка методов математического моделирования и численного анализа прикладных задач естествознания»

Объектом исследования являются информационные процессы в ИС ОВД Предметом исследования выступают математические методы, модели и алгоритмы оптимизации временных характеристик ИС ОВД

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

1 Анализ состава, структуры и условий функционирования ИС ОВД и разработка на этой основе ее структурно-параметрической модели, позволяющей получить оценки временных характеристик

2 Проведение вычислительных экспериментов по оценки временных характеристик в интересах разработки комплекса математических методов, моделей и алго-

ритмов

3 Разработка математических методов и алгоритмов оценки временных характеристик к И С

- в условиях жестких временных ограничений,

- при заданных временных ограничениях,

- без временных ограничений

4 Разработка комплекса математических моделей, методов и алгоритмов оптимизации выбора варианта модернизации ИС ОВД

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

Научная новизна При выполнении диссертационного исследования получены следующие новые научные результаты

1 Разработана структурно-параметрическая модель функционирования ИС ОВД, основанная на использовании взвешенных раскрашенных орграфов информационных процессов, отличающаяся от известных использованием ярусно-параллельного представления для оценки временных характеристик

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

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

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

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

Внедрение результатов работы. Результаты диссертационной работы внедрены в учебном процессе Воронежского института МВД России, в УВО при ГУВД по Воронежской области Внедрение результатов подтверждается соответствующими актами i

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

ютерные технологии автоматизированного проектирования систем машиностроения и аэрокосмической техники» (Воронеж, 2004), Международной научно-практической конференции «Обеспечение общественной безопасности в Центральном федеральном округе Российской Федерации» (Воронеж, 2007), Международной научно-практической конференции «Охрана, безопасность и связь» (Воронеж, 2007), Региональная научно-практическая конференция «Информационные технологии в науке, технике и образовании» (Воронеж, 2008)

Публикации По материалам диссертации опубликовано 14 печатных работ (7 статей, 7 материалов научных конференций), в том числе 6 работ опубликовано без соавторов

В работах, опубликованных в соавторстве, лично автором получены следующие результаты в [2] - разработана графовая модель, сформулировано и доказано утверждение о соответствии длины критического пути графа оптимальной длине расписания, в [4] - обосновано использование комбинации простых диспетчеров для составления оптимального расписания выполнения последовательности нитей в многопроцессорной системе, в [5] - предложен и обоснован метод локальной оптимизации в планирования выполнения заданий в вычислительных системах реального времени, в [7] - предложен и обоснован способ учета временной погрешности в модели выбора варианта модернизации ИС ОВД, в [11] - разработан алгоритм решения оптимизационной задачи теории расписаний на основе метода динамического программирования, в [12] - разработан метод использования эвристических алгоритмов для нахождения нижних оценок длительности выполнения запросов в РИС методом ветвей и границ, в [13] - проведено аналитическое сравнение точных и приближенных алгоритмов и осуществлен вычислительный эксперимент по выбору наилучшего приближенного алгоритма, в [14] - разработан и обоснован новый подход к использованию генетического алгоритма для решения задачи теории расписаний Работа [13] опубликована в журнале, рекомендованном по списку ВАК

Структура и объем работы Диссертация состоит из введения, четырех глав, изложенных на 142 страницах машинописного текста, 26 рисунков, 3 таблиц, заключения, библиографического списка использованной литературы, содержащего 104 наименования, и 2 приложений

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

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

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

3 Задача оценки временных характеристик должна быть адаптирована к временным ограничениям

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

- при заданных временных ограничениях целесообразно использовать генети-

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

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

4 Выбор варианта модернизации ИС следует осуществлять на основе моделей оптимизации, в которых используются разработанные в диссертации комплекс математических методов оценки временных характеристик

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

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

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

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

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

Структурно-параметрическая модель - это представленный в ярусно-параллельной форме (ЯПФ) взвешенный раскрашенный ациклический граф

</=(Г, Е, Р, Т), . (1)

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

Модель (1) декомпозируется на частные модели отдельных исполнителей I как С,=(У„ Е„ Т), а отношение Е, индуцируется из Е следующим образом - (V,', V,2) е Е, если существует последовательность (V,1, IV¡) е Е, , V,2) е Е

Рис 1 Схема проведения исследования

Графовая модель С, содержит множество вариантов упорядочивания заданий исполнителя г Решение задачи теории расписаний фактически заключается в замене отношения частичного порядка Е, для каждого исполнителя / отношением полного порядка и, и получении частной модели Н,=(У„ 11 „ Т,), содержащей единственный вариант упорядочивания заданий исполнителя г Синтез частных графовых моделей Я, приводит к получению общей графовой модели Н=(У, Ц Р, Т), где 11= и II, Таким

образом, вопрос об оценке начала и окончания времени выполнения операций свелся к

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

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

Таблица 1

Простые диспетчеры_;_

Обозначение Правило назначения приоритетов операций

все операции имеют одинаковые приоритеты

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

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

больший приоритет у операции с меньшим номером г яруса графа

£>5 больший приоритет у операции с меньшим номером 5 кояруса графа

о6 больший приоритет у операции с меньшим значением х-г

При проведении вычислительного эксперимента для графовых моделей с количеством вершин, не превышающим семи, и равнодлительными операциями были получены оптимальные расписания при применении простых диспетчеров Это позволило разработать новый алгоритм (комбинированный диспетчер и), представляющий собой последовательное составление расписаний с помощью простых диспетчеров 02-06 с последующим выбором расписания минимальной длительности

Вычислительный эксперимент по проверке эффективности [/ состоял в исследовании 100 графовых моделей с |Р|< 100 и \Р\< 10 Для графовых моделей с одинаковыми диспетчер Е? построил только оптимальные расписания, а для моделей с различными /, - как оптимальные, так и неоптимальные расписания, в среднем незначительно отличающиеся от оптимальных

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

В качестве генов и>=(/, р) предлагается использовать операции г с указанием их исполнителей р, хромосом 0=(И/, Е) - упорядоченные последовательности генов такие, чтобы для генов одного исполнителя существует полный порядок (IV- множество генов, Е - отношение порядка на множестве Ш) Генотип каждой особи состоит из одной хромосомы (тем самым особи представляют собой отдельные расписания) Фенотип особи (М, Н) (двоичную кодировку генотипа) определим матрицей смежности М=(тграфа й и матрицей его раскраски определяющей цвет

вершины, т е исполнителя Популяция - подмножество множества расписаний

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

Репродукция включает в себя работу генетических операторов (мутации и кроссовера) Мутация предназначена для того, чтобы увеличить вариабельность по-

пуляции путем замены выбранного случайным образом бита в хромосоме на противоположный Кроссовер ® обеспечивает получение потомка (М',Н') скрещиванием г-й иособей с фенотипами (А/,,//,) и (М)ГН/) следующим образом 1, если т" = т" = 1, „ 0, если от" =т" =0, ' 0(аи), если т" * т" я к <1, 1-0(аа),если т, *т)'нк>1

где 0{ак')- функция округления случайного числа а" е[0,1] и Н'=Н1=Н1 Эффективность каждой особи у, определяется в общем случае длиной соответствующего расписания, равной длине критического пути, и, в случае, когда операции равнодлительны - числом ярусов ярусно-параллельной формы Показатель приспособленности популяции должен отражать качество приспособленности всех

N

особей популяции Поэтому в качестве такого показателя принято у = 1/ М^у,, где

*

И- количество особей в популяции

В случае, если имеется значительный ресурс времени или размерность задачи невелика, следует использовать точные методы оценки временных характеристик, среди которых наиболее часто используемыми являются метод ветвей и границ (МВГ) и метод динамического программирования (МДП) В диссертации разработаны варианты этих методов для случая, когда времена всех операций одинаковы и равны /, использующие модель (1) в ярусно-параллельном представлении

В описании методов использованы частичные решения GJ = (У,Е,,Р,Т), где £ отношение полного порядка в первых ] ярусах для операций каждого исполнителя и последовательность вложенных отношений порядка

Я с Я, с £г с сЕ,=и (2)

Для МВГ приведем только отличительные особенности предложенных в работе правил ветвления, оценки частичных решений и обхода дерева решений

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

Для определения правила оценки разделим все яруса графов отношений £ на два класса - простые и составные

Ярус назовем простым, если ярус содержит не более одной операции одного исполнителя, и все предыдущие яруса с меньшим номером являются простыми или вовсе отсутствуют (для первого яруса) Остальные яруса - составные

В работе доказано утверждение о том, что в качестве оценки частичного решения можно принять Л„р+шах(ДСОС1„, тах|К оК^.1), где Япр - число простых ярусов

графа, Ясост- число составных ярусов, с К - операции, входящие в составные яруса, V, - операции г-го исполнителя

Предлагается правило обхода дерева решений, в соответствии с которым выбирается вершина, имеющая больший приоритет в соответствии с комбинированным диспетчером Г?

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

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

Граф частичных решений Г строится на основе последовательности (2) и представляет собой граф, вершинами которого являются множества частичных решений, а дуги соответствуют отношению частичного порядка -<, те г = ({0(},^) При этом осуществляется склеивание вершин С и С графа Г, если они совпадают при сужении на множество вершин модели (1), входящих в составные яруса, т е С], =0*1,„ Исток графа Г - граф С0=(У,Е,Р,Т), а сток в" =(У,и,Р,Т) В МДП

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

В работе доказано, что в качестве оценки частичных решений можно использовать величину /(67) = <гат{/(0,) + 1), где /(б,)- число пройденных ярусов в графе

частичных решений

Число вершин графа частичных решений Г = ({С?, можно существенно уменьшить, а, следовательно, сократить вычислительную сложность алгоритма, если использовать комбинированный диспетчер О*, дающий каждому частичному решению верхнюю оценку длины расписания г, В работе доказано, что если выполняется неравенство

/(б, ) + *«?,)> г, (КО,), (3)

то число не пройденных ярусов для графа частичных решений), то в, не лежит на оптимальном пути в дереве решений Следствием данного утверждения является то, что каждая вершина С,, отвечающая неравенству (3), удаляется из графа Г, следовательно, не производится ее дальнейшее ветвление, что приводит к сокращению размерности графа гик понижению вычислительной сложности предложенного алгоритма

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

Д' = {3{)- множество вариантов оборудования потенциально возможного у-го элемента РИС ,

со,={<?',<?2, ,Зк) (5' еД' )-вариант модернизации (те вариант оборудования используется для модернизацииу-го элемента ИС),

П = {и>,} - множество возможных вариантов модернизации ИС, причем П с /У х д2 х х д* (лк - множество подмножества допустимых векторов со,)

При решении задачи модернизации ИС использованы следующие показатели эффективности Смис(&>) ~ стоимость модернизированной ИС, Е(а>,)- относительная производительность, Кшс(о>!) - оценка относительной стоимости/производительности

При решении задачи модернизации накладываются ограничения на стоимость -Со и производительность - Е0

В работе рассмотрены следующие задачи оптимизации

су* = агё1шп Сшс (<а;), Е > Е 0, (3)

со* = а^ггпп£(&>,), Смис{ы1)<С0, (4)

ео*есоп ={(У„С^с(®))<Сд,£(0,)^£о}, (5) где сод - множество парето-оптимальных вариантов

о)*=^ттК(а},), £(<»,)> £в,Смяс(^)<Сд (6)

Остановимся более подробно на каждом из предложенных показателей оптимальности модернизированной ИС

Стоимость модернизированной ИС осуществляется по следующей формуле к

Смис(со1) = Сис-Сш"оса) + АСшс(а,), где а, = (Л,, Зк) - вариант выбора

J=l

оборудования всех атомарных элементов ИС в соответствии с /-м выбранным вариантом модернизации, Сис - стоимость существующей ИС, Сис О,) - стоимость модернизированной ИС в соответствии с выбранным ;-м вариантом модернизации, ДСДЖ,С О,) - ]Г св X; > где -стоимость оборудования ^-го элемента модернизированной ИС в соответствии с вариантом модернизации системы со,, характеристическая функция /ф равная 1, если осуществляется модернизация оборудования у-го элемента и 0 - в противном случае,

Относительный стоимостной коэффициент модернизированной ИС определяется отношением ¿(су,) = Сшс(а,)/Сис

Под производительностью системы будем понимать величину, обратную времени выполнения пользовательских запросов Р(<а, ) = (£«,;,,, где ¡¡, - усреднен-

I

ная временная оценка выполнения 1-го запроса, а/ - относительная частота поступления /-го запроса Коэффициент производительности Е(о),) = Ршс(а1)/Рис показывает во сколько раз возросла производительность ИС после модернизации

Показатель оптимальности отношения стоимость/производительность для модернизированной Кмис(о),) = V(а,)*Е'р{со,), где а,р - параметры выбора ИС по отношению к стоимости и производительности соответственно, которые с аналогичными коэффициентами экономической теории, целесообразно называть показателями эластичности выбора Если а > р, то политика модернизации предполагает минимизацию затрат на модернизацию в ущерб производительности системы, иначе -производительность является более приоритетным показателем при выборе варианта ИС Равенство а - р отражает пропорциональность затрат и производительности Для нахождения параметров а и р используют метод наименьших квадратов, суть

которого сводится к решению следующей задачи оптимизации ¿(1пг,)2=Х(а1п^-/?1п£,-К,)1

1 = 1 Г=1

Оптимизационные задачи (3)-(6) допускают единую формулировку в виде Найти

= (7)

при ограничениях

С<СП (8)

Е>ЕВ (9)

Задача (7)-(9) в общем случае является оптимизационной задачей большой размерности, поэтому для ее решения выбран МВГ, на начальном этапе которого находится допустимое решение и имеется возможность оценки его точности, а на последующих этапах осуществляется лишь его оптимизация Это позволяет использовать метод для модернизации ИС как с большим количеством элементов (используя приближенное решение), так и с малым количеством элементов (используя точное решение) Приведем только частные правила, учитывающие специфику рассматриваемой прикладной задачи, считая известной общую схему МВГ

Правило ветвления Дерево частичных решений представляет собой граф Г = (Л,5), где Я - вершины дерева, соответствующие множеству вариантов, в которых осуществляется выбор модернизации оборудования 1, 2, , р-го элемента системы, 5 -дуги, направленные от каждой вершины г, к вершинам множества {г,}, в которых осуществляется выбор модернизации оборудования р+1 элемента При этом выбираются только такие вершины р+1 элемента ИС, которые согласованы с вариантом оборудования на 1,2, ,р атомарном элементе Процесс ветвления заканчивается, когда осуществлен выбор модернизации оборудования Л-го варианта элемента, т е выбран вариант модернизации всех элементов, входящих ИС

Правило оценки Разделим все элементы системы на две группы в которых принято решение о выборе варианта модернизации {£,, ,8р} (множество вариантов модернизации соответствующих такому выбору обозначим как С1,), в которых решение не принято {¿р+,, ,8к)

Каждый вариант модернизации ИС оценивается с помощью описанных выше показателей стоимости и производительности Доказано, что

- в качестве нижней оценки стоимости множества вариантов, в которых осуществляется выбор оборудования первых р мест можно принять

ДС(Й,) = ДС(«) = ХаЧ + I ДС^ , (10)

7=1 I ~

где « = (<5,, ,5к), при условии, что вариант оборудованияу-го эле-

мента, имеющего наибольшую стоимость, равен 8 =аг§т1пС,

— '

- в качестве верхней оценки производительности для дерева частичных решений можно принять

1(П,) = 5>Л//'Ик . (П)

где t:¡ - значение длительности выполнения типовых запросов, рассчитанное для варианта со = (¿>¡, ,Sp,Sp+\, ,Sk), где <Sy sargmin/^ - выбранное оборудование

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

tr

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

£(П, )=£№,)/£'(<>.). (12)

где La(íi,) = C|ímr(ео)/Си;с в соответствии с формулой (10), Ё"(П,) - определяется по формуле (11)

Правило обхода дерева решений В процессе спуска по дереву решений на каждом шаге осуществляется выбор оборудования для одного элемента Для очередной рассматриваемой вершины находятся оценки стоимости C(íí,) и производительности £(Í2,) Далее осуществляется проверка выполнения ограничений E(Q,)<Edи C(í2,)>C0, в соответствии с вариантом решения прикладной задачи Если эти ограничения не выполняются, то найденной решение считается бесперспективным и спуск по дереву решений прекращается, тем самым осуществляется переход на более высокий уровень дерева решений Иначе, осуществляется спуск на следующий уровень дерева решений Таким образом, может быть найден некий вариант модернизации а *, удовлетворяющий ограничениям (8)-(9)

Если осуществляется решение задачи (5) нахождения парето-оптимального варианта модернизации РИС, то tu* является искомым решением

Для решения остальных оптимизационных задач (3), (4) и (6) объявим найденное решение со* рекордным и продолжим обход дерева решений

На последующих шагах метода ветвей и границ кроме проверки выполнения ограничений (8)-(9), необходимо добавить условие проверки

- для задачи минимизации стоимости (3) - С(П,)< С(а>*),

- для задачи максимизации производительности (4) - £(П,) > Е(а*),

- для задачи нахождения оптимального отношения стоимости/производительности (6) - К(С1,) < К(са*)

Если эти условия проверки не выполняются, то найденной решение Q; считается бесперспективным и спуск по дереву решений прекращается, тем самым осуществляется переход на более высокий уровень дерева решений

В процессе ветвления может быть найден вариант модернизации со1, при котором выполняется следующие условие С(ш,) <С(ш*) или Е{со,) > Е(т*), или К{со: ) < К(а>*) для задач (3), (4) и (6) соответственно В этом случае, найденное решение со. объявляется рекордным и продолжается процесс обхода дерева решений

Последний найденный рекордный вариант модернизации РИС признается искомым оптимальным вариантом

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

13

мов оценки временных характеристик в среде визуального программирования Borland Delphi 7 О

Данная информационная система состоит из следующих подсистем

1) «Подсистема управления выбором»,

2) «Информационная подсистема»,

3) «Вычислительная подсистема»

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

Результаты экспериментальных вычислений, приведенные в диссертации, проанализированы и на их основе даны практические рекомендации по выбору оптимального варианта модернизации ИС ОВД Полученные в ходе вычислительных экспериментов результаты, в частности, доказали эффективность разработанных в ходе исследования моделей, алгоритмов и автоматизированной информационной системы

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

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

1 На основе поведенного анализа состава, структуры и условий функционирования ИС ОВД разработана структурно-параметрическая модель функционирования ИС ОВД, основанная на ярусно-параллельном представлении раскрашенных взвешенных графов причинно-следственных отношений между информационными процессами, веса вершин в которых задают время выполнения, а цвета - исполнителей системы

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

3 Для задачи оценки временных характеристик ИС разработан комплекс математических методов и алгоритмов, адаптированный к временным ограничениям

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

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

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

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

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

5 Разработана автоматизированная информационная система, обеспечивающая получение оценок временных характеристик для заданной структуры ИС и позволяющая выбирать оптимальный вариант ее модернизации

6 Разработанная автоматизированная информационная система внедрена в деятельность УВО при ГУВД по Воронежской области

7 Разработанные математические методы и алгоритмы внедрены в учебный процесс кафедр высшей математики и информационно-технического обеспечения ОВД Воронежского института МВД России

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Основное содержание диссертации изложено в следующих работах

1 Ермошина (Никулина) Е Ю Планирование действий на основе использования эвристических алгоритмов // Сборник материалов Всероссийской научно-практической конференции курсантов, слушателей, студентов, адъюнктов и соискателей "Актуальные вопросы эксплуатации систем охраны и защищенных телекоммуникационных систем" - Воронеж Воронежский институт МВД России, 2003 - С 26-28

2 Никулина Е Ю О выборе метода планирования действий в системах охраны и безопасности / В В Меньших, Е Ю Никулина II Сборник материалов Всероссийской научно-практической конференции "Охрана, безопасность и связь" - Воронеж Воронежский институт МВД России, 2003 - С 26-28

3 Никулина Е Ю Выполнение пользовательских запросов для многопроцессорного сервера аутентификации // Сборник материалов Всероссийской научно-практической конференции курсантов, слушателей, студентов, адъюнктов и соискателей "Актуальные вопросы эксплуатации систем охраны и защищенных телекоммуникационных систем" - Воронеж Воронежский институт МВД России, 2004 -С 52-54

4 Никулина Е Ю Выбор алгоритмов планирования выполнения нитей в многопроцессорных системах / В В Меньших, Е Ю Никулина // Труды Российской конференции «Компьютерные технологии автоматизированного проектирования систем машиностроения и аэрокосмической техники» - Воронеж ВГТУ, 2004 -С 157-162

5 Никулина Е Ю Алгоритмы планирования выполнения заданий в вычислительных системах реального времени / В В Меньших, Е Ю Никулина // Вестник Воронежского института МВД России - Вып 2(21) - Воронеж Воронежский институт МВД России, 2005 - С 76-80

6 Никулина Е Ю Программная реализация эвристических алгоритмов при решении задач теории расписаний // Сборник материалов Всероссийской научно-

практической конференции "Охрана, безопасность и связь" - Воронеж. Воронежский институт МВД России, 2005 - С 26-28

7 Никулина Е Ю Математические методы и алгоритмы выбора вариантов модернизации РИС ОВД / В В Меньших, Е Ю Никулина // Сборник материалов международной научно-практической конференции "Обеспечение общественной безопасности в Центральном федеральном округе Российской Федерации" - Воронеж Воронежский институт МВД России, 2007 - С 20-23

8 Никулина Е Ю Метод ветвей и границ для выбора варианта модернизации распределенной информационной системы // Моделирование систем и информационные технологии Межвузовский сборник научных трудов Вып 5 / Сост И Я Львович, Ю С Сербулов, АНОО ВИВТ, Рос-НОУ (ВФ) - Воронеж Научная книга, 2008 -С 128-132

9 Никулина Е Ю Разработка модели выбора вариантов модернизации распределенной информационной системы ОВД // Вестник Воронежского института МВД России - Воронеж Воронежский институт МВД России -№4 -2007 -С 156160

10 Никулина ЕЮ Разработка модели выбора вариантов модернизации распределенной информационной системы ОВД // Сборник материалов международной научно-практической конференции "Охрана, безопасность и связь" 4 2- Воронеж Воронежский институт МВД России, 2008 - С 108-110

11 Метод динамического программирования для решения задач оптимизации / Е Ю Никулина, В В Меньших // Информационные технологии в науке, технике и образовании Материалы региональной научно-практической конференции / Сост Ю С Сербулов, А П Преображенский, АНОО ВИВТ, Рос-НОУ (ВФ) - Воронеж, Воронежский институт высоких технологий, 2008 - С 24-27

12 Никулина Е Ю Оценки длительности выполнения запроса в распределенных системах ОВД методом ветвей и границ / В В Меньших, Е Ю Никулина // Вестник Воронежского института МВД России - Воронеж Воронежский институт МВД России - №1 -2008 - С 109-114

13 Никулина ЕЮ Синтез алгоритмов оптимизации расписаний выполнения частично-упорядоченного множества задач / В В Меньших, Е Ю Никулина // Системы управления и информационные технологии - 2008 - №2(32) - С 54-56

14 Никулина Е Ю Оценки длительности выполнения запроса в распределенных системах ОВД с помощью генетического алгоритма / В В Меньших, Е Ю Никулина // Вестник Воронежского института МВД России - Воронеж Воронежский институт МВД России -№2 -2008 -С 131-140

Подписано в печать_

Уел печ л 0,93 Уч-изд л 1 Формат 60x84 1/16 Тираж 100 экз Заказ № Типография Воронежского института МВД России, 394065, г Воронеж, проспект Патриотов, 53

ВВЕДЕНИЕ

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ ОПТИМИЗАЦИИ ВРЕМЕННЫХ ХАРАКТЕРИСТИК В ИНФОРМАЦИОННЫХ СИСТЕМАХ ОРГАНОВ ВНУТРЕННИХ. ДЕЛ

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

1.2. Общая модель оптимизации временных характеристик в информационных системах

1.3. Методы и алгоритмы оптимизации временных характеристик в информационных системах

1.4. Постановка задач и схема проведения исследования

ГЛАВА 2. РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МЕТОДОВ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ВРЕМЕННЫХ ХАРАКТЕРИСТИК В ИНФОРМАЦИОННЫХ СИСТЕМ ОРГАНОВ ВНУТРЕННИХ ДЕЛ

2.1. Структурно-параметрическая модель функционирования информационных систем органов внутренних дел

2.2. Разработка и обоснование математических методов и алгоритмов оценки временных характеристик в жестких временных ограничениях

2.3. Разработка и обоснование математических методов и алгоритмов оценки временных характеристик при заданных временных ограничениях •

2.4. Разработка и обоснование математических методов и алгоритмов оценки временных характеристик без временных ограничений

ГЛАВА 3. ИСПОЛЬЗОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ ВРЕМЕННЫХ ХАРАКТЕРИСТИК ДЛЯ ОБОСНОВАНИЯ ВЫБОРА ВАРИАНТА МОДЕРНИЗАЦИИ РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ

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

3.2 Методы оценки вариантов модернизации распределенных информационных систем 92 •

3.3 Модели оптимизации выбора варианта модернизации распределенных информационных систем

ГЛАВА 4. РАЗРАБОТКА ИНФОРМАЦИОННОЙ СИСТЕМЫ ОПТИМИЗАЦИИ ВРЕМЕННЫХ ХАРАКТЕРИСТИК РАСПРЕДЕЛЕНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ ОРГАНОВ ВНУТРЕННИХ ДЕЛ

4.1 Структурная модель информационной системы оптимизации временных характеристик распределенной информационной системы

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

Актуальность темы. Одной из главных задач Министерства внутренних дел Российской Федерации является повышение эффективности обработки информации в информационных системах с учетом технических возможностей на современном этапе развития. В связи с этим в МВД России принята концепция создания «Единой информационно-телекоммуникационной системы органов внутренних дел», в рамках которой предполагается переход к использованию принципиально новых информационных систем, способных обеспечивать все возрастающие запросы пользователей.

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

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

Диссертационная работа выполнена на кафедре высшей математики

Воронежского института МВД России в соответствии с одним из научных направлений Воронежского института МВД России «Разработка методов математического моделирования и численного анализа прикладных задач естествознания».

Объектом исследования являются информационные процессы в ИС

ОВД.

Предметом исследования выступают математические методы, модели и алгоритмы оптимизации временных характеристик ИС ОВД.

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

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

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

2. Проведение вычислительных экспериментов по оценке временных характеристик в интересах разработки комплекса математических методов, моделей и алгоритмов.

3. Разработка математических методов и алгоритмов оценки времен- ' ных характеристик к ИС:

- в условиях жестких временных ограничений;

- при заданных временных ограничениях;

- без временных ограничений.

4. Разработка комплекса математических моделей, методов и алгоритмов оптимизации выбора варианта модернизации ИС ОВД.

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

Научная новизна. При выполнении диссертационного исследования получены следующие новые научные результаты:

1. Разработана структурно-параметрическая модель функционирования ИС ОВД, основанная на использовании взвешенных раскрашенных орграфов информационных процессов, отличающаяся от известных использованием ярусно-параллельного представления для оценки временных характеристик.

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

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

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

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

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

Апробация работы. Основные методические и практические результат ты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Всероссийской научно-технической конференции «Теория конфликта и ее приложения» (Воронеж, 2004г.); Всероссийской научно-практической конференции «Охрана, безопасность и связь» (Воронеж 2003, 2005); Всероссийской научно-практической конференции курсантов, слушателей, студентов, адъюнктов и соискателей «Актуальные вопросы эксплуатации систем охраны и защищенных телекоммуникационных систем» (Воронеж, 2003, 2004); Российской конференции «Компьютерные техноло-гйи автоматизированного проектирования систем машиностроения и аэрокосмической техники» (Воронеж, 2004); Международной научно-практической конференции "Обеспечение общественной безопасности в Центральном федеральном округе Российской Федерации" (Воронеж, 2007); Международной научно-практической конференции «Охрана, безопасность и связь» (Воронеж, 2007); Региональная научно-практическая конференция «Информационные технологии в науке, технике и образовании» (Воронеж, 2008).

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

ЗАКЛЮЧЕНИЕ

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

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

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

• 3. Для задачи оценки временных характеристик ИС разработан комплекс математических методов и алгоритмов, адаптированный к временным ограничениям.

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

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

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

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

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

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

6. Разработанная автоматизированная информационная система внедрена в деятельность УВО при ГУВД по Воронежской области.

7. Разработанные математические методы и алгоритмы внедрены в учебный процесс кафедр высшей математики и информационно-технического обеспечения ОВД Воронежского института МВД России.

1. Авен О.И., Гурин Н.Н., Коган А .Я. Оценка качества и оптимизация вычислительных систем. - М.: Наука, 1982. - 464с.

2. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. -М.: Радио и связь, 1990. 256с.

3. Башлы П.Н. Современные сетевые технологии : Учебное пособие. — М.: Горячая линия Телеком, 2006. - 334с.

4. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960.-400 с.

5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458 с.

6. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969. - 118 с.

7. Бешелев С.Д., Гурвич Ф.Г. Экспертные оценки. М.: Наука, 1973.79 с.

8. Блынский А.Д. Основные направления информационного обеспечения органов внутренних дел // iBUSINESS. №6. - 2002г. http://www.hse.ru-/pressa/ibusiness/2002094.htm

9. Богданов А.В., Корхов В.В., Мареев В.В., Станкова Е.Н. Архитектуры и топологии многопроцессорных вычислительных систем. М.: Изд-во: Интернет-университет информационных технологий - ИНТУИТ.ру, 2004. -176 с.

10. Богданов А.В. Архитектуры и топологии многопроцессорных вычислительных систем / А.В.Богданов, В.В.Корхов, В.В.Мареев, Е.Н.Отанко-ва. М.: Изд-во: Интернет-университет информационных технологий. -ИНТУИТ.ру, 2004. - 176 с.

11. Бронштейн И.Н. Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. 13-е изд., испр. - М.: Наука, 1986. - 544с.

12. Вайрадян А.С., Коровин А.В., Удалов В.Н. Эффективное функцио7 нирование управляющих мультипроцессорных систем. М.: Радио и связь, 1984.-328с.

13. Вентцель Е.С. Исследование операций. М.: Советское Радио, 1972. -551с.

14. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К.Вороновский, К.В. Махотило, С.Н. Пет-рашев, С.А. Сергеев. Харьков: «Основа» 1997.

15. Головин С. Технологии мультисервесных сетей // СЮ. №10.2005.

16. Дегтярев Ю.И. Методы оптимизации. М.: Советское радио, 1980.272 с.

17. Десятов А. Д. Моделирование процессов защиты информации в распределенных информационных системах органов внутренних дел: Дис. . канд. тех. наук: 05.13.18. / А.Д. Десятов. Воронеж, 2006г. - 134с.

18. Джонсон Д. Вычислительные машины и труднорешаемые задачи// Пер; с англ. М.: Мир, 1982. -416с.19.'Жуков Ю. Как правильно проектировать информационно-телекоммуникационные системы // Технологии и средства связи. №2. 2006. С. 25-26.

19. Зыков А.А. Основы теории графов. — М.: «Вузовская книга», 2004. . 664 с.

20. Исследование операций. Модели и применение / Под ред. Дж. Маузера, С. Элмаграби. Т2. М.: Мир, 1981. - 677 с.

21. Клещев Н.Т. и др. Телекоммуникации: Мир и Россия. Состояние и. тенденции развития / Под ред. Н.Т.Клещева. М.: Радио и связь, 1999. -480с.

22. Конвей Р.В. Теория расписаний / Р.В. Конвей, B.JI. Максвел, JI.B. Миллер. М.: Наука, 1975. - 360 с.

23. Корбут А.А. Дискретное программирование / А.А.Корбут, Ю.Ю. Финкелыптейн; Под ред. Д.Ю. Юдина. -М.: Наука, 1969. 368с.

24. КорбутА.А., Финкелыптейн Ю.Ю. Приближённые методы дискретного программирования // Изв. АН СССР. Техн. Кибернет. 1983. - №1- С. 165-176.

25. Концепция развития информационно-вычислительной системы МВД России на период 2002-2006 гг., утвержденная приказом МВД от 13.06.02.г. № 562.

26. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

27. Лазарев А.А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбина- ' торной оптимизации: Автореферат дис. . канд. физ. мат. наук: 01.01.09. / А.А. Лазарев. - М., 2007. - 36 с.

28. Лавренов С.М. Excel: Сборник примеров и задач. М.: Финансы и статистика, 2000. - 336 с.

29. Липский В. Комбинаторика для программистов. М.: Мир, 1988 —213 с.

30. Мартин Дж. Вычислительные сети и распределенная обработка данных: программное обеспечение, методы и архитектура. Вып. 1. - М.: Финансы и статистика, 1985. - 256 с.

31. Меньших В.В. Использование жестких диспетчеров в двухпроцессорной вычислительной системе // Автоматика и вычислительная техника, 1993. -№3. С. 76-78.

32. Меньших В.В. Конфликтные взаимодействия в процессе синтеза параметров управляющих воздействий в многоцелевых системах управления / В.В. Меньших, В.В. Сысоев // Автоматика и вычислительная техника. — 2002. -№ 1.- С. 35-39.

33. Меньших В.В. О выборе методов оптимизации последовательности выполнения запросов к вычислительным системам // Автоматика и вычислительная техника. 1996. - №1. - С.72-76.

34. Меньших В.В. О задаче оптимизации порядка выполнения запросов в вычислительных системах // Автоматика и вычислительная техника. 1993. -№1.С. 3-9.

35. Меньших В.В. О задаче оптимизации размещения программ и данных в памяти рабочей станции-сети // Весенняя Воронежская математическая школа «Понтрягинские чтения VIII»: Тезисы докладов. - Воронеж, 1997. -с: 99.

36. Меньших В.В. Об оптимизации порядка выполнения действий в вычислительных системах. // Весенняя Воронежская математическая школа «Понтрягинские чтения V»: Тезисы докладов. - Воронеж, 1994. - С. 96.

37. Меньших В.В. Оптимизация размещения программ и данных в памяти рабочей станции сети // Автоматика и вычислительная техника. — 1996. JVs 5. — С. 49-56. '

38. Меньших В.В. Поведение жестких диспетчеров в условиях неопределенности длительностей операций / В.В'. Меньших, Н.А. Агафонова, Н.Г. Бублик, А.А. Кипрушев // Автоматика и вычислительная техника. 1991. -№2.-С. 56-58.

39. Меньших В.В. Сравнение алгоритмов диспетчеризации в условиях неопределенности длительностей операций / В.В. Меньших, Н.Г. Бублик, Д.Э. Литвиненко // Управляющие системы и машины. 1990. - №3. - С. 6972.

40. Меньших В.В. Сравнение алгоритмов диспетчеризации для двухпроцессорной вычислительной системы / В.В. Меньших, Н.А. Агафонова И Автоматика и вычислительная техника. 1992. - №1. - С. 3-5.

41. Меньших В.В., Сысоев В.В. Структурная адаптация систем управления. М.: ИПРЖР, 2002. - 150с.

42. Метвеев М.Г., Свиридов А.С., Алейникова Н.А. Модели и методы искусственного интеллекта: применение в экономике. М.: Финансы и статистика, 2008. - 448с.

43. Моисеев Н.Н., Иванников Ю.П., Столярова Ю.М. Методы оптимизации. М.: Наука, 1978 - 352 с.

44. Никулина Е.Ю. Алгоритмы планирования выполнения заданий в вычислительных системах реального времени / В.В. Меньших, Е.Ю. Никулина // Вестник Воронежского института МВД России. Вып. 2(21). - Воронеж: Воронежский институт МВД Ррссии, 2005. - С.76-80.

45. Никулина Е.Ю. Разработка модели выбора вариантов модернизации распределенной информационной системы ОВД // Вестник Воронежского института МВД России. Воронеж: Воронежский институт МВД России. -2007. -№4. - С.156-160.

46. Никулина Е.Ю. Синтез алгоритмов оптимизации расписаний вы-' полнения частично-упорядоченного множества задач / В.В. Меньших, Е.Ю. Никулина // Системы управления и информационные технологии. — 2008. -№2(32). С. 54-56.

47. Никулина Е.Ю. Оценки длительности выполнения запроса в распределенных системах ОВД с помощью генетического алгоритма / В.В. Меньших, Е.Ю. Никулина // Вестник Воронежского института МВД России. Воронеж: Воронежский институт МВД России. - 2008. - №2 - С.

48. Оре О. Теория графов. М.: Наука, 1980. - 336 с.

49. Основы автоматизации управления в органах внутренних дел / Под. ред. А.П.Пожидаева, В.А. Минаева. М.: Академия МВД России, 1993. -331с.

50. Принятие решений: Метод анализа иерархий: Пер. с англ. М.: Радио и связь, 1993. - 320с.

51. Программа МВД России «Создание единой информационно-телекоммуникационной системы- органов внутренних дел», утвержденная приказом МВД России от 6.12.2004г. №813.

52. Рыбакова Н. Пилотный проект уже показал свою эффективность // Татар-информ. 2005. - 29 декабря 2005. - С. 3-4.

53. Савостицкий Ю.А.История развития глобальных компьютерных сетей // Информационное общество. 2000. - Вып. 4. - С.59-65.

54. Сарайкин В.Г. Информационная система для комплексной автоматизации процессов хозяйственной деятельности в лесопромышленном комт плексе. СПб.: СПбЛТА, 2003. - 232с.

55. Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. -М.: Мир, 1984. -455 с.

56. Севастьянов С. В. Геометрические методы и эффективные алгоритмы в теории расписаний //Дис. док. физ.-мат. наук.: 051318. Новосибирск: 2000.- 280с.

57. Сирота В. Компьютерные хроники // Мой мир. 2003. - №18-20.

58. Системы параллельной обработки: Пер. с англ. / Под ред. Д. Ивенса. М. : Мир, 1985. - 416с.

59. Стандарт Министерства обороны США 1985 г., (Department of Defense Trusted Computer System Evaluation Criteria, DOD, 1985.)

60. Стрюков C.A. Разработка моделей и программных средств для построения компьютерных информационных систем с распределенной архи-. тектурой: Автореферат дис. . канд. тех. наук: 05.13.18. // http://www.masters.donntu.edu.ua

61. Танаев B.C. Теория расписаний. Многостадийные системы // B.C. Танаев, Ю.Н. Сотсков, В.А. Струсевич. М.: Наука, 1989. - 335с.

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

63. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы. СПб: Питер, 2003. - 880 с.

64. Татт У. Теория графов. М.: Мир, 1988. - 424 с.

65. Телекоммуникации. Мир и Россия. Состояние и тенденции развития / Клещев Н.Т., Федулов А. А. и др. М.: Радио и связь, 2004. - 480с.

66. Теория линейного и целочисленного программирования: В 2-х т.:1 Т.1; Пер.с англ. С.А.Тарасова и др.; Под ред. Л.Г. Хачияна. М.Г Мир, 1991. -360с.

67. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. М.: Наука, 1984. - 334 с.

68. Устенко А.С. Основы математического моделирования и алгоритмизации процессов функционирования сложных систем. М.: Наука, 2000. -165 с.

69. Фаронов В.В. Delphi 7. Руководство программиста / В.В. Фаронов. -М.: Нолидж, 2003. 885 с.

70. Федеральный закон РФ «Об информации, информатизации и защите информации». // Российская газета. 1995. - 22 февраля. - С. 4.

71. Федоров В. «Орбита»: единая сеть МВД охватит всю Россию // www/ cnews .ru/revien/print. shtml?2007/08/02/261259

72. Феррари Д. Оценка производительности вычислительных систем. -М.: Мир, 1981.-263 с.

73. Харари Ф. Теория графов: Пер. с англ. М.: Мир, 1973. - 300с.94.'Харари Ф., Палмер. Перечисление графов. Пер. с англ. М.: Мир, 1977.-324с.

74. Халафян А.А. Статистический анализ данных. STATISTICA 6.0.: 2-е изд. испр. и доп. Краснодар: КубГУ, 2005. - 308 с.

75. Царегородцев А.В. Информационная безопасность в распределенных управляющих системах. М.: Изд-во РУДН, 2003. - 217с.

76. Якубайтис Э.А. Информационно-вычислительные сети. М.: Финансы и статистика, 1984. - 324 с.

77. Attia A.A.,Horacek P. Adaptation of genetic algorithms for optimization problem solving// 7th International Conference on Computing MENDEL 2001. -Brno, 2001.-pp. 36-41.

78. Clement R.P. & Wren A. "Genetic Algorithms and Bus-Driver Scheduling". Presented at the 6th International Conference for Computer-Aided Transport Scheduling. Lisbon: Portugal, 1993.-pp. 173-177.

79. Gantt H.L. ASME Transactions, 1903. -24-pp. 1322-1336.

80. Goldberg D.E. Genetic. Algorithms in Search Optimizations and Machine Learning. Addison.Wesly, 1989. - pp. 42-45.

81. Land A.H., and Doig A.G. An autmatic method of solving discrete programming problems. Econometrica. v 28. - 1960. - pp. 497-520.

82. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. Operations Research. v 11. — 1963. - pp.972.989.