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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

по специальности 05.13.01 - Системный анализ,

управление и обработка информации

Автореферат диссертации на соискание ученой степени

кандидата физико-математических наук

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

Минск, 2010

Работа выполнена в Учреждении образования «Гродненский государственный университет имени Янки Купалы»

Научный руководитель -Маталыцкий Михаил Алексеевич,

доктор физико-математических наук, профессор, заведующий кафедрой стохастического анализа и эконометрического моделирования Учреждения образования «Гродненский государственный университет имени Янки Купалы».

Официальные оппоненты:Апанасович Владимир Владимирович,

доктор физико-математических наук, профессор,

заведующий кафедрой системного анализа Белорусского государственного университета;

Малинковский Юрий Владимирович,

доктор физико-математических наук, профессор,

заведующий кафедрой экономической кибернетики и теории вероятностей Учреждения образования «Гомельский государственный университет имени Франциска Скорины».

Оппонирующая организация -Государственное научное учреждение

«Институт математики Национальной

академии наук Беларуси».

Защита состоится «17» _сентября_ 2010 г. в _10_ часов на заседании совета по защите диссертаций Д 02.01.14 при Белорусском государственном университете по адресу: 220030, Республика Беларусь, г. Минск, ул. Ленинградская, 8 (корпус юридического факультета), ауд. 407.

Телефон ученого секретаря совета: 209-55-58.

С диссертацией можно ознакомиться в Фундаментальной библиотеке Белорусского государственного университета.

Автореферат разослан «16» _июня__ 2010 г.

КРАТКОЕ ВВЕДЕНИЕ

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

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

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

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

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

Связь работы с крупными научными программами и темами

Диссертация выполнялась в соответствии с утвержденным научным планом работы Учреждения образования «Гродненский государственный университет имени Янки Купалы» на 2006-2010 гг. и планом развития научной, научно-технической и инновационной деятельности на период 2006-2010 гг. (приоритетное направление №5: фундаментальные научные исследования - разработка математических моделей и их применение к анализу систем и процессов в природе и обществе, развитие технических основ информатики и информационных технологий).

Тема диссертации соответствует п.6.1 «Математические модели и их применение к анализу систем и процессов в природе и обществе» и п. 6.3 «Развитие теоретико-методологических основ информатики и информационных технологий» Перечня приоритетных направлений фундаментальных и прикладных научных исследований РБ на 2006-2010 гг., утвержденного Постановлением Совета Министров РБ 17.05.2005 №512.

Полученные в работе результаты использовались при выполнении следующих научно-исследовательских работ:

- г/б НИР «Разработка вероятностных методов исследования моделей информационно-компьютерных сетей и производственных процессов», № госрегистрации 20062287, выполняемой в 2006-2010 гг. по государственной комплексной программе научных исследований «Информационные технологии», утвержденной Советом Министров и Президиумом НАН РБ;

- г/б НИР «Исследование сетей массового обслуживания и их применение в качестве моделей различных систем и процессов», № госрегистрации 20064102, выполняемой в 2006-2010 гг. в рамках государственной программы фундаментальных исследований «Математические модели», утвержденной Советом Министров и Президиумом НАН РБ;

Цель и задачи исследования

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

Для достижения поставленной цели решаются следующие задачи:

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

- разработать методику нахождения ожидаемых доходов в системах НМ-сетей с однотипными заявками произвольной структуры в случаях, когда доходы от переходов между состояниями сети зависят от состояний и времени или являются случайными величинами (СВ) с заданными моментами первых двух порядков;

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

- осуществить постановку и решить задачи оптимизации моделей ИКС, процессов производства изделий (ППИ) и НМ-сетей в переходном режиме с использованием предложенных стоимостных критериев и вышеуказанных методов;

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

Объектом исследования являются системы и сети обработки информации, ППИ, предметом исследования - основные вероятностно-временные характеристики их моделей - сетей МО в переходном и стационарном режимах, новые методы и методики нахождения этих характеристик.

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

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

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

Методика основана на: получении и решении систем РДУ для ожидаемых доходов в системах замкнутых сетей и применении разработанного алгоритма нахождения доходов систем открытых сетей, основанного на использовании доказанных соотношений для их многомерных z-преобразований - в случае детерминированных доходов; использовании найденных приближенных и точных выражений для средних значений случайных доходов.

