§ 29. Структура алгоритма, моделирующего процесс обслуживания заявок

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

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

(см. скан)

Рис. 11. Блок - схема алгоритма, моделирующего процесс обслуживания заявок.

Логические операторы изображаются, кружками. Если условие,

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

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

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

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

На блок - схеме (рис. 11) изображены следующие операторы:

1 — оператор определения момента поступления очередной заявки в систему. Для простоты здесь рассматривается ординарный поток заявок;

2 — оператор проверки принадлежности очередной заявки текущей реализации потока;

3 — оператор определения времени занятости линии, обслуживавшей предыдущую заявку;

4 — оператор формирования и фиксации новых значений моментов освобождения линий;

5 — оператор проверки наличия свободных линий в заданный момент времени;

6 — оператор проверки условия

7 — оператор составления табеля свободных линий, содержащего исходные данные для реализации заданного правила назначения обслуживающей линии;

8 — оператор выбора одной из свободных линий для обслуживания данной заявки (в соответствии с заданным правилом);

9 — оператор проверки факта срыва обслуживания по причине неполной надежности линий. Если обслуживание. срывается, вырабатывается признак в противном случае вырабатывается признак

10 - оператор определения времени, необходимого на ремонт линии, вышедшей из строя;

11 — оператор, подсчитывающий количество отказов;

12 — оператор подготовки алгоритма к моделированию процесса обслуживания новой заявки;

13 — оператор проверки условия, состоящего в том, что количество обследованных реализаций потока менее заданного;

14 — оператор подготовки алгоритма к моделированию процесса обслуживания новой реализации потока заявок;

15 — оператор, подсчитывающий количество обследованных реализаций;

16 — оператор обработки результатов моделирования;

17 — оператор формирования величин, выдаваемых в качестве результатов решения задачи;

18 — оператор определения момента потери заявки, не принятой к обслуживанию в момент поступления;

19 — оператор проверки возможности обслужить заявку, заставшую в момент поступления все линии занятыми;

20 — оператор проверки условия

21 — оператор составления табеля линий, которые могут обслужить данную заявку.

Работа рассматриваемого алгоритма состоит в следующем.

Оператор 1 вырабатывает моменты поступления заявок в систему обслуживания. Для этого реализуется один из рассмотренных в § 27 способов формирования потоков однородных событий. Пусть оператор 1 уже выработал момент поступления очередной заявки Путем сравнения, при помощи оператора 2, значения с Г, хранящимся в специальной ячейке памяти машины, устанавливается принадлежность данной заявки к текущей реализации потока.

Если условие, проверяемое оператором 2, оказывается выполненным, проводится моделирование процесса обслуживания заявки (передача управления по стрелке с индексом 1 к оператору 3). В противном случае от оператора 2 по стрелке с индексом 0 управление передается оператору 13 для перехода к очередной реализации потока (оператор 14) или окончанию моделирования (оператор 16).

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

Полученное оператором 3 значение прибавляется к моменту начала обслуживания предыдущей заявки, и определяется Значение фиксируется в специальных ячейках памяти машины. Эти операции выполняются оператором 4.

Проверка возможности обслужить поступившую заявку начинается работой оператора 5. Значение момента поступления заявки сравнивается с для

всех линий, и таким образом выявляются свободные линии. Если свободные линии имеются работа алгоритма продолжается в направлении, указанном стрелкой с индексом 1, в противном случае — в направлении, указанном стрелкой с индексом 0.

Проследим сначала первое направление. Итак, свободные линии имеются. Оператор 6 проверяет условие Если это условие не выполнено, значит, имеется единственная свободная линия. Эта линия и назначается для обслуживания рассматриваемой заявки. В случае, когда условие, проверяемое оператором 6, оказывается выполненным, имеется несколько свободных линий. Тогда выбирается (оператором 8) для обслуживания заявки одна из свободных линий по специальным правилам.

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

Для реализации упомянутых правил оператору 8 необходимы некоторые признаки или параметры, характеризующие каждую, из свободных линий. Эти признаки и параметры подготавливаются и сводятся в «табель свободных линий» оператором 7.

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

При рассмотрении настоящей задачи относительно судьбы заявки, обслуживаемой неисправной линией, сделаем предположение, что такая заявка получает отказ. Поэтому от оператора 9 по стрелке с индексом 1 переходим к оператору 10, а затем к оператору 11, который регистрирует отказ. Оператор 10 определяет время ремонта линии, вышедшей из строя. Поскольку трем обычно является случайной величиной с заданным законом распределения, работа оператора 10 аналогична: работе оператора 3, на которой мы, останавливав

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

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

От оператора 12 управление передается оператору 1 для работы с очередной заявкой.

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

Предположим теперь, что условие, проверяемое оператором 5, не выполнено. Тогда управление передается по направлению стрелки, отмеченной индексом 0, к оператору 18. Задача этого оператора — определить момент времени начиная с которого данная заявка, не принятая к обслуживанию в момент ее поступления, будет считаться исчерпавшей свой лимит времени пребывания в системе и в случае, если к моменту она не будет принята к обслуживанию, получит отказ. Величина сравнивается при помощи оператора 19 с моментами всех линий, и на этом основании проверяется возможность обслужить данную заявку. Если условие, проверяемое оператором 19, не выполняется, управление, передается в направлении стрелки с индексом 0 счетчику количества отказов (оператор 11). В случае, если имеется возможность обслужить данную заявку (условие, проверяемое оператором 19, выполнено), работа алгоритма проходит в направлении оператора 20. Заметим, что цепочка операторов 20 и 21 выполняет операции, аналогичные тем, которые мы рассматривали в связи с операторами 6 и 7.

