О НЕКОТОРЫХ ПОСТАНОВКАХ ЗАДАЧ И РЕЗУЛЬТАТАХ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Б. В. Гнеденко

Со времени выхода в свет первого издания монографии А. Я. Хинчина по теории массового обслуживания интерес к этому направлению исследований неизмеримо возрос как в Советском Союзе, так и за его пределами. За этот срок появились многочисленные оригинильные исследования, посвященные решению как чисто прикладных, так и теоретических вопросов. Методы исследования стали более разнообразны и гибки. Одновременно круг применений теории стал вначительно более широким. Если в двадцатые годы отдельные вопросы теории массового обслуживания возникали лишь в практике организации телефонных сетей, то теперь к вопросам телефонного дела добавились разнообразнейшие и интересные задачи ядерной физики, автоматизации производства, эксплуатации аэропортов, морских причалов, автомобильных хозяйств, железнодорожных станций, больниц, ремонтных пунктов, предприятий массового обслуживания населения (магазинов, пунктов проката, билетных касс и пр.). В связи с таким увеличением прикладной роли теории массового обслуживания за последние несколько лет появились хорошие обзоры, приспособленные преимущественно к нуждам практиков. В первую очередь при этом, пожалуй, следует назвать обзорную статью Т. Саати [1], позднее перепечатанную в несколько измененном виде в его книге [2], посвященной изложению содержания новой научной дисциплины, известной под названием исследования операций. Более математический характер носят статья Л. Такача [1] и обзор, составивший главу 9 недавно появившейся книги Баруча Райда [1].

Из довольно многочисленных теперь монографий по теории массового обслуживания хотелось бы упомянуть книги Авондо

Бодино и Бромбилла [1], Кокга и В. Смита [1], Л. Такача [2], Р. Сиски [1], Т. Саати [3], Дж. Риордэна [1]. Каждая из названных книг представляет известный интерес, однако в первую очередь хотелось бы выделить среди них монографии Р. Сиски и Т. Саати. Первая из них представляет собой подробную сводку результатов по теории массового обслуживания, связанных с задачами телефонного дела. Вторая книга ставит перед собой более широкие цели — изложение основных результатов, полученных относительно важнейших в теоретическом и прикладном отношениях задач теории массового обслуживания.

В существующей монографической литературе по теории массового обслуживания книга А. Я. Хинчина занимает значительное место, поскольку в ней впервые было систематически изучено строение входящего потока требований, а также распределение времени ожидания для системы с очередью при обслуживании ее одним прибором. Заметим, что именно в этой монографин А. Я. Хинчин изложил свои достаточные условия близости суммарного потока, слагаемые которого независимы и равномерно малы, к простейшему потоку. По сути дела, как это выяснил ученик А. Я. Хинчина Г. А. Ососков, условия Хинчина являются и необходимыми.

Ниже мы изложим некоторые вопросы, решению которых последнее время уделялось значительное внимание.

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

Первичным понятием теории массового обслуживания, изучению которого большое внимание уделил А. Я. Хинчин, является понятие потока требований, поступающих на систему обслуживания. Кратко мы будем называть его входящим потоком. В том виде, в каком понятие потока до сих пор встречалось в литературе, оно укладывается в общее понятие случайного процесса. Это обстоятельство четко отмечено в § 6 книги Хинчииа, где сказано, что поток требований является не чем иным, как дискретным случайным процессом, принимающим толькоцелочисленныенеотрицательныезначения. Нужно, однако, отметить, что такой подход становится теперь уже недостаточным, так как в ряде важных задач необходимо изучать поток требований не только во времени, но и в пространстве. Отсюда возникает мысль о следующем определении.

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

абсолютно аддитивная функция множества

принимает лишь неотрицательные целочисленные значения.

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

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

Не изменяя известных рассуждений монографии Хинчине, легко доказать, что поток г) тогда и только тогда определяется равенствами

(простейший поток), где постоянная, мера множества А, когда выполнены условия стационарности, ординарности и отсутствия последействия.

Более того, многие теоремы, доказанные Хинчиным относительно строения потоков и помещенные в настоящей книге, легко переносятся и на приведенное здесь определение потока.

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

