Упорядочение ориентированных графов

Большой вклад в развитие теории упорядочивания ориентированных графов внесли Хамлир и Чампинг (реинжиниринг БП).

Упорядочивания ориентированных графов применяется для установления уровней иерархий (подчинённости).

Цепь в неориентированном графе – последовательность вершин (рёбер) из данной вершины x_i в вершину x_k; в ориентированном графе – это последовательность дуг из данной вершины x_i в вершину x_k (цепь в ориентированном графе называется путь)

 

Цепь из вершины x_i в вершину x_i называется циклом.

Цикл минимальной длины – петля.

Длина цепи определяется количеством рёбер (дуг).

Для орграфа путь из вершины x_i в вершину x_i называется контуром.

 

Рассмотрим упорядочение в ориентированном графе.

 

Упорядочение осуществляется на основании операции предшествования:

x_i u_l x_j u_k x_k

вершина x_i предшествует x_j => x_i µ x_j

дуга u_l предшествует u_k => u_l µ u_k

 

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

 

Отношения предшествования обладают следующими свойствами:

1. антисимметричности: x_i µ x_j => x_j µ x_i

2. транзитивности x_i µ x_j; x_j µ x_k => x_i µ x_k

 

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

Упорядоченность предполагает, что начальная вершина не имеет предков, а конечная не имеет потомков.

Промежуточная вершина имеет как предков, так и потомков.

Упорядочение может осуществляться тремя способами:

1) графическим

2) по матрице смежности вершин

3) по матрице смежности дуг

 

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

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

РЕШИТЬ ЗАДАЧИ:

Задача 9.1. Строительство нового дома включает укрупненные операции, приведенные в таблице:

Проект строительства дома
№	Операция	Время (дни)	Предшествующие операции	Дуга графа
1.	Расчистка участка		нет	1-2
2.	Закладка фундамента		Расчистка участка (1)	2-3
3.	Возведение стен		Закладка фундамента (2)	3-4
4.	Монтаж электропроводки		Возведение стен (3)	4-5
5.	Штукатурные работы		Монтаж электропроводки (4)	3-6
6.	Благоустройство территории		Возведение стен (3)	5-7
7.	Отделка		Штукатурные работы (5)
8.	Настил крыши		Возведение стен (3)	3-8

Построить сетевой график, определить критический путь, параметры работ и параметры событий.

Задача 9.2. Упорядочить оргграф:

Определить критический путь, параметры работ и параметры событий.

 

Занятие 10.

системЫ массового обслуживания.

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

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

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

Примерами систем массового обслуживания могут служить:

• посты технического обслуживания автомобилей;

• посты ремонта автомобилей;

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

• станции технического обслуживания автомобилей;

• аудиторские фирмы;

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

• телефонные станции и т. д.

Основными компонентами системы массового обслуживания лю­бого вида являются:

• входной поток поступающих требований или заявок на обслужи­вание;

• дисциплина очереди;

• механизм обслуживания.

Раскроем содержание каждого из указанных выше компонен­тов.

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

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

• первым пришел - первый обслуживаешься;

• пришел последним — обслуживаешься первым;

• случайный отбор заявок;

• отбор заявок по критерию приоритетности;

ограничение времени ожидания момента наступления обслужи­вания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая дли­на очереди»).

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

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

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

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

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

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

• вероятностным распределением времени продолжительности об­служивания;

• конфигурацией обслуживающей системы (параллельное, после­довательное или параллельно-последовательное обслуживание);

• количеством и производительностью обслуживающих каналов;

• дисциплиной очереди;

• мощностью источника требований.

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

• вероятность немедленного обслуживания поступившей заявки;

• вероятность отказа в обслуживании поступившей заявки;

• относительная и абсолютная пропускная способность системы;

• средний процент заявок, получивших отказ в обслуживании;

• среднее время ожидания очереди;

• средняя длина очереди;

• средний доход от функционирования системы в единицу време­ни и т.п.

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

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

Независимо от характера процесса, протекающего в системе мас­сового обслуживания, различают два основных вида СМО:

• системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же по­кидает очередь;

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

Системы массового обслуживания с ожиданием делятся на си­стемы с ограниченным ожиданием и системы с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

• длина очереди;

• время пребывания в очереди.

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

Все системы массового обслуживания различают по числу каналов обслуживания:

• одноканальные системы;

• многоканальные системы.

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

⇐ Предыдущая12345Следующая ⇒

Поделиться: