Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності


НазваТеорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності
Дата конвертації27.06.2013
Розмір445 b.
ТипПрезентации



Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності.

  • Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності.

  • Засновником цієї теорії був А.Ерланг, який застосував методи теорії ймовірності для проектування телефонних станцій.



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

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

  • Задачі аналізу передбачають оцінку ефективності функціонування СМО за незмінних умов, наперед заданих вхідних характеристиках системи: структурі системи, дисципліні обслуговування, потоках вимог та законах розподілу часу їх обслуговування.

  • Задачі синтезу спрямовані на пошук оптимальних параметрів СМО.



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

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

  • Та частина системи в якій виникають запити називається підсистемою, що обслуговується.

  • Та частина системи, яка приймає ці запити називається обслуговуючою системою.

  • Сукупність цих двох підсистем утворює СМО.

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

  • Якщо підсистему, що обслуговується можна поділити на окремі елементи, то такий елемент називається джерелом вимог.



Обслуговування – виконання роботи по задоволенню заявки клієнта.

  • Обслуговування – виконання роботи по задоволенню заявки клієнта.

  • Об’єкт (суб’єкт) що виконує обслуговування вимог називається обслуговуючим апаратом (приладом) або каналом обслуговування.

  • Максимальна кількість вимог що можуть одночасно обслуговуватись визначає пропускну спроможність системи.

  • Системи обслуговування з пропускною спроможністю рівною одиниці називають однолінійними. Системи з пропускною спроможністю більше одиниці називаються багатолінійними.



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

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

  • Крім того можливо що обслуговування проводиться ланцюгом приладів (багатофазною).

  • Час обслуговування – період, протягом якого вимоги на обслуговування задовольняються.

  • Час очікування на обслуговування – період від моменту надходження вимоги у систему до початку її обслуговування.

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



Потік вимог, що надходять у систему називається вхідним потоком.

  • Потік вимог, що надходять у систему називається вхідним потоком.

  • Потік вимог, що залишають систему називається вихідним потоком.

  • При цьому залежно від класу системи заявка може залишити систему як обслуженою так і не обслуженою.



Області застосування теорії масового обслуговування:

  • Області застосування теорії масового обслуговування:

  • у промисловості (організація багатоверстатного обслуговування, ремонту обладнання, інструментального господарства, внутрізаводського транспорту (технологічний), проектування потокових ліній, );

  • у транспорті (задачі організації експлуатації аеропортів, річкових та морських причалів, планування маршрутів міського транспорту, визначення оптимальної кількості таксомоторів);

  • у зв’язку (організація телефонної служби, електронного зв’язку та Інтернет-послуг, доставка та сортування кореспонденції);

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





Основні показники функціонування СМО залежать від:

  • Основні показники функціонування СМО залежать від:

  • типу системи;

  • кількості каналів обслуговування (n);

  • характеристик заявок, які називаються потоком заявок;

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

  • Кожен канал обслуговує заявку від початку до кінця.

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



Існують різні потоки заявок.

  • Існують різні потоки заявок.

  • Найбільш простий регулярний потік – потік, у якому заявки поступають одна за одною через певні, строго визначені проміжки часу (конвеєр).

  • Математично регулярний потік описується досить просто, але він рідко використовується на практиці.

  • В більшості випадків потоки є нерегулярними або випадковими.

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



1. Ординарність. Потік називається ординарним, якщо ймовірність появи одночасно двох заявок прямує до нуля.

  • 1. Ординарність. Потік називається ординарним, якщо ймовірність появи одночасно двох заявок прямує до нуля.

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

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



Формула Пуассона, яка описує найпростіший потік заявок:

  • Формула Пуассона, яка описує найпростіший потік заявок:

  • де

  • Pm(t) – ймовірність того, що за будь-який проміжок часу тривалістю t надійде рівно m заявок;

  • інтенсивність або щільністю потоку – середнє число заявок, що поступає в систему за одиницю часу t.



Змінюючи m і t ми можемо визначити ймовірність будь-якого стану системи.

  • Змінюючи m і t ми можемо визначити ймовірність будь-якого стану системи.

  • Найбільший інтерес представляє ймовірність того випадку, коли за інтервал часу t не з’явиться жодної заявки (m=0):



