Зміст

Вступ

1. Мережі Петрі

1.1 Визначення мережі

1.2 Розмітка мережі

2. Розширення мереж Петрі

3. Приклади подання елементів виробничих систем

Література

Вступ

Тема контрольної роботи "Імітація процесів ГВС за допомогою апарата мереж Петрі".

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

В курсі "Основи автоматизованого проектування засобів обчислювальнної техніки" вивчаються методи, алгоритими та основні підходи до проектування сучасних обчислювальних засобів. Дисципліна базується на матеріалі курсів "Вища математика", "Програмування", "Чисельні методи" та ін. Методи постановки й рішення завдань автоматизації широко використовують апарат теорії графів і математичного програмування.

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

Мета роботи – навчитися застосовувати мережі Петрі для моделювання процесів у ГВС.

1. Мережі Петрі

Компоненти будь-якої системи і їхньої дії можна представити абстрактними подіями. Подія може відбутися один раз, повторитися багаторазово, породжуючи конкретні дії, або не відбутися жодного разу. Сукупність дій, що виникають як реалізації подій, утворюють процес. У загальному випадку та сама система може функціонувати в тих самих умовах по-різному, породжуючи деяку множину процесів.

Реальна система функціонує в часі, події відбуваються в деякі моменти часу й діють якийсь час. Якщо строго враховувати час, то такий підхід до моделювання великих паралельних систем буде мати ряд недоліків.

У великій системі доводиться враховувати стан всіх компонентів при кожній зміні її загального стану, що робить модель громіздкою.

Зникає інформація про причинно-наслідкові зв'язки між подіями в системі. Якщо дві події при функціонуванні системи відбулися одночасно, то ми не знаємо, чи відбулося це випадково, чи ні. Такі поняття, як конфлікти між компонентами системи або очікування одним з них результатів роботи інших, важко виражаються в термінах зміни станів системи.

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

Виходом може служити відмова від введення в моделі дискретних систем часу й тактованих послідовностей змін станів, і заміна їхніми причинно-наслідковими зв'язками між подіями. Моделі такого типу добре описуються термінами мережі Петрі.

Імітація процесів - це інтерпретація послідовності здійснення подій кожна з яких характеризується моментами запуску й закінчення.

Відзначимо особливості процесів гнучких виробничих систем (ГВС) із погляду функціонування:

• паралелізм;

• асинхронність;

• іерархичність.

Інтерпретація мереж Петрі заснована на поняттях умови й події. Стан системи описується сукупністю умов. Функціонування системи складається в здійсненні послідовності подій. Для виникнення події необхідне виконання деяких умов, називаних предумовами. Виникнення подій може привести до виконання умов, називаних постумовами. У мережі Петрі умови моделюються позиціями, події - переходами. Предумови події представляються вхідними позиціями відповідного переходу, постумови - вихідними позиціями.

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

Оскільки події які моделюються мережею Петрі є миттєвими і неодночасними, і їхній взаємозв'язок асинхронний, це зручний апарат для моделювання множини взаємозалежних і паралельних процесів. Використання мереж Петрі в завданнях, пов'язаних з розподілом ресурсів, привабливо наочністю, адекватністю й технологічністю при реалізації моделей на ЕОМ.

Мережі Петрі - це математична модель, що має широке застосування для опису поводження паралельних пристроїв і процесів. У цей час визначені й вивчені різноманітні класи мереж Петрі. Ми розглянемо загальні поняття й можливості використання мереж Петрі для завдання прямого керування в паралельних програмах.

1.1 Визначення мережі

Мережа Петрі є двочастковий орієнтований граф. Двочастковий граф - це такий граф, множина вершин якого розбивається на дві підмножини й не існує дуги, що з'єднує дві вершини з однієї підмножини. Отже, мережа Петрі - це набір

N = (T,P,A), T  Р = Ø, (1.1)

де Т = {t₁,t₂,...,t_n} - підмножина вершин, що називаються переходами; Р = {p₁, р₂, ..., p_m} - підмножина вершин, що називаються (подіями)місцями; А (T×P) – множина орієнтованих дуг.

По визначенню, дуга з'єднує або місце з переходом, або перехід з місцем.

Приклад

На рис. 1.1 наведений приклад мережі Петрі в графічному поданні. Переходи позначені рисками, а місця - окружностями. Кожен перехід t має набір вхідних in{t} і набір вихідних out{t} дуг. Мережі Петрі можуть представлятися також у формі продукційних правил (рис. 1.1,б).

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

Рис 1.1 Приклад мережі Петрі в графічному поданні

1.2 Розмітка мережі

