Кольорові сітки Петрі

Кольорові сітки Петрі є однією з найбільш важливих модифікацій традиційних сіток Петрі. За їх допомогою вдається досить компактно моделювати складні системи з великим числом різних динамічних об’єктів.

До таких систем, зокрема, відносяться багатономенклатурні багатоверстатні гнучкі виробництва.

Кольорова сітка Петрі (КСП) формально визначається як набір виду:

N = (P, Т, W, F, Н, l, y, m₀),

де Р = { р } – непорожня кінцева множина позицій;

Т = { t } – непорожня кінцева множина переходів;

W = {w} – непорожня кінцева множина кольорів маркерів;

F: P ´ T ® {0, 1, 2,...} і Н: Т ´ Р ® {0, 1, 2,...} – функції інцидентності множин позицій і переходів відповідно;

l: (Р ´ W) ´ Т ® (0, 1) – функція розподілу кольорів маркерів по вхідних позиціях переходів сітки;

y: T ´ (P ´ W) ® (P ´ W) – функція розподілу кольорів маркерів по вихідних позиціях переходів сітки;

m₀: (P ´ W) ® {0, 1, 2,...} – початкове маркування сітки.

Функція l довизначає умови збудження, а y - правило спрацьовування переходів, внаслідок чого здійснюється розподіл кольорів маркерів по позиціях сіткі при її функціонуванні.

Умова збудження переходу t Î T при деякому маркуванні m має вид:

(3.1)

Для кожного t Î T, що задовольняє умові (3.1), у загальному випадку функція l _t визначає множину допустимих вхідних розподілів кольорів маркерів, при яких ця умова виконується

.

Функція y _t для кожного допустимого вхідного розподілу з ставить у відповідність єдиний допустимий вихідний розподіл кольорів маркерів з множини

,

тобто визначає результат спрацьовування переходу і правило формування нового маркування сітки

.

Тоді умова спрацьовування переходу t, збудженого при вхідному розподілі кольорів маркерів , в наслідок чого буде утворено нове марування, має вид:

На рис. 3.8 представлений приклад графічного зображення КСП для двох кольорів: w₁ і w₂ (позначені відповідно «*» і «·»).

Функції l і y для даної сітки представлені нижче:

для t ₁: для t ₂: для t ₃:

l _{t 1}((p ₁, w₁)) = 1; l _{t 2}((p ₂, w₁)) = 0; l _{t 3}((p ₃, w₁), (p ₁, w₁)) = 0;

l _{t 1}((p ₁, w₂)) = 0; l _{t 2}((p ₂, w₂)) = 1; l _{t 3}((p ₃, w₂), (p ₁, w₂)) = 1;

l _{t 3}((p ₃, w₁), (p ₁, w₂)) = 1;

l _{t 3}((p ₃, w₂), (p ₁, w₁)) = 0;

y _{t 1}(p ₁, w₁) = (p ₂, w₂); y _{t 2}(p ₂, w₂) = (p ₃, w₁); y _{t 3}((p ₃, w₂), (p ₁, w₂)) = (p ₂, w₁);

y _{t 3}((p ₃, w₁), (p ₁, w₂)) = (p ₂, w₁).

Рис. 3.8. Графічне зображення КСП

Виділимо два окремих види КСП: перероджуючі (ПС) і селективні (СС) сітки.

У перероджуючих сітках (ПС) спрацьовування будь-якого переходу t дозволене за наявності у всіх вхідних позиціях p Î ^• t маркерів одного кольору w _j Î W. Після спрацьовування даного переходу в усіх його вихідних позиціях містяться маркери іншого кольору w _g Î W.

Функція l у ПС задається наступним чином:

де – допустимий вхідний розподіл виду:

Функція у ПС набуває значень з області допустимих вихідних розподілів:

Якщо , то перехід t при спрацьовуванні перероджує маркери кольору w _j у вхідних позиціях в маркери кольору w _g у вихідних позиціях.

Умова збудження переходу t Î T при вхідному розподілі маркування m для ПС записується у виді:

(3.2)

Нове маркування m¢, одержане в результаті спрацьовування переходу t при вхідному розподілі , визначається за правилом:

Приклад ПС з W = {w₁, w₂, w₃, w₄} показаний на рис. 3.9. Початкове маркування m₀ і функція y описуються матрицями (табл. 3.1, 3.2).

Таблиця 3.1 Таблиця 3.2

Рис. 3.9. Графічне зображення ПС

Селективною сіткою (СС) називається така сітка, у якій переходи пропускають тільки маркери певних кольорів, не змінюючи їх.

Функція l _t для СС задається так само, як і для ПС, а функція .

Умови збудження переходу t Î T СС і ПС при маркуванні mаналогічні (3.2). Нове маркування m ¢ при спрацьовуванні переходу t Î T по розподілу визначається за правилом:

Приклад СС для двох кольорів w₁ і w₂ (позначені «·» і «*») зображений на рис. 3.10. Функція l представлена матрицею (табл. 3.3).

Таблиця 3.3

Рис. 3.10. Графічне зображення СС

Отже, у СС множину переходів T можна розбити на підмножини Т_i, де " t Î T_i пропускає маркер кольору w _i. При цьому .

Підсіткою СС, що визначена на множині переходів Т_i Í Т, називається така сітка Петрі N_i = (P_i, T_i, F_i, Н_i, m _{i 0}), у якій:

;

;

;

.

Кожна підсітка N_i, є одноколірною сіткою з маркерами кольору w _i.

