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

Система может  находиться в одном состоянии S₀, S₁, S₂,…,S_k,…,S_n,…, нумеруемых по числу заявок, находящихся в СМО: S0 - в системе нет заявок (все каналы свободны); S₁ - занят один канал, остальные свободны; S₂ - заняты два канала, остальные свободны; …, S_k - занято k каналов, остальные свободны; …, S_n - заняты все n каналов (очереди нет); S_{n+1 -} заняты все n каналов, в очереди одна заявка; …, S_{n+r -} заняты все n каналов, r заявок стоит в очереди, ….

Граф состояний  показан на рисунке 7.

Размещено на http://www.allbest.ru/

Рис.7. Граф состояний  многоканальной СМО с ожиданием

Обратим внимание, что по мере увеличения в СМО от 0 до n увеличивается число каналов  обслуживания. При числе заявок в СМО, большем, чем n, интенсивность потока обслуживания сохраняется равной nµ.

Формулы для  предельных состояний СМО с ожиданием  выглядят следующим образом:

(1.27)

(1.28)

(1.29)

Вероятность того, что заявка окажется в очереди  равна:

(1.30)

Для n-канальной СМО  с ожиданием, используя прежние  формулы, можно найти:

среднее число занятых  каналов:

(1.31)

среднее число заявок в  очереди:

(1.32)

среднее число заявок в  системе:

(1.31) [4, 349 - 360].

1.2 Имитационное моделирование  систем массового обслуживания

1.2.1 "Когда другие  методы беспомощны…"

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

Методы математического  моделирования пока не смогут обеспечить исчерпывающего анализа таких задач  организационного управления, как:

1. Формирование инвестиционной  политики при перспективном планировании. Инвестиционная политика крупных фирма должна, в частности, учитывать финансовое обеспечение научно-исследовательских и опытно-конструкторских работ при создании новых видов продукции, возможности расширения рынка сбыта, критериальные оценки основных проектов, оценку степени риска при планировании тех или иных комплексов работ, источники финансирования (кредит, привлечение капитала продажей акций и т.д.), увеличение фонда заработной платы, размещение и сокращение финансовых активов, сравнительную оценку вариантов слияния с другой фирмой и приобретения последней и т.п. Полноценная операционная модель, с помощью которой можно было бы анализировать различные варианты инвестиционной политики, должна учитывать стохастическую природу и динамический характер инвестирования, а также предусматривать способ просеивания огромного количества стоящих перед фирмой альтернатив.

2. Выбор средств  обслуживания (или оборудования) при  текущем планировании. При этом  рассматривались задачи определения  количества контрольных прилавков  в большом торговом центре, количества  бензоколонок на бензозаправочной  станции и количества лифтов  в строящемся здании. Можно привести много других примеров, в которых рассматриваются вопросы распределения кадров, планировка заводских помещений, выбор мощности оборудования и т.д. Типичными вопросами, возникающими в связи с решением задачи выбора средств обслуживания или оборудования, являются вопросы, начинающиеся словами: сколько?, каких размеров? и как разместить?.

3. Разработка  планов с обратной информационной  связью и операционных предписаний.  Примеры такого рода задач  также многочисленны, хотя они  не сразу могут прийти на ум тем, кто не имеет достаточного профессионального опыта. К важным задачам данного класса относится, например, задача выработки правил составления календарных планов на предприятиях с мелкосерийным производством, комбинатах по ремонту различных изделий, вычислительных центрах и т.д. Эти предписания, или операционные алгоритмы, должны учитывать гарантийные сроки выполнения заказов, потребности в обслуживании, наличные ресурсы, производственные мощности, темпы повышения квалификации рабочих (или приток дополнительной квалифицированной рабочей силы), уровень снабжения сырьем. По мере поступления информации о новых уже выполненных заказах предприятие сталкивается с задачей уточнения или полного пересмотра своих планов-графиков.

Почему описанные выше классы задач с трудом поддаются анализу? Причина заключается в необходимости одновременного учета факторов неопределенности, динамической взаимной обусловленности текущих решений и последующих событий, в комплексной взаимозависимости между управляемыми переменными исследуемой операционной системы, а в ряде случаев также и в том, что требуется рассматривать строго дискретную и четко определенную последовательность интервалов времени. Такого рода "глобальные" системные задачи обладают слишком большой размерностью и наличием слишком большого количества внутренних взаимосвязей, в силу чего их не удается решить методами математического программирования.

Наиболее  эффективным из существующих в настоящее  время операционных методов, выходящих  за рамки обычного математического программирования, является метод имитационного моделирования на ЭВМ.

При имитационном моделировании, прежде всего, строится экспериментальная модель системы. Затем производится сравнительная  оценка конкретных вариантов функционирования системы путем "проигрывания" различных ситуаций на рассматриваемой модели.

При этом факторы  неопределенности, динамические характеристики и весь комплекс взаимосвязей между  элементами исследуемой системы  представляют в виде формул, хранящихся в памяти быстродействующей ЭВМ. Имитирование системы начинают с некоторого вполне конкретного исходного состояния. В результате принимаемых решений, а также вследствие ряда контролируемых и неконтролируемых событий, среди которых могут быть и события случайного характера, система переходит в последующие моменты времени в другие состояния. Эволюционный процесс, таким образом, продолжается до тех пор, пока не наступит конечный момент планового периода. Отрезки времени внутри планового периода нередко оказываются четко определенными и образуют упорядоченную последовательность на достаточно большом периоде имитирования.

Изложенные  выше соображения позволяют понять, почему метод имитационного моделирования  удается реализовать только с  помощью ЭВМ. Для получения статистической надежности, достаточной для обоснования управляющих решений, как правило, требуется многократное повторение имитационных тестов. Каждый сеанс имитирования настолько сложен, что попытка осуществить имитирование вручную (при разумных затратах времени) скорее всего потерпела бы полный крах. Поэтому неудивительно, что имитационное моделирование на ЭВМ обычно представляет собой весьма дорогостоящий способ исследования больших систем [11, 346 - 349].

1.2.2 Построение  имитационной модели

Структуру имитационной модели в большинстве случаев удобно описывать, определяя содержание фигурирующих в ней динамических процессов и результатов функционирования имитируемой системы. Обычно динамические процессы протекают в соответствии с определенными правилами принятия решений. Результаты функционирования реальной системы, как правило, атрибутированы (т.е. имеют вполне определенный физический смысл). Кроме того, наблюдаются атрибутивные связи, устанавливающие способ суммирования результатов функционирования системы.

В любой момент времени имитационная модель находится в некотором вполне определенном состоянии. Состояние системы характеризуется не только результатами, полученными к текущему моменту времени, но нередко включает в себя и некоторые ретроспективные данные.

Зная состояние системы и ее динамику, можно определить "действия" и состояния системы во все последующие моменты времени. Имитационные модели, обладающие эволюционной структурой, часто называют каузальными.

Построив  модель, операционист обязательно задается вопросом: "Насколько она реалистична?" Более правильным было бы спросить: "Позволяет ли модель разобраться в существе имитируемого процесса и можно ли с ее помощью прийти к надежным умозаключениям?" В конечном счете, поскольку имитационная модель может описывать реальные явления лишь приближенно, ее следует оценивать по возможности проведения на ее основе анализа управляющих решений, представляющих собой предмет конкретного операционного исследования. Определив цель имитационного эксперимента, операционист строит каждый элемент модели с надлежащей степенью детализации и точности. Здесь необходимо сделать предостережение. Опытные специалисты по имитационному моделированию утверждают, что даже для начинающего операциониста не представит труда построить модель из отдельных компонентов, каждый из которых будет соответствовать действительности, однако после "сшивания" отдельных частей получаемая в результате модель может вести себя не так, как имитируемая реальная ситуация. Поэтому не следует слепо предполагать, что имитационная модель как единое целое является в достаточной степени точной только потому, что каждая из составляющих ее частей, рассматриваемая изолированно от других, представляется вполне адекватной описываемому процессу. Это предостережение особенно важно по той причине, что цель имитационного моделирования заключается в воспроизведении поведения всей функциональной системы в целом, а не отдельных ее частей [11, 356 - 358].

При построении имитационной модели, предназначенной  для углубленного анализа проблем  организационного управления, преследуют, по крайней мере, одну из следующих целей:

1) Изучение  действующей функциональной системы.  Рассмотрим промышленную фирму,  которая недавно зарегистрировала  увеличение числа заказов на  свою продукцию и отметила, затем  заметное ухудшение качества обслуживания своих клиентов в части соблюдения сроков выполнения этих заказов. У этой фирмы может появиться желание построить имитационную модель, с помощью которой можно было бы изучить, каким образом существующие процедуры определения сроков выполнения принимаемых заказов, календарного планирования производства и оформления заявок на поставку сырья порождают наблюдаемые задержки.

