Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Алгоритм моделювання систем масового обслуговування

Основою побудови моделі є об'єктний підхід, який передбачає створення моделі системи як множини об'єктів, що взаємодіють між собою. У цій моделі можна виділити об'єкти — вимоги (покупці) і деякий ресурс (R) — пристрій для обслуговування (статичний об'єкт продавець). Якщо вимога претендує на ресурс, зайнятий у даний момент часу, то вона стає в чергу. Черга також є окремим об'єктом — списком, пов'язаним з ресурсом. Для системи обслуговування введемо також правило обслуговування «перший прийшов — першим обслужили».

Під час моделювання для кожної пари «вимога-ресурс» потрібно з'ясувати, як довго вимога j буде використовувати ресурс R, тобто треба зазначити проміжок часу між моментами призначення ресурсу R вимозі j і звільнення цього ресурсу. Однак перш ніж ресурс буде призначено вимозі;', на нього повинен надійти запит. У загальному випадку вимога може чекати в черзі до призначення ресурсу.

Опишемо алгоритм роботи системи обслуговування з погляду на «життєвий цикл» покупця, тобто від моменту його приходу до магазину до моменту виходу з нього. Оскільки покупці приходять до магазину безперервно протягом деякого періоду часу спостереження за системою (час, упродовж якого моделюється система), то потрібно відтворити потік покупців шляхом «створення» їх у моделі (генерування в деякі моменти часу — моментів їх приходу до магазину). Для створення об'єктів покупець використовується спеціальна підпрограма генерування (у мові GPSS [68] цій підпрограмі відповідає блок GENERATE). Наведемо алгоритм її роботи.

1. Створити динамічний об'єкт покупець. Такий об'єкт — це структура даних, яка включає в себе такі поля:

v номер покупця — j,

v момент його приходу — ,

v (якщо необхідно) властивості покупця або його атрибути, (наприклад, пріоритет покупця).

Потрібно також запланувати подію приходу покупця j на момент часу , тобто записати повідомлення про подію в СМП.

2. Запланувати наступну подію для покупця j — запит-призначення ресурсу R (продавець) на момент часу . Запланувати прихід наступного об'єкта — покупець j+1, тобто визначити подію приходу наступного покупця .

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

Перша — це підпрограма запиту і призначення ресурсу R вимозі j (у мові GPSS цій підпрограмі відповідає блок SEIZE). Алгоритм її роботи такий:

1. Якщо ресурс R (об'єкт продавець) може бути відразу призначеним для вимоги j, то змінити стан ресурсу R на «зайнятий». Запам'ятати момент початку обслуговування вимоги і передати керування підпрограмі обслуговування вимоги j.

2. Якщо ресурс R зайнятий, то поставити вимогу j в чергу до ресурсу R.

Друга — це підпрограма обслуговування вимоги j (у мові GPSS цій підпрограмі відповідає блок ADVANCE). Алгоритм її роботи дуже простий. Вона повинна визначити подію, яка настає після закінчення обслуговування вимоги j як (де — час обслуговування в пристрої), тобто створити повідомлення про подію в СМП, для того щоб передати керування підпрограмі звільнення ресурсу R вимогою j.

Третя — підпрограма звільнення ресурсу R вимогою j (у мові GPSS цій підпрограмі відповідає блок RELEASE). Алгоритм її роботи такий.

1. Змінити стан ресурсу R на «вільний». Передати керування підпрограмі знищення вимоги.

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

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

Крім вищенаведених підпрограм потрібна програма керування всім процесом моделювання (ПКМ), яка запускає процес моделювання і контролює пересування кожної вимоги («життєвий цикл») під час моделювання шляхом виклику зазначених підпрограм обробки окремих подій. Інше призначення цієї програми — вести список упорядкованих у часі подій — СМП і просувати годинник модельного часу від події до події. У мові GPSS функції ПКМ виконує програма інтерпретатор.

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

Планування настання кожної майбутньої події означає, що на початку кожної дії обчислюється (або встановлюється, наприклад на основі заданого статистичного розподілу) її тривалість. Це необхідно для того, щоб визначити час закінчення дії і занести цю інформацію (у першу чергу тривалість дії) у СМП. У реальному світі заздалегідь запланувати настання більшості подій неможливо, вони просто відбуваються як, наприклад, випадкові відмови устаткування або випадкові приходи покупців. Під час моделювання для кожної такої події потрібно зазначити кінцевий момент пов'язаної з нею деякої дії.

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

Час — це поточне значення часу моделювання (показання годинника модельного часу). На початку моделювання подія, пов'язана з моментом часу , є майбутньою подією, тобто ця подія відбуватиметься першою. Після того як показання годинника, що відображає моменти зміни станів системи під час моделювання, зміниться з на , запланована для майбутнього виконання подія вилучається з СМП і виконується підпрограма події. Виконання підпрограми майбутньої події означає, що відображено новий стан системи в момент часу , який формується на основі попереднього стану моделі в момент часу і характеру майбутньої події. У момент зазначити всі майбутні події неможливо, але протягом всього процесу моделювання будь-яка запланована подія одразу ж поміщається в СМП.

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

Рис. 2.13.Структурна схема імітаційної моделі

На початку моделювання (час моделювання ) ПКМ передає керування підпрограмі генерування об'єктів, що визначає момент приходу першого покупця і намічає подію запиту і призначення ресурсу R у СМП на момент часу . Оскільки інших подій у системі не зафіксовано, модельному часу присвоюється значення , викликаються підпрограма генерування об'єктів і підпрограма запиту і призначення ресурсу R.

Підпрограма генерування об'єктів визначає майбутню подію — момент приходу другого покупця і призначає в СМП настання цієї події на момент часу .

Підпрограма запиту і призначення перевіряє стан ресурсу R (продавця). Якщо ресурс R вільний, то він призначається першому покупцю, і стан ресурсу R змінюється на «зайнятий». Фіксується момент початку обслуговування вимоги . Керування передається підпрограмі обслуговування першого покупця.

Підпрограма обслуговування визначає подію закінчення обслуговування першого покупця як . Для цього в СМП створюється повідомлення про майбутню подію і керування передається підпрограмі звільнення ресурсу R першою вимогою в момент часу .

Таким чином, тепер у СМП є два елементи: один — з наміченою подією появи другого покупця на момент часу , другий — з наміченою подією закінчення обслуговування першого покупця в момент часу . Якщо , то годинник модельного часу буде переведено на час , тобто буде викликано заново підпрограму генерування об'єктів і згенеровано появу другого покупця. У цей же момент часу викликається підпрограма генерування об'єктів, яка намітить у СМП появу третього покупця на час , та виклик підпрограми запиту і призначення ресурсу R, але оскільки ресурс зайнятий обслуговуванням першого покупця, то другого покупця буде поставлено в чергу до ресурсу R.

У СМП знову буде два елементи: один — з наміченою подією появи третього покупця на час , другий — з наміченою подією закінчення обслуговування першого покупця на час . Якщо , то годинник модельного часу буде встановлено на час , тобто буде викликано підпрограму звільнення ресурсу R першим покупцем. Вона змінить стан ресурсу R із «зайнятий» на «вільний» і передасть керування підпрограмі знищення вимоги. Потім перевірить, чи є вимоги в черзі до ресурсу R і вибере другого покупця з черги, намітить для нього подію для підпрограми запиту і призначення ресурсу R для другого покупця.

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

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

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

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

2. Якщо потік покупців від генератора необмежений (наприклад, генерується необмежений пуассонівський потік), моделювання можна закінчити після проходження через модель визначеної кількості покупців, наприклад 1000. Для цього в підпрограмі знищення треба поставити лічильник покупців і припинити моделювання після проходження 1000 покупців. У мові GPSS такий лічильник організовується за допомогою команди START, за якою починається процес моделювання.

3. Потрібно змоделювати роботу системи протягом заданого періоду часу, наприклад 480 хв. У цьому випадку під час зміни модельного часу можна провадити порівняння поточного часу зі значенням 480 хв. Як тільки значення модельного часу буде більше або дорівнюватиме 480 хв, моделювання слід припинити. Однак цей спосіб може дуже сповільнити роботу моделі, оскільки потребує постійної перевірки умови закінчення процесу моделювання. Тому звичайно використовують такий спосіб. Генерують спеціальну вимогу-таймер за допомогою ще однієї підпрограми генерування об'єктів з наміченим часом входу в модель t^вх = 480 хв. Вимога-таймер після генерування відразу ж направляється ще в одну підпрограму знищення, в якій ставлять лічильник вимог на одиницю. За лічильником припиняють моделювання. У цьому випадку в СМП весь час буде знаходитись елемент списку для вимоги-таймера з моментом часу настання події 480 хв. Як тільки цю подію буде намічено наступною, показання годинника модельного часу переводиться на час 480 хв, від лічильника вимог віднімається одиниця і він приймає значення нуль, що і є ознакою закінчення моделювання.

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

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Приклад побудови моделі системи масового обслуговування	\|	Загальні відомості про мережі СМО

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.