ms

шому. Можна позбавитись від конфліктної ситуації створивши замість однієї позиції «є зелене світло у 1 та 2 напрямках» дві позиції «є зелене світло у 1 напрямку» та «є зелене світло у 2 напрямку», що призведе до збільшення кількості позицій вдвічі.

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

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

Представимо підсистему руху автомобілів через перехрестя мережею Петрі з інформаційними зв’язками (рисунок 3.21). В такому представленні моделі конфлікт при сумісному використанні маркеру в позиції «є зелене світло» не виникає. По-друге, не виникає необхідності вводити додаткові переходи чи додаткові позиції, що ускладнюють модель. Функціонування такої моделі якнайбільш наближено до функціонування реальної системи.

Рисунок 3.21. Підсистема руху автомобілів у і-ому напрямку, представлена мережею Петрі з інформаційними зв’язками

81

Часові затримки, які передбачаються для переходів, указані на рисунку (t1=-а×lnζ, де а – середнє значення інтервалу надходження автомобілів, ζ - рівномірно розподілена в інтервалі (0;1) випадкова величина).

Виділимо події, які відбуваються в підсистемі управління:

горить зелене світло в 1-ому та 2-ому напрямках;

горить жовте світло в усіх напрямках;

горить зелене світло в 3-ому та 4-ому напрямках;

горить жовте світло в усіх напрямках;

Подія «горить зелене світло в 1-ому та 2-ому напрямках» відбувається за умови, що вичерпаний час горіння червоного світла в усіх напрямках і настав час горіння зеленого світла в 1-ому та 2-ому напрямках. Результатом цієї події є виконання умови «є зелене світло Подія «горить жовте світло усіх напрямках» відбувається за умови, що

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

Умова «є зелене світло в першому напрямку» виникає разом з умовою «вмикається зелене світло на першому напрямку» і зникає разом з початком горіння червоного світла в обох напрямках. Так само умова «є зелене світло в другому напрямку». Таким чином, підсистема управління дорожнім рухом на перехресті представляється мережею Петрі як на рисунку 3.22.

жовте світло

Рисунок 3.22. Підсистема управління руху автомобілів на перехресті, представлена мережею Петрі

З’єднуючи підсистеми руху в кожному напрямку та підсистему управління рухом, отримуємо модель, що представлена на рисунку 3.23.

82

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

n

åМ (черга)k × Dtk

Середній час очікування автомобілів у черзі розраховується як сумарне очікування автомобілів у черзі, розділене на кількість автомобілів, що здійснили переїзд:

Запропонований підхід до побудови моделі перехрестя, керованого світлофорами, реалізований в системі Crossroads [Стеценко, Батора, 2007].

Приклад 2. Система керування запасами.

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

визначеним часом tконтролю. Якщо при перегляді стану запасів товару виявилось, що кількість товарів у запасі менша за m штук, то приймається

рішення про поповнення запасу товарів і здійснюється замовлення на доставку товарів. Доставка товарів здійснюється протягом відомого часу

tдоставки. Кількість товарів, що доставляються, доводить запас до максимального рівню запасів.

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

Виділимо події, які відбуваються в підсистемі обслуговування поку-

пців:

надійшов покупець;

покупка одиниці товару;

товар відсутній.

Подія «надійшов покупець» відбувається з часовою затримкою tнадх. Подія «покупка одиниці товару» здійснюється за умов, що є покупець у

84

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

Виділимо події, які відбуваються в підсистемі прийняття рішення про поповнення запасу:

контроль стану запасу;

прийняття рішення про достатній стан запасу;

прийняття рішення про недостатній стан запасу;

поповнення запасу;

періодичність контролю запасів.

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

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

