Методика оптимизации библиотечной системы обслуживания

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

В дальнейшем будет рассматриваться только про­стейший входящий поток в силу особой его роли в тео­рии массового обслуживания.

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

Получим аналитическое описание простейшего потока и рассмотрим его свойства подробнее.

Рис. 1.4 - Простейший поток событий

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

                                                                                                        (1.18)

где - плотность потока.

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

                                                        (1.19)

Тогда вероятность того, что не произойдет ни одного события, будет

                                                                                                     (1.20)

Отсюда вероятность того, что за время  произойдет хотя бы одно событие, равна

                                                                                     (1.21)

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

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

                                                                       (1.22)

откуда, имея в виду (1.20),

                                                                           (1.23)

Дифференцируя (1.23), находим плотность распреде­ления длин интервалов между последовательными со­бытиями

                                                                         (1.24)

Закон распределения с плотностью (1.24) называется показательным с параметром λ.

1.3.3 Время обслуживания            

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

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

                                                                                        (1.25)

и плотность его распределения

                                                                                                     (1.26)

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

                                                                                                 (1.27)

Параметр  имеет простой физиче­ский смысл. Величина, обратная , равна математиче­скому ожиданию времени обслуживания.

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

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

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

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

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

Закон распределения интервала времени между по­паданиями имеет вид

                                                                               (1.28)

откуда плотность распределения времени обслуживания      

                                                                                                        (1.29)

что  соответствует  показательному   закону   с  парамет­ром .

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

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

1.3.4 Основные типы систем массового обслуживания и  показатели эффективности  их функционирования

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

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

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

Степень загрузки системы обслуживания с отказами характеризует закон распределения числа занятых аппа­ратов. Во многих случаях для характеристики эффек­тивности системы обслуживания с отказами достаточно указать среднее число занятых аппаратов.

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

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

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

1.3.5 Система массового обслуживания с ожиданием

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

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

Пусть на вход n-канальной системы обслуживания поступает простейший поток требований с плотностью . Время обслуживания каждой из заявок  распреде­лено по показательному закону с параметром . Заявка, заставшая все каналы системы за­нятыми, становится в очередь и ожидает обслуживания. Время ожидания  будем считать случайным и рас­пределенным по показательному закону

                                                                                                                       (1.30)

где параметр  - величина, обратная среднему време­ни ожидания, т. е.

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

Перечислим состояния системы. Будем нумеровать их не по числу занятых каналов, как это сделано ранее, а по числу заявок, связанных с системой. При этом бу­дем заявку называть связанной с системой, если она либо обслуживается, либо ожидает в очереди. Возмож­ные состояния системы:

- свободны все каналы, очереди нет,

      - занят ровно один канал, очереди нет,

…………………………………………………….

 - занято ровно k каналов, очереди нет,

- заняты все п каналов, очереди нет,

  заняты вес   п   каналов,   одна   заявка   стоит в очереди,

…………………………………………………….

 - заняты   все п  каналов,  s заявок - в  очереди.

Вероятность нахождения системы в перечисленных состояниях находится по формуле:

                                                                 (1.31)

где - среднее число заявок приходящихся на среднее время обслуживания одной заявки;

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

1.4 Метод статистических испытаний

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

Пусть зависимость условной вероятности продажи  некоторого товара от его цены  описывается соотношением

                                                .                                               (1.32)

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

                    ,                                  (1.33)

где

         -нормирующая константа.

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

         Кривая  изображена на рис. 1.5.

Здесь абсцисса  выбрана так, чтобы значение  было достаточно малым (например, 0,001), а ордината  равна . Теперь понятно, что расчет  эквивалентен вычислению площади  под кривой  при .

Рис. 1.5 - Кривая .

         Пусть в прямоугольнике с координатами вершин (0,0), (0,b), (a,0), (a,b) формируется точка, координаты которой случайны и независимы, причем абсцисса равномерно распределена в , а ордината равномерно распределена в . Ясно, что вероятность попадания этой точки в область под кривой  равна площади под кривой, то есть искомой вероятности . С другой стороны эту вероятность легко оценить, если провести  испытаний, подсчитать количество  попаданий точки в область под кривой и вычислить отношение . Легко показать, что оценка  является несмещенной и состоятельной оценкой . В самом деле, введем индикатор

         Очевидно, что .

         Вычислим математическое ожидание и дисперсию случайной величины .

         .         (1.34)

Следовательно, оценка  вероятности  является несмещенной.

Страницы: 1, 2, 3, 4, 5, 6, 7