Отже, аналіз СС можна звести до аналізу сукупності одноколірних сіток.

Властивості КСП. Розглянемо властивості обмеженості, безпеки, зберігаємості та живучості КСП.

Обмеженість та безпека. Будемо розрізняти безпеку та обмеженість КСП у цілому і по кожному визначеному кольору w Î W. Назвемо позицію р Î Р k-обмеженою по кольору w Î W, якщо існує k Î {0, 1,...} таке, що на множині всіх досяжних маркувань m(p, w) £ k.

Сітка Петрі є k-обмеженою по кольору w, якщо всі її позиції k-обмежені по кольору.

Позиція р Î Р називається k-обмеженою, якщо існує k Î {0, 1,...} таке, що на множині всіх досяжних маркувань " w Î W, m(p, w) £ k.

Сітка Петрі називається k-обмеженою, якщо всі її позиції k-обмежені. Окремим випадком k-обмеженості сітки в цілому й обмеженості її по кольору w Î W є безпека і безпека по кольору w (випадок k = 1).

Очевидно, що якщо сітка з різнокольоровими маркерами k_i обмежена по кожному кольору w _i, то вона k-обмежена, де . Вірно і зворотнє: якщо сітка з різнокольоровими маркерами k-обмежена, то вона k-обмежена по будь-якому кольору w _i Î W.

Аналіз обмеженості сітки Петрі з різнокольоровими маркерами аналогічний аналізу обмеженості звичайної сітки.

Збереженість. У КСП виділимо збереженістьсітки в цілому і по окремих кольорах.

КСП є збереженою по кольору w _j, якщо існує вектор l= (l₁, l₂,..., l _n), l _i > 0 такий, що для всіх маркувань m(p, w _j), досяжних з початкового m₀(p, w _j), справедлива рівність:

Сітка Петрі з різнокольоровими маркерами називається збереженою, якщо існує вектор l = (l₁, l₂,..., l _n), l _i > 0, такий, що для кожного маркування m(p, w), " р Î Р, " wÎ W, досяжного з початкової сітки, справедлива рівність:

Якщо КСП є збереженою по будь-якому кольору w Î W, то вона є збереженою в цілому.

Живучість. КСП N назвемо живою, якщо:

1) " t Î T $m _i, m _j досяжні з початкового маркування m₀ такі, що (тобто маркування m _j досяжне з m _i);

2) " m _i, m _j досяжні з початкового маркування ;

3) " w Î W $m досяжне з початкової КСП таке, що $ р Î Р, m(p, w) ¹ 0.

Селективна сітка N є живою по кольору w _i, якщо сітка N_i, яка є фрагментом селективної сітки N і визначена на множині переходів Т_i, жива.

Графи досяжності сіток N_i є підграфами графа досяжності СС N при m_{0 i} (p) =m₀(p, w _i). При цьому маркування m _i, m _j, що належать графу досяжності СС, будуть належати графу досяжності G_i сітки N_i тоді і тільки тоді, коли:

m _i (p, w _l) = m _j (p, w _l); m _i (p, w _i) ¹ m _j (p, w _i), ; t ¹ i.

Отже, селективна сітка N жива тоді і тільки тоді, коли кожна N_i, , жива.

Перероджуюча сітка, наведена на рис. 3.9, не є живою. Селективна сітка, показана на рис. 3.10, також не є живою, оскільки сітки N ₁, N ₂ неживі.

Відзначимо, що КСП із кінцевим числом кольорів маркерів еквівалентна звичайній сітці Петрі з точки зору можливостей відображення властивостей об’єкта моделювання. Однак використання КСП дозволяє значно скоротити кількість позицій і переходів, необхідних для опису об’єкта, що значно спрощує і прискорює процес моделювання.

Практика моделювання показує, що незважаючи на теоретичну можливість, часто не вдається через велику розмірність та складність побудувати звичайну сітку Петрі для таких об’єктів, як дільниці ГВС із значною кількіст‘ю технологічного і транспортного устаткування. Використання ж КСП істотно спрощує цю задачу моделювання.

Оцінимо збільшення обсягу даних, необхідного для опису об’єкта сіткою при переході від КСП до еквівалентної їй звичайній сітці Петрі.

Нехай для КСП ï P ï = n; ï T ï = m; ï Wï = r. Тоді F – матриця розмірності n ´ т, Н – матриця розмірності т ´ n, m – матриця розмірності n ´ r.

Обсяг даних (число елементів) для опису КСП визначається виразом 2 mn + nr.

Щоб у сітці Петрі зберегти таку ж кількість станів, як і в еквівалентній їй КСП, необхідно кожній позиції КСП поставити у відповідність r позицій звичайній сітці. Очевидно, при цьому число переходів також збільшиться не менше, ніж у r разів. Отже, обсяг даних для її опису можна оцінити виразом 2 nmr ² + nr.

Таким чином, оцінкою зміни обсягу даних може служити відношення:

.

Очевидно, що при r = 1 значення g = 1. Для будь-якого m величина g оцінюється знизу виразом 2 r ²/(2 + r). Це означає, що при перетворенні КСП в еквівалентну їй звичайну сіику Петрі обсяг даних зростає не менше, ніж у 2 r ²/(2 + r) разів.

Відмітимо, що при m ® ¥ величина g ® r ², тобто при досить великій розмірності для опису КСП потрібно в r ² разів менше пам’яті, ніж для опису еквівалентної їй звичайній сітці Петрі.