Главная  Полное построение алгоритма 

[0] [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]

случае оно называется вторичным или условным событием. Независимыми событиями в системе обслуживания являются:

(а) Прибытие клиента.

(б) Завершение обслуживания клиента.

5. В начальном состоянии система пуста. В момент времени =0 обслуживающее устройство не занято и в очереди никого нет.

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

7. Для определения промежутков времени между прибытиями клиентов и продолжительностей их обслуживания применяется датчик случайных чисел.

Чтобы разработать алгоритм для моделирования конкретной системы одна очередь/одно обслуживающее устройство, нужно выяснить ряд вопросов:

1. Каковы распределения вероятностей промежутков времени между прибытиями клиентов и продолжительности обслуживания?

2. Каким датчиком случайных чисел и как пользоваться для получения случайных промел<утков времени?

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

4. Сколько времени следует продолжать процесс имитации? Должны ли часы отсчитывать по единице времени, или они должны переходить к моменту следующего определенного события?

5. Как будут «составлены расписания» для событий, относительно которых установлено (случайно или не случайно), что они должны произойти в определенное время? Иными словами, как мы убедимся, что эти события и все другие, являющиеся их следствием, действительно происходят и происходят вовремя? Что делать в случае «совпадения», т. е. когда два или более событий случаются одновременно?

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

(а) Число прибытий в процессе имитации.

(б) Средняя длина очереди.

(в) Среднее время ожидания в очереди.

(г) Максимальная длина очереди.

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



(е) Среднее, максимальное и минимальное время обслуживания.

(ж) Функция распределения длины очереди, т. е. процентные доли времени, в течение которого длина очереди была t.

(з) Число клиентов, которым не пришлось ждать.

Ответы на вопросы 1-6 зависят от специфики моделируемой системы обслуживания. Но как на них отвечать?

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

Фактически во всех вычислительных устройствах имеется системный датчик случайных чисел для равномерного распределения на интервале [О, 1). Это распределение может быть использовано для того, чтобы смоделировать другие распределения случайной переменной, применяя методы, описанные в разд. 6.3.

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

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

Для иллюстрации этого подхода на рис. 3.6.2 представлена принципиальная блок-схема алгоритма моделирования системы одна очередь/одно обслуживающее устройство. Чтобы получить моделирующую программу, необходима некоторая переработка этой блок-схемы. В частности, на рис. 3.6.2 нет условия для остановки (или возвращения). С этой целью мы вводим три различные целочисленные переменные ARR, СОМР и TERM, обозначающие соответственно




Шонирабаш/е cnedi/iauiezo сой/тии; постотВт S очередь

ПпонироВотс Medi/Kiineea заИсрсщия:, исключств из очереди

Рис 3.6.2. Блок-схема моделирования системы «одна очередь/одно обслуживающее

устройство».

время следующего прибытия, время завершения обслуживания и время окончания моделирования. Мы также вводим переменную CLOCK для записи текущего времени. Так как мы используем метод планирования событий, полагаем переменную CLOCK равной времени следующего запланированного события: это или время следующего прибытия, или время завершения обслуживания, или время окончания моделирования. Тогда блоки 2, 3 и 4 становятся такими, как показано на рис. 3.6.3.

Далее рассмотрим, что должно быть сделано в блоке 5 на рис. 3.6.2, когда имеет место новое прибытие. Во-первых, мы можем определить время следующего прибытия в соответствии с правилом вида

ARR=CL0CK+RANARR(1, МАХА)

где RANARR(1, МАХА) - функция, которая дает случайное целое число между 1 и некоторой фиксированной константой МАХА с определенным распределением вероятностей.



[0] [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]

0.001