Случайный процесс с конечным множеством состояний

1 2 3 4 5

Тема: Основные понятия теории массового обслуживания (ТМО)

План лекции

1. Основные понятия и предмет теории массового обслуживания.

2. Случайный процесс с конечным множеством состояний.

3. Поток событий. Простой поток и его свойства.

4. Нестационарный пуассоновский поток.

5. Поток с ограниченным последствием(поток Пальма).

6. Поток Эрланга.

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

8. Марковские случайные процессы.

Основные понятия и предмет теории массового обслуживания

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

СМО можно представить в виде структурной схемы:

Входной поток вызовов

Очередь

Каналы обслуживания

Выходной поток вызовов

…

Системы массового обслуживания могут быть как одно-, так и многоканальными. Если же требования обслуживаются несколькими устройствами в определенной последовательности, перемещаясь от одного устройства к другому, то имеет место сеть обслуживания. Сеть – это сложная СМО.

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

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

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

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

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

Особое значение СМО приобрели в информатике. Это прежде всего компьютерные системы, сети передачи информации, базы и банки данных.

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

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

Первые теоретические разработки в области теории СМО были выполнены сотрудником копенгагенской телефонной компании Агнером Эрлангом в 1908-1922 г. (Agner Erlang (1878-1929) – датский математик, основатель теории массового обслуживания и направления по исследованию трафика в телекоммуникационных системах). Его ранние работы по изучению местных телефонных сетей, автоматических телефонных станций и магистральных телефонных линий привели к осознанию того, что необходимо для создания эффективной сети. Эрланг получил формулу для расчета пропускной способности в телекоммуникационных сетях. В его честь была названа единица измерения трафика в телекоммуникационных системах.

Чаще всего эффективность функционирования любой СМО определяется по таким показателям:

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

- средний процент требований, которые не были обслужены;

- вероятность того, что требование, которое пришло в систему, будет принято для обслуживания;

- среднее время ожидания требования в очереди;

- закон распределения времени ожидания;

- среднее количество требований в очереди;

- закон распределения числа требований в очереди;

- коэффициент загруженности устройства для обслуживания;

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

Чтобы определить эти параметры, нужно охарактеризовать СМО, т.е. описать и задать такие характеристики:

- входной поток требований;

- дисциплина постановки требований в очередь и выбора требований из неё;

- правила, по которым осуществляется обслуживание;

- выходной поток требований;

- режим работы системы.

Случайный процесс с конечным множеством состояний

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

Рассмотрим физическую систему с множеством состояний

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

(1)

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

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

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

Схема возможных состояний системы и возможных переходов из состояния в состояние показана на рис.1.

…..…

…

Рис.1

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

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

В качестве примера рассмотрим одноканальную СМО (например, одну телефонную линию), в которой заявка, заставшая канал занятым, не становится в очередь, а покидает систему (получает «отказ»). Это – дискретная система с непрерывным временем и двума возможными состояниями:

– канал свободный, – канал занятый.