Если условие проверяемое оператором 20, не выполнено, значит, имеется единственная линия, могущая обслужить данную заявку. Поэтому по стрелке с индексом 0. управление, передается оператору

В случае, если условие оказывается выполненным, имеется несколько линий, могущих обслужить данную заявку. Из этих линий оператором 8 будет выбрана для обслуживания заявки одна определенная линия в соответствии с принятыми правилами. Значения признаков и параметров, сведенных в «табель линий, могущих обслужить заявку», вырабатываются оператором 21.

Далее управление передается оператору 8, и работа алгоритма до оператора 12 включительно протекает путем, описанным выше.

Оператор 13 сравнивает число обследованных реализаций с заданным Если условие, проверяемое оператором 13, выполнено, управление передается по стрелке с индексом 1 к оператору 14, который обеспечивает переход к обследованию заявок очередной реализации потока. Оператором 15 ведется учет количества обследованных реализаций. Если условие, проверяемое оператором 13, не выполнено, этим заканчивается обследование реализаций потока и происходит обработка и выдача результатов моделирования (операторы 16 и 17).

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

Рассмотрим операторы 7 и 8. Предположим сначала, что линии для обслуживания выбираются оператором 8 в случайном порядке. Тогда оператор 8 реализует выбор по жребию одного из событий в соответствии с заданными вероятностями Эти вероятности рассчитываются оператором 7. Способы выбора событий по жребию рассмотрены в главе И.

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

Наконец, если линии для обслуживания выбираются в порядке величин их номеров, операторы 7 и 8 могут

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

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

В соответствии с (8.58) выбираются возможные значения времени безотказной работы 7, и таким образом вычисляется момент выхода из строя каждой линии Аналогично, располагая временем занятости линии, вы рабатываемым оператором 3, можно определить момент окончания обслуживания

Условием срыва обслуживания является

Если неравенство (8.59) выполнено, вырабатывается значение признака и управление передается оператору 10. Может случиться, что неравенство (8.59) не выполнено. В этом случае величину нужно хранить в памяти для использования ее в дальнейшем, когда данная линия опять будет выделена для обслуживания какой-нибудь заявки.

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

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

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

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

Допустим, что условие, проверяемое оператором 9, выполнено, т. е. линия оказывается неисправной. Необходимо проследить как историю неисправной линии, так и историю заявки. От оператора 9 по направлению стрелки с индексом 1 управление необходимо передать оператору 10 для определения времени ремонта линии, а затем — оператору 4 для вычисления и фиксации (которое в этом случае имеет смысл времени ввода в строй неисправной линии). На этом рассмотрение истории линии можно закончить. Для того чтобы поместить заявку в очередь, необходимо от оператора 4 управление передать цепочке дополнительных операторов. Работа их сводится к следующему. Очередное значение вырабатываемое оператором 1, сравнивается с (момент выхода линии из строя), и проверяется условие

Если условие (8.60) не выполнено, сравниваемое значение записывается в специальные ячейки памяти (которые мы будем называть «регистром заявок») и управление передается оператору 1 для выработки значения Если условие (8.60) окажется выполненным, то в регистр заявок записывается сначала а затем и сравниваемое значение После этого управление может быть передано оператору 2 (и далее по рассмотренной выше схеме), но очередные выбираются сначала из регистра заявок (до тех пор, пока там имеются значения а затем уже вырабатываются оператором Заметим, что в некоторых случаях (по условию задачи) может потребоваться сравнение с моментом времени, вырабатываемым для данной заявки оператором 18. Если меньшим из них оказывается работа алгоритма протекает в соответствии с рассмотренной здесь модификацией схемы, В противном случае управление передается оператору 11 для фиксации очередного отказа.

Более сложной логики работы алгоритма требует случай, коэда заявка, для обслуживания которой

выделена неисправная линия, остается в системе как претендент на обслуживание вне очереди. Пусть момент выхода из строя, как и ранее, обозначается Определив V и (операторы 10 и 4), переходим к проверке условия (8.60). Если условие (8.60) выполнено, значит, очереди заявок нет, и тогда будет ближайшим моментом поступления очередной заявки. Поэтому переносится в регистр заявок, и работа алгоритма продол» жается описанным выше образом.

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

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

Алгоритм, блок - схема которого изображена на рис. 11, исходит из предположения о том, что заявки выбираются для обслуживания в порядке очереди.

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

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

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

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

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

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

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

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

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

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

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

Аналогично, вероятность отказа по причине занятости линий может быть оценена как

а вероятность отказа по причине недостаточной надежности

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

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

Если входной поток не является стационарным или если по другим причинам нельзя воспользоваться оценками вида (8.61), пригодными для эргодических случаев, необходимо вести учет отказов по реализации потока заявок.

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

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

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

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

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

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