ПЕРЕЧЕНЬ УЧЕБНО-МЕТОДИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Саратовский государственный технический университет имени Гагарина Ю.А.»

СЕТЕВОЕ ПЛАНИРОВАНИЕ ПРОЦЕССОВ

Методические указания к выполнению лабораторной работы

по курсу “Теоретические основы автоматизированного управления”

для студентов

направления

«Информатика и вычислительная техника»

Профиль

«Автоматизированные системы обработки информации и управления»

заочно-сокращенной формы обучения

Одобрено

редакционно-издательским советом

Саратовского государственного

технического университета им. Гагарина Ю.А.

Саратов 2015

Введение

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

Цель работы: Знакомство студентов с основными способами анализа и синтеза моделей сложных систем и процессов, описываемых сетевыми графиками.

Задание

1. Предложить словесное описание какого-либо процесса и найти его целевую функцию.

2. Разбить процесс на этапы.

3. Построить сетевой график процесса и рассчитать параметры сетевого графика на ЭВМ.

4. Сделать выводы.

Основные параметры сетевого графика

Как и всякий граф, сетевой график состоит из вершин и ориентированных рёбер (дуг). Дуги изображают работы, характеризуемые некоторым параметром (весом); вершины – события, являющиеся результатом выполнения одной или нескольких работ.

Рис. 1 Пример сетевого графа

События не имеют протяжённость во времени в отличии от работ, которые имеют определённую протяжённость. Термин «работа» может иметь следующие значения:

· действительная работа в прямом смысле этого слова, т. е. трудовой процесс, требующий затрат времени и ресурсов;

· ожидание, не требующее затрат труда, но занимающее некоторое время (например, процесс затвердевания бетона);

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

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

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

Необходимым и достаточным условием начала любой работы, кроме начальной, является окончание всех предшествующих ей работ (например, начало работы (10, 11) возможно после окончания работ (2, 10) и (7, 10) – рис. 1).

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

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

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

При построении сетевых графиков необходимо соблюдать следующие правила:

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

2. Не должно быть событий, в которые не входит ни одной работы, если только это событие не является исходным.

3. В сети не должно быть замкнутых контуров.

4. В сети не должно быть одинаковых работ, т. е. не должно быть параллельных дуг.

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

Таблица 1.

Обозначение пути	Перечень работ, составляющих путь	Продолжительность пути	Резерв времени
42	(0, 1), (1, 4), (4, 5), (5, 11), (11, 13)	140	30
42	(0, 1), (1, 5), (5, 11), (11, 13)	100	70
43	(0, 1), (1, 4), (4, 5), (5, 12), (12, 13)	120	50
44	(0, 1), (1, 5), (5, 12), (12, 13)	80	90
45	(0, 2), (2, 7), (7, 10), (10, 11), (11, 13)	170	0
46	(0, 2), (2, 10), (10, 11), (11, 13)	140	30
47	(0,3), (3, 6), (6, 7), (7, 10), (10,11), (11, 13)	139	31
48	(0,3), (3, 6), (6, 9), (9,11), (11, 13)	119	51
49	(0,3), (3, 8), (8, 9), (9,11), (11, 13)	140	30