Час обслуговування – найважливіша характеристика кожного каналу, яка визначає пропускну спроможність СМО і є випадковою величиною.

  • Час обслуговування – найважливіша характеристика кожного каналу, яка визначає пропускну спроможність СМО і є випадковою величиною.

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

  • F(t) – функція розподілу часу обслуговування;

  • – інтенсивність обслуговування, величина обернена до середнього часу обслуговування однієї заявки одним каналом.



Функціонування більшості СМО описується трьома параметрами:

  • Функціонування більшості СМО описується трьома параметрами:

  • числом каналів n;

  • середньою щільністю потоку заявок ();

  • середньою тривалістю обслуговування заявки одним каналом ( ).

  • Крім того для одного типу замкнених систем потрібен четвертий параметр:

  • загальна кількість заявок, що може увійти в систему (m).





Для системи з відмовами найважливішою характеристикою якості і умов роботи є ймовірність того, що всі n каналів зайняті (що рівноцінно втраті заявки):

  • Для системи з відмовами найважливішою характеристикою якості і умов роботи є ймовірність того, що всі n каналів зайняті (що рівноцінно втраті заявки):

  • Ймовірність того, що заявка буде обслужена:



Введемо такі позначення:

  • Введемо такі позначення:

  • P0 – ймовірність того, що всі канали вільні;

  • Pk – ймовірність того, що працює k каналів, причому k≤m;

  • – середнє число зайнятих або працюючих каналів. Ця величина визначається як математичне сподівання працюючих каналів:



N0 – середнє число вільних каналів:

  • N0 – середнє число вільних каналів:

  • Кз – коефіцієнт зайнятості каналів:

  • К0 – коефіцієнт простою каналів:



Для систем з очікуванням (чергою) важливими є ще два показники:

  • Для систем з очікуванням (чергою) важливими є ще два показники:

  • Моч – середнє число заявок, що очікують на обслуговування (середня довжина черги):

  • М – середнє число заявок у системі, тобто число заявок, що обслуговуються і чекають на обслуговування:



Введемо такі показники, що відображають економічний стан системи:

  • Введемо такі показники, що відображають економічний стан системи:

  • qобсл – вартість обслуговування однієї заявки за одиницю часу;

  • qвт – вартість втрат, в результаті виходу заявки за одиницю часу;

  • qочік – вартість втрат, пов’язаних з очікуванням заявки в черзі за одиницю часу;

  • qпр – вартість одиниці часу простою каналу;

  • t – інтервал часу, що розглядається.

  • Тоді функції вартості втрат будуть виглядати так:



1. Для систем з відмовами:

  • 1. Для систем з відмовами:

  • 2. Для систем з очікуванням:

  • 3. Для систем змішаного типу:



4.1. СМО з відмовами

  • 4.1. СМО з відмовами

  • Існує два типи систем з відмовами і залежно від типу використовуються різні математичні апарати:

  • одноканальна (найпростіша) система з відмовами, коли n=1;

  • багатоканальна система з відмовами, коли n≥2.



4.1.1. Одноканальні системи з відмовами

  • 4.1.1. Одноканальні системи з відмовами

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

  • Якщо у момент надходження заявки канал вільний, вона обслуговується, якщо ж канал зайнятий то заявка отримує відмову і вибуває із системи.

  • Основною характеристикою такої системи є ймовірність того, що у довільний момент часу t канал вільний.



Введемо величину яка є відношенням інтенсивності потоку заявок до інтенсивності обслуговування:

  • Введемо величину яка є відношенням інтенсивності потоку заявок до інтенсивності обслуговування:

  • Оскільки , то можна записати:

  • Величина – середнє число заявок, що поступає у систему за час обслуговування однієї заявки одним каналом.



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

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

  • або, розділивши чисельник і знаменник на отримаємо:



4.1.2. Багатоканальні системи з відмовами, системи Ерланга (M/M/n)

  • 4.1.2. Багатоканальні системи з відмовами, системи Ерланга (M/M/n)

  • Для багатоканальних систем з відмовами формули розрахунку дещо складніші.

  • Суть роботи таких систем залишається такою самою, але у складі системи n каналів обслуговування (n≥2).

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





Дана система може знаходитись у таких станах:

  • Дана система може знаходитись у таких станах:

  • Всі канали вільні P0;

  • Працює (зайнятий) один канал P1;

  • Працює (зайнято) k каналів Pk (відповідно n-k вільні);

  • Зайняті всі n каналів Pn (ймовірність того, що заявка отримає відмову).



