Тема 5. Методы моделирования систем массового обслуживания
При решении задач рациональной организации торговли, бытового обслуживания, складского хозяйства и т.п. весьма полезной бывает интерпретация деятельности производственной структуры как системы массового обслуживания, т.е. системы, в которой, с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой - происходит постоянное удовлетворение этих запросов.
Теория систем массового обслуживания. Система массового обслуживания (СМО) предполагает наличие следующих элементов: - входящий поток,
- очередь, - обслуживающее устройство (каналы обслуживания), выходящий поток. Необходимо уяснить следующие термины:
- требование – каждый отдельный запрос на выполнение какой-либо работы;
- обслуживание – выполнение работы по удовлетворению поступившего требования;
- обслуживающее устройство – объект, выполняющий обслуживание требований;
- время обслуживания – период, в течение которого удовлетворяется требование на выполнение какой-либо работы;
- время ожидания обслуживания – период от момента поступления требования до обслуживания.
Классификация СМО:
1) По числу каналов обслуживания:
- одноканальные,
- многоканальные,
2) В зависимости от условий ожидания:
- с потерями (отказами),
- с ожиданием.
3) по дисциплине обслуживания:
- с приоритетом,
- без приоритета.
4) по характеру обслуживания:
- однофазные,
- многофазные.
|
|
|
5) по месту нахождения источника требования:
- разомкнутые (источник требования находится вне СМО),
- замкнутые.
Теория системы управления запасами. Управление запасами заключается в установлении той или иной периодичности поставок, объемов, регулярности, сроков их выполнения. Совокупность правил, по которым принимаются решения по управлению запасами, называется системой (стратегией) управления запасами.
В качестве параметров, по которым осуществляется управление запасами могут выступать:
1) размеры запасов – в системе с фиксированным размером заказов как только уровень запасов снижается до определенного критического уровня (точки заказа) происходит пополнение запасов до определенного уровня; время между заказами может быть разным);
2) периодичность заказа на пополнение запасов – в системе с фиксированной периодичностью заказа пополнение запасов осуществляется через одинаковые периоды (например, раз в неделю); при этом количество пополняемого запаса может быть разным.
3) поддерживаемый уровень запасов – в системе с двумя фиксированными уровнями уровнями (s, S – система) уровень запасов регламентируется как сверху, так и снизу;
4) саморегулирующиеся системы (изменяющийся размер заказа, периодичность и т.д.).
|
|
|
Всякая СМО включает четыре элемента: входящий отток, очередь, обслуживающее устройство, выходящий поток.
Требованием (клиентом, заявкой) в СМО называется каждый отдельный запрос на выполнение какой-либо работы.
Обслуживание – это выполнение работы по удовлетворению поступившего требования. Объект, выполняющий обслуживание требований, называется обслуживающим устройством (прибором) или каналом обслуживания.
Временем обслуживания называется период, в течение которого удовлетворяется требование на обслуживание, т.е. период от начало обслуживания и до его завершения. Период от момента поступления требования в систему и до начало обслуживания называется временем ожидания обслуживания. Время ожидания обслуживания в совокупности со временем обслуживания составляет время пребывания требования в системе. СМО классифицируются по разным признакам.
1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.
2. В зависимости от условия ожидания требованием начала обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.
В СМО с потерями требования, поступившее в момент, когда все приборы заняты обслуживанием, получают отказ, они теряются для данной системы и никакого влияния на дальнейший процесс обслуживания не оказывают. Классическим примером системы с отказами является телефонная станция – требование на соединение получает отказ, если вызываемый абонент занят.
|
|
|
Для системы с отказами основной характеристикой эффективности функционирования является вероятность отказа или средняя доля заявок, оставшихся необслуженными.
В СМО с ожиданием требование, поступившее в момент, когда все приборы заняты обслуживанием, не покидает систему, а становится в очередь и ожидает, пока не освободится один из каналов. При освобождении очередного прибора одна из заявок, стоящих в очереди, немедленно принимается на обслуживание.
Для СМО с ожиданием основными характеристиками являются математические ожидания длины очереди и времени ожидания.
Примером системы с ожиданием может служить процесс восстановления работы телевизоров в ремонтной мастерской.
Встречаются системы, лежащие между указанными двумя группами (смешанные СМО). Для них характерно наличие некоторых промежуточных условий: ограничениями могут быть ограничения во времени ожидания начала обслуживания, по длине очереди и т.п.
|
|
|
В качестве характеристик эффективности может применяться вероятность отказа как в системах с потерями (или характеристики времени ожидания) и в системах с ожиданием.
3. По дисциплине обслуживания СМО делятся на системы с приоритетом в обслуживании и на системы без приоритета в обслуживании.
Требования могут обслуживаться в порядке их поступления либо случайным образом, либо в зависимости от установленных приоритетов.
4. СМО могут быть однофазными и многофазными.
В однофазных системах требования обслуживаются каналам одного типа (например, рабочими одной профессии) без передачи их от одного канала к другому, в многофазных системах такие передачи возможны.
5. По месту нахождения источника требования СМО делятся на разомкнутые (когда источник требования находится вне системы) и замкнутые (когда источник находится в самой системе).
К замкнутым относятся системы, в которых поступающий поток требований ограничен. Например, мастер, задачей которого является наладка станков в цехе, должен периодически их обслуживать. Каждый налаженный станок становится в будущем потенциальным источником требований на наладку. В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.
Если питающий источник обладает бесконечным числом требований, то системы называются разомкнутыми. Примерами подобных систем могут служить магазины, кассы вокзалов, портов и т.п. Для этих систем поступающий поток требований можно считать неограниченным.
Методы и модели исследования СМО можно условно разбить на аналитические и статистические (имитационного моделирования процессов массового обслуживания).
Аналитические методы позволяют получить характеристики системы как некоторые функции от параметров ее функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО.
К сожалению, аналитическому решению поддается лишь довольно ограниченный круг задач теории массового обслуживания. Несмотря на постоянно ведущуюся разработку аналитических методов, во многих реальных случаях аналитическое решение либо невозможно получить, либо итоговые зависимости оказываются настолько сложными, что их анализ становится самостоятельной трудной задачей. Поэтому ради возможности применения аналитических методов решения приходится прибегать к различным упрощающим предположениям, что в некоторой степени компенсируется возможностью применения качественного анализа итоговых зависимостей (при этом, разумеется, необходимо, чтобы принятые допущения не искажали реальной картины процесса).
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения таких задач массового обслуживания, в которых поток требований является простейшим (пуассоновским).
Под задачей управления товарными запасами понимается такая оптимизационная задача, в которой задана информация:
· о поставках товара;
· о спросе на товар;
· об издержках и условиях хранения товарных запасов;
· критерии оптимизации.
В практической деятельности и служб маркетинга используются более простые принципиальные системы регулирования товарных запасов, основанные на различных стратегиях пополнения запасов, т.е. на определенных правилах этого пополнения, выраженных в достаточно общей форме. В качестве параметров в этих системах принимаются величина имеющихся на складе запасов, допустимые колебания уровня запасов, размеры заказа на пополнение запасов, его периодичность и др. Системы различаются между собой в зависимости от того, какие из параметров выбраны в качестве регулирующих. Принципиальные системы регулирования запасов, используемые в практике маркетинга, подробно описаны во многих учебниках и пособиях. Поэтому дадим здесь лишь краткий обзор этих систем.
Система с фиксированным размером заказа. Это наиболее распространенная система, в которой размер заказа на пополнение запасов – постоянная величина, а поставка очередной партии товара осуществляется при уменьшении наличных запасов до определенного критического уровня, называемого точкой заказа. Поэтому регулирующими параметрами системы с фиксированным размером заказа являются: 1) точка заказа, т.е. фиксированный уровень запаса, при снижении до которого организуется заготовка очередной партии товара, и 2) размер заказа, т.е. величина партии поставки. Данную систему часто называют «двухбункерной», так как запас хранится как бы в двух бункерах: в первом бункере для удовлетворения спроса в течение периода между фактическим пополнением заказа, а во втором – для удовлетворения спроса в течение периода от момента подачи заказа до поступления очередной партии товара, т.е. во втором бункере хранится запас на уровне точки заказа.
Система с фиксированной периодичностью заказа.При этой системе заказы на очередную поставку товарного запаса повторяются через равные промежутки времени. В конце каждого периода проверяется уровень запасов и исходя из этого определяется размер заказываемой партии; при этом запас пополняется каждый раз до определенного уровня, не превышающего максимальный запас. Таким образом, регулирующие параметры этой системы: 1) максимальный уровень запасов, до которого осуществляется их пополнение и 2) продолжительность периода повторения заказов. Система с фиксированной периодичностью заказа эффективна, когда имеется возможность пополнять запас в различных размерах, причем затраты на оформление заказа любого размера невелики. Одним из достоинств этой системы можно считать возможность периодической проверки остатков на складе и отсутствие необходимости вести систематический учет движения остатков. К недостаткам системы относится то, что она не исключает возможность нехватки товарных запасов.
Система с двумя фиксированными уровнями запасов и с фиксированной периодичностью заказа. В этой системе допустимый уровень запасов регламентируется как сверху, так и снизу. Кроме максимального верхнего уровня запаса устанавливается нижний уровень (точка заказа). Если размер запаса снижается до нижнего уровня еще до наступления фиксированного времени пополнения запаса, то делается внеочередной заказ. В остальных случаях система с фиксированной периодичностью заказа. В данной системе имеется три регулирующих параметра: 1) максимальный уровень запаса, 2) нижний уровень запаса (точка заказа) и 3) длительность периода между заказами. Первые два параметра постоянны, третий – частично переменный. Рассматриваемая система сложнее предыдущей, однако, она позволяет исключить возможность нехватки товарного запаса. Недостатком системы является то, что пополнение запасов до максимального уровня не может производиться независимо от фактического расходования запасов.
Модель динамики предполагает наличие параметров, наилучшим образом отражающих исходные данные. Реализация этого требования осуществляется с использованием метода наименьших квадратов (МНК), с которым студенты знакомы из курса математической статистики.
В качестве основного литературного источника по данной теме рекомендуется использовать [1,4], в качестве дополнительного – [5,8].
Тема 7. Сетевые модели
Система методов СМ– система методов планирования и управления разработкой крупных народно-хозяйственных комплексов, научными исследованиями, конструкторской и технологической подготовкой производства новых видов изделий, строительством и реконструкцией, капитальным ремонтом основных фондов путем применения сетевых графиков.
Сетевое моделирование-разновидность структурного моделирования, применяемого когда моделируемый процесс представляет собой сложную систему, включающую большое количество операций с достаточно сложными взаимосвязями между ними. Сетевое планирование и управление дает возможность решать следующие задачи:
• четко отобразить состав и структуру управляемого процесса, выявить с требуемой степенью детализации операции, составляющие моделируемого процесса, установить взаимосвязи между ними
• вскрыть резервы сил, средств и времени, скрытые в нерациональной организации управляемого процесса, осуществлять контроль за ходом процесса сразу по нескольким направлениям;
• упростить внесение изменений, уточнений и дополнений в планы, обеспечивая гибкость и требуемую периодичность планирования, упростить систему отчетности
• корректировать принятые управленческие решения, получать прогнозы на будущее, предвидеть возможные отклонения процесса от плана и последствия вносимых изменений.
Сетевая модель – это план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графиком (рис.1.).
Элементы сетевой модели:
· работа - процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющий протяженность во времени;
· событие - момент времени, когда завершаются одни работы и начинаются другие,событие представляет собой результат проведенных работ и не имеет протяженности во времени;
· путь - любая непрерывная последовательность работ в сетевом графике, в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы.
Рис.1. Сетевой график
Система сетевого планирования основана на безмасштабном графическом изображении комплекса операций, показывающем технологическую последовательность и логическую взаимозависимость между всеми работами, направленными на достижение определенной цели.
Сетевой график (стрелочная диаграмма, сетевая модель или просто сеть) состоит из стрелок и кружков, обозначающих два основных элемента любой сети – работы и события. Работа – это реальный процесс или действие, требующее затрат труда, материалов или времени. Продолжительность выполнения работ измеряется в единицах времени: часах, днях, неделях, месяцах и т.д. Работы могут иметь также и количественные показатели, которые характеризуют трудоемкость, стоимость, материальные ресурсы и т.д. Работы обозначаются стрелками, которые соединяются между собой с помощью кружков (событий). Временные и количественные оценки проставляются обычно над стрелками. Событием называется результат, получаемый после выполнения работ, стрелки которых сходятся к данному кружку. Событие имеет двойственное значение. Для всех предшествующих работ оно является законченным свершением, а для последующих работ – начальным пунктом их выполнения. Всем событиям присваивается определенный цифровой шифр, который проставляется обычно внутри кружка. В общем смысле начальное (предшествующее) событие обозначается буквой i, а конечное (последующее) буквой j, работа в этом случае обозначается как i,j.
Во всяком сетевом графике бывает два особых события, которые не имеют двойственного значения – исходное и завершающее. Исходное событие – это момент начала выполнения комплекса работ. Оно не является результатом предыдущих работ, поэтому в него не входит ни одной стрелки. Исходные события принято обозначать буквой J. К особенностям завершающего события относится то, что оно свидетельствует об окончании всех работ и поэтому не имеет ни одной последующей работы. Из этого события не выходит ни одной стрелки. Обозначается оно буквой С.
Для получения безошибочной структуры сетевых графиков при их построении необходимо соблюдать следующие основные правила:
1. В сетевой модели не должно быть «тупиковых» событий, т. е. событий, из которых не выходит ни одна работа, за исключением завершающего события.
2. В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа.
3. В сети не должно быть замкнутых контуров и петель, т. е. путей соединяющих некоторые события с ними же самими.
При возникновении контура необходимо вернуться к исходным данным и путем пересмотра состава работ добиться его устранения
4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.
5. В сети рекомендуется иметь одно исходное и одно завершающее событие.
6. Длина стрелки не зависит от времени выполнения работы.
7. Каждая операция должна быть представлена только одной стрелкой.
8. Следует избегать пересечения стрелок.
9. Не должно быть стрелок, направленных справа налево.
10. Номер начального события должен быть меньше номера конечного события.
11. При построении сети исходное событие располагается с левой стороны, а завершающее – с правой. Нумерация событий обычно начинается с исходного и заканчивается на завершающем событии.
12. Для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием.
Расчет параметров сетевого графика. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы Рi,j, состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.2а).
На рис.2б изображен пример кодирования работ и событий в принятых обозначениях: tij – продолжительность работы Рi,j, t – ранний срок (ожидаемый момент) осуществления события, t* – поздний срок (предельный момент) осуществления события, n – номер события, nсм – номер предшествующего (смежного) события.
Рис. 2. Обозначение элементов сетевого графика: а – код работы; б – пример кодирования событий в принятых обозначениях; в – пример изображения события в принятых выше обозначениях
На рис. 2в приведён пример изображения события в принятых выше обозначениях.
Обозначим через 
множество работ, входящих в j-е событие, а через 
– множество работ, выходящих из i-го события.
Раннийсрок (ожидаемый момент) осуществления j-го события представляет собой момент времени, раньше которого событие произойти не может и рассчитывается по формуле
.
Поздний срок (предельный момент) осуществления i-го события показывает максимальную задержку во времени наступления данного события:
.
Одно из важнейших понятий сетевого графика – понятие пути L.
Критический путь – последовательность работ между начальными и конечными событиями сети, имеющих наибольшую продолжительность во времени. Минимальное время, необходимое для выполнения проекта, запланированного сетевым графиком, равно длине критического пути. Сетевой график может содержать не один, а несколько критических путей. Критическими называются также работы и события, расположенные на этом пути. Резервный интервал от t до t* для событий, лежащих на критическом пути, равен 0. Для завершающего события сетевого графика поздний срок свершения события должен равняться его раннему сроку, т. е. tп = t*п.
Длина критического пути равна раннему сроку свершения завершающего события, т. е. tкр = tп= t*п.
Любая из работ пути L на его участке, не совпадающем с критическим путем (замкнутым между двумя событиями критического пути), обладает резервом времени.
Среди резервов времени работ наиболее часто используют полный и свободный резервы времени работ.
Полный резерв времени 
работы Pi,j показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв 
определяется по формуле
.
Свободный резерв времени 
работы Pi,j представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. находится по формуле
.
Работы, лежащие на критическом пути, так же, как и критические события, резервов времени не имеют.
Анализ и оптимизация сетевого графика.Чаще всего продолжительность работы по сетевому графику заранее не известна и может принимать лишь одно из ряда возможных значений, т. е. продолжительность работы tijявляется случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми характеристиками – средним значением, или математическим ожиданием, 
и дисперсией σ2 i,j.
Для определения числовых характеристик 
и σ2i,j работы Pi,j на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки:
а) оптимистическую оценку аij;
б) пессимистическую оценку bij;
в) наиболее вероятную оценку mij.
Указанные три оценки являются основой для расчета средней ожидаемой продолжительности работы ( ) и ее дисперсии ( 
). При этом используется гипотеза об определенном законе распределения длительностей работ (так называемое β-распределение).
Предположение о β-распределении продолжительности работы Рi,j позволяет получить следующие оценки ее числовых характеристик:
;
.
Общая продолжительность пути L имеет нормальный закон распределения со средним значением 
(L), равным сумме средних значений продолжительности составляющих его работ и дисперсией σ2 (L), равной сумме соответствующих дисперсий σ2i,j:
;
.
Требуется оценить вероятность того, что срок выполнения проекта tкрне превзойдет заданного директивного срока Т.
Полагая tкp случайной величиной, имеющей нормальный закон распределения, получим
,
где Ф(z) – значение интеграла вероятностей Лапласа, где
,
где σкр – среднее квадратическое отклонение длины критического пути:
.
Если P(tкp ≤ Т) мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т. п.). Если P(tкp ≤ Т) значительна (например, более 0,8), то, очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.
Значения функции Лапласа определяются с помощью значений таблицы функций Лапласа или с помощью функции «НОРМРАСП» в среде MS Excel (см. подразд. 3.4).
Анализ сетевого графика. Сложность сетевого графика оценивается коэффициентом сложности, который определяется по формуле
,
где Kсл – коэффициент сложности сетевого графика; nраб – количество работ, ед.; nсоб – количество событий, ед.
Сетевые графики, имеющие коэффициент сложности от 1,0 до 1,5, являются простыми, от 1,51 до 2,0 – средней сложности, более 2,1 – сложными.
Определить степень трудности выполнения в срок каждой группы работ некритического пути можно с помощью коэффициента напряженности работ.
Коэффициентом напряженностиКн работы Pi,j называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим – критический путь:
где t(Lmax) – продолжительность максимального пути, проходящего через работу Pi,j , от начала до конца сетевого графика; tкр – продолжительность (длина) критического пути; t'кр – продолжительность отрезка рассматриваемого максимального пути, совпадающего с критическим путем.
Коэффициент напряженностиКн работы Pi,j может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути). Чем ближе к 1 коэффициент напряженностиКн работы Pi,j, тем сложнее выполнить данную работу в установленные сроки. Чем ближеКн работы Pi,j к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.
Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величиныКн выделяют три зоны: критическую (Кн> 0,8); подкритическую (0,6 <Кн< 0,8); резервную (Кн < 0,6).
Оптимизация сетевого графика методом «время-стоимость»
При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа Pi,j характеризуется продолжительностью ti,j, которая может находиться в пределах
где аij – минимально возможная (экстренная) продолжительность работы Pi,j, которую только можно осуществить в условиях разработки; bij – нормальная продолжительность выполнения работы Pi,j.
При этом стоимость сi,j работы Pi,j заключена в границах от cmin (при нормальной продолжительности работы) до сmах (при экстренной продолжительности работы).
Затраты на ускорение работы Pi,j (по сравнению с нормальной продолжительностью) на единицу времени рассчитываются по формуле
где hi,j – коэффициент затрат на ускорение работы Pi,j.
Вариант частной оптимизации сетевого графика с учетом стоимости предполагает использование резервов времени работ. Продолжительность каждой работы, имеющей резерв времени, увеличивают до тех пор, пока не будет исчерпан этот резерв или пока не будет достигнуто верхнее значение продолжительности bij. Стоимость выполнения проекта до оптимизации
.
Стоимость выполнения проекта после оптимизации уменьшится на величину
.
Для проведения частной оптимизации сетевого графика, кроме продолжительности работ ti,j, необходимо знать их граничные значения аij и bij, а также показатели затрат на ускорение работ hi,j, вычисляемые по формуле. Продолжительность каждой работы ti,j целесообразно увеличить в таком размере, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т. е. на величину свободного резерва времени .
В качестве основного литературного источника по данной теме рекомендуется использовать [1,4], в качестве дополнительного – [5,6,10,13].
Авторы надеются, что предлагаемый курс поможет студентам осмыслить неоднозначные процессы развития экономической системы современного мира и России, заглянуть в разнообразный и увлекательный мир прикладной математики и в итоге приобрести навыки профессионального видения и решения экономических проблем управления.
Желаем Вам успеха!
Дата добавления: 2018-04-05; просмотров: 1146; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!