Мережі Петрі можна розуміти (інтерпретувати) по-різному. Можна уявити собі, що місця представляють умови (буфер порожній, файл закритий і т.п.), а переходи - події (посилка або одержання повідомлення в буфер, запис у файл).

Стан мережі Петрі в кожен сучасний момент визначається системою умов. Для того щоб стало можливі зручним задавати умови типу "у буфері перебуває 3 записи", у модель мережі Петрі додаються фішки. Фішки зображуються крапками усередині місця. У застосуванні до програмування можна уявляти собі переходи як процедури, а місця - як змінні або буфер.

Фішка свідчить про те, що змінна/буфер має значення, а якщо місце має, приміром, 3 фішки, те це може інтерпретуватися як наявність трьох різних значень у буфері.

Якщо місце містить фішку, то місце маркіроване й мережа називається маркірованою. Початковий розподіл фішок задає початкове маркування М₀ мережі. Маркування мережі визначає її поточний стан.

Мережа на рис.1.2 у початковому стані містить одну фішку в місці р₃.

Рис 1.2 Послідовність станів мережі Петрі

Маркування формально задається функцією М: Р → I, I = {0,1,2,..}, а функція М представляється вектором, у якому i-й компонент задає маркування місця p_i.

Наприклад, початкове маркування мережі на рис. 1.2 представляється вектором М₀ = {1,0,0}.

На рис. 1.2 показана послідовність станів мережі Петрі в ході спрацьовування переходів. Початкова розмітка М₀ = (1,0,0) показана на рис1.2,а.

У цьому стані може спрацювати тільки перехід t₁. Розмітка мережі M₁ = (1,1,1) після спрацьовування t₁ показана на рис.1.2,б. Остання дозволяє одночасно спрацювати переходам t₁ й t₂ , розмітка М₂ = (1,2,3) після їхнього спрацьовування показана на рис.1.2,в.

Мережа переходить із одного стану в інше (від одного маркування до іншого), коли відбувається подія – спрацьовування переходу.

Перехід може спрацювати, якщо є хоча б одна фішка у всіх його вхідних місцях (рис.1.3)

Рис 1.3 Схема спрацьовування переходів

Спрацьовування переходу складається з того, що із всіх вхідних місць забирається по одній фішці й в усі вихідні місця додається по одній фішці.

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

В іншій інтерпретації перехід може представляти деякий пристрій. Пристрій може (але не повинен) спрацювати, якщо виконалися всі вхідні умови.

Якщо кілька переходів готові спрацювати, то спрацьовує один з них (кожен), або деякі з них, або всі (рис.1.4).

Рис 1.4 Варіанти спрацьовування мережі

Приклад

Розглянемо приклад конвеєра. Нехай є три обробні пристрої t₀, t₁, t₂ організовані у вигляді конвеєра. Це можуть бути, наприклад, верстати на заводі або функціональні пристрої конвеєрного процесора й взагалі будь-який конвеєр, у якому кожен обробний пристрій виконує лише частину загальної роботи, а результат буде вироблений лише останнім з них.

Особливістю нашого конвеєра є обмеженість ємності місць p₁ і р₂; місце p₁ може вмістити лише два результати (місце p₁ мережі є 2-обмеженим) попереднього етапу роботи конвеєра (виробляється переходом t₀), а місце p₂ - 3-обмеженим.

Символ n у місці р₀ означає наявність n фішок у ньому, n - ціле позитивної число.

Мережа Петрі, що забезпечує необхідне пряме керування, наведена на рис.1.5. Зрозуміло, що в місці p₁ не може нагромадитися більше 2 фішок при будь-яких порядках спрацьовування переходів мережі.

Місця p₁ і р₂ часто ще називають асинхронними каналами, з їхньою допомогою реалізується програмування засобами асинхронного message passing interface.

Рис 1.5 Імітаційна модель необхідного прямого керування

Мережа Петрі, у якій всі місця 1-обмежені, називається безпечною. Такою мережею можна задавати пряме керування в програмах.

Безпечна мережа ніколи, не допустить, щоб у змінну було покладено нове значення, якщо старе ще не було використано по призначенню. Порушення цього правила часто є причиною помилок у паралельних програмах.

2. Розширення мереж Петрі

Для того, щоб використати мережі Петрі для моделювання стохастичних процесів, були здійснені наступні розширення:

Використання часу (стохастичні Мережі Петрі)

Для моделювання різних процесів необхідно кількісно розглядати час. У стандарті мереж Петрі для цього немає механізмів. Стохастичні мережі Петрі як розширення стандарту мереж Петрі можуть розглядати час. У принципі будь-які елементи мережі Петрі можна об'єднати з компонентом часу. Так, час могло б розташовуватися в позиціях, мітках, дугах й/або переходах.