ній? У позиції «недостатній запас» з’являється маркер, яка або потрапляє в перехід «контроль стану запасів» або спричиняє перехід «поповнення запасу». Присвоїмо переходу «контроль стану запасів» більший пріоритет ніж перехід «поповнення запасу». Тепер, якщо в позиції «запас» є достатня кількість маркерів, то умова «недостатній запас» миттєво зникає, а замість неї з’являється умова «достатній запас». Якщо ж у позиції «запас» відсутня достатня кількість маркерів, то умова «недостатній запас» залишається і спричиняє спрацьовування переходу «поповнення запасу».

Рішення про достатній стан запасу приймається, якщо позиція «запас» містить не менше m маркерів. Інакше приймається рішення про недостатній стан запасу і здійснюється подія «поновлення запасу», в результаті

якої протягом часу tдоставки здійснюється доставка товарів і в позицію «запас» надходить відповідна кількість маркерів. Поповнення запасу відбува-

ється до максимального рівня N штук товарів, таким чином кількість товарів, що доставляються розраховується як максимальна кількість товарів мінус кількість товарів у запасі, тобто N-М(запас) штук товарів.

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

85

шення про поповнення стану запасів, кількість товарів, що доставляються,

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

запас N

m

N-М(запас)

контроль стану запасу закінчився

поповнення запасу

достатній

запас

періодичність

контролю підсистема прийняття рішення про поповнення запасу

Рисунок 3.24. Модель системи керування запасами товарів торгового підприємства

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

86

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

кількість товарів, що доставляються = «запас» + «кількість замовлених товарів» + «кількість невдоволеного попиту»,

де «запас» – це кількість маркерів у позиції «запас» на момент здійснення замовлення.

На рисунку 3.25 представлена підсистема прийняття рішень про поповнення запасу з ускладненою стратегію прийняття рішень.

запас

N

усі

кількість вдоволеного попиту

кількість невдоволеного попиту підсистема прийняття рішення про поповнення запасу

Рисунок 3.25. Підсистема керування запасами товарів торгового підприємства

В багатьох випадках інформаційні зв’язки дозволяють представити модель системи у більш зрозумілому і компактному вигляді. Порівняйте, наприклад, представлення події «поломка» звичайною мережею Петрі (див. рисунок 3.13) та представлення цієї ж події мережею Петрі з інформаційними зв’язками (рисунок 3.26). Обслуговування об’єктів відбуваєть-

87

ся тут тільки при наявності працюючого пристрою і наявність цього пристрою перевіряється за допомогою інформаційного зв’язку між позицією «пристрій працює» та переходом «обслуговування об’єктів». Успішність виконання обслуговування перевіряється також тільки наявністю працюючого пристрою за допомогою інформаційного зв’язку. В результаті відпадає необхідність використовувати позицію «поламаний пристрій» та перехід «ремонтування 1».

Рисунок 3.26. Моделювання поломок пристрою мережею Петрі з інформаційними зв’язками

Крім того модель з інформаційними зв’язками більш коректна. Дійсно в попередній моделі події «поломка» пристрій відправляється на ремонтування дещо пізніше, ніж потрібно, оскільки маркер потрапляє в позицію «поламаний пристрій» тільки після того, як сплине планований час обслуговування об’єкта. В моделі з інформаційними зв’язками такої проблеми не виникає, пристрій відправляється на ремонтування зразу, як тільки виникла поломка. Невеличка похибка може спостерігатися в цій моделі тільки при підрахунку середньої довжини черги об’єктів. Дійсно, повернення об’єкта, який оброблений не успішно, відбувається тільки після того, як закінчився планований час обслуговування і з’ясувалось, що пристрій зламався. Якщо значення середньої довжини черги важливо дослідити більш точно, то похибки можна уникнути, якщо замінити подію «обслуговування об’єктів» з часовою затримкою tобс на подію «припинення обслуговування об’єктів» з часовою затримкою t = min{tобс ,tпол }, що дорі-

внює мінімальному із значень планованого часу обслуговування та планованого часу виникнення поломки.

88

Приклад 3. Управління чергами.