Позднее И. Б. Погожев заинтересовался вопросом быстроты сближения с пуассоновским распределением в зависимости от числа слагаемых потоков. Для случая одинаково распределенных независимых стационарных потоков он нашел первый член асимптотического разложения по степеням (работа не опубликована, докладывалась на семинаре по теории массового обслуживания, МГУ, 1961 г.). Более детальное исследование этого вопроса в тех же условиях под влиянием доклада И. Б. Погожева было проведено П. Франкеиом. Б. И. Григелионис применил к доказательству предельной теоремы Хинчина-Ососкова методы классической теории суммирования. Случай суммирования нестационарных потоков изучен Б. И. Григелионисом. Им найдены необходимые и достаточные условия сближения суммарного потока с нестационарным пуассоновским; эти условия особенно просты в том случае, когда суммируются потоки типа процессов восстановления. Им же рассмотрен во всей полноте вопрос асимптотического разложения.

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

группы, поступает на прибор второй группы и т. д., интерес представляет не только поток входящих требований, но и те новые потоки, которые образуются требованиями, уже обслуженными приборами первой группы (или же получившими на них отказ), а также второй и последующими группами приборов. С такой ситуацией приходится иметь дело во многих реальных проблемах, в частности при расчете автоматических линий. К сожалению, это направление исследований находится совсем в зачаточном состоянии. Кроме результата Пальма, сформулированного и доказанного в монографии А. Я. Хинчина «Математические методы теории массового обслуживания» (стр. 107, § 28), можно отметить несколько статей Н. В. Яровицкого [1], [2]. Н. В. Яровицкий подверг систематическому изучению поток выходящих после обслуживания требований и ввел в рассмотрение односвязно зависимые потоки. Мы направляем читателя за определением потоков этого типа и их свойствами к указанным работам автора.

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

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

Если к потоку А с ограниченным последействием и конечной интенсивностью К применить последовательность операций разряжения и при

то поток стремится к простейшему потоку интенсивности

Обобщение этого результата было дано Ю. К. Беляевым.

Им же [1] был указан одни тип потоков, представляющий интерес для теории массового обслуживания.

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

Системы с потерями. Классическая проблема обслуживания с потерями за последние годы получила значительное развитие и в некоторых аспектах может считаться уже исчерпывающе разрешенной. Так, в примечаниях к тексту второй части монографии Хинчина было отмечено (стр. 84), что формулы Эрланга сохраняют свой вид в случае, когда обслуживается стационарный пуассоновский поток приборами одинаковой производительности, а функция распределения длительности обслуживания произвольна с конечным математическим ожиданием. Метод доказательства, примененный Б. А. Севастьяновым [1], оказался особенно удачным. Выяснилось, как мы отчасти увидим позднее, что его рассуждения применимы ко многим задачам более сложной природы.

Другое направление обобщений формул Эрланга было развито Пальмом [1] и Такачем [2], [3]. Они рассмотрели случай, когда на обслуживающую систему поступает произвольный поток типа Пальма, а длительность обслуживания каждого требования (на каждом приборе) имеет распределение

В работе [3] Л. Такач обобщил эту постановку задачи на следующую схему: требование остается в системе, если имеется хотя бы один свободный обслуживающий прибор или если число ожидающих требований не превосходит заданного числа в противном случае требование покидает систему обслуживания.

А. Шахбазов рассмотрел случай обслуживания пуассоновского потока требований (с потерями) приборами разной производительности.

В последних работах В. Бенеша [1] имеются попытки изучить вероятность потери при обслуживании произвольного нестационарного потока.

Еще в 1918 г., вскоре после опубликования работы К. Эрланга, Энгсет обобщил результат Эрланга на случай обслуживания конечного множества потребителей, каждый из которых может предъявить требование в случайный момент времени. К этой задаче возвращались неоднократно, в частности при изучении простоев механизмов, обслуживаемых одним рабочим или бригадой. Мы укажем на большое исследование Ж. Коэна [1]. В теоретическом и прикладном отношениях исключительно интересно при этом учесть то обстоятельство, что требование, получившее отказ, вновь и вновь предъявляет свои претензии к системе обслуживания.

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

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

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

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

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

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

Следующая задача в том же круге идей была рассмотрена Г. П. Климовым. Имеется группа однотипных приборов и вадаиного объема накопитель, в котором требовачия могут ожидать освобождения приборов. Требования, попавшие в систему, когда накопитель полон, теряются. На систему обслуживания поступает пуассоновский поток с параметром Спрашивается, как выбрать чтобы итог работы системы за время был максимален. Итог

оценивается функционалом Длительность обслуживания случайна и имеет показательное распределение: 1—

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

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

