Использование сетей Петри в математическом моделировании (стр. 2 из 5)
строительство и монтаж объектов промышленного, культурно-бытового и жилищного назначения;
реконструкция и ремонт действующих промышленных и других объектов;
планирование подготовки и переподготовки кадров, проверка исполнения принятых решений, организация комплексной проверки деятельности предприятий, объединений, строительно-монтажных организаций и учреждений. [7]
Использование методов сетевого планирования способствует сокращению сроков создания новых объектов на 15-20%, обеспечению рационального использования трудовых ресурсов и техники.
Сетевое планирование - совокупность методов, использующих сетевую модель как основную форму представления информации об управляемом комплексе работ. Использование сетевого планирования позволяет повысить качество планирования и управления при реализации комплекса работ, например, дает возможность четко координировать деятельность всех сторон (организаций), участвующих в реализации, выделять наиболее важные задачи, определять сроки реализации, а также координировать план его реализации.
Сетевая модель - информационная модель реализации некоторого комплекса взаимосвязанных работ, рассматриваемая как ориентированный граф без контуров, отображающий естественный порядок выполнения этих работ во времени; может содержать некоторые дополнительные характеристики (например, время, стоимость, ресурсы), относящиеся к отдельным работам и (или) к комплексу в целом. [5]
Наибольшее распространение получило графическое представление сетевой модели на плоскости, называемое сетевым графиком.
Для быстрого "погружения" в постановку и решение задач сетевого планирования рассмотрим простейший пример, заимствованный нами из монографий.
Предположим, что шеф-повар получил заказ приготовить яичницу из одного яйца. Вся процедура ее приготовления может быть разбита на ряд отдельных подзадач:
Взять яйцо - ---> Разбить яйцо - ---> Взять жир - --->
--> Положить жир на сковороду - ---> Растопить жир - --->
--> Вылить яйцо на сковороду - --->
--> Ждать, пока яичница не изжарится - ---> Снять яичницу
Некоторые из этих подзадач должны предшествовать другим (например, задача "взять яйцо" должна предшествовать задаче "разбить яйцо"). Ряд подзадач может выполняться параллельно (например, задачи "взять яйцо" и "растопить жир"). Шеф-повар хотел бы выполнить заказ как можно быстрее, при этом предполагается, что число его помощников не ограничено.
Необходимо распределить работу среди помощников так, чтобы заказ был выполнен за минимально возможное время.
Хотя этот пример может показаться легкомысленным, подобная задача возникает во многих ситуациях, связанных с планированием реальных действий. В больших вычислительных системах осуществляется планирование заданий с целью обеспечения минимального времени нахождения задания в системе, технолог на заводе может планировать организацию работы конвейера, минимизирующую время производства продукции, и т.п. Все проблемы подобного рода тесно связаны между собой и могут быть решены с использованием графов.
Давайте представим исходную задачу в виде графа. Каждая вершина графа представляет собой подзадачу, а каждая дуга (x,y) представляет требование, что задача y не может выполняться до тех пор, пока не завершено выполнение задачи x. Граф задачи показан на рисунке:
Рис.1. Граф задачи
Заметим, что в изображенном графе узлы 1 и 6 не имеют предшественников, и, следовательно, подзадачи, которые они представляют, могут выполняться сразу же и параллельно без ожидания завершения других подзадач. Все остальные подзадачи должны ждать завершения по крайней мере одной из этих подзадач. Как только эти первые две подзадачи завершены, соответствующие вершины и инцидентные дуги могут быть удалены из графа. Отметим, что получающийся в результате граф не содержит контуров, поскольку вершины и дуги удалялись из графа без циклов. Стало быть, новый граф также должен содержать по крайней мере один узел, не имеющий предшественников. В нашем примере существуют два таких узла - 2 и 7. Значит, подзадачи 2 и 7 могут выполняться параллельно во второй период времени.
Продолжив построение далее, мы найдем, что минимальное время, за которое может быть поджарена яичница, - шесть временных периодов (предполагая, что каждая подзадача требует ровно один период времени), а максимальное требующееся число помощников - два:
Период времени Помощник 1 Помощник 2
1. Взять яйцо Взять жир
2. Разбить яйцо Положить жир на сковороду
3. Растопить жир
4. Вылить яйцо на сковороду
5. Ждать, пока яичница не изжарится
6. Снять яичницу
Автоматизируем процесс построения решения задачи, модифицируя алгоритм топологической сортировки, проиллюстрированный программой, следующим образом: while (Граф не пуст)
{Определить вершины, не имеющие предшественников.
Распечатать эту группу узлов с указанием, что эти подзадачи
могут быть выполнены параллельно в следующий момент времени.
Удалить из графа данные вершины и инцидентные дуги}
Программа. Применение топологической сортировки для решения простейших задач сетевого планирования.
#include <iostream. h>
typedefstruct Leader *Lref; // Тип: указательназаголовочныйузел.
typedefstruct Trailer *Tref; // Тип: указатель на дуговой узел.
// Описание типа заголовочного узла.
typedefstruct Leader
{
int Key; // Информационноеполе.
int Count; // Количество предшественников.
Tref Trail;
Lref Next;
};
// Описание типа дугового узла.
typedefstruct Trailer
{
Lref Id;
Tref Next;
};
class Spisok {
private:
Lref Head; // Указатель на список заголовочных узлов.
Lref Tail; // Указатель на фиктивный элемент
// в конце списка заголовочных узлов.
int z; // Количество узлов, не имеющих предшественников.
public:
Spisok () { // Инициализация списка заголовочных узлов.
Head = Tail = new (Leader); z = 0; };
Lref L (int);
void Poisk ();
void Vyvod ();
};
void Spisok:: Poisk ()
{
Lref p,q; // Рабочие указатели.
p = Head; Head = NULL;
while (p! =Tail)
{
q = p; p = p->Next;
if (q->Count==0)
{ q->Next = Head; Head = q; }
}
}
Lref Spisok:: L (int w)
// Функция возвращает указатель на ведущего с ключом w.
{
Lref h = Head;
Tail->Key = w;
while (h->Key! =w) h = h->Next;
if (h==Tail)
// В списке нет элемента с ключом w.
{
Tail = new (Leader); z++;
h->Count = 0; h->Trail = NULL; h->Next = Tail;
}
return h;
}
void Spisok:: Vyvod ()
{
Lrefp,q; // Рабочие указатели.
Lref S,U; // Рабочие указатели.
Tref t;
cout << endl;
cout << "Результат... \n";
q = Head;
while (q! =NULL)
// Вывод всех элементов с нулевым количеством предшественников.
{
S = q; cout << " (";
while (S! =NULL)
{ cout << S->Key << " "; z--; S = S->Next; }
cout << ")";
// - ------------------------------------------------ -
U = NULL; // Указатель на очередной список элементов
// с нулевым количеством предшественников.
while (q! =NULL)
{
t = q->Trail;
while (t! =NULL)
{
p = t->Id; p->Count--;
if (p->Count==0) // Включение (*p) в список ведущих.
{ p->Next = U; U = p; }
t = t->Next;
}
q = q->Next;
}
q = U;
}
if (z! =0)
cout << "\nМножество не является частично упорядоченным! \n";
}
void main ()
{
Spisok A;
Lref p,q; // Рабочие указатели.
Tref t;
int x,y; // Рабочие переменные.
// Фаза ввода.
cout << "Задайте отношение частичного порядка... \n";
cout << "Элемент ";
cin >> x;
cout << " предшествует элементу ";
while (x! =0)
{
cin >> y;
p = A. L (x); q = A. L (y);
t = new (Trailer); t->Id = q; t->Next = p->Trail;
p->Trail = t; q->Count += 1;
cout << "Элемент ";
cin >> x;
cout << " предшествует элементу ";
}
// Поиск ведущих с нулевым количеством предшественников.
A. Poisk ();
// Фаза вывода.
A. Vyvod ();
} [11]
§3. Математические модели с использованием сетей Петри
Сети Петри являются эффективным инструментом дискретных процессов, в частности, функционирования станочных систем. Их особенность заключается в возможности отображения параллелизма, асинхронности и иерархичности.
На рис.2 приводится пример сети Петри, где Р - конечное непустое множество позиций (состояний); Т - конечное непустое множество переходов (событий), причем p
P и ti T; F: Р x Т - {0, 1, 2,... }; Н: Т x Р 
{0, 1, 2,... } - функции входных и выходных инциденций; μ0: Р {0, 1, 2,... } - начальная маркировка. Вершины сети p P изображены кружками, а вершины ti T - черточками (баркерами). Дуги соответствуют функциям инцидентности позиций и переходов. Точки в кружочках означают заданную начальную маркировку. Число маркеров в позиции равно значению функции μ: Р {0, 1, 2,... }. Переход от одной маркировки к другой осуществляется срабатыванием переходов. Переход t может сработать при маркировке μ, если он является возбужденным: 
(1) 
Рис.2. Сеть Петри
Данное условие показывает, что в каждой входной позиции перехода t число маркеров не меньше веса дуги, соединяющей эту позицию с переходом. В результате срабатывания перехода t, удовлетворяющего условию (1), маркировку μ заменяют маркировкой μ' по следующему правилу:
(2)По этому правилу в результате срабатывания из всех входных позиций перехода t изымается F (p,t) маркеров и в каждую выходную позицию добавляется H (t,p) маркеров. Это означает, что маркировка μ' непосредственно достижима из маркировки μ. Функционирование сети Петри - последовательная смена маркировок в результате срабатывания возбужденных переходов.