Теория массового обслуживания

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

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

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

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

8.1. Понятие о марковском случайном процессе

До сих пор мы рассматривали главным образом де­терминированные задачи исследования операций и методы оптимизации решении в этих задачах. Теперь будем заниматься задачами исследования операций в условиях неопределенности. Начнем со сравнительно благоприятного случая «доброкачественной» или «стохастической» неопределенности, когда неопределенные факторы, входящие в задачу, представляют собой случайные величины, вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Мы будем здесь заниматься, главным образом, прямыми задачами исследования операций, т. е. построением математических моделей некоторых случайных явлений, лишь бегло останавливаясь на обратных задачах (оптимизации решений), потому что они, как правило, сложны. В стохастических задачах исследования операций часто затруднительно даже построение математической модели, уже не говоря об оптимизации («не до жиру, быть бы живу»). В большинстве случаев не удается построить простую математическую модель, позволяющую в явном (аналитическом) виде найти интересующие нас величины (показатели эффективности) в зависимости от условий операции а и элементов решения х. Однако в некоторых особых случаях такую математическую модель удается построить. Это — когда исследуемая операция представляет собой (точно или приближенно) так называемый марковский случайный процесс.

А что такое «марковский случайный процесс»? Оп­ределение этого понятия мы дадим не сразу, сначала поговорим о том, что такое вообще «случайный процесс».

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

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

Пусть, например, физическая система S — обыкновенный самолет, совершающий рейс на заданной высоте, по определенному маршруту. Является ли этот процесс случайным? безусловно, да, так как он неизбежно (в силу турбулентности атмосферы и других факторов) сопровождается случайными возмущениями, колебаниями (в этом не усомнится никто, испытавший на себе так называемую «болтанку» или нарушение графика полетов).

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

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

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

0 t₀ (S₀) t

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

Это очень важное определение стоит того, чтобы его растолковать подробнее. Пусть в настоящий момент t₀ (см. рис.) система находится в определенном состоянии S₀. Мы наблюдаем процесс со стороны и в момент t₀ знаем состояние системы S₀ и всю предысторию процесса, все, что было при t < t₀. Нас, естественно, интересует будущее
(t > t₀). Можем ли мы его предугадать (предсказать)? В точности — нет, наш процесс случайный, значит — непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время τ система S окажется в состоянии S₁ или сохранит состояние S₀, и т. п.

Так вот, для марковского случайного процесса такое «вероятностное предсказание» оказывается гораздо проще, чем для немарковского. Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S₀ и забыв о его «предыстории» (поведении системы при t < t₀). Само состояние S₀, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Иначе формулируя, в марковском процессе «будущее зависит от прошлого только через настоящее».

Пример марковского процесса: система S — счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент t характеризуется показанием счетчика — числом частиц, пришедших до данного момента. Пусть в момент t₀ счетчик показывает S₀. Вероятность того, что в момент t > t₀ счетчик покажет то или другое число частиц S₁ (или не менее S₁), разумеется, зависит от S₀, но не зависит от того, в какие именно моменты приходили частицы до момента t₀.

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Пример: система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — х и «синих» — у, сохранившихся (не сбитых) к какому-то моменту. В момент t₀ нам известны численности сторон — х₀ и у₀. Нас ин­тересует вероятность того, что в какой-то момент
t₀ + τ численный перевес будет на стороне «красных». Спросим себя, от чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент t₀, а не от того, когда и в какой последовательности погибали сбитые до момента t₀ самолеты.

8.2. Понятие системы массового обслуживания

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

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

Системы массового обслуживания (СМО) делятся на два класса: СМО с отказами и СМО с ожиданием (очередью).

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

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

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

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

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

8.3. Однородный поток событий

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

Поток одинаковых событий, различающихся только моментами наступления, называется однородным. Такой поток можно представить последовательностью точек t₁, t₂, … на числовой оси времени наступления (рис).

Схема потока событий

Однородный поток называется простейшим (или стационарным Пуассоновским), если он обладает сразу тремя свойствами:

— стационарности, состоящим в том, что вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока должна быть постоянной. Это не число событий в единицу времени постоянно, поток неизбежно (если только он не регулярный) имеет случайные сгущения и разрежения, важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера: на одном участке длины 1 может быть больше событий, на другом – меньше, но среднее число событий, приходящихся на единицу времени, постоянно и от времени не зависит.

Отклонения от стационарности объясняется какими-либо причинами (число покупателей в магазине после рабочей смены, число вызовов на АТС ночью меньше). На практике часто встречаются потоки событий, которые (по крайней мере на ограниченном участке времени) могут считаться стационарными.

— отсутствия последействия, то есть вероятность наступления k событий на промежутке времени Dt не зависит от числа и способа появления событий ранее (число пассажиров, входящих в метро);

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

Итак, поток событий, обладающий всеми тремя свойствами (стационарности, отсутствия последействия и ординарности), называется простейшим или стационарным пуассоновским.

Дата добавления: 2014-01-03