Згідно загальних правил теорії ймовірності – сума ймовірностей всіх станів системи дорівнює 1 (нормувальна умова), тобто

  • Згідно загальних правил теорії ймовірності – сума ймовірностей всіх станів системи дорівнює 1 (нормувальна умова), тобто

  • Обслуговування вимоги триває випадковий час, розподілений за показниковим законом:

  • Якщо можливі стани системи пронумерувати, утотожнюючи їх з числом заявок в системі, то розмічений граф станів набере такого вигляду:





Система диференціальних рівнянь для ймовірностей станів буде мати такий вигляд (рівняння Ерланга):

  • Система диференціальних рівнянь для ймовірностей станів буде мати такий вигляд (рівняння Ерланга):



Природними початковими умовами для розв’язання цієї системи є:

  • Природними початковими умовами для розв’язання цієї системи є:

  • p0(0)=1, p1(0)=p2(0)=…=pn(0)=0

  • тобто у момент часу t0 система вільна від обслуговування.



Визначимо граничні ймовірності такої системи при роботі в усталеному режимі (при t→∞), тобто розв’яжемо систему таких алгебраїчних рівнянь:

  • Визначимо граничні ймовірності такої системи при роботі в усталеному режимі (при t→∞), тобто розв’яжемо систему таких алгебраїчних рівнянь:



Звідси, ймовірність того, що зайняті k каналів (формули Ерланга):

  • Звідси, ймовірність того, що зайняті k каналів (формули Ерланга):

  • при

  • Якщо підставити цю формулу у нормувальну умову, то отримаємо:





Ймовірність того, що заявка отримає відмову (всі n каналів зайняті):

  • Ймовірність того, що заявка отримає відмову (всі n каналів зайняті):

  • Ймовірність того, що заявка буде обслужена:

  • Інші показники не відрізняються від загальних показників ефективності функціонування СМО.



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

  • Середнє число зайнятих каналів дорівнює математичному сподіванню числа працюючих каналів:

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



4.1.3. Оптимізація СМО з відмовами

  • 4.1.3. Оптимізація СМО з відмовами

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



Оптимізацію розглянемо на прикладі контролю якості продукції.

  • Оптимізацію розглянемо на прикладі контролю якості продукції.

  • Нехай в технологічному процесі використовується вибірковий контроль якості виробів.

  • Якщо виріб не пройшов контроль, то він поступає на склад готової продукції, а далі споживачу.

  • Отже, серед виробів, що не пройшли контроль можуть бути як якісні так і дефектні.

  • За реалізацію дефектної продукції підприємство несе витрати (збитки), затрати на усунення дефектів.



Чим більше контрольних постів, тим вища ймовірність контролю і менша можливість випуску бракованої продукції.

  • Чим більше контрольних постів, тим вища ймовірність контролю і менша можливість випуску бракованої продукції.

  • Проте, збільшуються витрати підприємства на утримання контрольної служби.

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



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

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

  • Потрібно встановити таку кількість каналів n, яка б мінімізувала даний критерій.

  • Введемо такі позначення:



n – кількість контрольних постів;

  • n – кількість контрольних постів;

  • Зк – затрати на утримання одного контролера за одиницю часу;

  • Кбр – середній відсоток бракованої продукції характерний для даного виробництва;

  • Збр – затрати підприємства, пов’язані з реалізацією бракованої продукції;

  • Т – плановий період часу.

  • Тоді затрати підприємства на утримання контрольної служби: F1=n∙Зк∙Т



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

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

  • Серед цих виробів може виявитись бракованих ∙Pn∙Кбр виробів.

  • Тоді затрати підприємства, пов’язані з випущеною на ринок бракованої продукцією будуть рівні:

  • F2=∙Pn∙Кбр ∙Збр ∙T

  • Отже, сумарні затрати будуть знаходитись за формулою:

  • F= F1+ F2



Значення критерію залежить і від кількості каналів n.

  • Значення критерію залежить і від кількості каналів n.

  • Перший доданок критерію (F1) збільшується зі збільшенням кількості каналів n, а другий зменшується відповідно до поведінки величини Pn.

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

  • Найменша з отриманих величин і відповідає оптимальній кількості каналів.

  • Процес оптимізації має таку графічну інтерпретацію:









Можливі стани СМО з очікуванням:

  • Можливі стани СМО з очікуванням:

  • всі канали вільні P0;

  • працює (зайнятий) один канал P1, а решта вільні;

  • працює (зайнято) k каналів Pk, а решта вільні;

  • працює (зайнято) канал Pn-1, а один канал вільний.

  • зайняті всі n каналів Pn (ймовірність того, що хоча б одна заявка стане в чергу);

  • працює n каналів і надійшла одна заявка Pn+1;

  • працює n каналів і надійшло ще s заявок Pn+s,









Оскільки кількість заявок обмежена числом m, то система може знаходитись у (m+1) станах.

  • Оскільки кількість заявок обмежена числом m, то система може знаходитись у (m+1) станах.

  • Як правило кількість каналів є меншою від максимальної кількості потенційних заявок (n≤m).



Система може перебувати у таких станах:

  • Система може перебувати у таких станах:

  • всі потенційні заявки працюють, а канали обслуговування вільні P0;

  • одна заявка обслуговується одним каналом P1, відповідно решта каналів вільні, і працює m-1 потенційних заявок.

  • n заявок знаходиться в системі, при цьому зайняті всі n каналів Pn, а решта m-n потенційних заявок працює;

  • всі m потенційних заявок не працює, при цьому зайняті всі n каналів, а ще m-n заявок стоїть в черзі на обслуговування Pm;









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

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

  • Проілюструємо це на прикладі встановлення оптимальної кількості робітників-ремонтників на підприємстві.

  • В якості критерію приймемо сумарні витрати підприємства пов’язані з: утриманням ремонтної служби та втратами внаслідок простою обладнання



Зр – заробітна плата одного робітника, грн.

  • Зр – заробітна плата одного робітника, грн.

  • Sp – інші витрати, грн.

  • Сумарні витрати:

  • Загальні витрати:



Загальна кількість обладнання, що простоює:

  • Загальна кількість обладнання, що простоює:

  • Середні втрати підприємства від простою одиниці обладнання - Спр

  • Загальні витрати від простою в часі:



Основні втрати підприємства за період часу Т:

  • Основні втрати підприємства за період часу Т:



Аналіз моделей СМО в яких вхідні та вихідні потоки не описуються пуасонівським законом розподілу надзвичайно складний.

  • Аналіз моделей СМО в яких вхідні та вихідні потоки не описуються пуасонівським законом розподілу надзвичайно складний.

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



Контрольні запитання до теми 4:

  • Контрольні запитання до теми 4:

  • Що таке теорія СМО?

  • Наведіть класифікацію СМО за різними ознаками.

  • Опишіть показники ефективності СМО.

  • Назвіть основні типи задач масового обслуговування. Дайте коротку їх характеристику.

  • Що таке оптимізація СМО?





Схожі:

Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconТеорія ймовірності Теорія ймовірності
Під випробуванням розуміється здійснення намічених дій і отримання результату за виконання певного комплексу умов S. При цьому припускається,...
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconПобудова імітаційних моделей систем масового обслуговування план лекції Системи масового обслуговування
Характерні особливості смо випадковий потік заявок (транзакцій) на обслуговування
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconТеорія графів – спеціальний розділ математичного програмування, який вивчає кількісні і якісні характеристики графів
Певна вершина може бути з’єднана ребром сама з собою, тоді таке ребро називається
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconЛекція Теорія мовленнєвих актів
Курс: Теорія комунікації Лектор: доц. Малая Олеся Юліївна Лекція Теорія мовленнєвих актів
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconМедсестринська теорія намагається описати чи пояснити Медсестринство
Теорія є фундаментом для м\с практики і досліджень. Професіоналізм мед сестринської справи утверджується через розвиток і застосування...
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconТема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Теорія графів — розділ математики, що дає змогу формалізувати взаємозв'язки між різноманітними видами інформації, організувати абстрактне...
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconОснови теорії ймовірності та математичної статистики План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconНеобхідно вивчити: Хромосомну теорію спадковості
Хромосомна теорія спадковості основна теорія генетики, згідно якої матеріальними носіями спадковості є хромосоми, в яких лінійно...
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconОснови теорії ймовірності та математичної статистики проф. В. П. Марценюк План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Теорія масового обслуговування (queue(ing) theory) – спеціальний розділ математики, основою якого є теорія ймовірності iconПедагогічна теорія – абстракція. Педагогічна теорія – абстракція
Проблемі когнітивної компетенції школярів присвячені дослідження відомих педагогів та методистів: І. Забродіної, Л. Арістова, Ю....

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка