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

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

ИЗОТОВ Дмитрий Викторович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ЗАДАЧ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ЦЕНТРОВ ХРАНЕНИЯ И ОБРАБОТКИ ИНФОРМАЦИИ В АСУ ПРЕДПРИЯТИЯ

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

АВТОРЕФЕРАТ 4

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

49389

9 ИЮН 2011

Тула 2011

4849389

Работа выполнена в ГОУ ВПО «Тульский государственный университет»

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

ЛАРКИН Евгений Васильевич

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

ИЛЬИН Анатолий Александрович

Доктор технических наук, профессор ПРИВАЛОВ Александр Николаевич

Ведущая организация:

ОАО «АК «Центральный научно-исследовательский институт систем управления», г. Тула

Защита состоится « ДО »'ЬЫ^Н-Я' 2011 г. в 14-00 часов на заседании диссертационного совета Д 212.271.07 при ГОУ ВПО «Тульский государственный университет» (300012, г. Тула, проспект Ленина, 92, {

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Тульский государственный университет».

Автореферат разослан «о^Ь » МА&* 2011г. Учёный секретарь

диссертационного совета Ф.А. Данилкин

Общая характеристика работы

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

Известные математические постановки задач о размещении представляют собой частные случаи классических задач теории графов - «задачи о /»-медиане» и «задачи о ¿»-центрах», а также «задач о назначении», для решения которых, как правило, используются алгоритмы, основанные на идеях метода ветвей и границ. Этим задачам посвящен ряд работ таких авторов, как: S.L. Hakimi, Н. Noltermeier, J. Spoerhose, Н. Кристофидес, B.JI. Берес-нев, Э.Х. Гимади, В.Т. Дементьев, Е.В. Алексеева, Ю.А. Кочетов, Г.Г. Забуд-ский и другие.

В постановке применительно к компьютерным сетям в целях оптимизации информационно-вычислительного процесса (ИВП) наиболее известные подходы к решению подобных задач рассмотрены в работах О.Г. Алексеева, В.Д. Киселева, О.В. Есикова, И.В. Сергиенко, A.A. Корбута, Ю.Ю. Фин-кельштейна, Г.Ф. Янбых, Б.А. Столярова и других авторов.

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

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

3

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

Исходя из этого, научной задачей, решаемой в диссертационной работе, является разработка математических моделей и алгоритмов оптимизации ИВП путём оптимального размещения ЦХИ в узлах распределённой компьютерной сети.

Объектом исследования являются распределённые компьютерные сети АСУ предприятия.

Предметом исследования являются математические модели и алгоритмы размещения ЦХИ в компьютерной сети АСУ предприятия.

Целью диссертационной работы является повышение качества ИВП в распределённой компьютерной сети за счёт разработки математического и программного обеспечения задач оптимального размещения ЦХИ на основе анализа информационного взаимодействия между объектами АСУ и требований к показателям качества ИВП, а также применения новых информационных технологий с учётом перспективных направлений совершенствования современных АСУ.

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

анализ факторов, влияющих на эффективность информационных процессов в современной АСУ предприятия;

разработка методики оптимизации ИВП в распределённой КС;

разработка математических моделей, методов и алгоритмов оптимального размещения ЦХИ в распределенной КС;

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

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

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

1. Методика формирования ИВП, основанная на оптимизации размещения ЦХИ в распределённой компьютерной сети.

2. Математические модели оптимизации числа и мест размещения ЦХИ в компьютерной сети, основанные на классических задачах из теории графов о ¿»-центрах и р-медиане с учётом введения дополнительных ограничений для обеспечения заданных требований по оперативности и надежности представления информации.

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

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

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

Достоверность научных результатов подтверждена корректным применением используемого математического аппарата, а также согласованностью результатов теоретического расчёта с данными, полученными в ходе экспериментов с применением имитационной модели, а также в ходе решения практических задачи выбора ЦХИ. Работоспособность предложенных алгоритмов была подтверждена сравнением результатов «ручного» расчёта по контрольным исходным данным с результатами, полученными с помощью разработанного программного средства.

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

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

Ряд теоретических результатов внедрены в учебный, процессе ГОУ ВПО «Тульский государственный университет», а также Тульского филиала ОРАГС.

Апробация работы. Материалы диссертации докладывались, обсуждались и одобрены на межрегиональных и внутривузовских научных и научно-практических конференциях (Тула - 2005, 2007, 2011 г.г.), а также на международных конференциях (Москва - 1999 г., Волгоград - 2006 г., Тула -2011 г., Омск-2011 г.).

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

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

текста, содержит 27 рисунков, 28 таблиц, список используемой литературы из 77 наименований, а также 4 приложения.

Краткое содержание диссертации

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

В первой главе произведён анализ научных работ, посвященных проблемам повышения эффективности ИВП в распределённых КС и вопросам разработки математического и программного обеспечения АСУ, в состав которого входят рассматриваемые в работе задачи.

Рассмотрены факторы, влияющие на эффективность ИВП в распределённых компьютерных сетях.

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

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

Средние величины объемов информации, циркулирующей между отделами, представлены в таблице 1.

Таблица 1 - Средние величины объемов информации электронного

документооборота (тыс. знаков)

Отделы 1 отд. 2 отд. 3 отд. 4 отд. 5 отд.

1. Оргплановый 78/236 48/150 88/273 101/305

2. Производственный 236/78 58/44 122/106 243/94

3. Снабжения 150/48 44/58 86/96 125/50

4. Хранения и сбыта 273/88 106/122 96/86 249/72

5.Эксплуатационно-ремонтный 305/101 94/243 50/125 72/249

Характеристика электронного документооборота на предприятии в напряжённый период работы показана в таблице 2.

Согласно документам, в напряжённый период в офисах филиалов в полном объеме информация собирается и обобщается не реже, чем через каждые 2-6 часов. Общее количество источников, от которых собирают информацию, превышает 180.

Таблица 2 - Характеристика информационных потоков на предприятии

в напряжённый период (тыс. знаков в месяц)

Отправитель - получатель Объем информации

Офис 11,0

Производственные и ремонтные подразделения 7,0

Подразделения хранения и сбыта 12,0

Подразделения снабжения 2,5

На основе анализа факторов, влияющих на ИБП, сформулированы требования, предъявляемые к АСУ, основные направления её совершенствования и связанные с этим задачи.

Отмечается, что обеспечение требований к АСУ по надежности, производительности и способности адаптироваться к меняющимся задачам можно осуществить за счёт использования ЦХИ. В работе приведена классификация центров хранения и обработки информации.

Показано, что эффективность ИВП в распределенной КС предприятия существенно зависит от количества и размещения ЦХИ, что доказывает необходимость решения данной задачи в реальном масштабе времени.

Предполагается, что в соответствии с двухранговой моделью «Клиент/Сервер», часть узлов КС оборудуются как ЦХИ. Остальные же узлы оборудуются как автоматизированные рабочие места должностных лиц (АРМ ДЛ). При этом состав сети будет иметь вид, как на рисунке 1.

Рисунок 1 - Состав компьютерной сети АСУ предприятия

Исходя из этого, предложена методика оптимизации ИВП в АСУ предприятия, структурно представленная на рисунке 2, где жирным шрифтом выделены её основные разделы.

АСУ предприятия

технологическая подсистема

состав КС

компоненты

унифицированный КСА

набор типовых ФК

прикладные службы

сервисные программы

прикладные программы

служба информационной поддержки

телекоммуникационная сеть

служба распределенных баз данных

функциональная подсистема

ОПТИМИЗАЦИЯ ИВЙ-В АСУ

Проектирование физической структуры

задачи

Проектирование логической структуры

и модели

Оптимйзация размещения ЦХИ

■ ■ 1 I :>1> , ..!■■■ .. 1 .. ".„л.::'-'.'

Унификация функциональных компонентов комплекса средств автоматизации и программного _обеспечения КС__

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

Оптимизация структур локальных, объектовых и территориальных сетей связи

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

Модели для определения исходных параметров и

по критериям, характеризующим качество функционирования

по критерию стоимости

по критерию максимума интенсивности запросов ■ на обслуживание

модели для? оценки: принимаемых решений по размещению ЦХИ

модели для определения

объемно-временных характеристик потоков информации в АСУ

Рисунок 2 - Методика оптимизации информационно-вычислительного процесса в АСУ

В основу создания методики оптимизации ИБП АСУ предприятия положена разработка комплекса математических моделей, методов и алгоритмов оптимального выбора ЦХИ в распределенной компьютерной сети АСУ.

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

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

для АСУ с различными режимами функционирования и большим и разнообразным перечнем решаемых задач представляется целесообразным следующий подход: ЦХИ размещаются в тех узлах сети, где наиболее часто возникает потребность в информационном обслуживании, при этом, для учёта требований по оперативности, ЦХИ размещаются таким образом, чтобы временная задержка данных в сети не превышала бы заданного значения.

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

Во второй главе, исходя из требований оперативности и надежности представления выходной информации, производён выбор и обоснование показателей эффективности информационных процессов в современных АСУ предприятия, разработаны математические постановки задач выбора числа и мест размещения ЦХИ по узлам сети. Сформулированные задачи сведены к задачам целочисленного программирования. Предложены алгоритмы решения этих задач.

С целью формализации задач структурно АСУ представляется в виде совокупности объектов управления 1,..., N, каждый из которых является узлом КС. Все автоматизируемые функции по информационному обслуживанию должностных лиц предприятия разбиты на ряд 1.....L функциональных

задач (ФЗ). Каждый узел сети может быть оснащен либо как ЦХИ, либо как АРМ ДЛ. Каждая ФЗ может решаться в одном из ЦХИ.

Суммарное время передачи информации по сети при решении 1-й ФЗ в /-М узле сети определяется как сумма времен передачи информации по каналам связи при выполнении каждого из этапов (запроса, обработки, ответа и доведения) в процессе решения ФЗ:

Ji _ ,запр . .обр . ,отв , +довед

И - 41 + 41 + 41 + %

Математическая модель задача выбора ЦХИ по критерию минимума суммарного времени передачи данных по сети имеет вид: определить такие

хц> У^' г = Ь I = ^, при которых достигало бы минимума - N £

тр-=1^Тахй ¿=1 /=1

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

N

2>;7=1, / = и;

!=1

N

2>/=/>;

¿=1

(1)

(2)

(3)

У1>Ха, 1 = 1,1, / = 1,ЛГ; (4)

V , если/-я задача решается в/-м узле сети;

Но ()

,в противном случае;

("1 , если 1-й узел сети есть ЦХИ,

УГ\ (6)

(О , в противном случае;

р;гдхи>ргд ,1=\л,1=\^ , (7)

г>зад. ,

где - заданная вероятность надежного представления информации при

решении 1-Й ФЗ; р - количество ЦХИ в сети.

Физический смысл ограничения (2) заключается в том, что любая ФЗ может решаться только в одном узле сети, ограничения (3) - в том, что количество ЦХИ равняется величине р, ограничения (4) - в том, что ФЗ могут решаться только в ЦХИ.

Отличительной особенностью этой модели состоит в том, что она соответствует классической постановке целочисленной задачи, известной в теории графов как «задача о /»-медиане». Введение дополнительных ограничений (7) обеспечивает выполнение требований по надёжности. Для решения задачи необходимо определить величину р - общее количество ЦХИ в КС. Оценка этой величины проводится на основе анализа общего объема ИВП в АСУ, необходимого для выполнения ею своих прикладных функций.

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

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

По критерию стоимости задача выбора ЦХИ сформулирована на основе обоснованного предположения, что существует некоторое оптимальное число р и оптимальное размещение ЦХИ по объектам АСУ, являющихся узлами КС, при которых суммарные затраты в системе, приходящиеся на один запрос (затраты на передачу информационного запроса, его обслуживание и создание всех ЦХИ), были бы минимальны, а временные и надёжностные параметры не превышали бы заданных значений. Математическая постановка имеет вид «задачи о р-медиане» с дополнительным ограничением вида < Р, где Р - заданное число ЦХИ. Показано, что оптимальное размещение ЦХИ в условиях постоянной стоимости обслуживания одного запроса определяется только стоимостью передачи информации по каналам связи и затратами на создание ЦХИ.

Алгоритм нахождения минимального числа р для задачи по критерию стоимости основан на пошаговом подходе. На первом шаге находится оптимальное решение задачи при минимальном значении р, например, при р= 1. Далее решается, следует ли переходить к решению задачи при р=р+\ (р= 2). Для этого полученное на первом шаге минимальное значение затрат Фт,п(1) сравнивается с некоторой величиной затрат, являющейся нижней границей для всех вариантов с р=р+1:

Фщ(2) = (р + Щ0+Фт^,

гДе ф„™ = шш (рд, '.У

Z0 - затраты на создание ЦХИ,

Хг - интенсивность суммарного потока запросов;

<Ру - стоимость передачи информации от г'-го к_/-му узлу сети.

Если Фт!п(1) < Фоц(2), то полученное количество и размещение ЦХИ

является одновременно и решением задачи. В противном случае следует перейти ко второму шагу с р-р+1, а затем сравнить полученное на втором шаге решение с решением, полученным на предыдущем шаге.

Общая постановка задачи выбора числа и мест размещения ЦХИ в КС по критерию максимума интенсивности поступления запросов на информационное обслуживание сформулирована следующим образом: требуется определить минимальное число центров обработки информации, обслуживающих информационные запросы от АРМ ДЛ, и такое их размещение в узлах сети, чтобы значение времени задержки передачи сообщения для каждого АРМ ДЛ не превышало допустимой величины, а суммарная приведенная интенсивность поступления запросов на узлы КС, в местах расположения которых будут размещены ЦХИ, была при этом максимально возможной. Математическая постановка имеет вид «задачи о ¿»-центрах».

Д ля формализации задачи в этом случае компьютерная сеть была представлена в виде неориентированного графа С=(Х, Г), вершины х% г=1,

которого соответствуют узлам сети, а дуги - каналам связи. При этом «длины» дуг (7^, - время задержки сообщений в н>-м канале связи) графа (г образуют матрицу времен задержки передачи сообщения между соответствующими узлами сети. Веса соответствующие вершинам графа, определяют суммарный объем запросов на соответствующие этим вершинам узлы КС.

При разработке алгоритма решения «задачи о р-цвнтрах» исходная задача сводилась к задаче о покрытии. Особенности такого сведения заключается в следующем. Используя матрицу кратчайших путей £) = ||^|для заданного графа, переходим к матрице покрытий А - ||а,у|, которая составляется по следующим правилам:

Г1, если с1ц < Тпш,

О, в противном случае, где Ттах- допустимое время передачи данных из одного узла сети в другой.

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

хотя бы одна вершина, входящая во множество X*, из каждой вершины графа (7 была достижима в пределах заданного расстояния Ттах, т. е. чтобы выполнялось условие >1, /= Сумма должна быть при

¡еХ' ¡ех'

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

Требуется минимизировать целевую функцию

ЛГ *

в= (8) 1=1

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

I ацщ >1, у = (9)

/=1

х. = {0;1}, 1 = (10)

где д' = 1/д,- (т.к. в исходной задаче необходимо максимизировать сумму Xд, ); ^>0.

Специфические особенности задачи (8)-(10) позволяют значительно упростить процедуру вычисления нижней границы решения на основе использования двойственной задачи.

С этой целью в диссертации условие целочисленности (10) заменяется условием:

. 0<х;<1 /=1,...,ЛГ. (11)

Тогда по отношению к основной задаче (8), (9), (11), двойственная задача имеет вид: найти

N ■

2=тах £ V • (12)

М

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

N *

I < , / = 1,...,ЛГ, (13)

7=1

Vj-wiJ^<0, ¡ = 1,...,И, 7 = 1,...,Л^, ' (14)

где Ур^у - переменные двойственной задачи.

Из теории двойственности известно, что оптимальные решения основной и двойственной задачи совпадают, т. е. (¿-Х. Для приближенного решение двойственной задачи (12)-(14) выполняется условие <Q. Следовательно, приближенное решение двойственной задачи может быть использовано для оценки нижней границы при применении метода ветвей и границ. При этом точность приближенного решения может быть достаточно высокой. Использование двойственной задачи позволило значительно упростить оценку нижней границы без существенного уменьшения ее точности.

Третья глава посвящена исследованию разработанных математических моделей оптимизации ЦХИ в КС современных АСУ предприятия, а также экспериментальной оценке алгоритмов и программ оптимизации, проверке работоспособности разработанного математического аппарата с целью выработки рекомендаций по его применению.

На основе анализа организации информационного взаимодействия в компьютерной сети разработана имитационная модель системы массового обслуживания на языке ОРБ8/РС, применяемая при подготовке исходных данных для решения задачи оптимального выбора ЦХИ в узлах КС АСУ предприятия. Структура модели представлена на рисунке 3.

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

Рисунок 3 - Обобщенная структура имитационной модели компьютерной сети АСУ предприятия

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

С целью исследования работоспособности и эффективности алгоритма решения «задачи о ¿»-центрах» разработана программа «Центр».

Программа «Центр» решает «задачу о р-центрах» методом последовательного решения задачи о кратчайших путях и задачи о покрытии. Задача нахождения кратчайших путей между всеми парами вершин графа решается методом Флойда. Задача о покрытии решается методом ветвей и границ с использованием для оценки нижней границы приближенного решения двойственной задачи. Максимальная размерность решаемых задач зависит от наличия свободных ресурсов ЭВМ. Программа функционирует в среде операционной системы Windows и занимает 374 Кбайт дискового пространства.

Эффективность алгоритма решения «задачи о ¿»-центрах» оценивалась по результатам исследования основной задачи - задачи о покрытии (рисунок 3).

20

40

60

80

100

120

Рисунок 3 - Эмпирическая зависимость времени решения задачи о покрытии от размерности П и плотности заполнения матрицы исходных данных И

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

Характер зависимости времени решения «задачи о /»-медиане» от размерности матрицы исходных данных представлен на рисунках 4 и 5.

600 400 200 0

-44

-р=5

10 15 20 25 30 35 40 45 50 55 60

Рисунок 4 - Эмпирическая зависимость времени решения задачи о р-медиане от размерности исходных данных при значении р = 5

1400 1200 1000 800 600 400 200 0

1

У

у

н-

-р=10

15 20 25 30 35 40 45 50

Рисунок 5 - Эмпирическая зависимость времени решения задачи о р-медиане от размерности исходных данных при значении /7=10

Рисунок 6 - Эмпирическая зависимость времени решения задачи о р-медиане от значенияр при размерности матрицы исходных данных 30x30

Из графика на рисунке 6 видно, что время решения резко возрастает с увеличением значения р, но на практике при решении задач выбора ЦХИ значение р не будет превышать 10% - 30% от размерности матрицы исходных данных, что позволит успешно применять данный алгоритм.

Результаты исследования эффективности алгоритма решения «задачи о р-медиане» подтверждают возможность его применения для выбора ЦХИ, в том числе, и в условиях реального времени.

В диссертации рассмотрен процесс решения практической задачи выбора ЦХИ для конкретного предприятия по различным критериям. Результаты решения задачи показали, что:

при решении задачи по критерию времени («задача о ¿»-медиане») оптимальное размещение ЦХИ (для р = 5) суммарное время обслуживания запросов в сети по сравнению с исходным вариантом снижается примерно на 30%;

оптимальное решение задачи по критерию максимальной интенсивности запросов («задача о ¿»-центрах») для заданного максимального времени задержки передачи одного сообщения в сети Ттах = 5секунд соответствует минимальному значению р = 6. Уменьшение Ттах на 2 секунды приводит к увеличению числа р примерно в 2 раза, что пропорционально увеличивает стоимость обслуживании информационных запросов.

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

В заключении сформулированы основные результаты и выводы по работе.

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

Основные результаты работы

В результате теоретических и экспериментальных исследований была решена новая научная задача разработки математических моделей и алгоритмов оптимизации ИВП в распределенной АСУ предприятия путём оптимального размещения ЦХИ по узлам компьютерной сети.

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

1. Разработана методика оптимизации ИВП в распределенной АСУ предприятия, которая с учётом современных информационных технологий (распределенное хранение и обработка данных, виртуализация ресурсов компьютерной сети) на основе решения задач оптимального размещения центров хранения и обработки информации в компьютерной сети обеспечивает повышение качество ИВП в АСУ предприятия, а также минимизирует стоимость информационного обслуживания запросов в компьютерной сети. Применение данной методики дало следующие результаты:

при решении задачи по критерию времени («задача о р-медиане») оптимальное размещение ЦХИ (р = 5) суммарное время обслуживания запросов в сети по сравнению с исходным вариантом снижается примерно на 30%;

оптимальное решение задачи по критерию максимальной интенсивности запросов («задача о ^-центрах») для заданного максимального времени задержки передачи одного сообщения в сети Ттах = 5секунд соответствует минимальному значению р = 6. Уменьшение Ттах на 2 секунды приводит к увеличению числа р примерно в 2 раза, что пропорционально увеличивает стоимость обслуживании информационных запросов.

2. Сформулированы задачи и разработаны математические модели оптимизации числа и мест размещения ЦХИ в узлах компьютерной сети по различным критериям. Эти критерии, в зависимости от предъявляемых требований к качеству ИВП на различных уровнях иерархической структуры АСУ предприятия, могут быть сформулированы по-разному. Приняты следующие критерии:

критерий минимума суммарного среднего времени на обслуживание информационных запросов в сети (критерий оперативности) - целесообразно применять на производственном уровне (контур «офисы филиалов - подразделения - отделы»), объекты которого, как правило, функционируют в режиме реального времени;

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

критерий минимума стоимости обслуживания информационных запросов при заданных ограничениях на качество ИВП (экономический критерий) - можно применять на любых уровнях в условиях затруднённого финансирования;

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

3. Предложен подход к решению задачи выбора ЦХИ по критерию максимальной загрузки («задача о р-центрах»), основанный на сведении исходной задачи к задаче о покрытии, что позволяет за счёт применения теории двойственности в алгоритме решения задачи о покрытии повысить быстродействие метода ветвей и границ и, в конечном счёте, обеспечивает возможность применения программы решения этой задачи в реальном масштабе времени.

4. Разработан метод решения задачи выбора ЦХИ по критерию оперативности с учётом дополнительных ограничений («задача о р-медиане»), основанный на идеях метода ветвей и границ, с дихотомическим поиском решения; данный метод позволяет находить точное решение, как для симметричной, так и несимметричной матрицы исходных данных. Для решения задачи по экономическому критерию предложен пошаговый алгоритм, на каждом шаге которого последовательно решается «задача о /»-медиане», что позволяет найти минимальное число ЦХИ, которое обеспечивает выполнение ограничений на заданные показатели качества ИВП; это число и соответствует минимальным затратам на обслуживание информационных запросов.

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

6. На языке вРБЯ/РС разработана имитационная модель для оценки параметров процесса обслуживания информационных запросов в распределённой компьютерной сети, позволяющая определить исходные данные для решения задачи размещения ЦХИ, а также оценить влияние различных факторов на показатели качества ИВП.

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

18

Публикации по теме диссертации

1. Изотов, Д.В. Применение задачи о р-центрах для синтеза физической структуры компьютерной сети / П.В. Комогорцев, Д.В. Изотов // Материалы 6-й международной конференции «Проблемы управления безопасностью сложных систем».- М: ИПУ РАН. - 1999. - С. 203-205.

2. Изотов, Д.В. Общая характеристика задач оптимального синтеза компьютерной сети АСУ / Д.В. Изотов, А.Г. Ширяев // Внутривузовский научно-технический сборник № 19. - Тула: ТАИИ. - 2002. - С. 124-127.

3. Изотов, Д.В. Математическая модель задачи выбора центров обработки информации в компьютерной сети АСУ / Д.В. Изотов // Внутривузовский научно-технический сборник № 19. - Тула: ТАИИ. - 2002. - С. 120 - 123.

4. Изотов, Д.В. Имитационное моделирование информационных систем / A.A. Павлов, Д.В. Изотов // Электронный обучающий курс. - Тула: ТФ ОРАГС. - 2006. - 120 с.

5. Изотов, Д.В. Оценка надежности программного обеспечения информационных систем / Д.В. Изотов // Материалы III Международной научно-методической конференции «Современные проблемы преподавания матема-

. тики и информатики». - Волгоград: «Перемена». - 2006. - С. 552-555.

6. Изотов, Д.В. Определение весовых коэффициентов при оценке надежности программного обеспечения / Д.В. Изотов // Внутривузовский научно-технический сборник № 22. - Тула: ТАИИ. - 2008. - С. 252-259.

7. Изотов, Д.В. Алгоритм решения задачи выбора числа и мест размещения центров хранения и обработки информации / В.Н. Изотов, Д.В. Изотов // Материалы международной НПК «Интеллектуальный потенциал региона и управление знаниями». - М.-Тула: Изд-во ТулГУ. - 2011. - С. 96-98. - ISBN 978-5-7679-1865-2.

8. Изотов, Д.В.. Задача выбора центров хранения и обработки информации в компьютерной сети предприятия / О.В. Есиков, Д.В.Изотов // Материалы международной НПК «Интеллектуальный потенциал региона и управление знаниями». - М. - Тула: Изд-во ТулГУ. - 2011. - С. 374-377. -ISBN 978-5-7679-1865-2.

9. Изотов, Д.В. Имитационная модель компьютерной сети предприятия для определения параметров её функционирования / Д.В. Изотов // Материалы международной НПК «Интеллектуальный потенциал региона и управление знаниями». - М. - Тула: Изд-во ТулГУ. - 2011. - С. 378-381. - ISBN 9785-7679-1865-2.

10. Изотов, Д.В. Анализ задач выбора центров хранения и обработки информации в корпоративной сети АСУ современного мегавуза / В.Н. Изотов, Д.В. Изотов И Материалы 5-й международной НМК «Методы и средства подготовки конкурентоспособных специалистов: теория и практика». - Омск: НОУ ВПО «ЕврИЭМИ». - 2011. - С. 105-108.

11. Изотов, Д.В. Задача оптимального распределения информации в корпоративной вычислительной сети вуза по экономическому критерию / О.В. Есиков, Д.В. Изотов // Материалы 5-й международной НМК «Методы и средства подготовки конкурентоспособных специалистов: теория и практика». - Омск: НОУ ВПО «ЕврИЭМИ». - 2011. - С. 102-105.

19

12. Изотов, Д.В. Алгоритм решения задачи оптимального распределения информации в корпоративной вычислительной сети современного мега-вуза / Д.В. Изотов И Материалы 5-й международной НМК «Методы и средства подготовки конкурентоспособных специалистов: теория и практика». -Омск: НОУ ВЛО «ЕврИЭМИ». - 20 П. - С. 108-111.

13. Программа размещения центров хранения и обработки информации: Свидетельство о регистрации программы ЭВМ: ООО «ТехЛэнд-Автоматизация», г. Москва, г. Зеленоград / заявитель Изотов Д.В. - Свидетельство № 001459; зарегистрировано 17.03.2011.

14. Изотов, Д.В. Построение /Г-инфраструктуры предприятия на основе центров хранения и обработки информации с использованием технологии виртуализации / Д.В. Изотов // Журнал «Естественные и технические науки», № 2 (52). - М: Изд-во «Спутник +». - 2011. - С. 392-397. - ISSN 1684-2626.

15. Изотов, Д.В. Задача выбора числа и мест размещения центров хранения и обработки информации в компьютерной сети / Е.В. Ларкин, Д.В. Изотов // Журнал «Естественные и технические науки», № 3 (53). — М: «Спутник+».-2011.-С. 287-291. - ISSN 1684-2626.

Изд. лиц. ЛР № 020300 от 12.02.97. Подписано в печать 20.05.2011. Формат бумаги 60x84 1/16. Бумага офсетная. Усл. печ. л. 1, 2. Уч.-изд. л. 3.0 Тираж 100 экз. Заказ О £ ^

Тульский государственный университет. 300012, г. Тула, просп. Ленина, 92.

Отпечатано в Издательстве ТулГУ 300012, г. Тула, просп. Ленина, 95

Введение.

1 Анализ АСУ современного предприятия и факторов, влияющих на эффективность информационных процессов.

1.1 Пути совершенствования АСУ предприятия.

1.2 Анализ информационных процессов в АСУ.

1.3 Состав и отличительные особенности АСУ современного предприятия.

1.4 Анализ моделей оптимального размещения ЦХИ в распределённой компьютерной сети.

1.4.1 Проблемы оптимизации компьютерной сети.

1.4.2 Анализ подходов к оптимизации компьютерных сетей.

1.4.3 Анализ моделей решения задачи о размещении ЦХИ.

1.5 Методика оптимизации ИВП в современной АСУ.

Выводы.

2 Математическое обеспечение задач оптимизации ИВП в распределенной компьютерной сети АСУ предприятия.

2.1 Выбор и обоснование показателей эффективности функционирования компьютерной сети современной АСУ.

2.2 Математические модели задач выбора числа и мест размещения ЦХИ в распределенной компьютерной сети.

2.2.1 Постановка задачи по критерию минимума суммарного среднего времени передачи данных по сети.

2.2.2 Постановка задачи по критерию минимума стоимости.

2.2.3 Постановка задачи выбора по критерию максимума интенсивности поступления запросов.

2.3 Разработка алгоритмов решения задач выбора числа и мест размещения ЦХИ в компьютерной сети.

2.3.1 Разработка алгоритма решения задачи по критерию времени передачи данных по сети.

2.3.2 Разработка алгоритма решения по критерию стоимости.

2.3.3 Разработка алгоритма решения задачи по критерию максимума интенсивности поступления запросов.

Выводы.

3 Исследование разработанных моделей и алгоритмов оптимизации размещения ЦХИ в КС современной АСУ.

3.1 Имитационная модель компьютерной сети для определения параметров информационного процесса.

3.1.1 Классификация и оценка методов анализа характеристик компьютерных сетей.

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

3.2 Разработка программы и экспериментальное исследование эффективности алгоритмов решения «задачи о /^-центрах».

3.2.1 Тестовый пример.

3.2.2 Характеристика программы «Центр».

3.2.3 Исследование эффективности реализованных алгоритмов.

3.3 Разработка программы и экспериментальное исследование эффективности алгоритма решения «задачи о р-медиане».

3.4 Решение задачи оптимального размещению ЦХИ в АСУ современного предприятия.

Выводы.

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

Эффективность применения АСУ на прямую зависит от существующей ИТ-инфраструктуры информационной системы.

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

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

Основными требованиями к ИТ-инфраструктуре в настоящее время является надежность, производительность и способность адаптироваться к меняющимся задачам. Перечисленным требованиям в наибольшей степени удовлетворяют высокопроизводительные центры хранения и обработки информации (ЦХИ), обеспечивающие непрерывную работу информационных систем, а также имеющие относительно невысокую стоимость хранения информации. Создание ЦХИ оптимизирует также затраты на эксплуатацию занимаемых вычислительным оборудованием помещений и на обслуживающий персонал.

Таким образом, применение ЦХИ на предприятии является эффективным решением построения ИТ-инфраструктуры. В зависимости от задач предприятия и сложности его ИТ-инфраструктуры возможно построение ЦХИ"требуемых размеров и надежности. Всё это подчёркивает актуальность разработки математического и программного обеспечения задачи выбора числа и мест размещения ЦХИ, особенно, в случае использования распределённых компьютерных сетей.

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

Известные математические постановки задач о размещении представляют собой частные случаи классических задач теории графов - «задачи о р-медиане» и «задачи о ^-центрах» [1-7], а также «задач о назначении» [8-9], для решения которых, как правило, используются алгоритмы, основанные на идеях метода ветвей и границ. Этим задачам посвящён ряд работ таких авторов, как: S.L. Hakimi, Н. Noltermeier, J. Spoerhose, Н. Кристофидес, В.Л. Береснев, Э.Х. Гимади, В.Т. Дементьев, Е.В. Алексеева, Ю.А. Кочетов, Г.Г. Забудский и другие.

В постановке применительно к компьютерным сетям в целях оптимизации информационно-вычислительного процесса (ИВП) наиболее известные подходы к решению подобных задач рассмотрены в работах В.А. Балыберди-на, О.Г. Алексеева, В.Д. Киселева, О.В. Есикова, И.В. Сергиенко, A.A. Корбу-та, Ю.Ю. Финкелынтейна, Г.Ф. Янбых, Б.А. Столярова и других авторов [1017].

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

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

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

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

Актуальность темы диссертационной работы определяется следующими факторами: необходимость дальнейшего повышения эффективности ИВП в

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

Исходя из этого, научной задачей, решаемой в диссертационной работе, является разработка математических моделей и алгоритмов оптимизации ИВП путём оптимального размещения ЦХИ в узлах распределённой компьютерной сети.

Объектом исследования являются распределённые компьютерные сети АСУ предприятия.

Предметом исследования являются математические модели и алгоритмы размещения ЦХИ в компьютерной сети АСУ предприятия.

Целью диссертационной работы является повышение качества ИВП в современной АСУ предприятия за счёт разработки математического и программного обеспечения задач оптимального размещения ЦХИ на основе анализа информационного взаимодействия между объектами системы и требований к показателям качества ИВП, а также применения новых информационных технологий с учётом перспективных направлений совершенствования современных АСУ.

Поставленная цель достигается путем решения следующего комплекса взаимосвязанных задач: анализ факторов, влияющих на эффективность информационных процессов в современной АСУ предприятия; разработка методики оптимизации ИВП в распределённой КС; разработка математических моделей, методов и алгоритмов оптимального размещения ЦХИ в распределенной КС; разработка имитационной модели для оценки параметров информационного процесса в компьютерной сети и программного средства для экспериментального исследования разработанных методов и алгоритмов.

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

В первой главе произведён анализ научных работ, посвящённых проблемам повышения эффективности ИБП в распределённых компьютерных сетях и вопросам математического и программного обеспечения решаемых с этой целью задач. Рассмотрены факторы, влияющие на эффективность ИБП современной АСУ предприятия, сформулированы требования, предъявляемые к АСУ, основные направления её совершенствования и связанные с этим задачи. Разработана методика оптимизации ИБП. Показано, что эффективность информационных процессов в распределенной АСУ предприятия, построенной на базе компьютерной сети и содержащей значительные объемы информации, существенно зависит от количества и размещения ЦХИ по узлам компьютерной сети, что доказывает необходимость решения данной задачи, в том числе, в реальном масштабе времени.

Во второй главе, исходя из требований оперативности и надежности представления выходной информации, произведён выбор и обоснование показателей эффективности информационных процессов в современных АСУ предприятия, разработаны математические постановки задач выбора числа и мест размещения ЦХИ по узлам сети. Сформулированные задачи сведены к задачам целочисленного программирования. Предложенные методы и алгоритмы решения этих задач основаны на идеях метода ветвей и границ.

Третья глава посвящена исследованию разработанных математических моделей оптимизации ЦХИ в КС современных АСУ предприятия, а также экспериментальной оценке алгоритмов и программ оптимизации, проверке работоспособности разработанного математического аппарата с целью выработки рекомендаций по его применению. Обоснованы критерии оценки эффективности предложенных методов и алгоритмов. На основе анализа процесса информационного взаимодействия в компьютерной сети разработана имитационная модель на языке GPSS/PC, применяемая при подготовке исходных данных для решения задачи оптимального выбора ЦХИ в узлах КС АСУ предприятия. Приведены результаты вычислительных экспериментов. Выработаны рекомендации по размещению ЦХИ в компьютерной сети АСУ предприятия.

На защиту вынесены следующие основные положения:

1. Методика формирования ИВП, основанная на оптимизации размещения ЦХИ в распределённой компьютерной сети.

2. Математические модели оптимизации числа и мест размещения ЦХИ в компьютерной сети, основанные на классических задачах из теории графов о /7-центрах и р-медиане с учётом введения дополнительных ограничений для обеспечения заданных требований по оперативности и надежности представления информации.

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

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

Достоверность научных результатов подтверждена корректным применением используемого математического аппарата, а также согласованностью результатов теоретического расчёта с данными, полученными в ходе экспериментов с применением имитационной модели, а также в ходе решения практических задач выбора ЦХИ. Работоспособность предложенных алгоритмов была подтверждена сравнением результатов «ручного» расчёта по контрольным исходным данным с результатами, полученными с помощью разработанного программного средства.

Практическая значимость работы заключается« в том, что предложенные методика, модели и алгоритмы могут быть использованы для оптимизации ИВП как при совершенствовании существующих, так и при разработке новых АСУ предприятия. Практическая ценность результатов работы подтверждается их применением в ходе обоснования ЦХИ для конкретного предприятия. Алгоритмы доведены до рабочих программ и в силу своей общности позволяют решать широкий круг научно-технических задач.

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

Ряд теоретических результатов внедрены в учебный процессе ГОУ ВПО «Тульский государственный университет», а также Тульского филиала ОРАГС.

Апробация работы. Материалы диссертации докладывались, обсуждались и одобрены на межрегиональных и внутривузовских научных и научно-практических конференциях (Тула - 2005, 2007, 2011 г.г.), а также на международных конференциях (Москва - 1999 г., Волгоград - 2006 г., Тула - 2011 г., Омск-2011 г.).

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

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

Структура и объём работы. Диссертационная работа состоит из введения, трёх глав, заключения, изложенных на 160 страницах машинописного текста, содержит 27 рисунков, 28 таблиц, список используемой литературы из 78 наименований, а также 4 приложения.

Основные результаты работы заключаются в следующем:

Г. Разработана методика оптимизации' ИВП* в? распределенной АСУ предприятия.

2. Сформулированы задачи и разработаны« математические модели оптимизации числа и мест размещения 1ЦХИ в узлах компьютерной сети по различным критериям: по критерию минимума суммарного среднего времени поиска и передачи информации по каналам связи, по критерию максимума интенсивности поступления запросов на информационное обслуживание, а также по критерию минимума стоимости обслуживания информационных запросов. В математические модели включены дополнительные ограничения для обеспечения заданных требований по надежности представления информации.

3. Предложен алгоритм решения «задачи о р-центрах», основанный на сведении исходной задачи к задаче о покрытии, что позволяет за счёт особенностей двойственного решения повысить быстродействие метода ветвей и границ. Для сведения к задаче о покрытии предварительно решается задача нахождения кратчайших путей между всеми вершинами исходного графа. Предложен более эффективный подход к её решению, который экономит почти 50 % времени по сравнению с ЛЧсратным применением алгоритма Дейкст-ры.

4. Разработан эффективный алгоритм для «задачи о /?-медиане»-с учётом дополнительных ограничений, основанный на идеях метода ветвей и границ, с дихотомическим поиском решения; данный алгоритм позволяет находить точное решение, как для симметричной, так и несимметричной матрицы исходных данных. Эксперимент показал, что время решения-задачи резко возрастает с увеличением значения р; но на практике при решении задач оптимизации размещения ЦХИ значение р не будет превышать 10% - 30% от размерности матрицы исходных данных, что позволит успешно применять данный алгоритм.

5. На языке GPSS/PC разработана имитационная модели для оценки параметров процесса1 обслуживания5 информационных запросов в распределённой компьютерной сети, позволяющая определить, исходные1 данные для решения« задачи размещения ЦХИ. Применение специализированного языка имитационного моделирования GPSS/PC и модульного принципа разработки позволяют уменьшить трудоёмкость создания и исследования модели в 4-5 раз.

6. На языке PASCAL разработана программа, реализующая метод ветвей и границ с дихотомическим поиском для решения «задачи о р-медиане», а также программа для решения «задачи о ^-центрах» методом сведения её-к задаче о покрытии. Разработанные программные средства для автоматизации-" экспериментальной проверки предложенных методик и алгоритмов решения задачи позволяют управлять процессом исследования, проводить сравнительную оценку алгоритмов по выбранной программе и значительно сократить затраты на проведение исследований.

Экспериментальная проверка разработанных математических моделей, методик и алгоритмов показала их работоспособность и целесообразность включения в комплекс специального математического и программного обеспечения АСУ современного предприятия.

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе решена научная задача разработки математических моделей и алгоритмов оптимизации информационно-вычислительного процесса в распределённых АСУ современного предприятия за счёт оптимального размещения центров хранения; и обработки . информации в узлах компьютерной сети.

В соответствии с поставленной целью повышения качества ИВП с учётом современных информационных технологий разработана методика оптимального размещения ЦХИ. Методика базируется на комплексе математических моделей, позволяющих формализовать наиболее трудоёмкие процессы оптимизации ИВП в современной АСУ

Разработанные модели, алгоритмы и программы рекомендуются для включения в состав специального математического и программного обеспечения АСУ.

Модели и алгоритмы могут быть использованы для оптимизации ИВП как при совершенствовании существующих, так и при разработке новых АСУ предприятием. Практическая ценность результатов работы подтверждается их применением в ходе обоснования ЦХИ в АСУ конкретного предприятия. Алгоритмы доведены до рабочих программ и в силу своей общности позволяют решать широкий круг научно-технических задач.

В ходе работы были сделаны следующие основополагающие выводы:.

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

2. Основными требованиями к ИТ- инфраструктуре предприятия' в настоящее время-являются высокая надежность, производительность и способность адаптироваться«к. меняющимся задачам. Перечисленным требованиям в наибольшей степени удовлетворяют высокопроизводительные центры хранения' и обработки информации, обеспечивающие непрерывную работу информационных систем, а также имеющие относительно невысокую стоимость хранения информации. Создание ЦХИ оптимизирует также затраты на эксплуатацию занимаемых вычислительным оборудованием помещений и на обслуживающий персонал.

3. Обобщенную физическую структуру современной АСУ можно представить как совокупность объектов системы управления, каждый из которых является узлом компьютерной сети, связанных между собой каналами передачи данных. При этом, согласно двухранговой модели «клиент - сервер» часть узлов сети оборудуются как ЦХИ, обладающие мощными аппаратными и программными ресурсами для обработки и хранения информации. Остальные узлы оборудуются как АРМ ДЛ, предназначенные для обеспечения доступа соответствующих должностных лиц к ресурсам сети.

4. Сложность решения задач оптимизации ИВП обусловлена тем, что организационно структура АСУ современного предприятия соответствует территориально разнесённой и многоуровневой системе управления, а процесс управления характеризуется большим объёмом и высокой интенсивностью информационного потока. Кроме того, особенности разработки математического и программного обеспечения задач оптимизации размещения ЦХИ, которые обусловлены условиями их применения в реальном масштабе времени, порождают проблему снижения вычислительной сложности и повышения эффективности методов решения этих задач.

5. Существенные упрощения-в решении задач оптимизации АСУ предприятия можно обеспечить представлением системы управления в виде совокупности вложенных контуров. Применительно к распределенным компьютерным сетям, корпоративная сеть предприятия представляется в виде совокупности вложенных сетей. Данный подход позволяет оптимизировать сложные системы по принципу «сверху - вниз» с позиции назначения и наилучшего решения* основной целевой задачи всей системы. Это обеспечивает возможность рационального распределения информационных ресурсов по-мере декомпозиции системы.

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

7. В зависимости от конкретных требований и условий на каждом уровне управления предлагаются следующие подходы к решению задачи выбора числа и мест размещения центров хранения информации и следующие показатели эффективности их функционирования: для объектов производственного уровня, функционирующих в режиме реального времени, наиболее существенными являются требования по оперативности, поэтому в качестве показателя эффективности при решении данной задачи предлагается среднее суммарное время передачи данных по каналам связи; для этого основные функции управления в системе разбиваются на ряд функциональных задач, и осуществляется поиск такого варианта их распределения для решения в том или ином узле сети, чтобы выбранный показатель принимал бы минимальное значение, при этом надёжностные характеристики учитываются' в.качестве ограничений; для систем-управления с-различными, режимами функционирования и-большим и разнообразным- перечнем задач управления (административный уровень) представляется целесообразным следующий подход: ЦХИ размещаются в тех узлах сети, где наиболее часто возникает потребность в информационном обслуживании, при этом, для учета требований по оперативности, ЦХИ размещаются таким образом, чтобы временная задержка данных в сети не превышала бы заданного значения. В случае если на предприятии создаётся крупный. ЦХИ, содержащий высокопроизводительную СОД и СХД большой ёмкости, то он, как правило, устанавливается в головном офисе, а необходимость установки ЦХИ в филиалах определяется по результатам решения указанной задачи; в условиях затрудненного финансирования внедрения и эксплуатации проектируемой системы на всех уровнях, в качестве показателя эффективности предлагается выбрать, суммарные затраты в системе, приходящиеся на обслуживание одного информационного запроса, а надёжностные и временные характеристики учитывать в роли ограничений.

8. Для построения математических моделей задачи выбора числа и мест размещения ЦХИ по узлам сети предлагается использовать задачи, связанные с нахождением вершин графа с некоторыми заданными свойствами. Это задачи известные как «задача о /»-медиане» и «задача о р-центре». При этомг задачи по первому и третьему из вышеперечисленных критериев могут быть формализованы с использованием обобщенной «задачи о /»-медиане», задача по второму критерию - с применением «задачи о /»-центрах». Данные задачи можно формулировать в терминах целочисленного программирования.

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

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

2. Алексеева Е.В., Орлов А.В. Генетический алгоритм для* конкурентной задачи о р-медиане // Труды-14 Байкальскою международной, школы-семинара "Методы оптимизации и их приложения"; Том Г. Северо-байкальск: 2008. - с. 570-585.

3. Забудский Г.Г., Филимонов Д.В. Решение дискретной минимаксной задачи размещения на сети // Известите вузов. Математика, № 5 Омск: 2004., с. 33-36.

4. Кочетов ТО. А., Кононов А.В., Плясунов А.В . Конкурентные модели размещения производства // Журнал вычислительной математики и математической физики. Т. 49, № 6. 2009. - с. 1-17.

5. Hakimi S.L. On locating new facilities in a competitive environment. European J. Oper. Res. 1983. V. 12, P. 29-35.

6. Noltermeier H., Spoerhose J., Wirth H.C. Muliple voting location and single voting location on trees. European J. Oper. Res. 2007. V. 181. P. 654-667.

7. Spoerhose J., Wirth H.C. (r,p)-Centroid problems on paths and trees. Tech. Report 441, Inst. Сотр. Science, University of Wtirzburg, 2008.

8. Береснев B.JI. , Гимади Э.Х., Дементьев B.T. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. -335с.

9. Гимади Э.Х. Обоснование априорных оценок качества приближенного решения задачи стандартизации // Управляемые системы. Новосибирск, 1987. - Вып: 27. - с. 12-27.

10. Балыбердин B.A. Оценка и оптимизация характеристик систем обработки данных. М: Радио и связь, 1987.- 176 с.

11. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М: Наука, 1987. -279 с.

12. Киселев В.Д., Денисов Ю.И., Мягков, В.Ю. Щербина A.M. Модели и методы решения задач проектирования и испытаний АСУ. М.: Вооружение. Политика. Конверсия,' 1997. - 249 с.

13. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ« комбинаторных задач оптимизации. Киев: Наукова думка; 1981.-288 с.

14. Сергиенко И. В. Математические модели и методы! решения задач дискретной оптимизации. Киев: Наукова думка, 1988. - 384 с.

15. Финкелыптейн Ю.Ю., Корбут A.A. Дискретное программирование. М.: Наука, 1969. -368 с.

16. Корбут A.A., Сигал И.Х., Финкелыптейн Ю.Ю. Метод ветвей и границ (обзор теории, алгоритмов, программ и приложений) // Math. Operations-forsh Statist. Ser. Optimization. 1977. b. 8. № 2. с. 253-280.

17. Янбых Г.Ф., Столяров Б. А. Оптимизация информационно-вычислительных систем. М: Радио и связь, 1991. - 232 с.

18. Глушков В.М. Сети ЭВМ. М.: Связь, 1977. - 280 с.

19. Флинт Д. Локальные сети ЭВМ: архитектура, принципы построения, реализация. М: Финансы и статистика, 1986. - 359 с.

20. Балыбердин В.А. Методы анализа мультипрограммных систем, М: Радио и связь, 1982.- 152 с.

21. Попов Д.В., Галямов А.Ф. Анализ информационной и ИТ-инфраструктур организации // Программные продукты и системы. 2009, № 1.

22. Шляпцев O.A. Концепция построения и развития ИТ-инфраструктуры предприятия // Журнал школы IT-менеджмента «Системы управления бизнес-процессами». М: АНХ при Правительстве РФ, 2010.

23. Михайлов А. Консолидация ИТ-ресурсов холдинга // Москва, журнал СЮ №5, 2003. Электронный документ. URL: http://www.cio-world.ru/offline/2003/15/26749/index.html.

24. Евламова Н., Пахомов С. Виртуальные машины 2007 // журнал «Компьютер пресс», № 9, 2007.

25. Шаров В. Технология виртуализации подход IBM // журнал «BYTE Россия», № 5(93), 2006. - Электронный документ. URL: http://www.bytemag.ru/articles/detail.php?ID=8656.

26. Пояснительная записка к техническому проекту «Основной и резервные центры обработки данных первой очереди». Код проекта «Поля-рис»// Х5 Retail Group N.V. М: 2009. - 46 с.

27. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. -Киев: Техника, 1986.- 168 с.

28. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы: Пер. с англ. М: Мир, 1982.- 563 с.

29. Клейнрок JI. Вычислительные системы с очередями: Пер. с англ. -М: Мир, 1979.- 600 с.

30. Шварц М. Сети ЭВМ: анализ и проектирование: Пер. с англ. М: Радио и связь, 1981.- 336 с.

31. Янбых Г.Ф., Эттингер Б.Я. Методы анализа и синтеза сетей ЭВМ. -Л.: Энергия, 1980.- 96 с.

32. Data Processing-open Systems Interconnection-Basic Reference Model. ISO/DP 7498, August 1981. - 105 p.

33. Басакер P., Саати Т. Конечные графы и сети. М: Наука, 1974.368 с.

34. Исследование операций / В 2-х томах. Пер. с англ. // Под редакцией Моудера Дж., Элмаграби. М: Мир, 1981. - 677 с.

35. Zabudsky G.G., Filimonov D.V. Solving discrete minimax location problem on networks II International Conference on Operations Research. Klagenfurt, 2002. - P. 153.

36. Панюков A.B., Пельцвергер Б,В. Оптимальное размещение дерева в конечном множестве // Журнал вычислительной математики и математической физики. Т. 28: 1988;- с. 618-620.

37. Майника Э. Алгоритмы оптимизации на сетях и графах / Пер. с англ. М: Мир, 1981.-323 с.

38. Агеев A.A. Графы, матрицы и простейшая задача размещения // Управляемые системы. Вып. 29. Новосибирск, 1989. - с. 3-10.

39. Якубайтис Э.А. Архитектура вычислительных сетей. М: Статистика, 1980. - 279 с.

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

41. Якубайтис Э.А. Открытые информационные сети. М: Радио и связь, 1991.-208 с.

42. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. М: Радио и связь, 1991. - 248 с.

43. Костогрызов А.И., Петухов A.B., Щербина A.M. Основы оценки, обеспечения и повышения качества выходной информации в АСУ организационного типа. М.: Вооружение. Политика. Конверсия, 1994. - 278 с.

44. Изотов Д.В., Ширяев А.Г. Общая характеристика задач оптимального синтеза компьютерной сети АСУ // Внутривузовский научно-технический сборник № 19. Тула: ТАИИ, 2002. - с. 124 - 127.

45. Изотов Д.В. Математическая модель задачи выбора центров обработки информации в компьютерной сети АСУ // Внутривузовский научно-технический сборник № 19. Тула: ТАИИ, 2002. - с. 120- 123.

46. Изотов Д.В., Есиков О.В. Задача выбора центров хранения и обработки информации в компьютерной сети предприятия // Материалы международной НПК «Интеллектуальный потенциал региона и управление знаниями». М.-Тула: Изд-во ТулГУ, 2011. - с. 374-377.

47. Мамиконов А.Г., Кульба В.В., Косяченко С.А., Ужастов И.А. Оптимизация структур распределенных баз данных в АСУ. М: Наука. Гл. ред. физ.-мат. лит., 1990.- 240 с.

48. Series X Recomendations. The orenge book, VIII. 2 International Telecommunications Union. Geneva, 1977.

49. Изотов Д.В. Имитационная модель компьютерной сети предприятия для определения параметров её функционирования // Материалы международной НПК «Интеллектуальный потенциал региона и управление знаниями». М. - Тула: Изд-во ТулГУ, 2011. - с. 378-381

50. Фрэнк Г., Фриш И. Сети, связь и потоки: Пер. с англ. М: Связь, 1978.-448 с.

51. Изотов Д.В., Ларкин Е.В. Задача выбора числа и мест размещения центров хранения и обработки информации в компьютерной сети // Журнал «Естественные и технические науки», № 3 (53). М: Изд-во «Спутник +», 2011. - с. 394-397. - ISSN 1684-2626.

52. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М: Наука, 1976. — 264 с.

53. Geoffrion A.M., Mastern R.E. Integer programming algorithms: A framework and state-of-the-art survey. // Manag. Sci. 1972. V. 18. № 9.

54. Jarvinen P., Rajala J., Sinervo H. A branch-and-bound algorithm for seeking the p-median. // Opérât. Res. 1972. Y. 20. № 1. P. 173 -178.

55. Galvao R. D. A dual-bounded algorithm for the p-median problem // Operat. Res. 1980. V. 28. № 5. P: 1112 - 1121.

56. Алексеев О.Г., Ботвин Г.А., Буслаев В.А. Оптимизация параметрического ряда длин формализованных сообщений в системах управления // Стандартизация военной техники, 1989, № 4.

57. Шастова Г.А., Коекин А.И. Выбор и оптимизация структуры информационных систем. М: Энергия, 1972. - 256 с.

58. Изотов Д.В., Комогорцев П.В. Применение теории графов для решения задачи размещения центров обработки информации в сети ЭВМ // Сборник тезисов НТК, 3 ЦНИИ, 1997. с. 181-183.

59. Алексеев О. Г., Григорьев В. Ф. Некоторые алгоритмы решения задачи о покрытии и их экспериментальная проверка на ЭВМ // ЖВМ и МФ. -1984. Т.24, №10. - с. 1565-1570.

60. Зуев Ю. А. Задачи о покрытии: локальный подход и метод типа ветвей и границ//ЖВМ и МФ. -1979. Т. 19, №6.-с. 1566-1576.

61. Современное состояние теории исследования операций / Под ред. H. Н. Моисеева. М: Наука, 1979. - 303 с.

62. Голыптейн Е. Г. Теория двойственности в математическом программировании и её приложения. М: Наука, 1971. - 352 с.

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

64. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М: Радио и связь, 1988. - 206 с.

65. Trivedi К.S. Probability and Statistic with Realiability, Queuing and Computer Applications. En. CI., Pr. Hall, 1992. - 624p.

66. Computer Performance Modeling Handbook. Ed by S.S. Lavenberg. -N.J., Academic Press, 1988. 398 p.

67. Шеннон Р. Имитационное моделирование систем искусство и наука. - М: Мир, 1978. - 418 с.

68. Шрайбер Т.Дж. Моделирование на GPSS. М: Машиностроение, 1980. - 592 с.

69. Голованов О.В., Дуванов С.Г., Смирнов В.Н. Моделирование сложных дискретных систем на ЭВМ третьего поколения. М: Энергия, 1978. -160 с.

70. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. М: Мир, 1985.- 512 с.

71. Киселев В.Д., Бабаев A.A., Олейник В.А. Методика экспериментальной оценки эффективности алгоритмов оптимизации военно-технических решений // Тематический сборник № 16, часть 2. Л.: ВАА им. Калинина, 1988.

72. Вероятностные методы в вычислительной технике. ЛТод ред. Лебедева А.Н. и Чернявского Е.А. М: Высш. школа, 1986.- 312 с.