Борис Владимирович Гнеденко
Игорь Николаевич Коваленко
Введение в теорию
массового обслуживания
*** 1966 ***
От нас: 500 радиоспектаклей (и учебники)
на SD‑карте 64(128)GB — ГДЕ?..
Baшa помощь проекту:
занести копеечку — КУДА?..
|
РАСПОЗНАННЫЕ ФРАГМЕНТЫ
ВВЕДЕНИЕ Практические требования телефонного дела, физики и рациональной организации массового обслуживания (билетные кассы, магазины, автоматы и пр.) выдвинули в начале нашего столетия ряд интересных математических задач нового типа. Первоначально эти задачи касались преимущественно вопросов обслуживания абонентов телефонной станции, расчета запасов магазинов для бесперебойного снабжения покупателей, а также установления наиболее рационального числа продавцов и касс в торговых предприятиях. На первичное развитие этой теории особое влияние оказали работы известного датского ученого А. К. Эрланга (1878 —1929) — многолетнего сотрудника Копенгагенской телефонной компании. Основные его исследования в этой области относятся к 1908— 1922 гг. С того времени интерес к проблемам, выдвинутым Эрлангом, необычайно возрос. В результате значительно увеличилось число математиков и инженеров, а также экономистов, интересующихся и разрабатывающих подобные проблемы. Оказалось, что задачи типа телефонных возникают в самых разнообразных направлениях исследований: в естествознании, в технике, экономике, транспорте, военном деле, организации производства. Требования практики выдвигают перед теорией массового обслуживания большое число новых постановок задач. Рассмотрение их необходимо для приложений, для постепенного приближения условий, в которых они решаются, к истинной картине изучаемых явлений; с другой стороны, это поучительно для выработки методов исследования и для создания стройной теории, которая даст возможность решать все эти частные задачи почти автоматически. Нужно сознаться, что такая теория в полной мере еще не создана, но в тех попытках, которые уже имеются, особую роль играют случайные процессы, в особенности процессы Маркова и различные их обобщения. Прежде чем переходить к систематическому изложению материала курса, рассмотрим несколько областей применения, не вдаваясь при этом в подробности. Предположим, что на телефонную станцию в случайном порядке поступают вызовы. Если в момент поступления вызова на станции имеются свободные линии, то происходит подключение абонента к свободной линии и начинается разговор в течение того времени, которое необходимо для его завершения. Если же на станции все линии заняты, то возможны различные системы обслуживания абонентов. В настоящее время особенно хорошо разработаны две системы обслуживания: система с ожиданием и система с потерями. При первой системе обслуживания вызов, поступивший на станцию и нашедший все линии занятыми, становится в очередь и ожидает, когда все поступившие ранее требования будут обслужены. При второй организации работы каждый вызов, поступивший в момент, когда все линии заняты, получает отказ (происходит потеря требования) и все дальнейшее течение обслуживания происходит так, как будто бы этот вызов вообще не поступал. Заметим, что только что описанные системы обслуживания отличаются не только техническими особенностями, но и характером возникающих при их изучении задач. Действительно, для оценки качества обслуживания системой с ожиданием особенно существенно определение среднего времени ожидания начала обслуживания. Для систем с потерями время ожидания не представляет ни технического, ни математического интереса. Здесь важна другая характеристика — вероятность отказа (потери требования). Но если во второй постановке задачи вероятность отказа дает достаточно полное представление о том, на что можно рассчитывать при данной организации и технике обслуживания, то в первой задаче положение оказывается более сложным. Средняя длительность ожидания является важной, но не исчерпывающей характеристикой работы систем. Весьма существенно выяснить также возможный разброс фактических длительностей ожидания около их среднего значения. Далее представляет интерес средняя длина очереди и распределение длины очереди. Важно также выяснить, насколько загружены обслуживающие приборы. Нет нужды говорить, что ситуация, которая создается около театральной кассы (как, впрочем, и около иной кассы), когда в нее обращаются за билетами, весьма напоминает описание системы обслуживания абонентов на телефонной станции. Если только в первоначальной постановке задачи шла речь о телефонных линиях, то теперь вопрос касается занятости кассира. Стремление рационально обслуживать потребителей приводит к необходимости изучения закономерностей образования очередей. Знание этих закономерностей должно, в частности, помочь решению вопроса о числе касс, которые рационально установить для продажи билетов на железнодорожной станции или в магазине. Содержание каждой кассы вызывает некоторые расходы, но и потеря требований также наносит некоторый ущерб. Возникает вопрос о разыскании некоторого оптимума. Быть может, в экономическом отношении еще важнее вопрос организации на крупных предприятиях пунктов выдачи инструмента. Если такой пункт один, то квалифицированные рабочие теряют много времени на получение необходимого им инструмента и, кроме того, простаивают станки, которые могли бы в это время работать. Если же таких пунктов много, то их работники будут слабо загружены. Само собой разумеется, что только что затронутые вопросы имеют общий интерес и возникают при расчете пропускной способности аэропортов, подъездных путей, шлюзов, портовых причалов, больниц и пр. В тридцатые годы в связи с автоматизацией станков в промышленности наметился переход на обслуживание одним рабочим нескольких станков. Станки в случайные моменты времени в силу тех или иных причин выходят из строя и требуют к себе внимания рабочего. Длительность операции по приведению станка в порядок, вообще говоря, не постоянна и является случайной величиной. Спрашивается, как велика вероятность того, что в определенный момент времени (при заданном режиме работы станка и рабочего) будет ожидать обслуживания то или иное число станков из общего числа порученных рабочему? Дальнейшие естественные и важные для практики вопросы таковы: как велико среднее время простоя станков при том или ином числе станков, порученных рабочему? Сколько станков при заданной организации труда экономически оправдано поручить одному рабочему? Как рациональнее организовать обслуживание: поручить ли п станков одному рабочему или tis станков 5 рабочим? Мы не станем сейчас продолжать перечисление дальнейших вопросов, которые возникают при глубоком анализе проблемы обслуживания нескольких станков. Известно, что в ряде отделов современного естествознания, в частности в ядерной физике, широко используются так называемые счетчики Гейгера — Мюллера. Одна из особенностей работы этого прибора состоит в том, что частица, попавшая в счетчик, вызывает в нем разряд. В первом приближении можно считать, что этот разряд продолжается некоторое определенное время т, в течение которого вновь попадающие в счетчик частицы уже не регистрируются счетчиком. По этой причине счетчик показывает, как правило, не истинную картину, а несколько искаженный ход явлений. В связи с этим возникает задача построения поправок к показаниям счетчиков. На первое место при этом выдвигается подсчет вероятности потерь того или иного числа частиц при регистрации их счетчиком за определенный промежуток времени t. Другая важная задача для многих конкретных вопросов состоит в том, чтобы по показаниям счетчика восстановить истинный поток частиц, поступающий в счетчик. Для многих реальных задач научного, производственного и экономического характера естественны не только задачи, в которых рассматривается обслуживание с потерями и ожидание без ограничения времени. В самом деле, мы по себе знаем, что зачастую мы отказываемся от обслуживания только из-за возможной длительной задержки с началом обслуживания. Так, если мы видим, что в очереди к продавцу имеется более пяти покупателей, то мы уходим из магазина и откладываем предполагаемую покупку. Точно так же, сделав заказ на междугородный телефонный разговор, мы нередко ограничены временем и предупреждаем, что если разговор не будет дан до определенного момента, то наше требование должно быть снято. Несколько иная ситуация может создаваться, когда ограничено не время ожидания, а время пребывания в системе обслуживания. С такой постановкой задачи приходится встречаться при продаже скоропортящихся продуктов: от момента изготовления до употребления должно пройти не более чем т единиц времени, так как иначе эти продукты теряют свои ценные качества и могут представлять угрозу для здоровья потребителя. В качестве другой реальной иллюстрации такой постановки вопроса мы приведем обслуживание лиц, попавших в уличную катастрофу. Для них время пребывания в системе обслуживания ограничено и при том ограничено случайной величиной т, поскольку способность лица дождаться конца обслуживания зависит от полученной травмы и от его физических качеств. Под временем нахождения в системе обслуживания мы должны понимать все время от момента аварии до момента излечения (т. е. ожидание кареты скорой помощи, транспортировку, осмотр врачом, операцию и излечение). Хорошо известно, что не каждое потерпевшее лицо способно дождаться конца обслуживания, а иногда даже его начала. Таким образом, вполне естественна постановка следующей группы близких по характеру задач. Требования, поступающие для обслуживания, остаются в очереди, если число ранее прибывших и ожидающих обслуживания требований не превосходит заданного числа &, в противном случае требование теряется. Каждое требование остается в обслуживающей системе не более чем время т, даже если началось его обслуживание. Возможна также и третья постановка вопроса: ограничено время ожидания величиной т, но если до истечения этого срока обслуживание началось, то оно доводится до конца. Во всех трех случаях особый интерес представляет вычисление среднего числа потерь за определенный промежуток времени, среднего времени ожидания начала обслуживания или потерянного времени на ожидание. Во второй постановке задачи естественно различать среднее число потерь не совсем обслуженных требований, обслуживание которых все-таки было начато. В только что обрисованных, но еще недостаточно строго математически поставленных задачах мы исходили из предположения, что обслуживающие приборы обладают абсолютной надежностью и сами никогда не выходят из рабочего состояния. Известно, что такое положение несколько идеализирует реальные системы. В результате возникает естественная и важная задача учета влияния на эффективность системы обслуживания порчи обслуживающих приборов. Изучение этой задачи началось совсем недавно. Возможное разнообразие практически интересных вопросов здесь совершенно не ограничено. Для примера укажем на такую задачу, самолеты после каждого вылета проходят профилактический осмотр, а затем с некоторой вероятностью а направляются в ремонт или с вероятностью 1 —сс возвращаются в строй действующих. Учет выхода обслуживающих приборов из рабочего состояния для некоторых постановок задач можно включить в иную задачу, которая получила название обслуживания с преимуществом. Эта задача состоит в следующем, в систему обслуживания поступает не один, а несколько потоков требований. Требования потоков с меньшими номерами пользуются преимущественным нравом обслуживания и становятся при появлении в очередь впереди всех ранее поступивших требований с более высокими номерами породивших их потоков. Здесь приходится рассматривать две постановки вопроса: требование высокого ранга не прерывает обслуживания требований менее высоких рангов; требование высокого ранга прерывает уже проводящееся обслуживание более низкого ранга. Во втором случае приходится различать две возможности: при возвращении вытесненного требования в обслуживающий прибор предыдущая работа забывается и обслуживание начинается сначала; ранее произведенная работа не забывается. С обеими последними постановками вопроса приходится встречаться, например, в работе вычислительных машин. Назовем поломку или сбой машины преимущественным требованием, тогда могут представиться оба случая; предыдущая работа была проделана хорошо и вычисления после восстановления машины могут начинаться с того места, на котором они были прерваны; сбой машины ввел ошибку в предшествующие вычисления, их нужно проделать заново. Этим примером мы одновременно пояснили, как в систему обслуживания с преимуществом можно включить задачу учета поломки обслуживающих устройств. Задача, в которой следует принимать в расчет преимущественные требования, встречается постоянно: междугородный вызов прерывает местный телефонный разговор, к зубному врачу вне очереди принимаются больные с острой зубной болью и т. д. Можно указать множество других постановок задач реального содержания, которые в своей математической части сводятся к вопросам теории массового обслуживания. Но в столь подробном перечислении нет никакой необходимости, так как математическая теория не может претендовать на перечисление всех частных и даже только важнейших прикладных проблем, к которым она может применяться. Задача математической теории состоит в первую очередь в выработке общих методов, применимых не только к решению тех частных задач, на базе которых была начата ее разработка, но и множества других, быть может, даже очень далеких по своей формулировке от первоначальных. В последние годы появилось несколько монографий и учебных руководств по теории массового обслуживания. Мы упомянем в первую очередь книги А. Я. Хинчина [1], А. Бодино и Ф. Брамбилла [1], Л. Такача [1], Р. Сиски 1], Т. Саати [1], Дж. Риордана [1], В. Бенеша [1], Ле Галля ш- Среди названных своей полнотой выделяются книги Сиски, Саати и Ле Галля. Книги Хинчина, Такача, Бенеша и Ле Галля отмечены глубиной математического анализа. В книгах Сиски, Саати, а также в книге Баруча-Райда ш имеются прекрасные библиографические сводки. Им во многих отношениях уступает даже специальная библиография, составленная Алисой Дойг [1]. ГЛАВА 1 ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ В ПРОСТЕЙШИХ ПРЕДПОСЫЛКАХ § 1. 1. Простейший поток 1. Исторические замечания. Первичной задачей, с которой должно начаться каждое серьезное исследование по теории массового обслуживания или же по конкретным ее применениям, нужно считать изучение того потока требований, который поступает на обслуживающий прибор. Так, для расчета потерь частиц счетчиком необходимо знать, как поступают эти частицы в счетчик извне. Точно так же при организации работы телефонной станции нужно учитывать особенности потока вызовов, поступающих от абонентов на станцию. В подавляющем большинстве работ по теории массового обслуживания, как тех из них, которые послужили базой построения теории, так и современных, рассматривается простейший случай потоков, когда вероятность поступления в промежуток времени t ровно к требований задается формулой где к 0 — постоянное число, смысл которого вскоре будет изучен. Поступающий поток при этом считается таким, что для любой конечной группы непересекающихся отрезков времени числа появившихся на их протяжении требований представляют собой взаимно независимые случайные величины. Попытка указать достаточно общие условия, при выполнении которых такой поток действительно имеет место, были предприняты давно. Так, в §§ 81 и 82 известной книги Торнтона Фрая [1] даны понятия случайности в индивидуальном и коллективном смысле слова и показано, что при совместном их выполнении поток требований должен быть пуассоновским только что указанного вида. Нельзя сказать, что рассуждения Т. Фрая были исчерпывающими, но они указывали практикам достаточно широкие условия, при которых простейший поток оказывается единственно возможным. Несколько иные условия ранее рассмотрены М. Смолуховским и А. Эйнштейном [1] в их работах, посвященных теории броуновского движения. В монографии А. Я. Хинчина [2] эти условия были приведены к трем следующим: стационарность, отсутствие последействия, ординарность. Четвертое условие (см. стр. 16), которое постоянно отмечается в учебной литературе по теории вероятностей, как показал А. Я. Хинчин, является следствием перечисленных. В настоящем параграфе мы изучаем только этот подход. В последние годы появился ряд других подходов к получению потока Пуассона. С ними можно познакомиться пора-ботам Дж. Дуба [1], Р. Л. Добрушина [1], Бреймана [1]. О работах и результатах А. Я. Хинчина [2], Г. А. Ососкова [1], А. Реньи [1], Ю. К. Беляева [1] будет сообщено ниже. 2. Качественные предпосылки. Перейдем к краткому анализу только что перечисленных трех условий, обращая при этом особое внимание на их содержательный, физический смысл. Такой анализ крайне необходим, особенно если мы учтем важность тех выводов теоретического характера и практических приложений, которые базируются на указанных предпосылках. Стационарность потока означает, что для люоой группы из конечного числа непересекающихся отрезков времени вероятность появления в них соответственно klt k%, ... k требований зависит только от этих чисел и от длин указанных промежутков времени, но не зависит от их расположения на оси времени. В частности, вероятность появления k требований в промежутке времени (Т, T+t) не зависит от Т и является функцией только переменных & и t. Отсутствие последействия состоит в том, что вероятность поступления k требований в течение промежутка времени (Г, T-\-t) не зависит от того, сколько требований и как поступали до этого промежутка. Таким образом, это предположение означает, что условная вероятность поступления k требований за промежуток (Г, вычисленная при произвольном предположении о поступлениях требований до этого промежутка времени, совпадает с безусловной вероятностью того же события. В частности, отсутствие последействия означает взаимную независимость появления того или иного числа требований на обслуживание в неперекры-вающихся отрезках времени. Ординарность потока требований выражает собой условие практической невозможности появления двух или нескольких требований в один и тот же момент времени. Это условие точнее сформулируем следующим образом: обозначим через вероятность появления в промежутке длины h двух или более требований. Условие ординарности потока состоит в том, что при или, как мы станем записывать впоследствии, Поток требований, удовлетворяющий трем сформулированным условиям, принято называть простейшим потоком. 3. Анализ предпосылок. Перейдем теперь к анализу высказанных условий, определяющих простейший поток. Экспериментальная проверка, предпринятая в различных областях знаний — физике, телефонном деле, теории надежности (отказы элементов систем), транспорте, торговле и пр., — показала, что простейший поток наблюдается не так часто, как это предполагалось первоначально. Собственно, такого заключения можно было ожидать и до получения результатов экспериментальных исследований. Действительно, предположение стационарности в реальной обстановке является довольно сильной абстракцией. На самом деле оно нарушается в силу большого числа различных причин. В явлении радиоактивного распада необходимо учитывать, что со временем масса вещества, способного к распаду, уменьшается и тем самым стационарность в строгом смысле этого слова отсутствует. Поток вызовов, поступающий на телефонную станцию, не может считаться вполне стационарным, так как в течение суток режим работы станции существенно меняется. Поток вызовов скорой медицинской помощи, оказывается, также существенно зависит от времени суток. Однако если рассматривать явления в сравнительно ограниченные промежутки времени, то предположение стационарности может служить достаточно удовлетворительным первым приближением. Гипотеза отсутствия последействия во многих случаях также должна считаться недостаточно обоснованной. Имеются многочисленные явления, в которых наступление одного события влечет за собой появление других. Скажем, один телефонный звонок может повлечь за собой большое число звонков к другим абонентам. Другой пример — радиоактивный распад. В случае, когда имеется большое количество нераспавшегося вещества, то распад атома может вызвать распад других, в результате чего произойдет цепная реакция. Однако если взято небольшое количество вещества, то гипотеза отсутствия последействия достаточно удовлетворительна. Цепная реакция телефонных звонков оказывает на работу станции ничтожное влияние из-за наличия огромного числа других абонентов. Предположение ординарности потока во многих случаях оказывается выполненным далеко не с полной строгостью. Известно, например, что в магазины и в билетные кассы обращаются сразу группами. В речной порт под разгрузку поступают не только самоходные баржи, но и караваны барж, приводимых одним буксиром. К шлюзу подходит не только отдельный пароход, но и буксир с баржами. Подобные же появления групп событий наблюдаются и во многих физических явлениях. Несмотря на то, что три условия, о которых только что шла речь, как правило, не выполняются со всей определенностью, они могут служить хорошим отправным пунктом для изучения реальных потоков. Позднее мы выясним, какое влияние оказывает на характер потока каждое из указанных условий. 4. Вывод уравнений простейшего потока. Обозначим через Pk (tf) вероятность того, что в течение промежутка времени длительности t к обслуживанию будут предъявлены k требований. В силу стационарности потока эта вероятность не зависит ни от выбора начала отсчета, ни от всей его предыстории. Условия, определяющие простейший поток, позволяют однозначно, с точностью до одного параметра, найти формулы для вероятностей Pk(t). |