3. Выражения для вероятностных характеристик сетей МО с разнотипными заявками многих классов, которые применяются в качестве моделей информационных систем межбанковских расчетов (ИС МБР): мультипликативный вид стационарных вероятностей состояний сетей с системами со многими очередями, когда вероятности переходов между СМО сети зависят от ее состояний; ожидаемые доходы систем НМ-сетей с многолинейными СМО, полученные с помощью разработанной модификации метода последовательных приближений, совмещенного с методом рядов, позволяющей находить их удобным способом за процессорное время значительно меньшее, чем с помощью других методов.

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

5. Постановки и решения задач оптимизации стоимостных затрат сетей МО в переходном и стационарном режимах, которые являются моделями ЛИКС, ИС МБР, ППИ, с использованием средних характеристик, найденных с помощью указанных выше методов и методик, позволяющие находить оптимальные параметры этих систем и процессов.

Личный вклад соискателя

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

Апробация результатов диссертации

Основные результаты диссертации докладывались и обсуждались на: 1-3 международных научных конференциях «Современные информационные компьютерные технологии» (Гродно, ГрГУ, 2006, 2008, 2010); международной научной конференции «Актуальные проблемы социально-экономического развития РБ» (Гродно, ГрГУ, 2006); IV, V International Conferences «Analytic Methods of Analysis and Differential Equations» (Minsk, BSU, 2006, 2009); 19, 20 International Conferences on Queueing Theory «Mathematical Methods for Increasing Efficiency of Information Telecommunication Networks» (Grodno, GrSU, 2007; Minsk, BSU, 2009); международной научной конференции «Актуальные проблемы математического и компьютерного моделирования» (Гродно, ГрГУ, 2007); II, III международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, ВГТУ, 2007, 2009); международной конференции «X Белорусская математическая конференция» (Минск, ИМ НАН РБ, 2008); 3,4 International Conferences «Probability Theory, Random Processes, Mathematical Statistics and Applications» (Minsk, BSU, 2008, 2010); II международной научной конференции «Математическое моделирование и дифференциальные уравнения» (Минск, ИМ НАН РБ, 2009); международной научной конференции «Технологии информатизации и управления» (Гродно, ГрГУ, 2009); международной математической конференции «Актуальные проблемы анализа» (Гродно, ГрГУ, 2009); V International Conference «Informational Systems and Technologies» (Minsk, BSUIR, 2009); International Conference «Application of Mathematics in Simulation» of Polish Mathematical Society (Poland, Krynica Zdrуj, 2010); X-XIII республиканских научных конференциях аспирантов и студентов «Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях» (Гомель, ГГУ, 2007-2010); на научных семинарах кафедр теории вероятностей и математической статистики, системного анализа БГУ(Минск, БГУ, 2010).

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

По результатам диссертации опубликовано 46 научных работ. Среди них 16 статей в научных изданиях в соответствии с п. 18 Положения о присуждении ученых степеней и присвоении ученых званий в Республике Беларусь (общий объем - 8.2 авторских листа), из них 7 - в зарубежных журналах; 12 статей в научных журналах и сборниках научных трудов, 7 статей в сборниках материалов научных конференций, 11 тезисов докладов. Общий объем опубликованных материалов составляет 268 страниц. Без соавторов опубликовано 14 работ, из них 10 статей (3 - в рецензируемых журналах).

Структура и объем диссертации

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

В Приложениях приводятся вспомогательные результаты к главам диссертации, а также важные прикладные и практические результаты, полученные с помощью разработанных в ней методов и методик: описание применения сетей МО с разнотипными заявками многих классов в качестве вероятностных моделей ИС МБР; примеры применения НМ-сетей в качестве моделей оценки и прогнозирования доходов в сети Интернет, сети Интернет-магазинов, в страховых компаниях, логистических транспортных системах, предприятий от реализации их продукции, оценки затрат на содержание гибкого вычислительного кластера; анализ, оптимизация и применение НМ-сети с двумя типами заявок при моделировании межбанковских расчетов; алгоритм поиска оптимальной пропускной способности канала связи в ЛИКС с помощью метода ветвей и границ; пример применения алгоритма нахождения ожидаемых доходов в открытых НМ-сетях, основанный на использовании многомерных z-преобразований; описание конкретного технологического ППИ, при исследовании и оптимизации которого внедрялись результаты диссертации, а также представление его этапов в виде СМО с групповым поступлением и обслуживанием заявок в системах; имитационная модель такой сети, предназначенная для нахождения ее различных характеристик при произвольных распределениях времен обслуживания заявок в системах.