Для SimNet час установлюється в перехід (синхронізовані мережі Петрі). Таким чином, дії, що поглинають час, описуються переходами, оскільки стани описуються позиціями. Якщо мітки деяких позицій будуть інтерпретуватися як послуги, що виробляються за деякий номінальний час, то такі позиції можуть замінятися переходом. Крім того, у цьому випадку мітки таких переходів не затримуються в ньому протягом часу роботи, але встановлюються як недоступні (зарезервовані) у вихідних позиціях. Це допомагає уникнути ситуації, коли через паралельні процеси спрацьовування переходу стає неможливим протягом часу послуги. Це повинне вимагати повернення міток на вхідні позиції, які відбивають реальні процеси й не пристосовані до односпрямованого поняття потоку, яке використовується в стандарті мереж Петрі.

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

Коли перехід одержує можливість спрацьовування, він спрацьовує негайно. Мітки, узяті у вхідних позиціях, установлюються у вихідні позиції.

Час послуги може описуватися кожним з наступних розподілів:

постійний розподіл; однорідний розподіл;

експонентний розподіл; розподіл Эрланга;

пуасоновський розподіл; нормальний розподіл;

розподіл Вейбулла; бета-розподіл;

трикутний розподіл (симетричне); гамма-розподіл.

Пофарбовані (кольорові) мережі Петри

Для багатьох завдань моделювання необхідно розрізняти різні типи інформації й істотних потоків, які зустрічаються в системі. У відомій мірі це може досягатися окремими структурами мереж Петрі для кожного з типів потоку, які синхронізуються тільки в переходах. Але із цим методом модель губить свою подібність із вихідною системою, де різні типи потоків часто використають однакові маршрути передачі. Додаткові проблеми виникають, коли різним типам потоків потрібно поширювати обмежені ресурси.

Щоб моделі різних потоків мали взаємозалежності, розподіл типів потоків окремими позиціями й дугами неможливий. Тому бажано, щоб однорідні мітки одного потоку відрізнялися від однорідних міток іншого потоку. Це розширення стандарту мережі Петрі назване пофарбованою або кольоровою мережею Петрі.

Рішення Конфлікту.

Два переходи вступають у конфлікт, якщо обоє мають можливість спрацьовування, але після запуску одного переходу предумови або постумови іншого переходу стають нездійсненними. У цьому випадку перехід, що дійсно повинен спрацювати, визначається однією з наступних стратегій:

Пріоритет:

Пріоритет переходу може перебувати в проміжку значень [0, 255]. Величина 0 означає самий верхній, 255 - найнижчий пріоритет. Якщо різні переходи можуть спрацювати в той самий час, спочатку спрацьовує перехід із самим верхнім пріоритетом, а потім, можливо, інші переходи в міру зменшення пріоритетів, якщо умови їхнього спрацьовування усе ще виконуються.

Якщо дійсно мав місце конфлікт переходів, із запуском переходу із самим верхнім пріоритетом можливість спрацьовування переходу з нижнім пріоритетом виключається.

Імовірність:

Для кожного переходу може бути оголошена ймовірність спрацьовування. Якщо різні переходи того самого пріоритету можуть спрацювати в той самий час, спочатку спрацьовує той перехід, у якого ймовірність спрацьовування вище. Таким чином, крім дозволу конфлікту, також можуть бути описані ймовірності для переходів.

3. Приклади подання елементів виробничих систем

Розглянемо ГВМ (рис.1.6, а). Послідовність взаємодії його елементів полягає в наступному: переміщення за допомогою робота R заготівлі від конвеєра CV1 на конвеєр (або тактовий стіл) CV2; пересування заготівлі конвеєром CV2 на верстат М; обробка заготівлі на верстаті; пересування обробленої деталі від верстата на конвеєр (стіл) CV2; транспортування деталі роботом R від конвеєра CV2 на конвеєр CV3.

Вважаємо, що кожний з компонентів ГВМ — верстат М, робот R і конвеєр CV2 може бути завантажений тільки однією деталлю. Елементи модуля виконують свої операції незалежно друг від друга, тобто робот починає свої транспортні операції, коли на одному з конвеєрів, CV1 або CV2, перебуває деталь; конвеєр CV2, що одержав деталь від робота, починає пересуватися в напрямку верстата; завантажений заготівлею верстат М починає операцію обробки; оброблена деталь переміщається незавантаженим конвеєром CV2 у позицію розвантаження роботом.

Модель взаємодії елементів ГВМ і виконання виробничого процесу може бути інтерпретована мережею Петрі (рис.1.6, б). Компоненти структури мережі інтерпретуються в такий спосіб.

Позиції р_2--р₆ відображають окремі операції виробничого процесу відповідно:

- транспортування заготівлі роботом до конвеєра СV2,

