Теория массового обслуживания

ЛЕКЦИЯ 6. ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ ИСТОРИЯ ВОПРОСА Вентцель Елена Сергеевна (1907–2002) –автор научных работ и учебников по теории вероятностей, исследованию операций и ТМО. Гнеденко Борис Владимирович (1912–1995) –задачи, связанными с обороной страны. Автор многих работ по ТМО, один из основоположников теории надежности. Йохансон Фредерик Фердинанд (1855–1934) – датский инженер, директор Копенгагенской телефонной компании. Изложил первые идеи теории очередей в 1907 году в статье «Время ожидания и число вызовов». Каштанов Виктор Алексеевич (1934) – Один из руководителей разработок в области фундаментальных проблем системной безопасности. Коваленко Игорь Николаевич (1935) –ТВ и ее приложения, теория надежности, ТМО. Колмогоров Андрей Николаевич (1903–1987) – академик АН СССР. Вклад в развитие теории марковских процессов с непрерывным временем. Клейнрок Леонард (1934) – американский инженер в области ИТ и компьютерных сетей. Создание сети ARPANET – предшественницы Интернета. ИСТОРИЯ ВОПРОСА Марков Андрей Андреевич (1856–1922) –профессор ФМ СПб университета. Впервые исследовал широкий класс стохастических процессов с дискретным временем (марковские цепи) и непрерывным временем (марковские процессы). Цепи Маркова нашли широкое применение в работах Планка, Эйнштейна и других ученых. Пуассон Симеон Денни (1781–1840) – фр. математик, механик и физик, профессор Политехнической школы в Париже, почетный член Петербургской академии наук. Предложил и обосновал один из важнейших законов распределения случайных величин. Хинчин Александр Яковлевич (1894–1959) – автор (совместно с А. Н. Колмогоровым) современной теории случайных процессов и ТМО. Энгсет Торе Олаус (1865–1943) – норвежский математик и инженер, один из основоположников ТМО. Эрланг Агнер Краруп (1878–1929) – датский математик, статистик и инженер, сотрудник Копенгагенской телефонной компании, основатель научного направления по изучению трафика в телекоммуникационных системах. 1909 работа «Теория вероятностей и телефонные разговоры» - основа ТМО. Эрланг - единица измерения трафика. ПОНЯТИЕ О МАРКОВСКИХ ПРОЦЕССАХ Марковский случайный процесс - для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние (предыстории процесса). Пусть в настоящий момент t0 система находится в определенном состоянии S0. Типовая постановка задачи: Предсказать будущее состояние системы при t > t0 на уровне вероятности того, что через некоторое время τ система S окажется в состоянии S1 или останется в состоянии S0 и т.д. Пример марковского процесса. Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество самолетов X, y – самолетов Y. К моменту времени t0 количество сохранившихся (не сбитых) самолетов, соответственно, x0, y0. Нас интересует вероятность того, что в момент времени t0+τ численный перевес будет на стороне X. Здесь эта вероятность зависит от того, в каком состоянии находилась система в момент времени t0, и не зависит от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты. Пример немарковского процесса. Игра в шахматы. Процесс называется процессом с дискретным состоянием, если его возможные состояния S1, S2, … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно. Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти в любой момент. В исследовании операций большое значение имеют марковские случайные процессы с дискретными состояниями и непрерывным временем. 4 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ λ⋅∆t Каналы (приборы) обслуживания µ⋅∆t Потоком событий (событий-заявок, требований) называют последовательность событий, наступающих одно за другим в случайные моменты времени Предмет изучения ТМО – СМО и ее критерии эффективности (пропускная способность и др.). Цель ТМО – выработка рекомендаций по рациональному построению СМО, организации их работы, обеспечивающей требуемую эффективность функционирования СМО. Задачи ТМО – формулы для расчета зависимостей эффективности функционирования СМО от ее параметров: потока заявок, числа каналов и политики обслуживания, правила очереди. 5 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ Примеры СМО: ЭВМ, вычислительные системы, комплексы и сети передачи данных, автоматические телефонные станции, транспортные системы, промышленные предприятия и предприятия обслуживания, задачи обороны и защиты информации,…. Основные элементы СМО: входной поток заявок, очереди заявок, ожидающих обслуживания, каналы (приборы) обслуживания, выходной поток обслуженных заявок. Признаки классификации СМО: o число каналов обслуживания (одно- и многоканальные), o способ организации ожидания заявок (СМО с отказами, СМО с ожиданием, СМО с очередями; с приоритетами или без приоритетов), o число фаз обслуживания (одно- и многофазные), o тип взаимосвязи с потоками заявок (разомкнутые (открытые) и замкнутые*). Сети массового обслуживания (СеМО) - системы, сочетающие в себе свойства многоканальных и многофазных систем. 6 Сеть СМО В цеху функционируют три различных стадии обслуживания поступающих станков: калибровка-1, калибровка-2 и калибровка-3. Станки, которые прибывают в цех в среднем через каждые 10 часов, направляются с одинаковой вероятностью в одно из этих отделений. После обслуживания около 60% станков покидают цех, остальные с равной вероятностью могут направиться на любую из оставшихся стадий обслуживания. Обслуживание на 1-й стадии длится в среднем 5 часов, на второй - 40 часов и на третьей - 20 часов. Введем обозначения: СМО1- реализация процесса калибровки-1, СМО2 - реализация процесса калибровки-2, СМО3 - реализация процесса калибровки -3. КЛАССИФИКАЦИЯ СМО По числу каналов СМО подразделяют на одноканальные (когда имеется один канал обслуживания) и многоканальные. По дисциплине обслуживания СМО подразделяют на три класса: 1. СМО с отказами, в которых заявка, поступившая на вход СМО в момент, когда все каналы заняты, получает «отказ». 2. СМО с ожиданием (неограниченным ожиданием или очередью). 3. СМО смешанного типа (с ограниченным ожиданием). По ограничению на поток заявок СМО делятся на замкнутые и открытые. Если поток заявок ограничен и заявки, покинувшие систему, могут в нее возвращаться, то СМО является замкнутой, в противном случае – открытой. Пример замкнутой СМО. Работа бригады наладчиков в цеху. Поломка станков – источники заявок на обслуживание, наладчики – каналы обслуживания. После проведения ремонтных работ вышедший из строя станок снова становится источником заявок на обслуживание. Зависимость характеристик потока заявок от числа занятых каналов Замкнутые зависят Открытые не зависят По количеству этапов обслуживания. СМО делятся на однофазные и многофазные. Пример многофазной СМО. Обслуживание автомобилей на станции технического обслуживания (мойка, диагностирование и т.д.). 8 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ Размеченные графы состояний СМО исходная информация для уравнений состояний Графу системы, содержащему n вершин, можно поставить в соответствие матрицу вероятностей переходов Pn×n, элементами которой являются вероятности переходов pij между вершинами графа. Условие нормировки – по строкам. 9 ПОКАЗАТЕЛИ ЭФФЕКТИВНОСТИ СМО 1. Абсолютная пропускная способность СМО (А) – среднее число заявок, обслуживаемое СМО в единицу времени. 2. Относительная пропускная способность СМО (q, Q) – отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу поступивших за это же время заявок. 3. Средняя продолжительность занятости СМО. 4. Коэффициент использования СМО – средняя доля времени, в течение которого СМО занята обслуживанием заявок, и т.п. Показатели качества обслуживания заявок 1. Среднее время ожидания заявки в очереди. 2. Среднее время пребывания заявки в СМО. 3. Вероятность отказа заявке в обслуживании без ожидания. 4. Вероятность того, что вновь поступившая заявка немедленно будет принята к обслуживанию. 5. Закон распределения времени ожидания заявки в очереди. 6. Закон распределения времени пребывания заявки в СМО. 7. Среднее число заявок, находящихся в очереди. 8. Среднее число заявок, находящихся в СМО, и т.п. Стоимостные показатели эффективности функционирования СМО 10 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ПОТОКОВ СОБЫТИЙ Поток событий - последовательность однородных событий, появляющихся одно за другим в случайные моменты времени; наглядно изображается рядом точек с абсциссами t1,,…, tn. Ti = ti+1 – ti – интервалы между событиями. Поток однородный - случайная последовательность отдельных событий, упорядоченных по неубыванию моментов времени. Модель неоднородного потока событий –сумма нескольких однородных потоков (поток самолетов, приземляющихся на аэродроме). Регулярный поток – события следуют друг за другом через одинаковые промежутки времени. Рекуррентный поток - поток, для которого все функции распределения интервалов между заявками совпадают: P(τi) = P(τ). Стационарный поток – его вероятностные характеристики не зависят от выбора начала отсчета. Ординарный поток событий – вероятность попадания в элементарный интервал времени Δt двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. P{(t, t +Δ t)>1} = 0. Поток без последствий – число событий, попадающих в любой интервал времени τ, не зависит от того, сколько событий попало на любой другой непересекающийся с ним интервал. Пуассоновский поток - ординарный и без после действий. Простейший поток - стационарный пуассоновский поток. 11 ПРОСТЕЙШИЙ ПОТОК поток звонков на телефонную станцию, в милицию, на станцию скорой помощи; поток заявок в системах бытового обслуживания; поток отказов прибора; поток автомобильных аварий на дорогах города и т. д. Однородный поток, обладающий свойствами: Постоянство числа событий в ед.времени Будущее состояние зависит только от текущего и не зависит от предыстории Наступление одновременно двух событий и более – практически невозможно. 12 ПРОСТЕЙШИЙ ПОТОК Пусть в СМО требования поступают в случайные моменты времени 𝑡𝑡𝑖𝑖 = 0, 𝑡𝑡1 , 𝑡𝑡2 , … , 𝑡𝑡𝑘𝑘 , …, так что 𝑢𝑢𝑘𝑘 = 𝑡𝑡𝑘𝑘 − 𝑡𝑡𝑘𝑘−1 (k ≥ 1) – интервалы между поступлениями и, кроме того, 𝑡𝑡𝑘𝑘 = 𝑢𝑢1 + 𝑢𝑢2 +. . . +𝑢𝑢𝑘𝑘 (1) P{𝑢𝑢𝑘𝑘 < 𝑡𝑡} = 1 − 𝑒𝑒 −𝜆𝜆𝜆𝜆 (2) (𝜆𝜆𝜆𝜆)𝑘𝑘 −𝜆𝜆𝜆𝜆 P{ν(t) = k} = 𝑒𝑒 𝑘𝑘! (3) Предполагается, что случайные величины 𝑢𝑢1 , 𝑢𝑢2 , … , 𝑢𝑢𝑘𝑘 независимы и имеют показательное распределение с параметром λ: Такой входной поток требований в систему является простейшим (почему?). Пусть ν(t) - число требований, поступивших в СМО в интервале времени (0, t). Тогда справедлива формула Пуассона: Смысл (2) и (3). ⇒ Если длительности промежутков между поступлениями в систему последовательных требований имеют показательный закон, то случайное число требований, поступивших за время t, имеет распределение Пуассона с параметром λ, а процесс ν(t) является однородным пуассоновским процессом. ⇐ Имеет место и обратное: если число требований ν(t), поступивших за время t, является процессом Пуассона с интенсивностью λ, то длительности интервалов uk независимы и имеют одинаковое показательное распределение с параметром λ. 13 ПРОСТЕЙШИЙ ПОТОК: УДОБНЫЕ ДЛЯ ПРАКТИКИ СВОЙСТВА Инвариантность по отношению к операции суммирования: результирующий поток суммы пуассоновских потоков тоже является пуассоновским с 𝑛𝑛 суммарной интенсивностью: λ = ∑𝑖𝑖=1 λ𝑖𝑖 где n – число пуассоновских потоков, участвующих в суммировании, λ𝑖𝑖 – интенсивность i-ого потока. Поток с интенсивностью λ1 Поток с интенсивностью λ2 Суммарный поток с интенсивностью λ=λ1+λ2 Суперпозиция пуассоновских потоков. При наложении достаточного большого числа n независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям) получается поток, близкий к простейшему с интенсивностью λ, равной сумме интенсивностей входящих потоков. 14 МАРКОВСКОЕ СВОЙСТВО ПОКАЗАТЕЛЬНОГО РАСПРЕДЕЛЕНИЯ (отсутствие последействия) Введем события А={к моменту t поступило требование (заявка)} B={к моменту t+∆t поступит требование (заявка)} Пусть поток таков, что промежуток времени между наступлениями событий есть показательная СВ c ФР вида F (t ) = P {τ < t} = 1 − e −λt . Тогда вероятность события А P { A} =R (t ) =P {τ > t} =1 − P {τ < t} =e −λt . (R - reliability) Поставим задачу: определить вероятность наступления события B, при условии, что наступило событие А. Другими словами: определить вероятность поступления требования в момент t+∆t, при условии, что требование поступило в момент t. P {τ > t + ∆t} e −λ( t +∆t ) −λ⋅∆t . P { B / A}= P {τ > t + ∆t / τ > t}= = = e −λt P {τ > t } e 15 ПРОСТЕЙШИЙ ПОТОК Время обслуживания требований в СМО - с.в., в стационарном режиме описывается экспоненциальным (показательным) законом распределения с интенсивностью μ (среднее число требований, выполняемых в единицу времени), обладающее свойством: распределение длительности оставшейся части работ по обслуживанию не зависит от того, сколько оно уже продолжалось. Это обусловлено рядом причин: 1) отсутствием последействия; 2) простотой и удобством аналитических выражений; 3) именно так устроены многие реальные системы. Показательное распределение времени обслуживания имеет вид: ФР F(t)=1-e- μ t плотность ФР f(t)= μ e- λt Для простейшего потока с интенсивностью λ вероятность попадания на элементарный (малый) отрезок времени Δt хотя бы одного события потока: F(t)=1- e−λ Δt ≅ λ ∆t (от замены функции e−λ Δt двумя первыми членами ее разложения в ряд по степеням Δt) Среднее время обслуживания одним каналом одного требования (математическое ожидание показательной с.в. tобслуж= 1/μ Коэффициент загрузки СМО (среднее число каналов, которое должно быть для обслуживания в единицу времени всех поступающих требований) ρ= λ/μ. 16 МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ 𝑑𝑑 𝑃𝑃 (𝑡𝑡) = −𝜆𝜆𝑃𝑃0 (𝑡𝑡) + 𝜇𝜇𝑃𝑃1 (𝑡𝑡) = 0 𝑑𝑑𝑑𝑑 0 𝑑𝑑 𝑃𝑃 (𝑡𝑡) = −(𝜆𝜆 + 𝜇𝜇)𝑃𝑃1 (𝑡𝑡) + 𝜆𝜆𝑃𝑃0 (𝑡𝑡) + 2𝜇𝜇𝑃𝑃2 (𝑡𝑡) = 0 𝑑𝑑𝑑𝑑 1 … 𝑑𝑑 𝑃𝑃𝑘𝑘 (𝑡𝑡) = −(𝜆𝜆 + 𝑘𝑘𝑘𝑘 )𝑃𝑃𝑘𝑘 (𝑡𝑡) + 𝜆𝜆𝑃𝑃𝑘𝑘−1 (𝑡𝑡) + (𝑘𝑘 + 1)𝜇𝜇𝑃𝑃𝑘𝑘+1 (𝑡𝑡) = 0 𝑑𝑑𝑑𝑑 … 𝑑𝑑 𝑃𝑃 (𝑡𝑡) = −𝜆𝜆𝑃𝑃𝑠𝑠 (𝑡𝑡) + 𝑠𝑠𝑠𝑠𝑃𝑃𝑠𝑠−1 (𝑡𝑡) = 0 𝑑𝑑𝑑𝑑 𝑠𝑠 𝑘𝑘 𝜌𝜌 𝑃𝑃𝑘𝑘 (𝑡𝑡) = 𝑃𝑃0 (𝑡𝑡) 𝑘𝑘! 𝑠𝑠 𝑛𝑛 −1 𝜌𝜌 𝑃𝑃0 = � � � 𝑛𝑛! 𝑛𝑛=0 17 МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ Показатели эффективности работы СМО 1) р0 (вероятность того, что все обслуживающие каналы свободны); 2) вероятность отказа ротк (вероятность того, что заявка покинет СМО необслуженной) ротк=рs; 3) pk (вероятность того, что в системе k требований); 4) относительная пропускная способность Q (отношение среднего числа обслуживаемых в единицу времени заявок к среднему числу поступивших за это время заявок) Q=1–ротк; 5) абсолютная пропускная способность А (среднее число заявок, которое СМО может обслужить в единицу времени) А=λQ; Q=A/λ 6) среднее число свободных от обслуживания каналов z=N0 есть математическое ожидание числа свободных каналов z =sp0+(s–1)p1+…+1⋅ps-1+0⋅pn; 7) коэффициент простоя каналов ; 𝑲𝑲загр =N0/s. 8) среднее число занятых обслуживанием 𝒛𝒛� =Nзан каналов 𝒛𝒛� = 𝝆𝝆(𝟏𝟏 − 𝑷𝑷𝒔𝒔 ) = 𝝆𝝆𝝆𝝆; s=z+𝒛𝒛�; 9) коэффициент загрузки каналов 𝑲𝑲загр =Nзан/s. 18 ПРИМЕР. СМО С ОТКАЗАМИ Имеется цех, в состав которого входит три одинаковых станка. В систему поступают для обработки детали в среднем через 0,5 часа. Среднее время изготовления одной детали 0,6 час. Если при поступлении заявки на изготовление детали все станки заняты, то деталь направляется на другой участок таких же станков. Найти вероятности состояний системы и характеристики СМО. Сколько в среднем в этой системе обрабатывается деталей? Сколько в среднем работает станков? Решение. Возможные состояния системы: E0 – в СМО нет ни одной заявки; E1 – в СМО одна заявка; E2 – в СМО две заявки; E3 – в СМО три заявки (заняты все три станка). Вероятность того, что все станки свободны: −1  ρ ρ 2 ρ3  1 1 λ= = 2, µ=  1,67, P0= 1 + + +   0,31. 0,5 0.6  1! 2! 3!  Вероятность того, что заняты станки (1, 2, 3): 2 3 λ ρ ρ P1 = P0 = ρP0  0,37, P2 = P0  0, 22, P3 = P0  0,09. µ 2! 3! Пропускная способность (абсолютная, относительная):  ρs  ρs A= 1 P0  0,91. λ 1 − P0   1,82 дет / час, q =− s!  s!  Вероятность отказа в обслуживании, среднее число занятых станков: Pотк  ρs  ρs = P0  0,09, z = ρ 1 − P0   1,09. s! s!   Таким образом, в среднем в этой системе обрабатывается 1,82 дет/ч (или 91 % поступающих на обслуживание деталей), при этом примерно 9% деталей направляется для обработки на другие участки. В среднем работает в основном один станок ( z  1,09 ) , реже работают одновременно все три станка ( P3  0,09 ) (9% отказов). 19 СМО С ОТКАЗАМИ . УРАВНЕНИЯ КОЛМОГОРОВА ДЛЯ ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ λ E0 Нестационарный режим+Условие нормировки 𝑑𝑑 𝑃𝑃 (𝑡𝑡) = −𝜆𝜆𝑃𝑃0 (𝑡𝑡) + 𝜇𝜇𝑃𝑃1 (𝑡𝑡), 𝑑𝑑𝑑𝑑 0 𝑃𝑃0 (𝑡𝑡) + 𝑃𝑃1 (𝑡𝑡) = 1. 𝑑𝑑 𝑃𝑃1 (𝑡𝑡) = 𝜆𝜆𝑃𝑃0 (𝑡𝑡) − 𝜇𝜇𝑃𝑃1 (𝑡𝑡). E1 𝑑𝑑𝑑𝑑 µ 𝑃𝑃0 (𝑡𝑡) = Стационарный режим⇒ 0 = −𝜆𝜆𝑃𝑃0 (𝑡𝑡) + 𝜇𝜇𝑃𝑃1 (𝑡𝑡), 0 = 𝜆𝜆𝑃𝑃0 (𝑡𝑡) − 𝜇𝜇𝑃𝑃1 (𝑡𝑡), 𝑃𝑃0 (𝑡𝑡) + 𝑃𝑃1 (𝑡𝑡) = 1. 𝜆𝜆𝑒𝑒 −(𝜆𝜆 +𝜇𝜇 )𝑡𝑡 𝜆𝜆+𝜇𝜇 ⇓ + 𝜇𝜇 𝜆𝜆+𝜇𝜇 , 𝑃𝑃1 (𝑡𝑡) = 1 − 𝑃𝑃0 (𝑡𝑡) Абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени): Относительная пропускная способность (средняя доля заявок, обслуживаемых системой Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной) Пример. Технологическая система состоит из одного станка. На станок поступают заявки на изготовление деталей в среднем через 0,5 часа . Среднее время изготовления одной детали равно . Если при поступлении заявки на изготовление детали станок занят, то она (деталь) направляется на другой станок. Найти абсолютную и относительную пропускную способности системы и вероятность отказа по изготовлению детали. Таким образом, в среднем примерно 46 % деталей обрабатываются на этом станке. . В среднем примерно 54 % деталей направляются на обработку на другие станки. 20 СМО С ОТКАЗАМИ . ОПТИМИЗАЦИЯ ЧИСЛА КАНАЛОВ Определить оптимальное число каналов, обеспечивающее минимум затрат на систему, при условии достижения требуемого уровня ее безотказной работы, при условии λ ρ= = 1, Pотк ≤ 0,03, µ целевая функция, при этом, имеет вид: E ( n )= c ⋅ n , где с – стоимость канала. −1 Решение. Pотк P0 ρs P  =P0 = ⇒ Pотк ≤ 0.03 ⇒  0  ≥ 33 . s! s!  s!  −1  ρ ρ 2 ρ3  Поскольку P0 = 1 + + +  ,  1! 2! 3!  то требуемое неравенство впервые выполнится при s=4. 21 МНОГОКАНАЛЬНАЯ СМО БЕЗ ОТКАЗОВ …λ λ E1 E0 𝑃𝑃𝑘𝑘 = Ek … 2µ µ kµ 𝑘𝑘 𝜌𝜌𝑘𝑘 𝑃𝑃0 , 1 ≤ 𝑘𝑘 ≤ 𝑠𝑠, 𝑘𝑘! ⎨ 𝜌𝜌 ⎩𝑠𝑠! 𝑠𝑠𝑘𝑘−𝑠𝑠 𝑃𝑃0 , 𝑠𝑠 < 𝑘𝑘 ≤ 𝑠𝑠 + 𝑚𝑚. 𝑖𝑖 𝑠𝑠+1 𝜌𝜌 𝜌𝜌 � 𝑃𝑃0 = �� + 𝑖𝑖! 𝑠𝑠! (𝑠𝑠 − 𝜌𝜌) 𝑖𝑖=0 … sµ sµ … sµ sµ … очереди нет ⎧ 𝑠𝑠 Es+m Es (k+1)µ λ … …λ λ … −1 , В системе с неограниченной очередью отказы невозможны (Pотк=0, Q=1). Абсолютная пропускная способность в установившемся режиме совпадает с интенсивностью входящего потока заявок (A=λ). 𝑠𝑠≠𝜌𝜌. 22 МНОГОКАНАЛЬНАЯ СМО БЕЗ ОТКАЗОВ Вероятность ожидания 𝑃𝑃ожид = 𝑃𝑃0 𝜌𝜌 𝑠𝑠 Среднее число занятых каналов 𝑧𝑧̅ = 𝜌𝜌. 𝜌𝜌 𝑠𝑠 Среднее число находящихся в очереди Среднее время пребывания заявки в ν� 𝜌𝜌𝑠𝑠+1 𝜌𝜌 −2 очереди 𝜛𝜛 = 𝑃𝑃0 1 − заявок ν� = 𝜆𝜆 𝑠𝑠 𝑠𝑠! 𝑠𝑠! 1 − 𝑠𝑠 Среднее число заявок в СМО 𝑛𝑛� = ν� + 𝑧𝑧̅ Среднее время пребывания заявки в СМО (формулы Литтла) 𝑛𝑛� 𝑢𝑢� = 𝜆𝜆 23 ОДНОКАНАЛЬНАЯ СМО БЕЗ ОТКАЗОВ 24 ОДНОКАНАЛЬНАЯ СМО БЕЗ ОТКАЗОВ 25 ОДНОКАНАЛЬНАЯ СМО БЕЗ ОТКАЗОВ 26 МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ λ E λ E1 µ λ … λ E2 µ λ … λ Ek µ … µ Em+1 µ … µ Моменты отказа в обслуживании Моменты поступления заявок в СМО Моменты начала обслуживания заявок в канале обслуживания Моменты окончания обслуживания заявок в канале обслуживания 27 ЗАМКНУТАЯ СМО (ограниченное фиксированное число источников заявок) Бригада рабочих (s наладчиков) обслуживает m единиц техники (станков). Каждая единица техники может в любой момент выйти из строя и потребовать обслуживания со стороны рабочих. Интенсивность потока неисправностей каждого станка фиксирована и равна λ. Среднее время наладки единицы техники tобсл=1/µ, где µ – интенсивность потока обслуживаний. Если в момент выхода единицы техники из строя все рабочие заняты, то станок становится в очередь на обслуживание и ждет, пока рабочий не освободится. Найти основные показатели эффективности СМО. Граф состояний замкнутой СМО: Вероятность занятости рабочего: Pзанят = 1 − P0 . Абсолютная пропускная способность СМО: A= µ (1 − P0 ) Уравнения Колмогорова установившегося режима при s=1 для 1 + mρ + m(m − 1)ρ2 + ...  P0 P= = ( E0 )   m ... m ( m 1)...1 + − ⋅ρ   P1= P ( E1 )= mρP0 , −1 P= P ( E2= ) m(m − 1)ρ2 P0 , 2 ......................................... = Pm P ( E= m(m − 1)...1⋅ρm P0 . m) Среднее число неисправных единиц техники (2 способа): 1) ω= P1 + 2 P2 + ... + mPm ; µ 2) на основе абсолютной пропускной способности: ω= m − (1 − P0 ) . λ (1 − P0 ) − 1 − P . Среднее число неисправных единиц техники в очереди: τ= m − ( 0) ρ (если занят, то рабочий обслуживает µ единиц техники). Пример. 1) среднее время поломки техники 2/час; 2) m=3; 3) среднее время обслуживания 10 мин. m= 3, λ= 2, µ= 6, ρ= 1 , P0 ≈ 0,346, Pзанят= 0,654, A= 3,94, ω= 1,04 . 3 Так как, ω m = 0,347 , то около 35% производительности теряется из-за поломок. 28 ЛИТЕРАТУРА 1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М., 1987. 2. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. Высш.шк., 2000, 480 с. 3. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972, 552 с. 4. Т.Л.Саати. Элементы теории массового обслуживания и ее приложения: Пер. с англ. /Под. ред. И.Н. Коваленко, изд-ие 2. М., 1971. 5. Д.Кениг, Д.Штойян. Методы теории массового обслуживания: Пер. с нем. /Под. ред. Г.П.Климова. М., 1981. 6. Г.И.Ивченко, В.А.Каштанов, И.Н.Коваленко. Теория массового обслуживания. М., 1982. 7. Хинчин А.Е. Работы по математической теории массовогообслуживания / ред.: Б.В. Гнеденко. - 2-е изд., стереотип. - М. : УРСС, 2004. – 235с. 8. Л. Клейнрок. Теория массового обслуживания. М.: “Машиностроение”, 1969. 9. Л.А. Овчаров. Прикладные задачи теории массового обслуживания М.: “Машиностроение”, 1969. 10. О.А. Новиков, С.И. Петухов. Прикладные вопросы массового обслуживания. М.: “Советское радио”, 1969. 29