Принцип кругов эйлера. Логические задачи и круги эйлера. Отношения между понятиями. круги эйлера
Во всех рассмотренных выше СМО предполагалось, что все запросы, поступающие в систему - однородные, то есть, они имеют один и тот же закон распределения времени обслуживания и обслуживаются в системе согласно общей дисциплины выбора из очереди. Однако, во многих реальных системах запросы, поступающие в систему, неоднородны как по распределению времени обслуживания, так и по их ценности для системы и, следовательно, праву претендовать на первоочередное обслуживание в момент освобождения прибора. Такие модели исследуются в рамках теории приоритетных СМО. Эта теория довольно хорошо развита и ее изложению посвящено немало монографий (см., например, , , , и т.д.). Здесь мы ограничимся кратким описанием приоритетных систем и рассмотрим одну систему.
Рассмотрим однолинейную СМО с ожиданием. На вход системы поступают независимых простейших потоков, поток имеет интенсивность . Будем обозначать
Времена обслуживания запросов из потока характеризуются функцией распределения с преобразованием Лапласа - Стилтьеса и конечными начальными моментами
Запросы из потока назовем запросами приоритета к.
Считаем, что запросы из потока более приоритетны, чем запросы из потока, если Приоритетность проявляется в том, что в момент окончания обслуживания следующим на обслуживание выбирается из очереди запрос, имеющий максимальный приоритет. Запросы, имеющие один и тот же приоритет, выбираются согласно установленной дисциплине обслуживания, например, согласно дисциплине FIFO.
Рассматриваются различные варианты поведения системы в ситуации, когда во время обслуживания запроса некоторого приоритета в систему поступает запрос более высокого приоритета.
Система называется СМО с относительным приоритетом, если поступление такого запроса не прерывает обслуживание запроса. Если же такое прерывание происходит, то система называется СМО с абсолютным приоритетом. В этом случае, однако, требуется уточнить дальнейшее поведение запроса, обслуживание которого оказалось прерванным. Различают следующие варианты: прерванный запрос уходит из системы и теряется; прерванный запрос возвращается в очередь и продолжает обслуживание с места прерывания после ухода из системы всех запросов, имеющих более высокий приоритет; прерванный запрос возвращается в очередь и начинает обслуживание заново после ухода из системы всех запросов, имеющих более высокий приоритет. Прерванный запрос обслуживается прибором после ухода из системы всех запросов, имеющих более высокий приоритет, в течение времени, имеющего прежнее или некоторое другое распределение. Возможен вариант, когда требуемое время обслуживания в последующих попытках идентично времени, которое требовалось для полного обслуживания данного запроса в первой попытке.
Таким образом, имеется достаточно большое число вариантов поведения системы с приоритетом, с которыми можно ознакомиться в вышеупомянутых книгах. Общим в анализе всех систем с приоритетами является использование понятия периода занятости системы запросами приоритета к и выше. При этом основным методом исследования этих систем является метод введения дополнительного события, кратко описанный в разделе 6.
Проиллюстрируем особенности нахождения характеристик систем с приоритетами на примере системы, описанной в начале раздела. Будем считать, что это система с относительным приоритетом и найдем стационарное распределения времени ожидания запроса приоритета если бы он поступил в систему в момент времени t (так называемого виртуального времени ожидания), для системы с относительными приоритетами.
Обозначим
Условием существования этих пределов является выполнение неравенства
где величина вычисляется по формуле:
Обозначим также .
Утверждение 21. Преобразование Лапласа - Стилтьеса стационарного распределения виртуального времени ожидания запроса приоритета к определяется следующим образом:
где функции задаются формулой:
а функции находятся как решения функциональных уравнений:
Доказательство. Заметим, что функция представляет собой преобразование Лапласа - Стилтьеса распределения длины периода занятости системы запросами приоритета I и выше (то есть, интервала времени с момента поступления в пустую систему запроса приоритета I и выше и до первого после этого момента, когда система окажется свободной от присутствия запросов приоритета I и выше). Доказательство того, что функция удовлетворяет уравнению (1.118), почти дословно повторяет доказательство Утверждения 13. Отметим лишь, что величина есть вероятность того, что период занятости системы запросами приоритета I и выше начинается с прихода запроса приоритета а величина трактуется как вероятность ненаступления катастрофы и запросов приоритета I и выше, за периоды занятости, порожденные которыми наступает катастрофа, за время обслуживания запроса приоритета , начавшего данный период занятости.
Сначала вместо процесса рассмотрим существенно более простой вспомогательный процесс - время, в течение которого ожидал бы начала обслуживания запрос приоритета к, если бы он поступил в систему в момент времени t и после этого в систему не поступало запросов более высокого приоритета.
Пусть - преобразование Лапласа - Стилтьеса распределения случайной величины . Покажем, что функция определяется следующим образом:
(1.119)
Вероятность того, что система пуста в момент времени - вероятность того, что в интервале началось обслуживание запроса приоритета
Для доказательства (1.119) применим метод введения дополнительного события. Пусть независимо от работы системы поступает простейший поток катастроф интенсивности s. Каждый запрос назовем «плохим», если во время его обслуживания поступает катастрофа, и «хорошим» - в противном случае. Как следует из утверждений 5 и 6, поток плохих запросов приоритета к и выше является простейшим с интенсивностью
Введем событие A(s,t) - за время t в систему не поступали плохие запросы приоритета к и выше. В силу утверждения 1 вероятность этого события подсчитывается как:
Подсчитаем эту вероятность иначе. Событие A(s,t) является объединением трех несовместных событий
Событие состоит в том, что катастрофы не поступили ни за время t, ни за время При этом, естественно, за время t в систему поступали только хорошие запросы приоритета к и выше. Вероятность события очевидно, равна
Событие состоит в том, что катастрофа поступила в интервале , но в момент поступления система была пуста, а за время не поступило плохих запросов приоритета к и выше.
Вероятность события вычисляется как:
Событие состоит в том, что катастрофа поступила в интервале но в момент ее поступления в системе обслуживался запрос приоритета ниже k, который начал обслуживаться в интервале а за время t - и не поступило плохих запросов приоритета k и выше. Вероятность события определяется следующим образом:
Поскольку событие есть сумма трех несовместных событий, то его вероятность есть сумма вероятностей этих событий. Поэтому
Приравнивая два полученных выражения для вероятности и умножая обе части равенства на после несложных преобразований получаем (1.119)
Очевидно, что для того, чтобы за время ожидания запроса, поступившего в момент t не поступило катастрофы, необходимо и достаточно, чтобы за время не поступило катастроф и запросов приоритета и выше, таких, что за периоды занятости (запросами приоритета и выше), порожденные ими, наступает катастрофа. Из этих рассуждениий и вероятностной трактовки преобразования Лапласа - Стилтьеса получаем формулу, дающую связь преобразований в очевидной форме.
Система массового обслуживания состоит из следующих элементов (рисунок 5.6).
1 - входящий поток требований ω(t ) – совокупность требований к СМО на проведение определенных работ (заправка, мойка, ТО и др.) или оказание услуг (покупка изделий, деталей, материалов и др.). Входящий поток требований может быть постоянным и переменным.
Требования бывают однородные (одинаковые виды работ или услуг) и неоднородные (разные виды работ или услуг).
2 - очередь – требования, ожидающие обслуживания. Очередь оценивается средней длиной r – числом объектов или клиентов, ожидающих обслуживания.
Рисунок 5.6 – Общая схема системы массового обслуживания
3 - обслуживающие аппараты (каналы обслуживания) – совокупность рабочих мест, исполнителей, оборудования, осуществляющих обслуживание требований по определенной технологии.
4 - выходящий поток требований ω’(t ) – поток требований, прошедших СМО. В общем случае выходящий поток может состоять из требований обслуженных и необслуженных. Пример необслуженных требований: отсутствие нужной детали для автомобиля, находящегося в ремонте.
5- замыкание (возможное) СМО – состояние системы, при котором входящий поток требований зависит от выходящего.
На автомобильном транспорте после обслуживания требований (ТО, ремонт) автомобиль должен быть технически исправным.
Системы массового обслуживания классифицируются следующим образом.
1 По ограничениям на длину очереди:
СМО с потерями – требование покидает СМО необслуженным, если в момент его поступления все каналы заняты;
СМО без потерь – требование занимает очередь, даже если все каналы
заняты;
СМО с ограничениями по длине очереди m или времени ожидания: если существует ограничение на очередь, то вновь поступившее (m +1)-е требование выбывает из системы необслуженным (например, ограниченная емкость накопительной площадки перед АЗС).
2 По количеству каналов обслуживания п:
Одноканальные: n =1;
Многоканальные n ≥2.
3 По типу обслуживающих каналов:
Однотипные (универсальные);
Разнотипные (специализированные).
4 По порядку обслуживания:
Однофазовые – обслуживание производится на одном аппарате (посту);
Многофазовые – требования последовательно проходит несколько аппаратов обслуживания (например, поточные линии ТО; конвейерная сборка автомобиля; линия внешнего ухода: уборка → мойка → обсушка → полировка).
5 По приоритетности обслуживания:
Без приоритета – требования обслуживаются в порядке их поступления на СМО;
С приоритетом – требования обслуживаются в зависимости от присвоенного им при поступлении ранга приоритетности (например, заправка автомобилей скорой помощи на АЗС; первоочередной ремонт на АТП автомобилей, приносящих наибольшую прибыль на перевозках).
6 По величине входящего потока требований:
С неограниченным входящим потоком;
С ограниченным входящим потоком (например, в случае предварительной записи на определенные виды работ и услуг).
7 По структуре СМО:
Замкнутые – входящий поток требований при прочих равных условиях зависит от числа ранее обслуженных требований (комплексное АТП, обслуживающее только свои автомобили (5 на рисунке 5.6));
Открытые – входящий поток требований не зависит от числа ранее обслуженных: АЗС общего пользования, магазин по продаже запасных частей.
8 По взаимосвязи обслуживающих аппаратов:
С взаимопомощью – пропускная способность аппаратов непостоянна и зависит от занятости других аппаратов: бригадное обслуживание нескольких постов СТО; использование «скользящих» рабочих;
Без взаимопомощи – пропускная способность аппарата не зависит от работы других аппаратов СМО.
Применительно к технической эксплуатации автомобилей находят распространение замкнутые и открытые, одно- и многоканальные СМО, с однотипными или специализированными обслуживающими аппаратами, с одно- или многофазовым обслуживанием, без потерь или с ограничением на длину очереди или на время нахождения в ней.
В качестве показателей эффективности работы СМО используют приведенные ниже параметры.
Интенссивность обслуживания
где ω - параметр потока требований.
показывает количество требований, поступающих в единицу времени, т.е.
| A =ωg , | (5.13) |
где g - .
Относителъная пропускная способность определяет долю обслуженных требований от общего их количества.
Вероятность того, что все посты свободны Р 0 , характеризует такое состояние системы, при котором все объекты исправны и не требуют проведения технических воздействий, т.е. требования отсутствуют.
Вероятность отказа в обслуживании Р отк имеет смысл для СМО с потерями и с ограничением по длине очереди или времени нахождения в ней. Она показывает долю «потерянных» для системы требований.
Р оч определяет такое состояние системы, при котором все обслуживающие аппараты заняты, и следующее требование «встает» в очередь с числом ожидающих требований r.
Зависимости для определения названных параметров функционирования СМО определяются ее структурой.
где n зан - .
Время связи требования с системой:
СМО с потерями
| t сист =gt д; | (5.16) |
СМО без потерь
| t сист =t д +t ож. | (5.17) |
| И =С 1 r +С 2 n сн +(С 1 +C 2)ρ, | (5.18) |
где С 1 - стоимость простоя автомобиля в очереди;
r - средняя длина очереди;
С 2 -стоимость простоя обслуживающего канала;
n сн - количество простаивающих (свободных) каналов;
t ож - среднее время нахождения в очереди.
Из-за случайности входящего потока требований и продолжительности их выполнения всегда имеется какое-то среднее число простаивающих автомобилей. Поэтому требуется так распределить число обслуживающих аппаратов (постов, рабочих мест, исполнителей) по различным подсистемам, чтобы И= min. Этот класс задач имеет дело с дискретным изменением параметров, так как число аппаратов может изменяться только дискретным образом. Поэтому при анализе системы обеспечения работоспособности автомобилей используются методы исследования операций, теории массового обслуживания, линейного, нелинейного и динамического программирования и имитационного моделирования.
Пример. Станция технического обслуживания имеет один пост диагностирования (п= 1). Длина очереди ограничена двумя автомобилями (т= 2). Определить параметры эффективности работы диагностического поста, если интенсивность потока требований на диагностирование в среднем А =2 треб./ч, продолжительность диагностирования t д = 0,4 ч.
Интенсивность диагностирования μ=1/0,4=2,5.
Приведенная плотность потока ρ=2/2,5=0,8.
Вероятность того, что пост свободен,
P 0 =(1-ρ)/(1-ρ m +2)=(1-0,8)/(1-0,8 4)=0,339.
Вероятность образования очереди
P оч =ρ 2 Р 0 =0,8 2 0,339=0,217.
Вероятность отказа в обслуживании
P отк =ρ m +1 (1-ρ)/(1-ρ m +2)=0,8 3 (1-0,8)/(1-0,84)=0,173.
Относительная пропускная способность
g =1-P отк =1-0,173=0,827.
Абсолютная пропускная способность
А =2 0,827=1,654 треб./ч.
Среднее количество занятых постов или вероятность загрузки поста
n зан =(ρ-ρ m +2)/(1-ρ m +2)=(0,8-0,8 4)/(1-0,8 4)=0,661=1-P 0 .
Среднее количество требовниий, находящихся вочереди,
Среднее время нахождения требования в очереди
t ож =r /ω=0,564/2=0,282 ч.
Пример. На автотранспортном предприятии имеется один пост диагностирования (п= 1). В данном случае длина очереди практически неограниченна. Определить параметры эффективности работы диагностического поста, если стоимость простоя автомобилей в очереди составляет С 1 = 20 ре (расчетных единиц) в смену, а стоимость простоя постов С 2 = 15 ре Остальные исходные данные те же, что и для предыдущего примера.
Вероятность того, что пост свободен
P 0 =1-ρ=1-0,8=0,2.
Вероятность образования очереди
P оч =ρ 2 Р 0 =0,8 2 0,2=0,128.
Относительная пропускная способность g =1, так как все намеченные автомобили пройдут через диагностический пост.
Абсолютная пропускная способность А =ω=2 треб./ч.
Среднее количество занятых постов n зан =ρ=0,8.
r =ρ 2 /(1-ρ)=0,8 2 /(1-0,8)=3,2.
Среднее время ожидания в очереди
t ож =ρ 2 /(1-ρ)/μ=0,8 2 /(1-0,8)/2,5=1,6.
Издержки от функционирования системы
И =С 1 r +С 2 n сн +(С 1 +C 2)ρ=20 3,2+15 0,2+(20+15) 0,8=95,0 ре/смену.
Пример. На том же автотранспортном предприятии число постов диагностирования увеличено до двух (n =2), т.е. создана многоканальная система. Так как для создания второго поста необходимы капиталовложения (площади, оборудование и т.д.), то цена простоя средств обслуживания увеличивается до С’ 1 =22 ре. Определить параметры эффективности работы системы диагностирования. Остальные исходные данные те же, что для предыдущего примера.
Интенсивность диагностирования и приведенная плотность потока остаются теми же: μ=2,5, ρ=0,8.
Вероятность того, что оба поста свободны,
Р
0 =1: 
=0,294.
Вероятность образования очереди
P оч =ρ n Р 0 /n !=0,8 2 0,294/2=0,094,
т.е. на 37 % ниже, чем в предыдущем примере.
Относительная пропускная способность g =1, так как все автомобили пройдут через диагностические посты.
Абсолютная пропускная способность А =2 треб./ч.
Среднее количество занятых постов n зан =ρ=0,8.
Среднее количество требований, находящихся в очереди,
r =ρP оч /(n -ρ)=0,8 2 0,094/(2-0,8)=0,063.
Среднее время нахождения в очереди
t ож =P оч /(n -ρ)/μ=0,094/(2-0,8)/2,5=0,031.
Издержки от функционирования системы
И =С 1 r +С 2 n сн +(С 1 +C 2)ρ=20 0,063+22 1,2+(20+22) 0,8=61,26 ре/смену,
т.е. в 1,55 раза ниже, чем при тех же условиях для одного диагностического поста, главным образом за счет сокращения очереди автомобилей на диагностику и времени ожидания автомобилей более чем в 50 раз. Следовательно, строительство второго диагностического поста в рассматриваемых условиях целесообразно. Используя формулу (5.18) из условия И 1 =И 2 , можно оценить предельные значения цены простоя средств обслуживания при строительстве и оснащении второго диагностического поста, которая в рассмотренном примере составляет C 2 пр =39 ре.