- пересування заготівлі до верстата конвеєром,

- обробку,

- пересування обробленої деталі конвеєром CV2 до робота,

- транспортування деталі роботом і розміщення її на конвеєрі CV3.

Наявність мітки в одній з позицій відповідає стану виконання якоїсь із технологічних операцій. Позиції р₇...р₉ відображають відповідно стану компонентів ГВМ: робота, конвеєра CV2 і верстату. Позиція р₁ інтерпретується як склад заготівель. Наявність мітки в одній з позицій р₇...р₉ відповідає ситуації, у якій деякі з компонентів ГВМ виконують певну виробничу операцію.

Наприклад, маркування (2, 0, 0, 1, 0, 0, 0, 0, 1), досяжне з початкового маркування (3, 0, 0, 0, 0, 0, 0, 0, 0) внаслідок послідовності спрацьовувань переходів. Т відповідає стану системи, у якому перша заготівля обробляється на верстаті, тоді як інші заготівлі чекають своєї черги на складі.

Переходи t_v..t_ts відповідають подіям, що відбивають початок або завершення моделюємих операцій. Наприклад, перехід t₂ інтерпретується як подія, пов'язана із завершенням операції транспортування заготівлі роботом й установки її на конвеєрі CV2, а також з початком операції переміщення заготівлі конвеєром CV2 до верстата.

У даному прикладі технологічні операції моделюються позиціями. Іноді використовуються моделі, у яких виконання операції моделюється переходами. Як ілюстраці. такого підходу розглянемо модуль автоматичного пакування (рис. 1.7, а). Технологічні операції виробничого процесу виконуються в такій послідовності:

- операція заповнення конвеєром CV1 накопичувача (локального складу);

- заповнення роботом R тари, розміщеної на палеті;

- пересування палети з пакувальною тарою уздовж конвеєра

Мережна модель складського модуля представлена на рис.1.6, б.

Рис. 1.6. Схема модуля автоматичного пакування об'єктів виробництва (а), мережна модель складського модуля (б) і дерево досяжних маркувань (в)

Переходи t_l3 t₂, t_s відображають виконання технологічних операцій відповідно:

• заповнення накопичувача;

• пересування й установку пляшок у тару роботом R;

• переміщення палети із заповненою тарою уздовж конвеєра CV2.

Позиції р_ь, p_it р_ь відображають стан основних компонентів модуля: конвеєра CV1, робота R і конвеєра CV2. Відсутність мітки в одній з розглянутих позицій означає, що відповідний компонент виконує певну технологічну операцію.

Позиції р_1, р₂ відображають відповідно накопичувач С и заповнювану тару.

Число міток, що перебувають у цих позиціях, відображає кількість пляшок, які заповнюють накопичувач або впакованих у тарі. Наприклад, маркування (2, 4, I, 1, 1), досяжне з початкового маркування i₀ = (0, 0, 1, 1, 1).

Література

1. Системы автоматизированного проектирования. В 9-ти кн.Учебное пособие для вузов. Под редакцией Норенкова И.П. М.: Высш. шк., 1986.

2. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. Учебное пособие для вузов. - М.: Высш. шк., 1986.

3. П. Шеннен и др. Математика и САПР. т.1. М.: Мир, 1988.

4. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

5.Системы автоматизированного проектирования в радиоэлектронике. Справочник. М.: Радио и связь, 1986.

6. Погребной В.К. О декомпозиции графов на классы изоморфных подграфов. В кн.: Вопросы программирования и автоматизации проектирования. Изд. ТГУ, 1979, с. 82-96.

7. Петренко А.И. Основы автоматизации проектирования. К.: Техника, 1982. - 295 с.

8. Ильин В.Н.. Основы автоматизации схемотехнического проектирования. Г.: Энергия, 1979. - 392 с.

9. Демидович Б.П., Марон И.А. Основы вычислительной математики. Г.: Изд-во "Наука", 1966. - 664 с.

10.Разевиг В.Д. Система сквозного проектирования электронных устройств DesignLab 8.0.- М.: Изд-во "Солон",1999. - 698 с.

11. Автоматизация схемотехнического проектирования на мини-эвм: Учебное пособие/ Под ред. Проф. Анисимова. Л. Изд-во ЛГУ, 1983. - 200 с.

12. Чуа Л.О., Пен-Мин Линь. Машинный анализ электронных схем: Алгоритмы и вычислительные методы. Пер с англ. Г.: Энергия, 1980. – 640 с.

13. Математическое и программное обеспечение САПР радиоэлектронной аппаратуры: Учебное пособие/ Огороднейчук И.Ф., Семенец В.В., Куник Э.Г. и др. К.: УМК ВО, 1988. - 104 с.