Полный объем диссертации составляет 177 страниц, включая 35 рисунков на 16 страницах, 7 таблиц на 3 страницах, 8 приложений на 40 страницах. Количество использованных библиографических источников составляет 234, включая собственные публикации автора (на 19 страницах).

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

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

В первом разделе главы 1 проведен обзор основных математических методов исследования сетей МО в стационарном и переходном режимах, выделен ряд нерешенных проблем и задач. Перечислены задачи, решаемые в работе, и охарактеризована их научная новизна. В разделе 1.2 описано применение сетей МО в качестве математических моделей ИКС, ИС МБР, ППИ и других объектов. В разделе 1.3 проведено исследование марковских сетей МО с разнотипными заявками многих классов с системами со многими очередями в случае, когда вероятности переходов заявок между СМО сети зависят от ее состояний, и описано применение их в качестве адекватных вероятностных моделей различных объектов. Рассматривается открытая сеть МО, которая состоит из СМО, в каждой из которых для обслуживания заявок формируются очередей, . Состояние очереди -й СМО характеризуется вектором , где - число заявок типа класса в очереди -й СМО, , , , . В сеть поступает простейший поток заявок с параметром ; времена обслуживания заявок типа класса в -й очереди -й СМО очередях имеют показательное распределение с параметром , - вероятность того, что после завершения обслуживания в очереди -й СМО, когда состояние сети равно , заявка типа класса переходит в очередь -й СМО как заявка типа класса , , , , , . Для такой сети получено достаточное условие представимости стационарных вероятностей состояний в следующей форме произведения (теорема 1.1):

,

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

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

, (1)

где - число заявок в системе , . На интервале времени в сеть поступает заявка с вероятностью , и если в момент на обслуживании в -й СМО находится заявка, то в интервале ее обслуживание закончится с вероятностью , . Пусть - вероятность перехода заявки после обслуживания в системе в систему , , . Получена система РДУ для вероятностей состояний такой сети.

Определим -мерную производящую функцию

. (2)

Предположим, что все СМО сети функционируют в условиях высокой нагрузки, т.е. , . Тогда справедливо следующее утверждение.

Теорема 2.1. Выражение для производящей функции (2) имеет вид

,

где , , , , .

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

В разделе 2.2 приведено обоснование рекуррентного метода анализа средних значений для открытых сетей с однотипными заявками и многолинейными СМО. Пусть система обслуживания состоит из идентичных линий обслуживания, время обслуживания заявок в которых распределено по произвольному закону с интенсивностью , . Обозначим через , , - соответственно среднее число заявок, среднее время пребывания заявок (в очереди и на обслуживании) и среднее число занятых линий обслуживания в -ой СМО на интервале времени , , . Тогда справедливы рекуррентные соотношения

, ,

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

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

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

где - затраты на содержание одной заявки в -ой СМО, а - затраты на содержание одной линии обслуживания в -ой СМО, - заданные числа, .

В разделе 2.4 исследована модель ЛИКС в виде сети МО с однолинейными системами, функционирующей в условиях высокой нагрузки. Сформулирована задача минимизации стоимостного критерия для нахождения оптимальной заказной пропускной способности канала связи в следующем виде:

, (3)

где - оплата услуг провайдера, - объем трафика информации, проходящего через выделенный канал связи в Интернет в момент времени t , С(G) - стоимость единицы трафика, которая является функцией от пропускной способности выделенного канала связи Интернет Kбит/с и представляет собой максимальное количество килобит в секунду, которое может пропустить выделенный канал, - объем в байтах -го сообщения на -ом сервере, -число сообщений, проходящих через -ый сервер в момент времени t, - количество серверов.

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

В главе 3 проведено исследование нового класса сетей МО - марковских сетей с доходами или НМ-сетей произвольной структуры. В разделе 3.1 рассматривается открытая сеть Джексона с доходами, описанная в разделе 2.1, причем все СМО сети - однолинейные, состояние сети характеризуется вектором (1).

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

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



, . (4)

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

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