Системы с ожиданием. Пожалуй, максимальное число работ, относящихся к теории массоаого обслуживания, посвящено изучению образования очередей в системах с ожиданием. Распределение длительности ожидания, условия образования увеличивающейся очереди, распределение длительности непрерывной занятости прибора — вот примерный перечень вопросов, которым было уделено много внимания. Особенно интересовал исследователей случай одного обслуживающего прибора. Мы знаем, что для пуассоновского потока и произвольного распределения длительности обслуживания общие результаты были получены А. Я. Хинчиным. Изящные результаты были получены здесь также Линдли, Л. Такачем, А. Шахбазовым [1] и др. Линдли получил интегральное уравнение для распределения длительности ожидания начала обслуживания в случае одного прибора для произвольного пальмовского потока и произвольного распределения длительности обслуживания. Это интегральное уравнение дало ему возможность заключить, когда очередь будет расти неограничено и когда распределение величины очереди стремится к стационарному состоянию.

Обслуживание одним прибором неординарного потока было предметом исследований Гэйвера [1], Миллера [1] и Шахбазова [1]. А. Шахбазов ввел усложнение, представляющее интерес для теории надежности, а именно: он предположил дополнительно, что прибор, начиная обслуживание требования без предварительного ожидания его освобождения, требует времени на «разогрев».

Киффер и Вольфовиц [1], [2] исследовали обслуживание произвольного пальмовского потока при условии произвольного распределения длительности обслуживания

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

Известно, что если интенсивность поступления требований в систему равна средней производительности системы, то длина очереди со временем возрастает неограничено (за исключением тривиального случая регулярного поступления требований, равного длительности обслуживания). Возникает вопрос изучения асимптотического поведения различных характеристик обслуживания. Этот вопрос интересовал многих исследователей. Я приведу здесь результаты И. Н. Коваленко.

Пусть -интенсивность входящего потока, — средняя длительность обслуживания одного требования, число обслуживающих приборов равно единице и где Если то средняя длительность времени ожидания начала обслуживания будет расти, имея порядок Функция распределения длительности ожидания у подчинена такому предельному распределению

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

Точно так же, если дисперсия времени обслуживания конечна, то для распределения числа требований в системе имеет место предельная теорема: при

Большое внимание уделялось последние годы изучению обслуживания с очередью при наличии преимущественных требований. Система обслуживания может быть описана таким образом: имеется классов требований, каждый из которых образует простейший поток; потоки между собой независимы. Внутри каждого класса обслуживание производится в порядке строгой очередности. Различаются две схемы: обслуживание без прерывания (английский термин — head of the line) и обслуживание с прерыванием (preemtive priority). Предположим, что в некоторый момент времени происходит обслуживание требований класса и поступает требование класса для первой схемы вновь

поступившее требование ожидает окончания обслуживания низшего класса, но вато немедленно занимает первую освободившуюся линию, еслн только перед ним не было требований того же или более высокого класса. Вторая схема в свою очередь подразделяется на две категории: в первой из них учитывается время, уже потраченное на его обслуживание (preemptive resume), во второй (preemptive repeat) это время теряется и обслуживание начинается сначала. Отметим здесь лишь работу Миллера [2], в которой указаны предшествующие исследования, а также для случая даны такие характеристики: производящая функция стационарных вероятностей числа преимущественных и непреимущественных требований, находящихся в пункте обслуживания, преобразования Лапласа для функций распределения времени обслуживания и периода занятости, а также для числа требований, обслуженных за один период занятости.

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

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

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

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

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

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

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

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

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

длины очереди. Исходя из разных прикладных задач, почти одновременно ряд авторов пришли к постановке бливких задач теории обслуживания в таких условиях:

1) требование, поступившее в систему обслуживания, ожидает начала обслуживания в течение времени (вообще говоря, случайное);

2) требование остается в системе обслуживания не более чем время (даже в том случае, если его начали обслуживать, но длительность обслуживания превышает

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

Случай был детально исследован И. Н. Коваленко [1]. В этой работе он рассмотрел несколько более широкую схему, чем мы только что наметили. В ней учтено то обстоятельство, что длительность пребывания зависит от того, сколько времени требование ожидало начала обслуживания.

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

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

Отметим, что в этой небольшой обзорной статье не было возможности даже только упомянуть все наиболее интересные работы. Довольно полная библиография (до 1957 г.) составлена Дойгом [1]. Она может служить хорошим дополнением к библиографии, имеющейся в уже упомянутых книгах Сиски и Саати.

(см. скан)

(см. скан)