книги из ГПНТБ / Приоритетные системы обслуживания
..pdf
ПРИОРИТЕТНЫЕ
СИСТЕМЫ
ОБСЛУЖИВАНИЯ
И З Д А Т Е Л Ь С Т В О МОСКОВСКОГО УНИВЕРСИТЕТА
19 7 3
Г О С . П У Б Л И Ч Н А Я |
' |
Н А У ч н о - т е х! ?s*4tstfA« |
, |
Б И Б Л И О Т Е К А ИШ¥ „ . 1 |
-\()ЦГ<1 УДК 519.21 |
|
Приоритетные системы обслуживания — один из наи более интенсивно развивающихся разделов теории мас сового обслуживания. Эти системы находят широкое применение в теории связи, при обработке информации, проектировании вычислительных систем, автоматизации производственных процессов, в вопросах медицинского обслуживания населения и т. п. До сих пор на русском языке не было систематического изложения этого раз дела. Эта монография восполняет пробел. Методы, используемые здесь, основаны на введении дополни тельного события, которое позволяет многим форму лам придать наглядный вероятностный смысл. Кроме того, затронуты также вопросы асимптотики приоритет ных систем.
Книга рассчитана на математиков, инженеров, студен тов и аспирантов, интересующихся проблемами теории массового обслуживания.
Авторы монографии:
Б. В. Г н е д е н к о, Э. А. Д а н и е л я н, Б. Н. Д и м и т р о в, Г. П. К л и м о в , В. Ф. М а т в е е в
Рецензенты:
докт. физ.-матем. наук Ю. К. Беляев, докт. физ.-матем. наук А. Д. Соловьев
Печатается по постановлению Редакционно-издательского совета Московского университета
(С)Издательство Московского университета, 1973 г.
П0223—095 99—73 077(01)—73
|
|
|
|
|
|
|
О Г Л А В Л Е Н И Е |
|
|
|
|
|||
П р е д и с л о в и е |
|
|
|
|
|
|
|
" |
|
|
|
7 |
||
О б о з н а ч е н и я |
|
|
|
|
|
|
|
|
|
|
|
9 |
||
|
|
|
|
|
|
|
|
|
Ч А С Т Ь |
I |
|
|
|
|
|
|
|
Неприоритетные системы M | G111 оо |
|
|
|
|
|||||||
Г л а в а |
1. Система с абсолютно надежным прибором |
|
|
|
10 |
|||||||||
§ |
1. |
Дополнительное |
событие |
|
|
|
|
10 |
||||||
§ |
2. |
Период |
занятости |
|
|
|
|
|
|
|
|
11 |
||
§ |
3. |
Число вызовов, обслуженных за период занятости |
|
. . . . |
17 |
|||||||||
§ |
4. |
Длина очереди в периоде занятости |
|
|
|
|||||||||
§ |
5. |
Число вызовов, обслуженных внутри периода |
занятости . . . |
20 |
||||||||||
§ |
6. |
Виртуальная |
длина |
|
очереди |
|
|
|
|
23 |
||||
§ |
7. |
Возможное |
число |
обслуженных |
вызовов |
|
|
|
25 |
|||||
§ |
8. |
Совместное распределение длины очереди и числа |
обслуженных |
27 |
||||||||||
|
|
вызовов |
|
|
|
|
|
|
|
|
|
|
||
§ |
9. |
Время |
ожидания |
|
|
|
|
|
|
|
|
29 |
||
§ |
10. |
Виртуальное |
время |
|
ожидания |
|
|
|
|
31 |
||||
§ |
11. |
Метод |
вложенных |
|
цепей |
Маркова |
|
|
|
33 |
||||
Г л а в а |
2. Система с прибором, подверженным поломкам одного типа . |
38 |
||||||||||||
§ |
1. |
Описание системы |
|
|
|
|
|
|
|
|
39 |
|||
§ |
2. |
Период занятости, начинающийся с п вызовов |
|
|
39 |
|||||||||
§ |
3. |
Виртуальная |
длина |
очереди |
|
|
|
|
44 |
|||||
§ |
4. |
Число вызовов, обслуженных за время t |
|
|
|
49 |
||||||||
§ |
5. |
Совместное распределение длины очереди и числа |
обслуженных |
52 |
||||||||||
|
|
вызовов |
|
|
|
|
|
|
|
|
|
|
||
§ |
6. |
Время |
ожидания |
|
|
|
|
|
|
|
|
53 |
||
§ |
7. |
Виртуальное |
время |
|
ожидания |
|
|
|
|
58 |
||||
§ |
8. |
Метод |
вложенных |
|
цепей |
Маркова |
|
|
|
64 |
||||
§ |
9. |
Инверсионный порядок |
обслуживания. Время |
ожидания и время |
68 |
|||||||||
|
|
пребывания |
в |
системе |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
Ч А С Т Ь |
II |
|
|
|
|
Приоритетные |
системы |
M r |
| G r |
111 °° с абсолютно надежным |
прибором |
|
||||||||
Г л а в а |
3. Период занятости приоритетных систем |
|
|
|
72 |
|||||||||
§ |
1. |
Обозначения |
и |
точные |
определения |
|
|
|
72 |
|||||
§ |
2. |
Распределение периода занятости систем без |
прерывания . . |
74 |
||||||||||
§ |
3. |
Системы с прерыванием. Схема |
1 (потеря прерванного |
вызова). |
76 |
|||||||||
|
|
Период |
занятости |
|
|
|
|
|
|
|
|
|||
§ |
4. |
Системы с прерыванием. Схема 3 (обслуживание заново). Пери |
81 |
|||||||||||
§ |
5. |
од занятости |
|
|
|
|
|
|
|
|
|
|||
Совместное |
распределение периода занятости и числа |
обслужен |
84 |
|||||||||||
|
|
ных за |
этот |
период |
вызовов |
|
|
|
|
|||||
3
Г л а в а |
4. Система |
с |
относительным |
приоритетом |
|
|
|
|
|
9С |
|||||||||||||
§ |
1. |
Изучение |
при |
помощи |
системы |
M | G | l | o o |
с ненадежным прибо |
|
|||||||||||||||
|
|
ром |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
92 |
§ |
2. |
Виртуальная |
длина |
очереди |
|
|
|
|
|
|
|
|
|
|
99 |
||||||||
§ |
3. |
Виртуальное |
время |
ожидания |
|
|
|
|
|
|
|
|
|
106 |
|||||||||
§ |
4. |
Инверсионный порядок обслуживания. Время |
ожидания . . . |
112 |
|||||||||||||||||||
§ |
5. |
Вложенные цепи Маркова. Длина очереди |
и |
время |
ожидания . |
114 |
|||||||||||||||||
§ |
6. |
Об одной |
интересной |
закономерности |
|
|
|
|
|
|
127 |
||||||||||||
Г л а в а |
5. Система |
с |
абсолютным приоритетом (схемы с прерыванием) . |
129 |
|||||||||||||||||||
§ 1. Связь |
между |
системами с абсолютным приоритетом и неприори- |
|
||||||||||||||||||||
|
|
тетнои |
|
. . . |
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
130 |
|||
§ |
2. |
Совместное распределение виртуальных времен ожидания для |
|
||||||||||||||||||||
|
|
вызовов |
различных |
приоритетных |
классов |
|
|
|
|
|
134 |
||||||||||||
§ |
3. |
Метод вложенных цепей Маркова для схемы 2 |
|
|
|
139 |
|||||||||||||||||
§ |
4. |
Виртуальная |
длина |
очереди |
|
|
|
|
|
|
|
|
|
|
148 |
||||||||
Г л а в а |
6. Система |
с |
чередованием |
приоритетов |
|
|
|
|
|
|
153 |
||||||||||||
§ |
1. Метод вложенных цепей Маркова |
|
|
|
|
|
|
|
154 |
||||||||||||||
§ |
2. |
Виртуальное |
время |
ожидания |
|
|
|
|
|
|
|
|
|
159 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Ч А С Т Ь |
I I I |
|
|
|
|
|
|
|
|
||
Приоритетные |
системы |
M r | G r | l | o o |
с |
ненадежным |
прибором |
|
|||||||||||||||||
Г л а в а |
7. Предельные теоремы и асимптотика приоритетных |
систем . |
169 |
||||||||||||||||||||
§ |
1. Предельные |
распределения |
при |
нагрузке, |
близкой |
к |
единице . |
169 |
|||||||||||||||
§ |
2. |
Предварительные |
сведения |
и |
результаты |
|
|
|
|
|
173 |
||||||||||||
§ |
3. |
Особые точки функций як (s) и |
со* (s) |
в |
случае |
|
показательного |
176 |
|||||||||||||||
|
|
распределения |
длительности |
обслуживания |
|
|
|
|
|||||||||||||||
§ |
4. |
Асимптотические оценки для периода занятости |
|
|
|
178 |
|||||||||||||||||
§ |
5. |
Асимптотика |
|
времени |
ожидания |
|
|
|
|
|
|
|
184 |
||||||||||
Г л а в а |
8. Система |
с |
относительным |
приоритетом |
первого |
типа . |
195 |
||||||||||||||||
§ |
1. Описание |
систем |
обслуживания |
|
|
|
|
|
|
|
|
195 |
|||||||||||
§ |
2. |
Одно |
вспомогательное |
соотношение |
|
|
|
|
|
|
197 |
||||||||||||
§ |
3. |
Метод |
|
вложенных |
цепей |
|
Маркова |
|
|
|
|
|
|
|
199 |
||||||||
§ |
4. |
Метод |
|
вложенных |
цепей |
Маркова |
(продолжение) . . . |
205 |
|||||||||||||||
§ |
5. |
Виртуальное |
время |
ожидания |
|
|
|
|
|
|
|
|
|
208 |
|||||||||
§ 6. Виртуальная длина очереди |
|
|
|
|
|
|
|
|
|
|
214 |
||||||||||||
Г л а в а |
9. Система с относительным приоритетом второго типа. Неиден |
|
|||||||||||||||||||||
тичное обслуживание |
заново |
прерванного вызова |
|
|
|
|
225 |
||||||||||||||||
§ |
1. Производящая |
функция |
числа |
вызовов |
в |
системе |
|
. . . . |
226 |
||||||||||||||
§ |
2. Стационарное |
распределение |
времени |
ожидания |
|
вызовом при |
|
||||||||||||||||
|
|
оритета |
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
• |
|
|
|
230 |
|
§ |
3. |
Виртуальное |
время |
ожидания |
|
|
|
|
|
|
|
|
|
234 |
|||||||||
§ |
4. |
Виртуальная |
длина |
очереди |
|
|
|
|
|
|
|
|
|
|
238 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Ч А С Т Ь |
I V |
|
|
|
|
|
|
|
|
||
Однолинейные |
системы |
многоэтапного |
обслуживания |
с |
приоритетом |
|
|||||||||||||||||
Г л а в а |
10. Система |
с |
приоритетом |
|
|
|
|
|
|
|
|
|
|
247 |
|||||||||
§ |
1. Описание |
и |
характеристики |
системы |
|
|
|
|
|
|
247 |
||||||||||||
§ |
2. |
Дополнительные |
замечания, |
обозначения |
|
|
|
|
|
251 |
|||||||||||||
§ |
3. |
Полное время пребывания вызова на приборе |
|
|
|
253 |
|||||||||||||||||
§ |
4. |
Число поступивших в систему вызовов за полное время пребы |
|
||||||||||||||||||||
|
|
вания на приборе отдельного вызова |
|
|
|
|
|
|
259 |
||||||||||||||
§ |
5. |
Период |
занятости |
системы |
|
|
|
|
|
|
|
|
|
|
263 |
||||||||
§ |
6. |
Период занятости прибора вызовом типа ѵ |
|
|
|
|
275 |
||||||||||||||||
§ |
7. |
Число |
|
обслуженных за |
период |
занятости |
системы |
вызовов . . |
279 |
||||||||||||||
4
§ |
8. |
Вложенная |
цепь |
Маркова |
|
|
285 |
||||
§ |
9. |
Длина |
очереди |
|
|
|
|
287 |
|||
§ |
10. |
Время |
ожидания |
до |
первого поступления на |
обслуживание . . |
294 |
||||
§ |
11. |
Время полного обслуживания отдельного вызова |
299 |
||||||||
§ |
12. |
Число поступивших в систему вызовов за время полного обслу |
|
||||||||
|
|
живания |
отдельного |
вызова |
|
301 |
|||||
§ |
13. |
Общее |
время |
пребывания |
в системе отдельного вызова . . . |
303 |
|||||
Г л а в а |
11. Системы с приоритетом и дополнительными допущениями . |
304 |
|||||||||
§ |
1. |
«Разогрев» |
прибора |
|
|
|
304 |
||||
§ |
2. Этапы |
прерывания и настройки прибора |
|
3!6 |
|||||||
§ |
3. |
Системы |
с |
разветвленной |
структурой обслуживания . . . . |
337 |
|||||
§ |
4. |
Неординарный |
поток |
вызовов, ненадежный |
прибор . . . . |
345 |
|||||
|
|
|
|
|
Ч А С Т Ь |
V |
|
|
|
|
Приложение методов |
приоритетных |
систем к одной производственной |
|
|||||||
|
|
|
|
|
системе |
|
|
|
|
|
Г л а в а |
12. Система с конечным числом источников, абсолютным приори |
|
||||||||
тетом и ограничениями |
|
|
|
|
|
357 |
||||
§ |
1. Детерминированная |
система |
управления |
конечным числом |
объ |
|
||||
|
|
ектов |
|
|
|
|
|
|
|
357 |
§ |
2. |
Приоритетная |
система с ограничением на |
время ожидания |
. . |
367 |
||||
Д о п о л н е н и я |
|
|
|
|
|
|
|
377 |
||
§ |
1. |
Пуассоновый |
поток |
|
|
|
|
|
377 |
|
§ |
2. |
Рекуррентный |
поток |
|
|
|
|
|
378 |
|
§ |
3. |
Регенерирующий процесс |
|
|
|
|
379 |
|||
§ |
4. |
Функция восстановления. Теорема Смита |
|
|
379 |
|||||
§ |
5. |
Тождество |
Вальда |
|
|
|
|
|
381 |
|
§ |
6. |
Одна предельная теорема для цепи Маркова |
|
381 |
||||||
§ |
7. |
Тауберова |
теорема |
|
|
|
|
|
382 |
|
§ |
8. |
Некоторые |
сведения |
из анализа |
|
|
|
383 |
||
§ |
9. |
Некоторые |
свойства |
случайных |
величин |
|
|
384 |
||
О б з о р п р и о р и т е т н ы х с и с т е м |
|
|
|
|
387 |
|||||
Литература |
|
|
|
|
|
|
|
439 |
||
Предисловие
Теория массового обслуживания за короткий период време ни превратилась из очень специальной области исследований, свя занной лишь с задачами телефонной связи, в обширную область исследований, в которой нуждаются самые разнообразные направ ления практической деятельности. Одновременно с расширением поля практических приложений расширялся и круг собственно математических вопросов, которыми стала заниматься эта теория. Многие из этих вопросов еще только поставлены и их решение тре бует длительной и настойчивой работы. Предлагаемая книга по священа теории однолинейных систем обслуживания с приорите том.
Практические аспекты обслуживания с приоритетом необычай но широки и разнообразны. Сюда относятся и многочисленные задачи теории связи, и вопросы медицинского обслуживания насе ления, и проблемы обработки информации, и важные аспекты про ектирования вычислительных систем, и задачи автоматизации производственных процессов. Вот почему можно высказать уверен ность в том, что эта первая книга на русском языке, посвященная специально задачам обслуживания с приоритетом, потенциально имеет буквально неограниченный круг читателей. Этой книгой мо гут заинтересоваться математики и экономисты, инженеры и орга низаторы производства, специалисты по проблемам высшей нерв ной деятельности и работники транспорта.
Конечно, было бы наивно думать, что книга, посвященная математической теории вопроса, может содержать решение каждой частной задачи практики. Однако широкий спектр возможных по становок вопросов в ней затронут и предложены методы, которые можно использовать в многочисленных частных и специальных постановках практически важных вопросов.
Авторы книги в течение ряда лет разрабатывают различные аспекты теории приоритетного обслуживания. Разработанные ими методы исследования в значительной степени опираются на пред ложенный Г. П. Климовым прием катастроф. Эти методы оказа лись весьма удачными и приспособленными к обобщениям. Чита тели заметят, как от главы к главе выявляется эта особенность методов.
Книга состоит из пяти частей и обзора.
7
В части I на примере бесприоритетной системы обслуживания читатель может познакомиться с методами, используемыми в даль нейшем. Наряду с новым изложением уже известных результатов приводятся ранее неизученные характеристики систем.
Вчасти I I проводится анализ различных одноэтапных приори тетных систем.
Вчастности, при помощи асимптотических методов выводятся формулы для некоторых характеристик систем. Обобщению ряда
результатов, изложенных в части I I |
на случай ненадежного при |
|
бора, посвящена часть I I I . |
|
|
Исследование многоэтапных приоритетных систем составляет |
||
содержание части IV. |
|
|
В частности, рассмотрены системы с так называемым |
смешан |
|
ным приоритетом и с разветвленной |
структурой обслуживания. |
|
Многие задачи этой части возникли |
из моделирования |
организа |
ции работы ЭВМ. Так, система с прерыванием и настройкой при бора является моделью счета больших задач на ЭВМ.
Небольшая часть V служит примером применения методов, предлагаемых в книге для модели одного химико-технологического процесса.
Вобзоре отражено современное состояние исследований си стем обслуживания с приоритетом.
Вкниге приведена почти исчерпывающая библиография работ по приоритетным системам обслуживания.
Настоящая книга еще не решает всех проблем, которые могут возникнуть и даже уже возникают в теории приоритетного обслу живания. Например, книга полностью обходит многолинейные си стемы обслуживания. Несомненно, что будущее заставит, оттолк нувшись от рассмотренных в настоящей книге задач и методов исследования, искать новые пути совершенствования теории и от веты на запросы практики. Авторы будут благодарны за все поже лания и замечания читателей по книге.
Об о з н а ч е н и я
ф.р. — функция распределения
сл. в. — случайная величина * — знак стилтьесовской свертки
Функции, к которым применяется преобразование Лапласа— Стилтьеса, обозначаются прописными латинскими буквами; преоб
разование Лапласа — Стилтьеса |
— соответствующими строчными |
латинскими или греческими буквами, например |
|
оо |
оо |
о |
о |
Моменты обозначаются соответствующими малыми латински ми или греческими буквами, снабженными внизу индексом (указы вающим порядок момента), например
оо |
00 |
о |
о |
Ч А С Т Ь I
Н Е П Р И О Р И Т Е Т Н Ы Е С И С Т Е М Ы M I G 111 0 0
Г Л А В А 1. СИСТЕМА С АБСОЛЮТНО НАДЕЖНЫМ ПРИБОРОМ
В настоящей главе на примере одной из простых систем мас сового обслуживания (СМО)—одноканальной системы с ожида нием, пуассоновым входящим потоком и длительностью обслужи вания вызовов, распределенной по произвольному закону, — де тально рассмотрены основные подходы, базирующиеся на вероят ностной интерпретации преобразований Лапласа и производящих функций. Все эти подходы оказываются применимыми к различ ным обобщениям указанной системы: к одноканальным системам с ожиданием, ненадежным прибором и приоритетами. Целью главы
помимо изучения характеристик |
системы M | G | l | o o является |
озна |
|||||
комление |
читателя |
с методами, |
применяемыми |
в |
дальнейшем. |
||
|
|
§ 1. Дополнительное событие |
|
|
|||
При решении задач массового обслуживания |
часто приходит |
||||||
ся пользоваться преобразованием |
Лапласа—Стилтьеса |
|
|||||
|
|
оо |
|
|
|
|
|
|
|
j"e-s < |
|
dA(t), |
|
|
|
|
|
о |
|
|
|
|
|
некоторой |
функции |
распределения |
(ф. p.) A |
(t) |
неотрицательной |
||
случайной |
величины (сл. в.) или производящими |
функциями |
вида |
||||
|
2J Pfc2 |
й л и 2J P k |
T\ ' = e Z 2J рь ÄT E ~Z - |
|
|||
|
k>0 |
ftJïO |
|
fe>0 |
|
|
|
Вид этих функций наводит на мысль, что им можно придать неко торый вероятностный смысл.
П р и м е р 1. Рассмотрим |
поток вызовов, |
поступающих в некоторую |
систе |
му обслуживания. Пусть число |
z такое, что |
О ^ г ^ 1. Раскрасим поступающие |
|
вызовы следующим образом. Каждый вызов объявляется либо красным, |
либо |
||
синим, причем .произвольный вызов объявляется красным с вероятностью |
z не |
||
зависимо от того, какого цвета остальные вызовы. Если теперь рн есть вероят
ность поступления k вызовов в некотором интервале времени, то ^ |
pf.zk |
есть |
ftS=o |
|
|
вероятность поступления (в этом интервале) лишь красных вызовов |
(или |
веро- |
10