2) Анализ гипотетической  функциональной системы. Обратимся  к больнице, руководство которой  рассматривает вопрос внедрения новой системы управления запасами медицинских препаратов. Руководство больницей может изъявить желание построить с использованием ретроспективных данных имитационную модель, чтобы проверить, каким будет средний уровень средств, связанных в запасах, и как часто будут возникать нехватки различных видов препаратов в случае, если будет реализован предлагаемый план.

3) Проектирование  более совершенной функциональной  системы. Рассмотрим предприятие  с мелкосерийным производством,  в котором станочные мощности распределены в соответствии с приоритетами, присвоенными выполняемым работам. У фирмы может появиться желание построить имитационную модель для нахождения эффективного способа определения системы приоритетов с тем, чтобы все работы могли выполняться без больших задержек и чтобы при этом коэффициент использования оборудования предприятия был достаточно высок.

Перейдем  теперь к описанию этапов построения и использования имитационной модели.

Шаг 1. Построение модели. Содержание данного этапа  почти не отличается от содержания этапа построения операционной модели любого другого типа. Опасность при этом заключается в излишней детализации модели, которая может привести к слишком большим затратам машинного времени при выполнении соответствующего эксперимента. Лучший способ уберечься от такого рода опасности заключается в том, чтобы постоянно помнить о конкретной цели исследования. Например, если модель должна помочь в выборе одного из двух вариантов размещения нового складского помещения, то, по-видимому, нет необходимости при построении имитационной модели делить плановый период на часы или дни: вполне достаточно использовать отрезки времени, продолжительность которых равняется 1 недели. Однако если с помощью модели нужно решить, сколько в новом складе должно быть погрузочно-разгрузочных платформ (например, одна или две), то, возможно, возникнет необходимость имитировать процесс функционирования упомянутого складского помещения, ориентируясь на отрезки времени продолжительностью от 5 до 15 мин.

Шаг 2. Разработка проекта эксперимента. Операционист сможет уменьшить вероятность той или иной ошибки и, таким образом, потери времени, если он подробно разработает сопровождающие эксперимент процедуры до того, как модель будет "приведена в действие". Это означает, что операционисту необходимо тщательно продумать, какие функциональные характеристики имитируемой системы планируется измерять. Кроме того, следует определить, с помощью какого метода математической статистики будут учитываться флуктуации экспериментальных данных, полученных в результате этих измерений.

Шаг 3. Разработка программного обеспечения. Весь имитационный эксперимент проводится на быстродействующей  ЭВМ. Другими словами, все стадии эволюционного развития модели, так  же как и генерирование случайных событий, протекают в ЭВМ. Если имитируемая система обладает очень простой структурой, то может оказаться, что при разработке соответствующего "вычислительного варианта" модели удобнее всего использовать один из стандартных языков программирования типа Фортран, PL/I или Алгол. Однако представляется более вероятным, что предпочтение будет отдано одному из языков моделирования, такому, как Симскрипт или GPSS, трансляторы с которых имеются для многих больших ЭВМ. В процессе практического применения метода имитационного моделирования операционист убедится, что перечисленные выше этапы не являются полностью независимыми и не выполняются в строго установленной последовательности. Так, например, если специалист по исследованию операций уже владеет языком моделирования, скажем GPSS, то он, возможно, захочет "сформулировать" имитационную модель сразу на этом языке.

1.2.3 Языки  имитационного моделирования

Операционисту, не являющемуся одновременно специалистом в области программирования для ЭВМ, транслировать выбранную им имитационную модель в соответствующую машинную программу никогда не придется. Тем не менее знать содержание основных этапов отображения модели на машинные программы представляется совершенно необходимым.

Для проигрывания простых типовых моделей можно использовать так называемые специальные стандартные программы, которые требуют от операциониста лишь задания определенного количества входной информации. Наиболее показательными примерами таких программ являются моделирующие программы управления запасами. Существует несколько специальных стандартных программ, проверяющих стратегию управления запасами с точки зрения их эффективности. Чтобы использовать такого рода программы, необходимо задать конкретные предписания (которые формулируются, например,

следующим образом: "при снижении уровня запасов до 4 единиц заказать 10 дополнительных единиц") или располагать формулой для определения этих предписаний при известном уровне спроса. При этом в качестве входной информации необходимо представить также либо ретроспективные данные относительно спроса, либо распределение вероятностей для уровней спроса. При наличии всей указанной выше информации машинная программа обеспечивает имитирование функциональной системы для любого заданного операционистом числа интервалов времени, а также вычисляет такие статистические характеристики системы, как средний уровень запасов, количество оформляемых заказов и т.д.