Теорема 3.1. Если и так, что , то , где вектор - определенный вектор, называемый вектором прибылей. Для общего дохода сети для этого достаточно, чтобы , .

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

В разделе 3.2 проведено исследование ожидаемых доходов в открытой сети МО, описанной в разделе 2.1. Число состояний такой сети счетно и поэтому анализ доходов в ней усложняется. Для нахождения доходов систем такой сети был предложен метод многомерных -преобразований. Пусть доходы от переходов между состояниями сети не зависят от времени, а интенсивности обслуживания заявок в системах линейно зависят от их числа, т.е. , . Введем -преобразование для дохода системы :

,

.

Теорема 3.2. Функция удовлетворяет соотношению

. (5)

Где

, ,

На основании соотношений (5) построен алгоритм нахождения ожидаемых доходов систем сети.

В разделе 3.3 исследовано нахождение доходов НМ-сети с разнотипными заявками многих классов, описанной в разделе 1.3, с помощью модификации метода последовательных приближений, совмещенного с методом рядов.

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

, (6)

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



. (7)

Очевидно, что , и пусть также .

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

Теорема 3.4. Последовательность , , построенная по схеме (7), при любом ограниченном по нулевом приближении сходится при к единственному решению системы уравнений (6).

Теорема 3.5. Любое приближение , , представимо в виде степенного ряда , коэффициенты ряда удовлетворяют рекуррентным соотношениям:

, ,

, ,

где , - символ Кронекера. Если , то ряд сходится при любом конечном .

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

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

,

.

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

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

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

В разделе 3.5 проведено исследование ожидаемых доходов систем открытой сети с однотипными заявками и многолинейными СМО, когда известны только первые моменты доходов от переходов между ее состояниями.

Для ожидаемых доходов систем сети , , и , , получены неоднородные линейные ОДУ первого порядка с разрывными правыми частями:

, , (8)

, .(9)

Для частных случаев, когда в СМО сети бесконечное число линий обслуживания или, когда это число больше или равно числу заявок в замкнутой сети, система (8) принимает вид

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

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

,,

где , - целая часть числа , - целая часть числа .

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

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

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

ЗАКЛЮЧЕНИЕ

Основные научные результаты диссертации

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

1. Получены выражения для многомерных производящих функций вероятностей состояний открытой сети произвольной структуры с параметрами входящего потока и обслуживания заявок, зависящими от времени, функционирующей в условии высокой нагрузки, с помощью которых, в отличие от существующих методов, можно находить вероятности состояний и среднее число заявок в системах в виде многократных рядов в переходном режиме [5, 8, 23, 41].

Разработан рекуррентный по моментам времени метод анализа средних значений для открытой сети МО с произвольными распределениями времен обслуживания в системах, который в отличие от известных, позволяет находить средние характеристики произвольных сетей в переходном и стационарном режимах за небольшое процессорное время [11, 22, 30].

2. Разработана методика исследования ожидаемых доходов в марковских НМ-сетях произвольной структуры с однотипными заявками в случае, когда доходы от переходов между их состояниями являются детерминированными функциями, зависящими от состояний сети и времени [10, 39, 45], основанная на получении систем со счетным или конечным числом РДУ для ожидаемых доходов и использовании предложенных способов и алгоритма решения этих систем [6, 7, 15, 16, 36, 46]. Исследовано асимптотическое поведение доходов при больших значениях времени.

Для сетей с многолинейными СМО, когда доходы от переходов между их состояниями являются СВ с заданными моментами первых двух порядков, найдены приближенные соотношения для ожидаемых доходов систем и дисперсий доходов и точные выражения для некоторых частных случаев [2, 4, 6, 12, 21, 24, 25, 27, 28, 37].

3. Проведено исследование марковских сетей МО с разнотипными заявками многих классов. Получены выражения в форме произведения для стационарных вероятностей состояний сетей с системами со многими очередями, когда вероятности переходов заявок между СМО зависят от состояний сетей [1, 26, 29].

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

4. Для сети МО с групповым поступлением и обслуживанием заявок в системах, функционирующей в условиях большой нагрузки, получены выражения для среднего числа заявок в очередях систем и на обслуживании [3, 19]. Данная сеть впервые используется в качестве модели ППИ [17, 18, 20, 40] и позволяет учесть случайность входящих потоков изделий и времен их обработки группами на различных этапах.

