7.12. Стохастические потоки в сетях

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

Рассмотрим сеть, пропускные способности дуг которой вадаются распределениями вероятностей, являющимися

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

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

Рис. 7.19.

Рис. 7.20.

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

каналов может иметь выход на другие последовательные каналы или стоки, представлен рис. 7.21. В качестве источника берется начальная совокупность заявок на обслуживание, а в качестве стока та же совокупность (после удовлетворения спроса),

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

Рис. 7.21.

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

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

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

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

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

Упражнения

(см. скан)

Более исчерпывающее описание теории потоков в сетях с различных точек зрения дается в работах [5], [10], [12] и [14] литературы к главе I. Мы также отсылаем читателя к списку литературы в конце этой главы и к более обширной библиографии, содержащейся в перечисленных выше книгах.

ЛИТЕРАТУРА

(см. скан)

(см. скан)

ОТВЕТЫ К УПРАЖНЕНИЯМ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)