Основные показатели сетевого графика.

⇐ ПредыдущаяСтр 7 из 27Следующая ⇒

Определение 4.6. Ранним временем наступления события х iназывается длина максимального пути L (х 0, х i) от начала всех работ до момента х i. Длина пути | L (х 0, х i)| определяется как сумма длин всех его дуг. Обозначим раннее время

Рис. 4. 14. Сетевой график

По определению, t ( x 0) = 0. Раннее время момента завершения всех работ t ( xk) = t * называется критическим временем сетевого графика, а путь L (х 0, х k) = L * , длина которого равна критическому времени, называется критическим путем сетевого графика.

Пример 4. 7. В сетевом графике на рис.4.14 проведем расчет ранних времен всех вершин и занесем результаты расчета в левые четверти кружков, изображающих вершины. Так для вершин х 4, х 5, х 6будем иметь:

t ( x 4) = max {17, 26} = 26, t ( x 5) = m ах{8, 9} = 9, t ( x 6) = m ах{28, 37, 14, 15} = 37.

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

t (xi) = max{t (xm) + T (umi)}.

В этой формуле рассматривается для всех соседних к xiпредшествующих вершин хтнаибольшая из сумм раннего времени вершины-соседки и длительности работы от нее до заданной вершины. Например, если уже известны ранние времена t ( x 4)= 26 и t ( x 5) = 9 (см. рис. 4.14), то легко найти t ( x 6) = max {(26 + 11), (9 + 6) = 37}. Расчет ранних времен ведется по этой формуле от начальной вершины к конечной подобно распространению прямой волны (см. рис. 4.14). В конце расчета получаем критическое время t * = t ( x 6) = 37 и критический путь L *( x 0, x 6) = { u 02, u 24, u 46} сетевого графика. Критический путь на рис. 4.14 выделим.

Определение 4.7. Поздним временем наступления события х iназывается разность критического времени t * сетевого графика и длины максимального пути L *( xi, xk) от момента xiдо момента окончания всех работ. Обозначим позднее время

По определению имеем для конечной вершины

Так, для вершины х 2сетевого графика на рис. 4.14 получаем:

Таблица 4.1

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

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

начиная от конечной вершины к начальной (см. рис. 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. —
(Университетский учебник. Сер. Прикладная математика и информатика).

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