У деяких задачах виникають процеси пов’язані з управлінням чергами. Наприклад, у черзі клієнти, що очікують, переходять (переїжджають) з однієї черги в іншу. Реалізувати такий фрагмент звичайною мережею Петрі неможливо. А за допомогою мережі Петрі з інформаційними зв’язками та зв’язками, що залежать від поточного маркірування мережі Петрі, такий фрагмент представляється так, як це показано на рисунку 3.27. Припустимо, що у черзі Ч1 знаходиться у даний момент часу 3 маркери, а у черзі Ч2 – 2 маркери, тоді в результаті перевірки умов запуску переходів «порівняння з чергою 1» та «порівняння з чергою 2» отримаємо, що умова запуску переходу «порівняння з чергою 1» не виконана, а умова запуску переходу «порівняння з чергою 2» - виконана. В результаті запуску переходу «порівняння з чергою 1» у позиції «Ч1 довша за Ч2» з’явиться маркер, що спричиняє запуск переходу «перехід з Ч1 до Ч2». В результаті запуску переходу «перехід з Ч1 до Ч2» один маркер з Ч1 видаляється і додається до черги Ч2, а умова «Ч1 довша за Ч2» зникає.

порівняння з чергою 2

перехід з

Ч2 до Ч1 перехід з Ч1 до Ч2

порівняння з чергою 1

Рисунок 3.27. Фрагмент мережі Петрі, що моделює перехід з однієї черги в іншу за умови, що вона коротша

Процес функціонування мережі Петрі з інформаційними зв’язками відрізняється від процесу функціонування звичайної мережі Петрі тим, що

89

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

3.7. Приклади розв’язання задач

Задача 1. Складіть формалізовану модель системи засобами мереж масового обслуговування для наступної задачі:

Система передачі даних забезпечує передачу пакетів даних із пункту А в пункт С через транзитний пункт В. У пункті А пакети надходять через 10±5 мс. Тут вони буферуються в накопичувачі ємністю 20 пакетів і передаються по будь-якій із двох ліній АВ1-за час 20 мс або АВ2-за час 20±5 мс. У пункті В вони знову буферуються в накопичувачі ємністю 25 пакетів і далі передаються по лініях ВС1 (за 25±3 мс) і ВС2 (за 25 мс). Причому пакети з АВ1 надходять у ВС1, а з АВ2 - в ВС2. Щоб не було переповнення накопичувача, у пункті В вводиться граничне значення його ємності - 20 пакетів. При досягненні чергою граничного значення відбувається підключення резервної апаратури і час передачі знижується для ліній ВС1 і ВС2 до 15 мс.

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

Розв’язання. Об’єктом обслуговування в системі, яка описана в умові задачі, є пакети даних, що передаються. Обслуговування здійснюють лінії зв’язку АВ1, АВ2, ВС1, ВС2. Оскільки пакети, які передавались лінією АВ1, передаються далі лінією ВС1, то об’єднувати лінії АВ1 і АВ2 в одну СМО не можна. Тому, кожній з ліній зв’язку поставимо у відповідність СМО: лінії АВ1 – СМО1, лінії АВ2 – СМО2, лінії ВС1 – СМО3, , лінії

ВС2 – СМО4.

Перша і друга СМО, що відповідають буферу пакетів даних у пункті А, мають спільну чергу, в якій за умовою задачі не може міститись більше 20 пакетів. Тому черга має обмеження 20 місць. Канал першої СМО, який відповідає лінії АВ1, обслуговує пакети з часом tобр=20. Канал другої СМО, який відповідає лінії АВ2, обслуговує пакети з часом tобр=20±5. Після обробки у першій СМО пакет надходить до третьої СМО. А після обробки в другій СМО пакет надходить до четвертої СМО. На сумарну кількість пакетів у чергах третьої та четвертої СМО за умовою задачі складає 25 пакетів. Канал третьої СМО відповідає лінії ВС1 і має параметр часу обслуговування, що дорівнює 25±3 мс за умови, що сума пакетів, яка міс-

90