Резервы сетевого графика

Поздние времена удобно считать по формуле обратной волны:

начиная от конечной вершины к начальной (см. рис. 4.14). В этой формуле рассматриваются все соседние к xiпоследующие вершины xn.

Определение 4.8. Полным резервом, временидля работы uijназывается величина

Свободным резервом временидля работы uijназывается величина

Пример 4.8 .Для работы вне критического пути u 15(см. рис. 4.14) имеем τ15= 31 – 5 – 4 = 22 и σ15= 9 – 5 – 4 = 0. Для работы на критическом пути и 24имеем τ24= 26 – 7 – 19 = 0 и σ24= 26 – 7 – 19 = 0. Остальные резервы приведены в табл. 4.1. Обратим внимание, что всегда τ ij≤ σ ij, и на критическом пути для любой работы резервы нулевые: τтп= σтп= 0.

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

Сети Петри

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

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

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

Определение 4.11.Сетью Петри называется ориентированный граф с двумя типами вершин, так называемый «двудольный» граф:

Г = á Р , T , F ñ ,

где Р — { p 1, ... , рт} — первый тип вершин, называемых позициями ; Т — { t 1, ..., tn} — второй тип вершин, называемых переходами ; F — множество дуг.

При этом Р ∩ T = 0, т. е. вершины распадаются на два непересекающихся класса. А дуги соединяют вершины разных типов. Графически позиции сети Петри на плоскости принято изображать кружками, а переходы — планками (барьерами). Множество F задается двумя матрицами смежности. В одной матрице строки соответствуют вершинам Т , а столбцы — вершинам Р .

В другой матриц, наоборот, строки соответствуют вершинам Р , а столбцы — Т .

Пример 4.12. Сеть Петри на рис. 4.16 моделирует функцию одной переменной у = f ( x ). Здесь р 1— аргумент, р 2— значение функции, t — преобразователь (правило f ).

Пример 4.13. Сеть Петри на рис. 4.17 моделирует функцию двух переменных у = f ( x 1, x 2).

Пример 4.14. Сеть Петри на рис. 4.18 моделирует вектор-функцию

Пример 4.15. На рис. 4.19 изображена модель случайного процесса. Здесь р 1— некоторое условие; t 1, t 2, t 3означает «срабатывает либо t 1, либо t 2, либо t 3.

Определение 4.12. Разметкой(маркировкой) сети Петри Г = á Р , T , F ñ называется функция μ, отображающая множество позицийР во множество натуральных чисел с нулем ℕ 0= {0, 1, 2,…}, т. е.

μ: P → ℕ 0.

Разметку можно записать в векторной форме μ = (μ1, ..., μ m).

Число μ k= μ( pk), рк∈ Р , изображается на графе сети точками в соответствующем кружке рк. Эти точки называются маркерами(фишками). Их ровно μ kштук в позиции рк. Размеченная сеть обозначается á Р , T , F , μ ñ .

Пример 4.16. Сеть Петри на рис. 4.20 моделирует ситуацию с функцией одной переменной.

Пример 4.17. На рис. 4.21 моделируется ситуация с функцией двух переменных.

Пример 4.18. На рис. 4.22 моделируется функция одной переменной. Сравните с рис. 4.20.

Определение 4.13. Функционированием(работой) размеченной сети Петри á Р , T , F , μ ñ называется процесс изменения разметки начиная от начальной разметки μ по следующим правилам.

1. Если для перехода t ∈ T все входные позиции имеют ненулевую разметку, то происходит обязательное срабатывание (запуск) этого перехода.

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

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

Рис . 4.16. Функция одной переменной

Рис . 4.17. Функция двух переменных

Рис . 4.18. Вектор-функция

Рис . 4.19. Случайная функция

Рис . 4.20. Вычисление функции одной переменной

Рис . 4.21. Вычисление функции двух переменных

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

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

Рис . 4.22. Вычисление функции одной переменной для двух значений аргументов

Цит. по: Дискретная математика: учебник для студ. вузов /
Т.С. Соболева , А.В. Чечкин; под ред. А.В. Чечкина. —
М.: Издательский центр «Академия» , 2006. — С. 49 – 71. —
(Университетский учебник. Сер. Прикладная математика и информатика).