5. Осуществлены постановки и получены решения задач оптимизации сетей МО в переходном и стационарном режимах, которые являются моделями ЛИКС, ИС МБР, ППИ, с использованием предложенных стоимостных критериев; входящие в критерии характеристики находятся с помощью разработанных в диссертации методов и методик [4, 13, 14, 19, 30, 31, 32, 33, 34, 35, 38, 42, 43, 44].

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

Рекомендации по практическому использованию

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

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

Результаты работы внедрены в ОАО «Гродненский комбинат строительных материалов» - при создании и оптимизации вероятностных моделей процессов производства строительных блоков и кирпича; ООО «НБИТ» - при проектировании, реализации и исследовании распределенного сервера для обработки и обслуживания информации рекламного характера в сети Интернет и рекламно-информационной сети; Расчетном центре Национального банка РБ - при оценке и выборе алгоритмов формирования подмножества проводимых платежей в зависимости от характеристик их входного потока и выделенных банками резервов на их проведение и прогнозировании доходов от межбанковских платежей; Гродненском государственном университете им. Я. Купалы - при создании и исследовании модели локальной компьютерной сети с целью оптимизации ее функционирования, а также при чтении спецкурса «Применение теории массового обслуживания в экономике». Материалы работы вошли в содержание «Сайта о нахождении вероятностно-временных характеристик сетей массового обслуживания», созданного автором и зарегистрированного в Государственном регистре информационных ресурсов, регистрационное свидетельство № 4200900734 от 20.11.2009 г.

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

Статьи в научных журналах, рекомендованных в Перечне ВАК

Matalytski, M. Queueing networks with multi-type messages of multiple classes: analysis and applications / M. Matalytski, E. Koluzaeva // Computer Science. - 2006. - V. 6, № 9. - P. 19-26.

Matalytski, M. Finding of expected incomes in open exponential network of arbitrary architecture / M. Matalytski, E. Koluzaeva // Scientific Research of the Institute of Mathematics and Computer Science Czestochowa University of Technology. - 2007. - Vol.1, №6. - P. 179-190.

Колузаева, Е.В. Анализ и компьютерная оптимизация стохастической модели процесса производства изделий / Е.В. Колузаева // Вестник ГрГУ. Сер. 2. - 2007. - №3. - С. - 83-90.

Matalytski, M. Analysis and optimization of Markov HM-networks with stochastic incomes from transitions between their states / M. Matalytski, E. Koluzaeva // Scientific Research of the Institute of Mathematics and Computer Science Czestochowa University of Technology. - 2008. - Vol.1, №7. - P. 22-27.

Matalytski, M. State probabilities of computer networks models with dependent from time arrival and service parameters / M. Matalytski, E. Koluzaeva // Computer Science. - 2008. - Vol. 8, №14. - Р. 7-18.

Колузаева, Е.В. Анализ доходов в открытых НМ-сетях произвольной архитектуры / Е.В. Колузаева, М.А. Маталыцкий // Вестник ГрГУ. Сер.2. - 2008. - №1. - С. 22-29.

Колузаева, Е.В. Анализ ожидаемых доходов в открытой сети с помощью z-преобразований / Е.В. Колузаева, М.А. Маталыцкий // Вестник ГрГУ. Сер. 2. - 2008. - №3. - С. 11-19.

Колузаева, Е.В. Нахождение вероятностей состояний моделей информационно-компьютерных сетей с зависимыми от времени параметрами потока и обслуживания, функционирующих в условиях высокой нагрузки / Е.В. Колузаева, М.А. Маталыцкий // Вестник ГрГУ. Сер.2. - 2008.- № 3. - С. 22-29.

Маталыцкий, М.А. Исследование марковских сетей с доходами и разнотипными заявками многих классов методом последовательных приближений / М.А. Маталыцкий, Е.В. Колузаева // Известия НАН РБ. Сер. физ.-мат.н. - 2008. - №4. - С. 113-118.

Маталыцкий, М.А. О методах анализа и применении НМ-сетей массового обслуживания / М.А. Маталыцкий, Е.В. Колузаева // Обозрение прикладной и промышленной математики. - 2008. - Т.15, вып.3. - С.564-565.

