Главная > Энциклопедия кибернетики. Т.1
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
След.
Макеты страниц

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

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

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ, теория очередей

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

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

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

Более сложные полумарковские процессы могут служить моделью математической процессов действия систем массового обслуживания. Их применение возможно при условии, когда среди случайных величин, характеризующих состояние системы в момент , может быть одна с произвольным законом распределения, все же остальные распределены по экспоненциальному закону (возможно, при некотором расширении пространства состояний процесса). Так, в системе массового обслуживания с экспоненциально распределенным временем обслуживания при входящем потоке с ограниченным последействием число требований в системе в момент t представляет собой полумарковский процесс Метод, в аналитическом отношении эквивалентный методу полумарковских процессов и называемый методом вложенных цепей Маркова, разработал англ. математик Д. Кендал (по существу, этот же метод сов. математик А. Я. Хинчин использовал при решении конкретных задач М. о. т. раньше Д. Кендала). Этот метод состоит в выборе такой последовательности моментов времени при которой последовательность значений процесса образует Маркова цепь с конечным или счетным мн-вом состояний. Чаще всего последовательность образуется моментами поступления в систему требований или моментами окончания операций обслуживания. Таким методом получены осн. ф-лы М. о. т. (см. Длина очереди, Хинчина—Полачека формула, Период занятости в системах массового обслуживания). Получена также теорема об общем аналитическом виде стационарных характеристик широкого класса однолинейных систем массового обслуживания и обобщена на нестационарный случай.

Системы массового обслуживания, к которым метод полумарковских процессов не применим, изучаются с помощью многомерных марковских процессов вида где дискретная компонента с конечным или счетным мн-вом возможных значений, обозначающая такие величины, как число занятых приборов, величину очереди и т. числовые переменные, интерпретируемые либо как время, прошедшее с момента начала операции, либо как время до ее окончания. Методом процессов такого рода исследован широкий класс систем массового обслуживания с потерями. В 60-х годах когда обнаружили, что многие ф-лы М. о. т., выведенные в предположении о независимости длительностей обслуживания требований, сохраняют силу и при зависимых длительностях обслуживания, была построена теория для широкого класса систем. В значительной степени в- М. о. т. применяются методы теории суммирования независимых случайных величин и теории случайных блужданий. В 60-х годах интенсивно развивались асимптотические методы М. о. т. Замечено, что во многих случаях, когда изучение системы обслуживания, характеризующейся некоторыми распределениями между поступлением требований, времени обслуживания и т. п.), анализ осн. характеристик системы при общем виде затруднителен; в то же время, в определенных предельных

условиях, связанных с поведением параметров распределений выполняются простые асимптотические ф-лы. Напр., рядом авторов изучено поведение систем обслуживания с ожиданием в случае загрузки, стремящейся к критической (т. е. к такой загрузке, при которой отношение числа поступающих в систему требований к числу требований, которое может быть обслужено, близко к единице). При соответствующей нормировке распределение времени ожидания и длины очереди сходится к экспоненциальному распределению. Параллельно развивается теория систем с малой загрузкой (интенсивность входящего потока рассматривается, как малый параметр), что имеет существенное значение для теории высоконадежных систем (см. Облегченное резервирование). В большинстве задач М. о. т. находят распределения различных величин, связанных с процессом функционирования системы (длины очереди, времени ожидания и вероятности полного обслуживания); дальнейшая ступень развития теории состоит в решении задач оптимизации структуры системы и процесса обслуживания. Для широкого класса случаев была решена задача об установлении оптим. режима обслуживания в схеме обслуживания с приоритетом, когда имеется несколько типов требований, каждый из которых характеризуется определенным ср. временем обслуживания и к.-л. ф-цией потерь стоимостью единицы времени ожидания). Для исследования сложных систем массового обслуживания широко применяется Монте-Карло метод, связанный с моделированием процесса поведения системы. Для алгоритмизации решения задач М. о. т. на ЭВМ созданы некоторые алгоритм, языки (напр., СЛЭНГ).

Первыми исследователями М. о. т. являются датский ученый А. Эрланг и сов. математик А. Я. Хинчин. В своих работах А. Эрланг в 1909-1922 гг. исследовал М. о. т. в связи с организацией телефонных сетей. А. Я. Хинчин в 1932-1933 гг. решил ряд задач из области многостаночного производства, а позднее разработал матем. теорию исследования систем массового обслуживания. Развитие производства, техники, эконом, связей в 50-е гг. привело к необходимости исследования новых систем массового обслуживания. В настоящее время М. о. т. успешно применяется в различных областях нар. х-ва, экономики, техники и науки, разрабатываются новые методы исследований, расширяется круг методов изучения и оптимизации систем массового обслуживания, поддающихся решению, изыскиваются новые пути практического приложения имеющихся теор. результатов. Исследования М. о. т. имеют большое значение при проектировании и построении различных систем автоматизированного управления производством и транспортом, для рациональной орг-ции производства и снижения себестоимости продукции.

Лит.: Хинчин А. Я. Работы по математической теории массового обслуживания. М., 1963; Бусленко Н. П. Математическое моделирование производственных процессов на цифровых вычислительных машинах. М., 1964 [библиогр. с. 361—362]; Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М., 1966 [библиогр. с. 421—428]; Климов Г. П. Стохастические системы обслуживания. М., 1966 [библиогр. с. 242—243]; Саати Т. Л. Элемент теории массового обслуживания и ее приложения. Пер. с англ. М., 1971 [библиогр. с. 450—509]. И. Н. Коваленко.

1
Оглавление
email@scask.ru