Путь, имеющий наибольшую продолжительность, называется критическим (L_кр). В сети может быть несколько критических путей. Длительность критического пути (t_кр) определяет общую продолжительность работ (например, в табл. 1: L₅=L_кр: t_кр=170. Разница между продолжительностью критического пути t_кр и любого другого пути сети t(L_к) называется полным резервом времени пути и обозначается P(L_k).

P(L_k)=t_кр-t(L_k).

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

Для любого события (i) сетевая модель позволяет определить наиболее ранний срок его свершения из возможных t_p(i) и наиболее поздний t_n(i) из допустимых.

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

t_p(i)=t[L(I ],

например, t_p(5)=t[L(I ]=t[L(0,1,4,5)]=70.

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

Обозначив максимальный из следующих за событием I путей через L(i C), получим

t_n(i)=t_кр-t[L(I ],

например, t_n(5)=170-t[L(5 ]=170- t[L(5,11,13)]=170-70=100.

Резерв времени события (i) определяется как разница между поздним и ранним сроком свершения события и обозначается

=t_n(i)-t_p(i)

например, =30дней

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

События критического пути не имеют резерва времени, т. к. у них t_n(i)=t_p(i)

Используя t_n(i) и t_p(i) всех событий сети можно для любой работы определить

1. ранний срок начала t_рн(i,j);

2. ранний срок окончания t_ро(i,j);

3. поздний срок начала t_пн(i,j);

4. поздний срок окончания t_по(i,j);

по формулам: t_рн(i,j)=t_р(i);

t_пн(i,j)= t_п(j)-t(i,j);

t_ро(i,j)= t_р(j)+t(i,j);

t_по(i,j)=t_n(j);

Для всех работ критического пути:

t_рн(i,j)=t_пн(i,j); t_ро(i,j)=t_по(i,j).

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

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

Для работы критического пути R_n(i,j)=0.

Для остальных работ, величина R_n(i,j) определяется формулой:

R_n(i,j)= t_n(j)- t_p(j)-t(i,j);

например, R_n(5,12)= 160-70-40=50.

Частный резерв времени первого вида R¹ _n(i,j) показывает какая часть полного резерва времени работы (i,j) может быть использована для увеличения её продолжительности при условии, что это увеличение не вызовет изменение позднего срока свершения её начального события и следовательно, сокращения резервов времени ни у одной из предшествующих этому событию работ. Частный резерв первого вида вычисляется по формуле: R¹ _n(i,j)= t_n(j)- t_n(j)-t(i,j);

например, R¹ _n(5,12)=160-100-40=20.

Частный резерв второго вида R¹¹ _n(i,j) или свободный резерв времени – это максимальное количество времени, на которое можно увеличить продолжительность работы или отсрочить её начало, не изменяя при этом ранних сроков начала последующих работ, при условии, что начальное событие этой работы наступило в свой ранний срок.

R¹¹ _n(i,j)= t_p(j)- t_p(j)-t(i,j);

например, R¹¹ _n(5,12)=110-70-40=0.

Для определения «узких мест» графика, т. е. тех работ, на которых следует сосредоточить основное внимание, недостаточно знать лишь резервы времени. Более полной характеристикой степени трудности выполнения работ служит коэффициент напряжённости работы К_н(i,j). Он равен отношению продолжительностей несовпадающих (заключённых между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим - критический путь.

Здесь t¹(L_кр) – сумма весов дуг максимального пути совпадающих с критическим путём;

t(L_max) –сумма весов дуг максимального пути, проходящего через работу (i,j).

С учётом ранее приведённых формул:

например, К_н(5,12)=1-50/170=0,71

Чем выше коэффициент напряжённости, тем сложнее выполнять данную работу.

Величина К_н(i,j) заключена внутри отрезка [0,1]. Работ критического пути К_н(i,j)=1.

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

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

1. критическая зона – работы, имеющие значения К_н(i,j) 0,8 0,9

2. зону резерва, объединяющую работы, для которых К_н(i,j) 0,5 0,6

3. промежуточная зона, к которой относятся работы с коэффициентом напряжённости, лежащим в пределах (0,5 0,6)<К_н(i,j)<(0,8 0,9)

Перераспределение ресурсов внутри сетевого графика должно идти, как правило, в одном направлении: из зон менее напряжённых к зонам более напряжённым. Чем меньше будет объём критической и резервной зон, тем лучше синтезирована модель процесса, описываемого сетевым графиком.

Порядок выполнения работы

1. Дать словесное описание какого-либо процесса, состоящего из 10-20 этапов.

2. Сформулировать цель задачи.

3. Разбить весь процесс на этапы.

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

5. Составить таблицу рассматриваемого процесса следующего вида:

Таблица 2.

Этап	Наименование выполняемых работ	Вес дуги	Предшествующие этапы работ
1	2	3	4

Например: для строительства одноэтажного общежития необходимо выполнить следующие работы:

Таблица 3.

Этап	Наименование выполняемых работ	Вес дуги	Предшествующие этапы работ
1.	Подготовка стройплощадки	1	-
2.	Укладка фундамента	2	1
3.	Монтаж вертикальных стен	3	2
4.	Монтаж крыши	7	3
5.	Настил полов	5	2
6.	Отделка внутренних стен	6	3
7.	Установка сантехники	4	3
8.	Монтаж электропроводки	4	4
9.	Сборка системы отопления	6	7, 8
10.	Оборудование буфета	2	5, 6, 7

6. Используя таблицу составить сетевой график процесса.

Например, для таблицы 3. сетевой график имеет вид:

Здесь l_ф_i –фиктивная дуга, вес которой равен нулю.

Ф_i – фиктивный узел, вводимый для выполнения требований, предъявляемых к сетевому графику.

7. Проверить правильность составления сетевого графика

8. С помощью алгоритма Дейкстры [I] рассчитать критический путь сети, определить t_p(i), t_n(i)

9. Рассчитать на ЭВМ величины: t_p(i), t_n(i), t_p(i,j), t_n(i,j), R_n(i,j).

10. Сделать выводы.

11. Оформить результат работы в виде отчёта, приложить программу расчета на ЭВМ и сдать его преподавателю.

Литература

ПЕРЕЧЕНЬ УЧЕБНО-МЕТОДИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ

ОСНОВНАЯ ЛИТЕРАТУРА

1. Советов, Б. Я. Теоретические основы автоматизированного управления : учеб. для вузов / Б. Я. Советов, В. В. Цехановский, В. Д. Чертовской. - М. : Высшая школа, 2006. - 463 с. (19 экз. НТБ СГТУ)

2. Автоматизированные системы управления на автомобильном транспорте : учебник / А. Б. Николаев [и др.] ; под ред. А. Б. Николаева. - М. : ИЦ "Академия", 2011. - 288 с. : ил.; 22 см. - (Среднее профессиональное образование). - Библиогр.: с. 284-285 (17 назв.). - Гриф: рек. Федер. гос. учреждением "Федер. ин-т развития образования" в качестве учебника для использования в учеб. процессе образоват. учреждений, реализующих программы сред. проф. образования. - ISBN 978-5-7695-6006-4: 666.71 р. (10 экз. НТБ СГТУ)

3. Гусев, А. И. Информационное обеспечение систем управления : учеб. пособие для студ. спец. 220201 / А. И. Гусев, Р. А. Тимофеева ; М-во образования и науки РФ, Саратовский гос. техн. ун-т. - Саратов: СГТУ, 2011. - 136 с. (40 экз. НТБ СГТУ)

4. Автоматизированные системы управления и связь [Электронный ресурс] : учебное пособие / сост.: С. А. Сазонова, С. А. Колодяжный. - Воронеж : Воронежский государственный архитектурно-строительный университет, ЭБС АСВ, 2014. - 172 с. Режим доступа: http://www.iprbookshop.ru/30831

5. Рудинский, И. Д. Технология проектирования автоматизированных систем обработки информации и управления [Электронный ресурс]: учебное пособие / Рудинский И. Д. - Москва : Горячая линия - Телеком, 2011. - 304 с. Режим доступа: http://www.iprbookshop.ru/12057

Дата добавления: 2021-03-18; просмотров: 111; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!