Маталыцкий, М. А. Об одном рекуррентном методе анализа средних значений для открытых сетей с однотипными заявками / М.А. Маталыцкий, Е.В. Колузаева // Вестник ГрГУ. Сер 2. - 2008. - №2. - С. 95 - 102.

Matalytski, M. Analysis of HM-networks with stochastic incomes from transitions between states / M. Matalytski, K. Koluzaeva // Scientific Research of the Institute of Mathematics and Computer Science Czestochowa University of Technology. - 2009. - Vol. 2, № 8. - P. 105-118.

Matalytski, M. Optimization of stochastic model of local computer network with method of branch and bounds / M. Matalytski, E. Koluzaeva // Scientific Research of the Institute of Mathematics and Computer Science Czestochowa University of Technology. - 2009. - Vol. 8. - P. 95-104.

Колузаева, Е.В. Анализ и оптимизация локальной компьютерной сети университета / Е.В. Колузаева // Вестник ГрГУ. Сер.2. - 2009. - №2. - C. 121-128.

Маталыцкий, М.А. Марковские сети массового обслуживания произвольной топологии с доходами / М.А. Маталыцкий, Е.В. Колузаева // Доклады НАН РБ. - 2009. - Т.53, №3. - С. 10-17.

Колузаева, Е.В. Нахождение ожидаемых доходов в открытой двухузловой НМ-сети с помощью z-преобразований / Е.В. Колузаева// Вестник ГрГУ. Сер.2. - 2010. - №1. - C. 20-30.

Статьи в научных журналах и сборниках научных трудов

Колузаева, Е.В. Аналитическое и программное обеспечение одной задачи оптимизации производства изделий / Е.В. Колузаева, М.А. Маталыцкий // Актуальные проблемы социально-экономического развития Республики Беларусь: сб. науч. статей молодых ученых: в 2 ч. - Гродно: ГрГУ, 2006. - Ч.2. - С. 164-168.

Колузаева, Е.В. Математическая модель и программное обеспечение одного процесса производства изделий / Е.В. Колузаева // Современные информационные компьютерные технологии: сб. науч. статей. - Гродно: ГрГУ, 2006. - С. 40-46.

Колузаева, Е.В. Анализ и оптимизация сетей массового обслуживания различной размерности и их применения / Е.В. Колузаева, М.А. Маталыцкий // Сборник научн. Работ студентов высших учебн. заведений Республики Беларусь «НИРС, 2006» / редкол.: А.И. Жук (пред.) [и др.]. - Минск: Изд. Центр БГУ, 2007. - С. 58-60.

Колузаева, Е.В. Моделирование производственного процесса с помощью тандемной стохастической сети с групповым поступлением и обслуживанием заявок / Е.В. Колузаева, М.А. Маталыцкий // Актуальные проблемы математики и компьютерного моделирования: сб. науч. трудов. - Гродно: ГрГУ, 2007. - С. 204-206.

Колузаева, Е.В. Анализ экспоненциальных НМ-сетей со случайными доходами от переходов между состояниями / Е.В. Колузаева, М.А. Маталыцкий // Современные информационные компьютерные технологии: сб. науч. статей: в 2 ч. - Гродно: ГрГУ, 2008. - Ч.2. - С.75-79.

Колузаева, Е.В. Об усовершенствовании MVA метода для открытых сетей МО и его применении / Е.В. Колузаева // Современные информационные компьютерные технологии: сб. науч. статей. - Гродно: ГрГУ, 2008 - С. 79-82.

Колузаева, Е.В. Нахождение средних характеристик стохастических моделей информационно-компьютерных сетей, функционирующих в условиях высокой нагрузки / Е.В. Колузаева // Современные информационные компьютерные технологии: сб. науч. статей. - Гродно: ГрГУ, 2008. - С. 72-75.

Колузаева, Е.В. Анализ ожидаемых доходов НМ-сети произвольной топологии со случайными доходами от переходов между ее состояниями / Е.В. Колузаева, М.А. Маталыцкий // Актуальные проблемы современного анализа: сб. науч. трудов. - Гродно: ГрГУ, 2009. - С. 84-93.

Колузаева, Е.В. Применение НМ-сетей с ограниченным временем ожидания заявок в очередях при моделировании межбанковских платежей / Е.В. Колузаева, М.А. Маталыцкий, С.Э. Статкевич // Технологии информатизации и управления: сб. науч. статей. - Минск: БГУ, 2009. - С. 27-31.

Маталыцкий, М.А. Применение сетей с разнотипными заявками многих классов при моделировании систем межбанковских и межфилиальных расчетов / М.А. Маталыцкий, А.А. Карпук, Е.В. Колузаева // Теория вероятностей, математическая статистика и их приложения: сб. науч. статей. - Минск: РИВШ, 2009. - Вып. 2. - С. 114-120.

Колузаева, Е.В. Исследование НМ-сетей со случайными доходами от переходов между их состояниями / Е.В. Колузаева, М.А. Маталыцкий // Известия Томского государственного университета. Сер. Информатика, вычислительная техника и управление. - 2009. - № 5. - С. 91-100.

Колузаева Е.В. О некоторых методах анализа и оптимизации НМ-сетей и их применении / Е.В. Колузаева, М.А. Маталыцкий // Научные исследования преподавателей факультета математики и информатики: сб. науч. статей. - Гродно: ГрГУ, 2010. - С.73-88.

Статьи в сборниках материалов научных конференций

Колузаева, Е.В. Анализ и оптимизация стохастических моделей обслуживания пациентов в медицинских центрах / Е.В. Колузаева, М.А. Маталыцкий // Массовое обслуживание. Математические методы повышения эффективности информационно-телекоммуникационных сетей: материалы Междунар. науч. конф., г. Гродно, 29 янв.- 1 февр. 2007 г. / редкол.: А.Н. Дудин (отв.ред.)[и др.]. - Минск: РИВШ, 2007. - Вып. 19. - С. 106-112.

Колузаева, Е.В. Компьютерная оптимизация открытых сетей массового обслуживания большой размерности с помощью рекуррентного по моментам времени MVA-метода / Е.В. Колузаева // Теория вероятностей, случайные процессы, математическая статистика и приложения: сб. науч. статей Междунар. научн. конф., Минск, 15-17 сент. 2008 г. / редкол.: Н.Н. Труш (отв.ред.)[и др.]. - Минск: БГУ, 2008. - С.149-153.

Колузаева, Е.В. Анализ и компьютерная оптимизация сетей массового обслуживания в переходном режиме / Е.В. Колузаева // Массовое обслуживание. Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей: материалы Междунар. науч. конф., Минск, 26-29 янв. 2009 г. / редкол.: А.Н. Дудин (отв.ред.)[и др.]. - Минск: РИВШ, 2009. - Вып.20. - С. 114-118.

Колузаева, Е.В. Исследование модели локальной компьютерной сети университета и ее оптимизация / Е.В. Колузаева // Массовое обслуживание. Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей: материалы Междунар. науч. конф., Минск, 26-29 янв. 2009 г. / редкол.: А.Н. Дудин (отв.ред.)[и др.]. - Минск: РИВШ, 2009. - Вып.20. - С. 119-123.

Колузаева, Е.В. Оптимизация модели локальной компьютерной сети университета методом ветвей и границ / Е.В. Колузаева, М.А. Маталыцкий // Информационные системы и технологии: материалы V Междунар. конф.-форума:в 2 ч., Минск, 16-17 нояб. 2009 г. / редкол.: Н.И. Листопад [и др.] - Минск: БГУИР, 2009. - Ч.1. - С. 35-38.

Маталыцкий, М.А. Применение НМ-сети с двумя типами заявок при моделировании межбанковских платежей / М.А. Маталыцкий, А.А. Карпук, Е.В. Колузаева // Массовое обслуживание. Современные математические методы анализа и отимизации информационно-телекоммуникационных сетей: материалы Междунар. науч. конф., Минск, 26-29 янв. 2009 г. / редкол.: А.Н. Дудин (отв.ред.)[и др.]. - Минск: РИВШ, 2009.- Вып.20. - С. 151-157.

Колузаева, Е.В. Анализ и оптимизация сетей массового обслуживания различной топологии / Е.В. Колузаева // Теория вероятностей, случайные процессы, математическая статистика и приложения: сб. науч. статей Междунар. научн. конф., Минск, 22 февр., 2010 г. / редкол.: Н.Н. Труш (отв.ред.)[и др.]. - Минск: БГУ, 2010. - С. 153-157.

Тезисы докладов

Matalytski, M. About solution of difference equation for queueing networks and its applications / M. Matalytski, E. Koluzaeva // Analytical methods of analysis and differential equations: Abstracts of reports of the international conference, September 13-19, 2006, Minsk, Belarus. - Minsk: Institute of Mathematics of NAS of Belarus, 2006. - P. 86.

Колузаева, Е.В. Экспоненциальные сети массового обслуживания с доходами и их применения / Е.В. Колузаева, М.А. Маталыцкий // Современные проблемы прикладной математики и математического моделирования: материалы II Междунар. науч. конф., Воронеж, 11-16 дек. 2007 г. - Воронеж: ВГТУ, 2007. - С.100-101.

Колузаева, Е.В. О решении оптимизационной задачи для процесса производства изделий / Е.В. Колузаева, М.А. Маталыцкий // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях: материалы X респ. науч. конф.:в 2 ч., Гомель, 12-14 марта, 2007 г. / редкол.: Д.Г. Лин [и др.]. - Гомель: ГГУ им. Ф. Скорины, 2007. - Ч.1. - С. 144-146.

Колузаева, Е.В. О некоторых методах анализа НМ-сетей и их применении / Е.В. Колузаева, М.А. Маталыцкий // X Белорусская математическая конференция: тез. докл. Междунар. науч. конф., Минск, 3-7 ноября, 2008 г. - Минск: ИМ НАН РБ, 2008. - Ч.5. - С. 9.

Колузаева, Е.В. Моделирование одного процесса производства изделий / Е.В. Колузаева // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях: материалы XI респ. науч. конф.:в 2 ч., Гомель, 17-19 марта, 2008 г. / редкол.: О.М. Демиденко (гл.ред.)[и др.]. - Гомель: ГГУ, 2008. - Ч.1. - С. 168-170.

Колузаева, Е.В. О нахождении вероятностей состояний сетей массового обслуживания, функционирующих в условиях высокой нагрузки / Е.В. Колузаева, М.А. Маталыцкий // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях: материалы XI респ. науч. конф.:в 2 ч., Гомель, 17-19 марта, 2008 г. / редкол.: О.М. Демиденко (гл.ред.)[и др.]. - Гомель: ГГУ, 2008. - Ч.1. - С. 101-102.

Колузаева, Е.В. Математический анализ модели ЛКС университета, функционирующей в условиях высокой нагрузки / Е.В. Колузаева // Актуальные проблемы анализа: тез. докл. Междунар. матем. конф., Гродно,7-10 апр., 2009 г. / редкол.: Я.В. Радыно,В.Г. Кротов, Ю.М. Вувуникян(отв.редактор.).- Гродно: ГрГУ, 2009. - C. 136-137.

Колузаева, Е.В. Математическое моделирование и оптимизация локальной компьютерной сети / Е.В. Колузаева // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях: материалы XII респ. науч. конф.:в 2 ч., Гомель, 16-18 марта, 2009 г. / редкол.: О.М. Демиденко (гл.ред.)[и др.]. - Гомель: ГГУ, 2009. - Ч.1. - С. 197-199.

Колузаева Е.В. О некоторых методах исследования и оптимизации сетей массового обслуживания в переходном режиме / Е.В. Колузаева // Современные проблемы прикладной математики и математического моделирования: материалы III Междунар. научн. конф.:в 2 ч., Воронеж, 2-7 февр, 2009 г. - Воронеж: «Научная книга», 2009. - Ч.1. - С. 157.

Колузаева, Е.В. О некоторых методах решения разностно-дифференциальных уравнений для ожидаемых доходов НМ-сети / Е.В. Колузаева, М.А. Маталыцкий // Аналитические методы анализ и дифференциальных уравнений: тез. докл. Междунар. математич. конф.: в 2 ч., Минск, 24-28 августа 2009 г. - Минск: ИМ НАН РБ, 2009. - Ч.1. - С. 87.

Колузаева, Е.В. Применение метода z-преобразований для вычисления ожидаемых доходов в НМ-сетях / Е.В. Колузаева, М.А. Маталыцкий // Математическое моделирование и дифференциальных уравнений: тез. докл. II Междунар. математич. конф.:в 2 ч., Минск, 24-28 авг. 2009г. - Минск: ИМ НАН РБ, 2009. - Ч. 1. - С. 53-55.

Размещено на Allbest.ru

...