Методы оптимизации и исследование операцийдля бакалавров информатики. Ч. IV. Сетевое планирование и массовое обслуживание: учебное посо- бие. — Томск: Изд-во НТЛ, 2013. — 164 с

Б. А. Гладких

МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ ДЛЯ БАКАЛАВРОВ ИНФОРМАТИКИ

Часть IV Сетевое планирование и массовое обслуживание

ÐÛ

***

ËÈÒÅÐÀ ÒÓ

ËÜÑÒÂÎ Í ÒÅ À ÄÀ

ÎÉ ÑÊ

-ÒÅÕÍÈ× ÍÎ Å Ó×

ÈÇ

ТОМСК «Издательство НТЛ» 2013

УДК 517.8 Г 522

Г 522

Гладких Б. А. Методы оптимизации и исследование операций для бакалавров информатики. Ч. IV. Сетевое планирование и массовое обслуживание: учебное пособие. — Томск: Изд-во НТЛ, 2013. — 164 с.

ISBN 978-5-89503-525-2 Книга представляет собой заключительную часть серии учебных пособий, написанных на основе лекций, в течение ряда лет читавшихся автором на факультете информатики Томского государственного университета. Электронные копии всех книг серии размещены в открытом доступе на сайте Научной библиотеки ТГУ: Ч. I. Введение в исследование операций. Линейное программирование Ч. II. Нелинейное и динамическое программирование Ч. III. Теория решений

http://vital.lib.tsu.ru/vital/ access/manager/Repository/ vtls:000374996

http://vital.lib.tsu.ru/vital/ access/manager/Repository/ vtls:000416882 http://vital.lib.tsu.ru/vital/ access/manager/Repository/ vtls:000444907 Ч. IV. Сетевое планиро- http://vital.lib.tsu.ru/vital/ вание и массовое обслу- access/manager/Repository/ живание vtls:000447583 Отзывы и замечания присылать по адресу [email protected] Рецензент: доктор физ.-мат. наук, профессор А. А. Назаров

ISBN 978-5-89503-525-2

УДК 517.8

c Б. А. Гладких, 2013  c Издательство НТЛ,  обложка, 2013

Оглавление Введение

4

20. Основы сетевого планирования и управления 20.1. Проект и его сетевая модель . . . . . . . . . . . . . . . . 20.2. Временной анализ проекта . . . . . . . . . . . . . . . . . 20.3. Распределение ресурсов . . . . . . . . . . . . . . . . . . 20.4. Программное обеспечение для управления проектами . 20.5. Оптимизация стоимости проекта . . . . . . . . . . . . . 20.6. Анализ проекта со случайными длительностями работ 20.7. Исторические замечания . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

6 7 16 25 35 40 50 68

21. Элементы теории массового обслуживания 21.1. Предмет теории массового обслуживания . . . . . 21.2. Описание и основные свойства случайных потоков 21.3. Простейший (пуассоновский) поток . . . . . . . . . 21.4. Марковские процессы . . . . . . . . . . . . . . . . . 21.5. Система M/M/n/0 (с потерями) . . . . . . . . . . 21.6. Система M/M/n/∞ (с ожиданием) . . . . . . . . . 21.7. Исторические замечания . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

78 79 86 89 98 108 119 124

. . . . . . .

. . . . . . .

. . . . . . .

22. Имитационное моделирование систем массового обслуживания 131 22.1. Общие вопросы имитационного моделирования . . . . . . . 132 22.2. Система моделирования GPSS . . . . . . . . . . . . . . . . . 140 22.3. Дискретно-событийное моделирование в MATLAB/Simulink151 22.4. Исторические замечания . . . . . . . . . . . . . . . . . . . . 158 Литература

162

Введение В предыдущих главах мы рассматривали базовый инструментарий исследования операций (методы оптимизации, общие принципы анализа решений), не привязываясь к конкретным предметным областям. Теперь займемся более частными вопросами и попытаемся взглянуть на исследуемые системы «при б´ольшем увеличении». Как отмечалось во введении в курс [4, ч. I, с. 22], на сегодняшний день в арсенале исследования операций имеется ряд хорошо изученных и проверенных на практике проблемноориентированных математических моделей. Включение тех или иных в программу обучения определяется практическими потребностями формирования профессиональных компетенций. Нам представляется, и это нашло отражение в Государственных образовательных стандартах по информационным технологиям и прикладной информатике, что для будущего IT-специалиста чрезвычайно полезным является знакомство по крайней мере с двумя предметными областями исследования операций: сетевым планированием и массовым обслуживанием. Сетевое планирование и управление. Современные программные комплексы по праву относятся к наиболее сложным и трудоемким творениям человеческой цивилизации. Крупные системы содержат миллионы команд, в их разработке участвуют сотни и даже тысячи специалистов, процесс программирования и отладки длится годами, затраты исчисляются многими миллионами долларов. Совершенно ясно, что успех таких проектов определяется не только и не столько квалификацией отдельных

Введение

5

исполнителей, как четкой, научно обоснованной организацией их совместного труда. В связи с этим в современном индустриальном программировании стали широко использоваться научные методы организации производства, которые были разработаны в 1960–1970 гг. для управления разработками сверхсложных технических систем (ракетно-космических комплексов, уникальных строек) и которые во второй половине XX века сформировались в самостоятельную науку управление проектами (project management) [1, 12]. Управление проектами — комплексная дисциплина, использующая достижения классического менеджмента, экономики, психологии и, что является для нас наиболее интересным, — исследования операций. Как показала практика, наиболее эффективным способом упорядочения работ в сложном проекте является сетевое планирование и управление, основанное на математическом аппарате теории графов, математического программирования и теории вероятностей. Поэтому гл. 20 мы посвятили краткому изложению математической стороны управления проектами. Массовое обслуживание. Как ни удивительно, данный термин является чисто русским и на английский язык дословно не переводится, в англоязычной литературе используется словосочетание queueing theory (теория очередей). Теория массового обслуживания описывает операции, в которых случайный поток объектов (требований, заявок) обрабатывается обслуживающими устройствами (приборами), при этом из-за случайного характера протекающих процессов могут образовываться очереди либо происходить отказы в обслуживании. Знание основ теории массового обслуживания необходимо для понимания работы операционных систем и компьютерных сетей. В гл. 21 и 22 мы познакомимся с начальными понятиями теории массового обслуживания, простейшими математическими моделями, а также с основами компьютерного моделирования таких систем.

Глава 20 Основы сетевого планирования и управления Сетевое планирование и управление — СПУ (network-based analysis, planning, scheduling) — раздел исследования операций, который изучает специфические математические методы планирования и управления сложными комплексами взаимосвязанных работ — проектами. Особенностью таких комплексов является то, что в них имеется большое число элементарных работ, связанных условиями технологической зависимости (предшествования), для их выполнения требуются разнообразные ресурсы (людские, материальные, энергетические, финансовые), которые, как правило, ограничены. Задача СПУ состоит в оптимальном календарном, ресурсном, стоимостном планировании проектов и поддержки оперативного управления ими. Примеры проектов: • разработка и изготовление сложного изделия (в том числе программного); • строительство; • единичное и мелкосерийное производство; • выполнение образовательной программы.

20.1. Проект и его сетевая модель

7

20.1. Проект и его сетевая модель Под проектом (project) понимается некоторый комплекс взаимосвязанных работ (activities, tasks). Каждая работа имеет четко выраженные моменты начала и окончания и в общем случае требует для своего выполнения: 1) времени, 2) ресурсов. С этой точки зрения работы могут быть классифицированы на три группы: Основные понятия

• реальные работы, требующие времени и ресурсов, к ним относится большинство работ в проекте; • работы-ожидания. Они требуют времени, но не нуждаются в ресурсах. Примеры — ожидание высыхания краски или затвердения цемента, ожидание резолюции начальника на документе; • фиктивные работы (dummies). Имеют нулевую продолжительность и не требуют ресурсов. Как мы увидим в дальнейшем, такие работы иногда необходимы для синхронизации других работ. Продолжительность или длительность (duration) является важнейшей характеристикой работы. Для рутинных, жестко регламентированных работ она определяется технологической инструкцией и может быть достаточно точно известна заранее. Для слабо формализованных, рисковых работ, таких, как научное исследование или программирование, продолжительность работы точно предсказать нельзя, возможны лишь ее вероятностные оценки. В связи с этим в сетевом планировании имеются два подхода: 1) с постоянными и известными заранее длительностями, 2) со случайными длительностями работ. Мы начнем изучение теории с более простого случая постоянных длительностей, анализ проектов со случайными длительностями работ отложим до параграфа 20.6. .

Глава 20. Основы сетевого планирования и управления

8

П р и м е р. Основные положения теории будем иллюстрировать на простейшем, весьма условном примере строительства дачного домика (табл. 20.1). Таблица 20.1. Проект строительства дома в форме таблицы Номер

Работа

Длительность

Предшественники

1

Чертеж

2

—

2

Фундамент

3

1

3 4 5 6

Канава Стены Сантехника Крыша

2 5 3 4

1 2 3; 4 4

7 8 9 10

Электрика Отделка Благоустройство Сдача

3 7 2 1

6 5; 7 5; 6 8; 9

Весь проект содержит 10 работ, для каждой работы приведены: — порядковый номер, на него ссылаются другие работы; — условное название работы (несколько первых букв подчеркнуты для будущих ссылок); — длительность (в днях), которую считаем пока постоянной; — список порядковых номеров предшественников (predecessors). Предшественники некоторой работы — это те работы, которые необходимо выполнить, прежде чем можно начать данную работу. Список предшественников определяется технологией выполнения проекта. В нашем случае у работы Чертеж предшественников нет, остальные работы технологически связаны с предшественниками. Например, прежде чем начать монтировать Сантехнику, следует закончить копку Канавы и сложить Стены.

20.1. Проект и его сетевая модель

9

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

Планирование проекта всегда начинается с табличного представления, однако работать с ним неудобно. Суть сетевого планирования и управления состоит в графическом представлении проекта в виде сетевого графика (network chart, network diagram, arrow diagram). Изобразить сетевой график можно двумя способами: 1) на языке работ и 2) на языке событий. Сетевой график на языке работ представляет собой ориентированный граф, вершинами которого являются р а б о т ы, а дуги отображают отношение предшествования: стрелка направлена от предшествующей работы к последующей. Последующая работа может быть начата только после того, как выполнены все предшествующие ей работы. В качестве примера на рис 20.1 показан график проекта на языке работ, соответствующий процессу строительства домика. Способ представления проекта на языке работ (по англ. activity-on-node — AON, или precedence diagramming method — PDM ) является самым естественным, однако алгоритмы вычислений в этом случае получаются чуть более сложными. По этой причине исторически первой использовалась альтернативная форма сетевого графика. График на языке работ

10 Чер

Глава 20. Основы сетевого планирования и управления Фун

Сте

Кры

Эл

Кан

Сан

Бла

Отд

Сда

Рис. 20.1. Сетевой график на языке работ

Сетевой график на языке событий представляет собой ориентированный граф, вершинами которого являются с о б ы т и я (events), соответствующие моментам начала и окончания работ, а дуги обозначают работы (по англ. такой способ называется activity-onarrow — AOA, или arrow diagramming method — ADM ). График на языке событий

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

При составлении графика следует придерживаться следующих шести правил, проиллюстрированных на рис. 20.3.

20.1. Проект и его сетевая модель

11

Рис. 20.3. Типичные проблемы при составлении сетевого графика на языке событий и способы их решения. Пояснения в тексте

1. В графе не должно быть орциклов (контуров), в противном случае возникает парадоксальная ситуация, «circulus vitiosus»1 . Алгоритм выявления орциклов мы приведем ниже. Орциклы, если они есть, исправить невозможно, следует пересмотреть сам проект. 2. В графе должна быть одна и только одна вершина, в которую не идет ни одна дуга. Если таких вершин несколько, следует добавить вспомогательную вершину — начало проекта и фиктивные работы (dummy activities) с нулевой продолжительностью, о которых мы говорили выше (рис. 20.3, а). Фиктивные работы обычно изображаются штриховыми линиями. 3. В графе должна быть одна и только одна вершина, из которой не идет ни одна дуга. Если таких вершин несколько, следует добавить вспомогательную вершину — конец проекта и фиктивные работы (рис. 20.3, б ). 1

Circulus vitiosus (лат.) — порочный круг, то же самое через то же самое.

12

Глава 20. Основы сетевого планирования и управления

4. В графе не должно быть параллельных ребер (двуугольников). Эта ситуация исправляется введением дополнительной вершины и фиктивной работы (рис. 20.3, в). Замечание. Тот факт, что между двумя вершинами может быть только одна дуга, дает возможность однозначно идентифицировать работы парой вершин — исходящей и входящей. Это — так называемая (i, j) нотация работ, которой мы будем в дальнейшем пользоваться.

5. Если для начала одной из последующих работ требуется выполнение не всей входящей работы, а только ее части, то входящую работу следует разделить на две части и граф перестроить в соответствии с рис. 20.3, г. В качестве иллюстрации рассмотрим такой пример. Пусть работа а означает покраску пола, работа b — проветривание помещения, а работа c — расстановку мебели. Тогда работу а логично разделить на две части: a1 — подсушивание краски до состояния, когда можно пройти в комнату и открыть форточку, и a2 — окончательная просушка краски. 6. Если для начала одной из следующих работ необходимо выполнение не всех входящих работ, а только некоторых, то следует ввести дополнительное событие, дополнительную фиктивную работу, граф перестроить в соответствии с рис. 20.3, д. Содержательный пример: а — подводка электричества, b — подводка воды, с — подключение электроплиты, d — подключение стиральной машины. Оба языка представления сетевого графика являются равносильными, перевод с одного на другой происходит достаточно просто. Действительно, если имеется график на языке событий, то график на языке работ строится совершенно очевидным образом: для данной работы последующими работами — преемниками (successors) являются те, которые исходят из вершины, соответствующей событию окончания данной работы. Перевод на другой язык

20.1. Проект и его сетевая модель

13

Несколько сложнее выглядит процесс перевода с языка работ на язык событий. Один из возможных алгоритмов приведен ниже, мы его проиллюстрируем на нашем проекте строительства домика, заданном на языке работ. Шаг 1. Построение избыточного графа событий. Для каждой работы из графа работ создается фрагмент графа событий, состоящий из пары вершин, соответствующих событиям начала и конца работы, и соединяющей их дуги, соответствующей данной работе. Отношение предшествования работ отображается фиктивными работами, связывающими конец предшествующей работы с началом преемника. Кроме того, согласно правилам 2 и 3, вводятся начальное и конечное события, они соединяются фиктивными работами соответственно со всеми начальными (не имеющими предшественников) и всеми конечными (не имеющими преемников) работами. П р и м е р. Для графа работ на рис. 20.1 построенный избыточный граф событий имеет вид, показанный на рис. 20.4 (изза мелкого масштаба события показаны кружками без разделения на секторы).  Построенный таким образом граф событий удовлетворяет всем приведенным выше правилам и, в принципе, может использоваться для расчетов. Однако он содержит слишком много лишних событий и фиктивных работ, от которых можно избавиться без потери информации о проекте. Чер

Фун

Сте

Кры

Эл

Кан

Сан

Бла

Отд

Сда

Рис. 20.4. Избыточный граф событий для примера. Висячие вершины не имеют заливки

14

Глава 20. Основы сетевого планирования и управления

Шаг 2. Удаление висячих вершин. Самый очевидный способ упрощения графа — удаление «висячих» вершин, т. е. событий, у которых имеется одна входящая и одна выходящая работа, причем одна из них фиктивная. При этом необходимо следить за выполнением правила 4 и не допускать образования параллельных ребер. Возможные варианты расположения висячих вершин и соответствующие способы преобразования графа приведены на рис. 20.5. Фиктивная работа при удалении висячей вершины объединяется с реальной работой.

Рис. 20.5. Варианты преобразования графа работ при удалении висячих вершин

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

20.1. Проект и его сетевая модель 0

Чер 2

1

Фун

2

Сте

3

3

Кры

5

15 4

4

7

3

Отд 7

9

Сда 10 1

2

Б ла

Ка н 2

Эл

5

Сан

6

8

3

Рис. 20.6. Сетевой график на языке событий для проекта постройки домика. Выполнена правильная нумерация вершин (см. ниже)

Правильная нумерация не единственна, приведенный ниже алгоритм, основанный на разбиении вершин графа на ярусы (слои), производит одну из них. Он же позволяет проверить граф на отсутствие орциклов. Шаг 0. Номер яруса L = 0. Шаг 1. Находятся все вершины, в которые не идет ни одна дуга. Если таких вершин нет, переход на Шаг 4. Если есть, то эти вершины относятся к ярусу L. Шаг 2. Если L = 0, то вершина (единственная), отнесенная к ярусу 0, получает номер 0. Если L > 0, то вершины текущего яруса нумеруются в произвольном порядке, продолжая нумерацию, выполненную на предыдущих шагах. Шаг 3. Пронумерованные вершины выбрасываются вместе с инцидентными им дугами. Номер яруса увеличивается: L = L + 1. Возврат на Шаг 1. Шаг 4. Если все вершины графа пронумерованы, то нормальное завершение алгоритма. Если нет, то это означает, что в графе имеются орциклы и правильная нумерация невозможна. Применительно к нашему проекту алгоритм правильной нумерации дает результат, показанный на рис. 20.6. После того как сетевой график проекта построен, начинается этап его анализа. Анализ проекта может осуществляться с трех точек зрения:

16

Глава 20. Основы сетевого планирования и управления • с точки зрения времени выполнения (временн´ой анализ), материальные и стоимостные ресурсы при этом полагаются как бы неограниченными; • с точки зрения распределения ограниченных материальных ресурсов; • с точки зрения стоимости — специфического и важнейшего вида ресурса.

Для анализа пригоден сетевой график как на языке работ, так и на языке событий, однако исторически первыми были разработаны алгоритмы анализа, использующие граф событий.

20.2. Временной анализ проекта Цель временного анализа — рассчитать возможные сроки наступления событий (в том числе срок выполнения проекта в целом) с учетом возможного распараллеливания работ, а также определить резервы времени для работ. Будем считать, что отсчет времени начинается с начала проекта. Ранним сроком (early, earliest time) наступления некоторого события называется минимально возможное время, необходимое для выполнения в с е х работ, предшествующих данному событию. Если ребрам графа приписать длины и длину ребра считать равной длительности соответствующей работы, то ранний срок любого события будет равен длине д л и н н е й ш е г о из путей, ведущих из начальной вершины в данное событие. Самый длинный из путей, ведущих из начальной вершины графа в конечную, называется критическим путем (critical path). Следовательно, минимально возможное время выполнения всего Ранние сроки и критический путь

20.2. . Временной анализ проекта

17

проекта, т. е. ранний срок конечного события равен длине критического пути в сетевом графе проекта. Это время называется критическим временем проекта T . Для нахождения критического пути в графе применяется стандартный подход динамического программирования для решения задачи о кратчайшем пути [4, ч. II, с. 235], только вместо минимизации осуществляется максимизация. Алгоритм вычисления ранних сроков событий Ei (от Early — ранний) и критического пути состоит из трех этапов. Этап 1 (правильная нумерация). Вершины сети нумеруются в соответствии с приведенным выше алгоритмом (см. с. 15). Начальная вершина получает номер 0, конечная — n. Этап 2 (вычисление ранних сроков событий). Введем следующие обозначения: tij — длительность работы (i, j), т.е. мы пользуемся нотацией, в которой работа идентифицируется парой вершин (см. замечание на с. 12); Γ(i) — множество вершин, в к о т о р ы е идут дуги из вершины i; Γ−1 (j) — множество вершин, и з к о т о р ы х идут дуги в вершину j. Вершины просматриваются в порядке правильной нумерации, ранние сроки событий вычисляются по правилу E0 = 0, Ej = max (Ei + tij ), j = 1, . . . , n. i∈Γ−1 (j)

Таким образом, длина критического пути (критическое время проекта) T = En . Этап 3 (построение критического пути). Критический путь строится с конца. В него включается конечная вершина, далее, идя в обратном стрелкам направлении, последовательно до-

18

Глава 20. Основы сетевого планирования и управления

бавляются вершины, для которых разность ранних сроков в точности равна длительности работы: Ej − Ei = tij . П р и м е р. Проведем расчет ранних сроков и построим критический путь для нашего проекта строительства домика. Сначала вычисляем ранние сроки: E0 = 0; Γ−1 (1) = {0}, E1 = E0 + t01 = 0 + 2 = 2; Γ−1 (2) = {1}, E2 = E1 + t12 = 2 + 3 = 5; Γ−1 (3) = {2}, E3 = E2 + t23 = 5 + 5 = 10; Γ−1 (4) = {3}, E4 = E3 + t34 = 10 + 4 = 14; Γ−1 (5) = {1, 3}, E5 = max[(E1 + t15 ), (E3 + t35 )] = = max[(2 + 2), (10 + 0)] = 10; Γ−1 (6)

= {5}, E6 = E5 + t56 = 10 + 3 = 13;

Γ−1 (7)

= {4, 6}, E7 = max[(E4 + t47 ), (E6 + t67 )] = = max[(14 + 3), (13 + 0)] = 17

и т. д. Затем строим критический путь, идя против стрелок от конечной вершины номер 10. Следующая вершина 9 входит безальтернативно, от нее назад есть два пути: в вершину 8 или вершину 7. Выбираем 7, потому что E9 − E7 = t79 = 24 − 17 = 7. Далее идем в вершину 4, так как E7 − E4 = t47 = 17 − 14 = 3, и так далее до начальной вершины. Ранние сроки событий и критический путь изображены на рис. 20.7. Согласно принятым обозначениям (см. рис. 20.2), ранний срок события записывается в левой нижней части круга, описывающего данное событие. Критическое, т. е. минимально возможное время выполнения проекта T = E10 = 25 дням. Входящие в критический путь работы показаны двойными стрелками, на цветных графиках они обычно выделяются красным цветом. 

20.2. Временной анализ проекта 0 0

Чер

1 2

2

Фун 3

2

Сте

5

5

3 10

19

Кры 4

4 14

Эл 3

7 17

Сда 10 1 25

2

2

7

9 24

Бл а

Ка н

Отд

5 10

Сан

6 3 13

8 14

Рис. 20.7. Ранние сроки событий и критический путь Замечание 1. Критических путей может быть несколько, все они имеют одинаковую длину. Замечание 2. События и работы, лежащие на критическом пути, называются критическими. Суть метода управления проектами по критическому пути (critical path method — CPM) состоит в особом внимании к критическим работам. Любая задержка критической работы приводит к задержке всего проекта, однако их доля в крупном проекте может быть мала, не более нескольких процентов. Поэтому внимание руководителя не рассеивается на множестве всех работ, а концентрируется на небольшом их числе. В итоге вероятность срыва плановых сроков резко снижается. Этим объясняется высокая практическая эффективность метода в реальных проектах (см. исторические замечания в конце главы). Замечание 3. Приведенный алгоритм может быть использован не только для нахождения критического пути графа в целом, но и для построения длиннейшего пути из начальной в некоторую другую вершину. Для этого отслеживание пути на этапе 3 начинается не с конечной, а с выбранной вершины.

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

20

Глава 20. Основы сетевого планирования и управления

Алгоритм вычисления поздних сроков Li (от Late — поздний) подобен алгоритму вычисления ранних сроков. Разница в том, что граф просматривается в порядке, о б р а т н о м правильной нумерации, при этом поздние сроки вычисляются по формулам Ln = En = T, Li = min (Lj − tij ), i = n − 1, . . . , 0. j∈Γ(i)

П р и м е р. Дополним сетевой график нашего проекта поздними сроками всех событий (рис. 20.8). Для примера покажем подробно расчет нескольких поздних сроков: L10 = E10 = 25; Γ(9) = {10}, L9 = L10 − t9,10 = 25 − 1 = 24; Γ(8) = {9}, L8 = L9 − t89 = 24 − 2 = 22; Γ(7) = {9}, L7 = L9 − t79 = 24 − 7 = 17; Γ(6) = {7, 8}, L6 = min[(L7 − t67 ), (L8 − t68 )] = = min[(17 − 0), (22 − 0)] = 17; Γ(5) = {6}, L5 = L6 − t56 = 17 − 3 = 14; Γ(4) = {7, 8},

L4 = min[(L7 − t47 ), (L8 − t48 )] = = min[(17 − 3), (22 − 0)] = 17

и т. д. Легко видеть, что для критических событий ранние и поздние сроки совпадают.  Замечание. Поскольку каждая работа связана с двумя событиями — начала и конца данной работы — и однозначно ими идентифицируется, в литературе и пакетах по сетевому планированию часто используются следующие обозначения: ESij = Ei — раннее начало (early start); EFij = Ei + tij — раннее окончание (early finish); LSij = Lj − tij — позднее начало (late start); LFij = Lj — позднее окончание (late finish).

20.2. Временной анализ проекта 0 0 0

Чер

1

2

2 2

Фун

2

3

5 5

Сте

3

21

Кры

5 10 10

4

4 14 14

Эл

9

7 24 24

Сда 10 1 2525

2

Бл а

Ка н 2

Отд

7

3 1717

5

Сан

6 3 13 17

10 14

8 14 22

Рис. 20.8. Ранние и поздние сроки событий Замечание. Существует чрезвычайно компактный, хотя далеко не оптимальный по трудоемкости алгоритм нахождения наибольших путей между л ю б ы м и д в у м я вершинами ориентированного графа. Он основан на операции специального возведения в степень взвешенной матрицы смежности графа A = (aij )n×n , которая строится по правилу ⎧ ⎪ ⎪ ⎨0, если i = j, aij = tij , если в графе есть дуга (i, j), ⎪ ⎪ ⎩ −∞ в противном случае. Определим операции специального умножения a ∗ b = a + b и специального суммирования ai = max ai . С их помощью введем специальi

i

ное умножение матриц C = A ∗ B, в котором элементы результирующей матрицы вычисляются обычным образом, но операции умножения и суммирования заменены на специальные: cij =

n  k=1

aik ∗ bkj = max(aik + bkj ). k

Легко убедиться, что при таком определении (i, j)-й элемент матрицы AN = A ∗ . . . ∗ A будет равен длине длиннейшего пути из вершины i N

в вершину j, достижимый за N шагов. Если N постепенно увеличивать, то, начиная с некоторого показателя степени, матрица стабилизируется и ее элементы дадут искомые значения длин путей.

22

Глава 20. Основы сетевого планирования и управления

В то время как задержка любой критической работы неизбежно приводит к увеличению критического времени проекта, остальные работы имеют резервы (float, lack) времени, которыми можно разумно воспользоваться. Различают несколько видов резервов. Свободным резервом (free float, free lack) для работы (i, j) называется время, на которое можно задержать ее выполнение при условии, что ранний срок события, соответствующего моменту окончания данной работы, останется неизменным: Резервы времени

τijсв = Ej − Ei − tij . Полным резервом (total float, total lack) для работы (i, j) называется время Fij , на которое можно задержать ее выполнение при условии, что критическое время проекта останется неизменным: Fij = τijпол = Lj − Ei − tij . Принципиальное отличие свободного резерва от полного состоит в том, что свободный резерв каждая работа может использовать по своему усмотрению, все равно он пропадает зря, потому что ранний срок наступления последующего события не может быть меньше из-за других работ. Полный же резерв нужно использовать с осторожностью: если одна работа выбрала весь полный резерв времени и тем самым оказалась на критическом пути, то другие работы, попавшие на тот же критический путь, удлинять невозможно, иначе сорвется срок всего проекта. На рис. 20.9, a схематически изображены резервы времени и возможные стратегии начала работы. Если работа имеет свободный резерв, то ее можно по-разному расположить на отрезке времени, отведенном на ее выполнение. Например, работу можно начать скоро как только возможно (As Soon As Possible — ASAP), т. е. как только будут завершены все предшествующие по технологии работы. Такая стратегия описывается народной мудростью «Никогда не откладывай на завтра то, что можно сделать сегодня», но, к сожалению, далеко не все ей следуют. Противополож-

20.2. Временной анализ проекта

23

ная стратегия (As Late As Possible — ALAP), наоборот, предписывает тянуть с началом работы до последнего мгновения, растрачивая на ожидание работы весь свободный резерв времени2 . ASAP = As Soon As Possible

ALAP = As Late As Possible

Рис. 20.9. Резервы времени (а) и две крайние стратегии начала работ (б )

П р и м е р. Найдем резервы времени для всех работ в нашем простейшем проекте строительства домика. Ручные вычисления удобно проводить с помощью таблицы (табл. 20.2). В итоге видим, что три работы (Кан, Сан, Бла), которые раньше были опознаны как некритические, действительно имеют резервы времени. Однако они не могут одновременно выбрать все свои полные резервы времени. Действительно, вместе с полным резервом длительность работы Кан составляет 12, Сан — 7, Бла — 10 дней, если же разрешить всем этим работам использовать свои полные резервы, то время выполнения проекта составит 32 дня вместо исходных 25.  Заключительным этапом временн´ого анализа является построение календарного графика (schedule graph) проекта. Стандартной формой его представления является полосковая или ленточная диаграмма (bar diagram), названная в честь ее изобретателя Генри ГанКалендарный график проекта

2

Существует даже специальный термин студенческий синдром (student syndrome), см. http:// en.wikipedia.org/wiki/ Student_syndrome.

24

Глава 20. Основы сетевого планирования и управления Таблица 20.2. Расчет резервов времени Работа

i

j

Ei

Ej

Lj

tij

св τij

пол τij

Чер Фун Кан Сте Сан Кры Эл Отд Бла Сда

0 1 1 2 5 3 4 7 8 9

1 2 5 3 6 4 7 9 9 10

0 2 2 5 10 10 14 17 14 24

2 5 10 10 13 14 17 24 24 25

2 5 14 10 17 14 17 24 24 25

2 3 2 5 3 4 3 7 2 1

0 0 6 0 1 0 0 0 8 0

0 0 10 0 4 0 0 0 8 0

та (см. исторические замечания в конце главы) графиком Ганта (Gantt chart). На рис. 20.10 представлен календарный график нашего проекта, построенный по данным табл. 20.2. По оси абсцисс откладывается календарное время в принятом для проекта масштабе, в нашем случае в днях, отсчитываемых с момента запуска проекта. В реальных сетевых графиках время измеряется с учетом производственного календаря (расписание рабочего дня, выходные, праздники и проч.). Каждая работа отображается горизонтальной полоской, начало и конец которой соответствуют плановым срокам выполнения данной работы. При наличии резервов времени работа размещается сообразно выбранной стратегии, в данном случае ASAP. Критические работы обычно выделяются красным цветом. Резервы времени обозначаются узкими полосками, примыкающими к работам. На нашем графике мы отдельно показали свободный и полный резерв в соответствии с обозначениями рис. 20.9, а, но пакеты программ сетевого планирования, например Microsoft Project, обычно показывают на графике только полный резерв. Вертикальная линия отмечает текущее время.

20.3. Распределение ресурсов

25

Чер Фун Кан Сте Сан Кры Эл Отд Бла Сда

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Рис. 20.10. Календарный график проекта для примера. Стратегия ASAP

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

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

26

Глава 20. Основы сетевого планирования и управления

ства дачного домика. Слегка приближаясь к действительности, будем считать, что для выполнения перечисленных в исходной таблице (см. табл. 20.1) работ требуется не только время, но и единственный вид трудовых ресурсов — рабочие, т. е. мы пока предполагаем, что рабочие обладают универсальными навыками и могут исполнять любую работу, если имеется достаточное их число. Необходимое для каждой работы число рабочих приведено в табл. 20.3. Таблица 20.3. Потребность в ресурсах в проекте строительства дома Номер

Работа

Длительность, дни

Рабочие, чел.

1

Чертеж

2

1

2

Фундамент

3

3

3 4 5 6

Канава Стены Сантехника Крыша

2 5 3 4

1 3 2 2

7 8 9 10

Электрика Отделка Благоустройство Сдача

3 7 2 1

1 2 1 3

Пусть объем доступного ресурса (число рабочих) в каждый момент времени постоянен и равен V = 3. Спрашивается, можно ли в таких условиях выполнить проект за минимальные 25 дней? Для того чтобы ответить на этот вопрос, построим (см. рис. 20.11) временной профиль использования (иногда говорят загрузки — loading) нашего единственного ресурса Рабочие, соответствующий приведенному на рис. 20.10 календарному графику проекта. Из рисунка видно, что при данном каПрофиль использования ресурсов

20.3. Распределение ресурсов

27

Чер Фун Кан Сте Сан Кры Эл Отд Бла Сда Кан Фун

Сте

Кры

Чер 0

5

10

Бла Эл 15

Отд 20

Сда

Сан

25

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

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

28

Глава 20. Основы сетевого планирования и управления

при этом возможна конкуренция нескольких работ за дефицитные или уникальные ресурсы. Во-вторых, каждый вид ресурса имеет особенности его потребления. Укажем только некоторые из них: — возобновляемость. Все ресурсы делятся на возобновляемые (renewable), т. е. постоянно имеющиеся в наличии независимо от того, потребляются они или нет, и невозобновляемые (nonrenewable). Трудовые и многие материальные ресурсы (помещения, оборудование, энергия) относятся к категории возобновляемых; расходуемые материалы, будучи однажды истраченными, не возобновляются; — складируемость. Важной характеристикой невозобновляемых ресурсов является складируемость (stackable). Одни складируемые ресурсы, например бетонные плиты, будучи привезенными в некоторый момент времени, сохраняются и в будущем, другие не сохраняются полностью или частично (строительный раствор или жидкий кислород); — доступность по календарю. Обычно возобновляемые ресурсы доступны только в соответствии с заранее установленным календарем. Он может быть как стандартным для всего проекта (начало и конец рабочего дня, выходные, праздники), так и индивидуальным для данного ресурса. Например, приглашенный со стороны электрик может работать только в выходные по вечерам. Доступный объем возобновляемого ресурса может быть как постоянным, так и меняться со временем. Например, в каникулярное время можно привлечь дополнительные трудовые ресурсы для выполнения сезонных работ; — равномерность потребления. Некоторые возобновляемые ресурсы целесообразно загружать равномерно во времени. Это относится прежде всего к трудовым ресурсам, так как зарплату штатному работнику приходится платить независимо от его загрузки. Электроэнергия также весьма критична к равномерности потребления, условия ее поставки зачастую предполагают плату за установленную мощность, фактическая потребляемая мощ-

20.3. Распределение ресурсов

29

ность не должна сильно от нее отличаться. В-третьих, оптимизация распределения ресурсов может осуществляться по различным критериям. В качестве целевой функции могут выступать время выполнения проекта или его стоимость. Кроме того, существуют разнообразные дополнительные ограничения на календарный график. По указанным причинам проблема календарного планирования ресурсов не имеет общего решения. Более того, даже простые с виду попытки оптимального управления ресурсами при их строгой формализации приводят к чрезвычайно трудно решаемым задачам дискретного математического программирования. Реализованные в пакетах управления проектами алгоритмы рассчитаны на самые простые случаи и являются эвристическими, дающими приближенное, но приемлемое на практике решение. Классической постановкой задачи календарного планирования считается выравнивание (leveling) ресурсов, при которой ситуации превышения доступного уровня устраняются путем переноса сроков выполнения работ, при этом общее время выполнения проекта, как правило, увеличивается, однако при удачном стечении обстоятельств может остаться неизменным. Алгоритмы выравнивания ресурсов подразделяются на две группы: параллельные и последовательные. При параллельном планировании допускается прерывание однажды начатой работы. При нехватке ресурсов она приостанавливается и вновь запускается при появлении освободившихся от других работ ресурсов. Такой стиль управления зачастую можно наблюдать во время ремонта: приходят маляры, красят одну стену, потом их перебрасывают на более срочный объект, а начатая работа стоит недоделанная... При последовательном планировании прерывать начатую работу нельзя до ее окончания. Разумеется, параллельные алгоритмы дают большую свободу действий, однако при этом возможны потери времени и денег при каждой переброске ресурсов на другую работу.

30

Глава 20. Основы сетевого планирования и управления

В качестве иллюстрации приведем Эвристический алгоритм простой алгоритм последовательновыравнивания ресурсов го планирования ресурсов. Для его описания мы будем пользоваться аналогией с процессом обработки прерываний в вычислительной системе. Предположим, что планировщик проекта (человек или процесс) постоянно находится в состоянии сна, из которого его выводит сигнал прерывания. Этот сигнал возникает при запуске проекта, а также в момент окончания любой работы. Планировщик обрабатывает прерывание в соответствии с приведенным ниже алгоритмом (время исполнения алгоритма считается ничтожно малым), после чего засыпает до следующего прерывания. Алгоритм обработки одного прерывания следующий. Шаг 1. Фиксация времени прерывания t. Шаг 2. Удаление из графика выполненной работы, учет освободившихся ресурсов. Шаг 3. Определение фронта ждущих работ, т. е. работ, которые были ранее отложены, а также работ, непосредственно следующих за выполненной. Шаг 4. Если ждущих работ нет либо ресурсов недостаточно ни для одной из ждущих работ, то переход на Шаг 9. Шаг 5. Если текущих ресурсов достаточно для всех ждущих работ, то запуск из всех. Переход на Шаг 9. Шаг 6. Пересчет сетевого графика: а) установка ранних сроков всех ждущих работ в t; б) пересчет полных резервов времени ждущих работ. Шаг 7. Установление приоритетов ждущих работ: а) более высокий приоритет для работы с меньшим полным резервом времени; б) при равных резервах более высокий приоритет для работы, с б´ольшим произведением времени на объем ресурсов (чел./дни);

20.3. Распределение ресурсов

31

в) при равных предыдущих приоритетах более высокий приоритет для работы с б´ольшим объемом ресурсов. Шаг 8. Запуск ждущих работ и выделение им ресурсов в соответствии с приоритетами до тех пор, пока хватает ресурсов. Оставшиеся работы приобретают статус отложенных. Шаг 9. Конец обработки, ожидание следующего прерывания. П р и м е р. На рис. 20.12 представлен процесс выравнивания возобновляемого ресурса Рабочие для нашего демонстрационного проекта. Доступный объем ресурса, т. е. общее число рабочих, попрежнему равно трем. Календарь данного ресурса для простоты считаем непрерывным, т. е. работа идет без выходных дней. В качестве исходного взят календарный график (см. рис. 20.11), где работы, имеющие резервы, размещены по стратегии ASAP. В таблице на рис. 20.12 перечислены все прерывания, они же показаны на сопровождающем таблицу календарном графике. Объясним подробно процесс обработки прерываний, при этом для выявления фронта ждущих работ полезно иметь перед глазами исходный календарный график (рис. 20.11). П р е р ы в а н и е 0 в момент времени t = 0 вызвано началом проекта. Все рабочие свободны (V = 3). Единственная ждущая работа Чер требует одного исполнителя (vЧер = 1). На шаге 5 она запускается, процесс планирования засыпает. П р е р ы в а н и е 1. Закончившаяся в момент времени t = 2 работа Чер вызывает прерывание. Удаляем данную работу из проекта, выполнявший ее работник освободился, доступный объем ресурсов опять стал равен V = 3. Рассматривая исходный календарный график на рис. 20.11, видим, что после Чер технологически следуют работы Фун и Кан. Обе их запустить невозможно, так как vФун + vКан = 3 + 1 = 4 > V = 3, поэтому придется учитывать приоритеты, выполняя шаги 6–8. Пересчет графика не потребуется, так как никакие работы мы не сдвигали. Из двух ждущих работ Фун является критической с нулевым резервом, поэтому все ресурсы отдаются ей. Работа Кан получает статус отложенной.

Глава 20. Основы сетевого планирования и управления Прер.

Причина

t

V

Фронт

v

F

0 1

Чер

0 2

3 3

2

Фун

5

3

3

Сте

10

3

4 5

Кан Кры

2 14

1 3

6

Эл, Сан

17

3

1 1 3 1 3 1 2 2 2 2 1 1 2 1

0 10 0 7 0 2 4 0 4 0 0 8 0 5

7 8

Бла Отд

19 24

1 3

Чер Кан Фун Кан Сте Кан Сан Кры Сан Сан Эл Бла Отд Бла — Сда

3

0

Кан Фун

Сте

Кры

Чер 0 0

1

Эл

5

10

2

3

Бла

Сан

Отд

15 4

5

Сда

32

20 6

7

25 8

Рис. 20.12. Процесс и результат выравнивания ресурса Рабочие. Обозначения: Прер. — номер прерывания; Причина — идентификатор работы, окончание которой вызвало прерывание; t — текущее время прерывания; V — доступный после прерывания объем ресурса; Фронт — фронт работ (на каждую работу своя строка); v — количество ресурса, необходимого для выполнения данной работы; F — полный резерв времени работы. Выбранные для запуска работы отмечены галочкой . Номера прерываний на графике соответствуют таблице

20.3. Распределение ресурсов

33

П р е р ы в а н и е 2 вызывается окончанием работы Фун. Текущее время t = 5, доступные ресурсы V = 3. Выбросив из графика работу Фун, видим, что во фронт работ войдут Сте и ранее отложенная Кан, при этом работу Кан следует сдвинуть вправо на три дня, установив ранний срок начала ESКан = t = 5. Ее полный резерв уменьшится на 3 дня и составит 10 − 3 = 7 дней. После пересчета полных резервов времени выясняется, что из двух конкурирующих работ Кан и Сте последняя является более важной, так как имеет нулевой резерв. Все 3 единицы ресурса отдаются ей, эта работа запускается, работа Кан опять откладывается, процесс планирования засыпает. П р е р ы в а н и е 3. Через 5 дней работа Сте заканчивается, вызывая прерывание. Текущее время t = 10, текущие ресурсы V = 3. Фронт работ составляют следующие за Сте Кры и Сан, а также отложенная Кан. Сдвинув работу Кан еще на 5 дней вправо и установив ранний срок ESКан = t = 10, вычисляем ее новый полный резерв, он составляет теперь FКан = 7 − 5 = 2 дня. На все три работы ресурсов не хватает, поэтому запускаем работы согласно приоритетам. Наивысший имеет Кры, имеющая нулевой резерв, ей отдаем двух рабочих. Следом идет Кан с резервом 2 дня, требующая одного рабочего. На этом ресурсы закончились, работа Сан становится отложенной, процесс планирования уходит в режим ожидания. П р е р ы в а н и е 4. Первой в момент t = 12 вызовет прерывание работа Кан, она возвратит одну единицу ресурса (V = 1). Фронт ждущих работ состоит из единственной отложенной на предыдущем прерывании работы Сан. Однако для нее нужно 2 единицы ресурса, поэтому данное прерывание в соответствии с Шагом 4 является безрезультатным. Спим дальше. П р е р ы в а н и е 5. В момент t = 14 происходит прерывание по окончанию работы Кры. Она возвращает 2 единицы ресурса, что вместе с остатком от прошлого прерывания дает V = 3. По

34

Глава 20. Основы сетевого планирования и управления

технологии после Кры могут начаться работы Эл и Бла, кроме того, имеется отложенная работа Сан. Пересчитывая график и сдвигая Сан на 4 дня, вычисляем ее полный резерв FСан = 4 − 4 = 0. Таким образом, работы Сан и Эл выходят на критический путь и получают приоритет по ресурсам. Других ресурсов не остается, работа Бла откладывается. П р е р ы в а н и е 6 в момент t = 17 вызывается окончанием сразу двух работ: Эл и Сан. Все рабочие свободны (V = 3). По технологии может начинаться Отд, кроме того, ждет отложенная Бла. Ресурсов хватает на обе эти работы, они запускаются. П р е р ы в а н и е 7. Через два дня при t = 19 заканчивается работа Бла, возвращающая одну единицу ресурса. Однако фронт работ пустой, поэтому данное прерывание безрезультатное. Один рабочий простаивает. П р е р ы в а н и е 8. В момент t = 24 заканчивается работа Отд, возвращаются выполнявшие ее двое рабочих. Все трое готовы принять участие в единственной оставшейся работе Сда, которая благополучно запускается. Процесс планирования ресурсов с выравниванием завершен. Как видим, за счет сдвига некоторых работ в пределах резерва времени удалось ликвидировать превышение (перегрузку) ресурса, при этом общее время проекта осталось неизменным.  Замечание. Приведенный эвристический алгоритм легко обобщается на случай нескольких ресурсов и на некоторые другие усложнения постановки задачи, например на неравномерный профиль их доступности. Скорее всего, хотя это нигде прямо не указано, именно он лежит в основе метода выравнивания ресурсов, примененного в популярном пакете сетевого планирования Microsoft Project, о котором мы будем говорить ниже.

20.4. Программное обеспечение для управления проектами

35

20.4. Программное обеспечение для управления проектами Программы для управления проектами по методу критического пути были разработаны почти сразу же после появления первых электронных вычислительных машин. Более того, программа расчета сетевых графиков была одной из самых первых коммерческих прикладных программ в истории (см. исторические замечания в конце главы). ЭВМ первых поколений не имели графических устройств ввода-вывода, поэтому сетевое планирование и управление велось по бумажной технологии. Исходные данные проекта в бумажном виде передавались на вычислительный центр, там переносились на перфокарты, перфокарты вводились в ЭВМ, результаты распечатывались в виде рапортичек-уведомлений на каждую работу, которые раздавались руководителям подразделений. Если работа оказывалась на критическом пути, соответствующая рапортичка перечеркивалась красной полосой. Увидев такую на своем столе в начале рабочего дня, начальник вздрагивал и делал все возможное, чтобы не сорвать запланированный срок, иначе он лишался премии. За прошедшие 50 лет вычислительная техника изменилась до неузнаваемости, однако базовые алгоритмы сетевого анализа остались прежними, основные нововведения относились к созданию графического человеко-машинного интерфейса и организации совместной работы многих пользователей над большим проектом. Число разработанных к настоящему времени программных систем для управления проектами измеряется несколькими десятками3 . Они различаются по различным параметрам: — по масштабу: для малого проекта и корпоративные (Enterprise Project Management — EPM). Соответственно варьи3

См. обзор http://en.wikipedia.org/wiki/List_of_project_management_software.

36

Глава 20. Основы сетевого планирования и управления

руется их функциональность. Простейшие программы проводят только временной анализ исходного проекта, более продвинутые обеспечивают постоянное отслеживание проекта в диалоговом режиме, помогают распределять ресурсы, определяют стоимость работ, учитывают риски и т. д. Наиболее крупные интегрированы в корпоративные автоматизированные системы управления (Enterprise Resource Planning — ERP), поддерживают комплексное управление портфелем проектов (Project Portfolio Management); — способу организации вычислительного процесса: автономные однопользовательские, клиент-серверные, «облачные» Web-сервисы (Software as a Service — SaaS); — условиям использования: коммерческие и свободно распространяемые. Мировой рынок программного обеспечения и SaaS-услуг для управления проектами составляет в 2012 г. около 1.2 млрд долл. и продолжает расти. Среди систем высшего класса (highend) лидирующие позиции принадлежат пока программному продукту Primavera компании «Oracle», в секторе средних и малых систем почти монопольное положение занимает Microsoft Project с очень агрессивной маркетинговой политикой. Велик выбор простых свободно распространяемых программ. В частности, альтернативой коммерческому продукту Microsoft может считаться совместимая с ним по форматам система OpenProj (http://sourceforge.net/projects/openproj). Microsoft Project

Под общим названием Microsoft Project предлагается несколько продуктов:

• Microsoft Project Standard — однопользовательская настольная версия для небольших проектов; • Microsoft Project Professional — обладает всей функциональностью однопользовательской версии и, кроме того, выпол-

20.4. Программное обеспечение для управления проектами

37

няет функции «толстого» клиента для корпоративной версии. Версии Standard и Professional формально относятся к семейству приложений Microsoft Office, хотя продаются отдельно от других программ этого пакета; • Microsoft Project Server — серверная часть корпоративной версии, поддерживающей совместное управление проектами и ресурсами; • Microsoft Project Online — «облачный» вариант Microsoft Project Server, который компания «Microsoft» планирует выпустить в 2013 г. Корпоративная версия Microsoft Project вместе с методологией разработки программного обеспечения Microsoft Solution Framework составляют интегрированное решение под названием Microsoft Enterprise Project Management Solution (MS EPM). Приложения Microsoft Project хорошо адаптированы к российским условиям, обеспечиваются фирменной поддержкой, обучением и сертификацией пользователей, они повсеместно используются в управлении реальными проектами. На специальном сайте (см. http://www.microsoftproject.ru) размещена обширная информация для пользователей системы. Поскольку наша задача состоит в изложении только математической стороны управления проектами, мы не будем подробно знакомиться с самой системой и приемами работы с ней, эти вопросы подробно описаны в учебных руководствах [7] и достойны отдельного специализированного курса. Приведем только краткую иллюстрацию, показывающую удобство и интуитивную понятность интерфейса пользователя. На рис. 20.13 приведен наш демонстрационный пример строительства дачного домика в различных представлениях: табличном, сетевом и в виде календарного графика (в этом представлении дополнительно включена опция, показывающая стрелочками зависимость работ). Для облегчения сопоставления с теорети-

38

Глава 20. Основы сетевого планирования и управления

а) Представление в форме таблицы

б) Cетевое представление на языке работ (фрагмент)

в) Календарный график (график Ганта). Стратегия ASAP

Рис. 20.13. Демонстрационный проект строительства домика в пакете Microsoft Project в различных представлениях

20.4. Программное обеспечение для управления проектами

39

ческими результатами календарь ресурса Рабочие выбран непрерывным, без выходных дней, дата начала проекта установлена на первое число месяца. Легко видеть, что показываемое системой табличное представление и расчетные параметры проекта на рис. 20.13, а полностью идентичны тем, которое фигурировали при изложении теории (табл. 20.1–20.3), это же относится к графу проекта на языке работ (ср. рис. 20.13, б с рис. 20.1) и календарному графику (ср. рис. 20.13, в с рис. 20.10). Интересно сравнить теоретические результаты работы разобранного нами алгоритма выравнивания ресурсов (см. рис. 20.12) с теми, которые дает Microsoft Project (рис. 20.14). Налицо полное совпадение.

Рис. 20.14. Выданный Microsoft Project календарный график после выравнивания ресурса

Говоря о календарных планах, мы до сих пор имели в виду п р е д в а р и т е л ь н о е планирование проекта, проводимое до начала его реализации. Однако сама аббревиатура СПУ подразумевает не только планирование, но еще и оперативное у п р а в л е н и е. Для этого в пакете программ имеется функция отслеживания (tracking) выполнения проекта. В корпоративной версии существуют специальные, весьма изощренные средства общения исполнителей с системой для информирования о состоянии порученных им работ. Сроки и иные параметры предварительного (так называемого базового) плана постоянно сравни-

40

Глава 20. Основы сетевого планирования и управления

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

20.5. Оптимизация стоимости проекта Выше мы рассматривали проект с точки зрения времени и ресурсов, теперь обратимся к анализу стоимости. Типовое программное обеспечение, в том числе Microsoft Project, имеет некоторые средства для контроля за стоимостью проекта, как плановой, так и текущей. Для каждого из ресурсов определяется стоимость использования (Per Use Cost), которая может быть как фиксированной, так и повременной. При этом для трудовых ресурсов (исполнителей) можно ввести две повременных ставки: стандартную ставку (Standard Rate) и ставку сверхурочных (Overtime Rate). Менеджер проекта, варьируя время и ресурсы, может попытаться вручную, методом проб и ошибок подобрать их таким образом, чтобы получить приемлемую стоимость при заданных ограничениях. Разумеется, об оптимизации в точной математической постановке здесь речи не идет. Тем не менее задачи об оптимизации стоимости проекта могут быть поставлены достаточно корректно, один из возможных подходов был исследован еще на заре сетевого планирования первооткрывателем метода критического пути Джеймсом («Джимом») Келли (см. исторические замечания в конце главы). Разумеется, эта задача представляет скорее теоретический интерес, чем практический, тем не менее мы ее рассмотрим как пример строгого подхода к оптимизации сложной операции. Кроме того, здесь представляется удобный случай познакомиться с основными идеями параметрического линейного программирования.

20.5. Оптимизация стоимости проекта

41

Первый вопрос, который возникает при системном анализе любой операции, — какие переменные являются управляемыми? В нашей постановке задачи мы будем считать, что таковыми являются д л и т е л ь н о с т и работ. Основное предположение состоит в том, что величины tij , которые мы до сих пор считали постоянными, можно в определенных пределах изменять. Одну и ту же работу можно выполнить медленнее, можно быстрее, но за срочность нужно платить дополнительно. В общем случае зависимость стоимости конкретной работы от длительности имеет вид, показанный на рис. 20.15. Здесь tmin ij и tmax означают разумные границы, определенные технологиij ей или иными практическими соображениями. Реальная зависимость стоимости от времени cij (t) может быть нелинейной, однако с достаточной для практики точностью ее можно аппроксимировать линейной зависимостью Постановка задачи

Рис. 20.15. Зависимость стоимости работы от длительности

cij (tij ) = cmax − kij (tij − tmin ij ij ) = aij − kij tij ,

(20.1)

где aij — некоторая начальная стоимость, а kij имеет смысл ко-

42

Глава 20. Основы сетевого планирования и управления

эффициента удешевления работы при увеличении времени ее выполнения на одну единицу. Если известны минимальные и максимальные продолжительности каждой работы, можно рассчитать сетевой график проекта в двух вариантах: • форсированном: tij = tmin ij ; • ленивом: tij = tmax ij , и для каждого из них определить критическое время: Tmin и Tmax . П р и м е р. Продолжим наш демонстрационный пример со строительством дачного домика и будем предполагать, что работы, идентифицируемые парой событий (i, j), могут иметь переменную длительность в границах, указанных в табл. 20.4. В этой же таблице приведены коэффициенты удешевления (удорожания) работ в некоторых единицах стоимости при их удлинении (сокраТаблица 20.4. Границы длительности и коэффициенты удешевления работ для примера i

j

tmin ij

tmax ij

kij

Чертеж

0

1

1

3

2

Фундамент

1

2

3

3

0

Канава Стены Сантехника Крыша

1 2 5 3

5 3 6 4

1 3 2 3

3 5 4 5

2 4 3 3

Электрика Отделка Благоустройство Сдача

4 7 8 9

7 9 9 10

2 5 2 1

3 8 2 1

2 3 0 0

Работа

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

20.5. Оптимизация стоимости проекта

43

функцию, в таблице не приводятся. Заметим, что работы Фун, Бла и Сда не могут менять длительность, поэтому соответствующие им коэффициенты удешевления нулевые. Проведя расчет длины критического пути для форсированного и ленивого режимов работы (подробные выкладки опускаем), получаем Tmin = 18, Tmax = 28.  Идея минимизации стоимости проекта состоит в том, чтобы, использовав пропадающие впустую свободные резервы времени, растянуть сроки выполнения работ и тем самым уменьшить их стоимость; это можно понимать как «торговлю свободным временем». Задачу об оптимизации стоимости можно поставить в двух вариантах: • минимизация прямых затрат при ограничении времени выполнения проекта; • минимизация полных затрат. Под прямыми затратами (direct cost) пониМинимизация маются затраты, идущие непосредственно на прямых затрат выполнение работ проекта. В соответствии с (20.1) величина прямых затрат равна    cij tij = (aij − kij tij ) = D0 − kij tij , (20.2) D= (i,j)∈U

(i,j)∈U

где постоянное слагаемое D0 =

(i,j)∈U

 (i,j)∈U

aij не зависит от оптими-

зируемых переменных, оно задает некоторую начальную точку отсчета стоимости и имеет смысл только при реальном экономическом анализе, в формальной постановке его можно опустить. Если время выполнения проекта не ограничивать, то задача минимизации (20.2) по переменным tij имеет тривиальное решение: время выполнения всех работ следует установить максималь-

44

Глава 20. Основы сетевого планирования и управления

но возможным: tij = tmax ij . В связи с этим вводится дополнительное ограничение: весь проект должен уложиться в нормативный срок T , находящийся в границах [Tmin , Tmax ]. Для формальной постановки задачи следует определить переменные, целевую функцию и ограничения. Переменные, полностью определяющие сетевой график: Ti — время наступления события i (i = 0, . . . , n), где n — номер события, соответствующего концу проекта; tij — длительность работы (i, j); число этих переменных равно количеству реальных работ. Целевую функцию (20.2) можно упростить, опустив постоянное слагаемое и избавившись от отрицательных значений путем смены направления оптимизации:  kij tij → max . (20.3) L= (i,j)∈U

Ограничения задачи делятся на несколько групп: max а) tmin ij  tij  tij ;

б) Tj  Ti +tij , где (i, j) ∈ U . Ограничения этой группы задают сам сетевой график, их количество равно числу элементов множества U всех дуг, включая дуги, соответствующие фиктивным работам; в) T0 = 0, Tn  T , где T — нормативный срок выполнения проекта, выбранный из промежутка [Tmin , Tmax ]. Получившаяся оптимизационная задача есть задача линейного программирования. Входящие в условия числовые коэффициmax енты tmin ij , tij , kij задаются исходными данными, множество ребер U определяется структурой сетевого графика. Остается неопределенным вопрос: как выбрать значение входящего в условие параметра T . Пока мы будем считать, что оно некоторым образом выбрано из диапазона [Tmin , Tmax ], далее займемся этим вопросом особо.

20.5. Оптимизация стоимости проекта

45

П р и м е р. В сетевом графике нашего демонстрационного проекта 11 событий, 10 реальных и 4 фиктивные работы (см. рис. 20.6), при этом некоторые переменные принимают фиксированные значения: T0 = 0, t12 = 3, t89 = 2, t9,10 = 1. Следовательно, остаются 17 изменяемых переменных: T1 , T2 , . . . T10 ; t01 , t15 , t23 , t34 , t47 , t56 , t79 . С учетом этого имеем следующую задачу линейного программирования: L = 2t01 + 2t15 + 4t23 + 3t34 + 2t47 + 3t56 + 3t79 → max, 1  t01  3,

1  t15  3,

3  t23  5,

2  t47  3,

2  t56  4,

5  t79  8,

T1  0 + t01 , T5  T1 + t15 ,

T2  T1 + 3, T5  T3 + 0,

T7  T6 + 0,

T8  T4 + 0,

T9  T8 + 2,

T10  T9 + 1,

3  t34  5,

T3  T2 + t23 ,

T4  T3 + t34 ,

T6  T5 + t56 , T8  T6 + 0,

T7  T4 + t47 ,

T9  T7 + t79 ,

T10  T.

Если задаться конкретным значением параметра T , то эту задачу можно решить обычным симплексным методом. Воспользовавшись надстройкой «Поиск решения» из пакета Excel [4, ч. II, с. 211], найдем, например, оптимальное решение при T = 22 (напомним, что длительности работ t12 , t89 , t9,10 мы не меняли и в целевую функцию они не вошли): t11 = 3, t15 = 3, t23 = 3, t34 = 3, t47 = 2, t56 = 4, t79 = 5, T1 = 3, T2 = 6, T3 = 11, T4 = 14, T5 = 11, T6 = 19, T7 = 16, T8 = 19, T9 = 21, T10 = 22; L = 81. Аналогичные расчеты можно провести для всех значений параметра T из отрезка [Tmin , Tmax ] и получить зависимость L(T ). Разумеется, полностью построить целевую функцию L(T ) таким образом невозможно, так как область изменения аргумента непрерывна, можно лишь вычислить ее значения в отдельных точках. В таблице и на графике на рис. 20.16 показаны результаты оп-

46

Глава 20. Основы сетевого планирования и управления

Цел. ф-я и затраты

18

19

20

21

22

T 23

24

24

26

27

28

L Прямые Косвенные Полные

63 35 0 35

68 30 3.5 33.5

73 25 7 32

77 21 10.5 31.5

81 17 14 31

84 14 17.5 31.5

87 11 21 32

90 8 24.5 32.5

93 5 28 33

96 2 31.5 33.5

98 0 35 35

50 40

Полные

30 Косвенные

20 10

Прямые

0 18

20

22

24

26

28

30

Рис. 20.16. Иллюстрация к примеру: таблица и графики зависимости затрат от продолжительности проекта. Показаны узловые точки кусочно-линейных функций

тимизации для всех целочисленных значений параметра из промежутка [18, 28], причем в данный момент нас интересуют только прямые затраты. В первой строке таблицы для каждого T приведены достигнутые значения целевой функции L(T ), но, поскольку они мало что говорят, во второй строке приведены д о п о л н и т е л ь н ы е прямые затраты, вычисляемые по правилу max F (T )−F (T ). Их следует понимать как величину превышения прямых затрат при данной длительности проекта над минимальными затратами, получающимися при самом ленивом режиме реализации. Как и следовало ожидать, они монотонно уменьшаются с увеличением нормативного срока проекта и остаются нулевыми при всех T  Tmax . 

20.5. Оптимизация стоимости проекта

47

Рассматривая на рис. 20.16 построенный О параметрическом по точкам график целевой функции (или линейном соответствующий ей график дополнительпрограммировании ных прямых затрат), легко заметить, что он похож на непрерывную кусочно-линейную зависимость с несколькими узловыми точками (в нашем конкретном случае при значениях аргумента T = 18, 20, 22, 27, 28). Если это действительно так, то нет необходимости решать оптимизационную задачу при всех значениях параметра, достаточно найти способ вычисления узловых точек, а промежуточные значения можно получить линейной интерполяцией. В общем виде данная проблема относится к области параметрического линейного программирования (Parametric Linear Programming) [6, гл. 3], основные положения которого были сформулированы еще в середине 1950-х гг. классиками исследования операций Саулом Гассом (Gass, Saul; 1926–2013) и Томасом Саати (Saaty, Thomas; р. 1926). Постановка параметризованной задачи заключается в том, что некоторые коэффициенты, которые в обычной задаче линейного программирования были константами, становятся л и н е й н ым и функциями е д и н с т в е н н о г о параметра λ. Задача обычно ставится в одном из двух вариантах: — с параметром в целевой функции L=

n  j=1 n 

(cj + λcj )xj → min, aij xj = bi ,

i = 1, . . . , m,

j=1

xj  0,

j = 1, . . . , n;

— с параметром в правой части ограничений L=

n  j=1

cj xj → min,

48

Глава 20. Основы сетевого планирования и управления n 

aij xj = bi + λbi ,

i = 1, . . . , m,

j=1

xj  0,

j = 1, . . . , n,

которые, впрочем, могут быть легко преобразованы друг в друга путем перехода к двойственной задаче, когда коэффициенты целевой функции и правые части ограничений меняются местами [4, ч. I, с. 110]. Наша задача минимизации прямых затрат относится ко второму варианту, роль параметра λ выполняет T — нормативный срок проекта. Он входит в правую часть одного из ограничений. Применительно к этому варианту основной результат теории параметрического линейного программирования состоит в том, что оптимальное значение целевой функции L∗ (λ), рассматриваемое как функция параметра, действительно представляет собой в ы п у к л у ю к у с о ч н о - л и н е й н у ю функцию. Построены практические алгоритмы (они являются модификациями симплексного метода), которые позволяют находить точки перегиба этой функции. По сравнению с общей задачей параметрического линейного программирования задача минимизации прямых затрат в сетевом проекте имеет ряд особенностей. Эти особенности позволили патриарху сетевого планирования Джиму Келли (см. исторические замечания в конце главы) разработать специализированный метод, основанный на теории наибольшего потока в сети4 . Подробное изложение метода с примерами можно найти в [8, с. 160]. При выполнении реального проекта кроме прямых затрат приходится нести затраты, связанные с поддержанием проекта в целом. Например, при строительстве дома нужно постоянно платить за аренду техники, охрану, содержание вспомогательного персонала и т. п. С определенной долей условности эти Минимизация полных затрат

4

Kelley J. E. Critical-path planning and scheduling: mathematical basis // Operation Res. 1961. V. 9. No 3. P. 296–320.

20.5. Оптимизация стоимости проекта

49

косвенные расходы можно считать постоянными во времени, тогда их величина будет линейно возрастать с увеличением длительности проекта T . Складывая их с прямыми, мы получаем ситуацию, когда прямые и косвенные затраты, имея противоположные тенденции изменения, формируют функцию полных затрат, имеющую выраженный минимум. Соответствующая этому минимуму длительность проекта T ∗ является оптимальной. П р и м е р. В условиях предыдущего примера предположим, что каждый лишний день строительства нашего домика связан с косвенными затратами в размере 3.5 у. е. Возвращаясь к таблице и графику на рис. 20.16, наблюдаем зависимость дополнительных косвенных и полных затрат от времени выполнения проекта. Как видим, функция полных затрат имеет минимум при T ∗ = 22. Оптимальные характеристики проекта (продолжительности работ, сроки событий) мы получили как раз для этого значения параметра.  К решению задачи об оптимизации стоимости по полным затратам мы шли кружным путем, через параметрическое линейное программирование. Такой подход имеет смысл, если из некоторых экономических соображений нас интересует детальный вид зависимости прямых затрат от длительности реализации проекта. Если же нужен только конечный результат, то решение можно получить напрямую, не ограничивая критическое время проекта Tn параметром T , а введя его (критическое время Tn ) в целевую функцию. Пусть величина косвенных затрат в единицу времени равна q, тогда задача линейного программирования, минимизирующая полные затраты, приобретает вид L=



kij tij − qTn → max,

(i,j)∈U max tmin ij  tij  tij ,

(20.4)

50

Глава 20. Основы сетевого планирования и управления Tj  Ti + tij ,

(i, j) ∈ U,

T0 = 0. П р и м е р. Легко убедиться непосредственной проверкой, решив в пакете Microsoft Excel задачу (20.4), что если подставить все данные сетевого графика из примера на с. 45 и установить q = 3.5, то при максимизации модифицированной целевой функции полу∗ = 22, все чится оптимальное значение критического времени T10 значения оптимизируемых переменных будут такими же, как и в этом примере. 

20.6. Анализ проекта со случайными длительностями работ Во всех предыдущих рассуждениях мы полагали длительности работ известными величинами, которые могут быть достаточно точно оценены тем или иным способом. Такая ситуация характерна для рутинных проектов, связанных с производством или строительством. Однако бывают случаи, когда это невозможно сделать, потому что сам проект носит экспериментальный характер, длительности работ зависят от многих непредсказуемых факторов и допускают весьма расплывчатые оценки. В таких случаях их целесообразно рассматривать как с л у ч а й н ы е величины и применять к анализу проектов вероятностный подход. При вероятностном подходе параметры сетевого графика, в частности длина критического пути, становятся случайными, следовательно, можно ставить вопрос о вычислении с р е д н е г о ожидаемого времени выполнения проекта или вероятности выполнения проекта в заданный срок. Казалось бы, вероятностный подход к сетевому планированию должен был появиться позже детерминированного, однако на самом деле они возникли практически одновременно, так как были ориентированы на различные типы работ (см. исторические

20.6. Анализ проекта со случайными длительностями работ

51

замечания в конце главы). Первая технология управления сложным научно-техническим проектом, называемая PERT — Program Evaluation and Review Technique (Техника оценки и обзора программ), с самого начала исходила из того, что длительности работ не могут быть заданы однозначно, а допускают лишь вероятностные оценки. Само понятие случайной величины предполагает, что исследователю известно, хотя бы приблизительно, вероятностное распределение этой случайной величины. Объективно измерить распределение длительности работы чрезвычайно сложно: для этого данную работу нужно выполнить много раз, накопить статистику, построить эмпирическую функцию распределения, сгладить ее, при этом результат может оказаться слишком сложным для теоретического анализа. По этой причине обычно используется другой способ: из некоторых соображений выбирается модельный класс распределений, описываемых несколькими параметрами, которые определяются экспертным путем для каждой работы. Хотя выбор модельных распределений невозможно строго обосновать, некоторые общие требования можно сформулировать априорно: — во-первых, по своей физической сути длительность любой работы tij представляет собой положительную непрерывную случайную величину, распределенную в ограниченном промежутке max [tmin ij , tij ]; — во-вторых, многочисленные наблюдения, основанные на анализе реальных работ, показали, что обычно эмпирическое распределение длительности имеет вид одногорбой (чаще всего несимметричной) кривой. Следовательно, модельная плотность распределения pij (t) должна быть непрерывной унимодальной max функцией, имеющей максимум внутри диапазона [tmin ij , tij ] и равной нулю вне его. Авторы классического метода PERT, проанализировав обширный фактический материал (хронометражи отдельных видов работ, нормаБета-распределение

52

Глава 20. Основы сетевого планирования и управления

тивные данные и т. д.), выбрали в качестве модельного так называемое бета-распределение (пишут также β-распределение или B-распределение). Изучение этого любопытного распределения мы начнем с частного случая, когда случайная величина t меняется в пределах от 0 до 1. Функция плотности такого н о р м и р о в а н н о г о бета-распределения имеет вид  C tp−1 (1 − t)q−1 при 0  t  1, (20.5) f (t) = 0 при t < 0, t > 1, где p > 0 и q > 0 — параметры распределения; C — нормирующий множитель. Свое название распределение получило потому, что нормирующий множитель определяется из условия C = 1/B(p, q), где выражение B(p, q) =

1

0

tp−1 (1 − t)q−1 dt

представляет собой хорошо известную специальную функцию — бета-функцию (функцию Эйлера первого рода)5 , названную в честь изучавшего ее Леонарда Эйлера (1707-1783). Она широко используется в различных разделах математики и теоретической физики. В частности, с помощью бета-функции описываются многие свойства элементарных частиц и строится современная теория струн. Не менее знаменита гамма-функция (функция Эйлера второго рода), определяемая выражением ∞ Γ(x) = tx−1 e−t dt. 0

Эту функцию можно считать обобщением факториала, потому что Γ(x + 1) = x Γx, следовательно, для целочисленных x имеет 5

Свойства функций Эйлера см., например, в справочнике: Градштейн И. С., Рыжик И. М. Таблицы интегралов, сумм, рядов и произведений. Разд. 8.3.

20.6. Анализ проекта со случайными длительностями работ

53

место соотношение Γ(x) = (x − 1)! Между функциями B и Γ имеется простая зависимость: B(p, q) =

Γ(p)Γ(q) . Γ(p + q)

В зависимости от значений параметров p, q плотность бетараспределения выглядит по-разному (рис. 20.17), при этом p от3.5

f (t) 3

p=0.5, q=2 2.5

p=2, q=4 2

p=3, q=3

1.5 1 0.5 0 0

0.2

0.4

0.6

0.8

t

1

Рис. 20.17. Функция плотности бета-распределения при различных значениях параметров

вечает за левую часть кривой, а q — за правую. Если параметры поменять местами, кривая зеркально отобразится относительно вертикальной оси симметрии, показанной на рисунке штрихпунктирной линией. Когда p, q ∈ (0, 1), соответствующий край кривой распределения асимптотически приближается к вертикальной оси, при p, q ∈ [1, 2] кривая пересекает ось абсцисс в точках 0 и 1, при p, q ∈ (2, ∞) наблюдается гладкое сопряжение с осью абсцисс. Таким образом, при p > 1, q > 1 плотность бета-распределения представляется одногорбой кривой, скошенность которой зависит от соотношения p и q, при p < q максимум (точка максимума называется модой) распределения сдвинут влево от оси симметрии, при p > q — вправо, при p = q распределение симметрично.

54

Глава 20. Основы сетевого планирования и управления

Используя упомянутые выше свойства функций Эйлера, легко получить основные числовые характеристики нормированного бета-распределения. Мода (mode) находится приравниванием нулю производной плотности (20.5). Выполнив простейшие выкладки, получаем m[t] =

p−1 . p+q−2

Mомент r-го порядка (r-th moment) вычисляется по формуле 1 1 B(p + r, q) r . t f (t)dt = C tp+r−1 (1 − t)q−1 dt = Kr [t] = B(p, q) 0 0 Среднее значение — математическое ожидание (mean, average, expected value) — получается, если положить r = 1: M [t] = K1 [t] = =

B(p + 1, q) Γ(p + 1)Γ(q)Γ(p + q) = = B(p, q) Γ(p + q + 1)Γ(p)Γ(q) p Γ(p)Γ(q)Γ(p + q) p = . (p + q)Γ(p + q)Γ(p)Γ(q) p+q

Для дисперсии (variance, dispersion) имеем соотношение

2 p B(p + 2, q) 2 − = D[t] =K2 [t] − M [t] = B(p, q) p+q p2 p (p + 1) pq − . = = 2 2 (p + q)(p + q + 1) (p + q) (p + q) (p + q + 1) Перейдем теперь к общему случаю бета-распределения, когда случайная величина t меняется в промежутке [a, b]. Она получается из нормированной величины t линейным преобразованием t = a + (b − a)t, ее числовые характеристики пересчитываются по известным в теории вероятностей формулам, что дает m[t ] = a + (b − a)m[t] = a + (b − a)

p−1 ; p+q−2

(20.6)

20.6. Анализ проекта со случайными длительностями работ M [t ] = a + (b − a)M [t] = D[t ] = (b − a)2 D[t] =

aq + bp ; p+q

(b − a)2 p q . (p + q)2 (p + q + 1)

55 (20.7) (20.8)

Сравнивая (20.6) с (20.7), видим, что M [t ] =

a + b + (p + q − 2)m[t ] . p+q

(20.9)

Таким образом, если в качестве модельного вероятностного распределения продолжительности работ принять бетараспределение, то для каждой работы (ij), нужно экспертным путем задать ч е т ы р е числа: a, b, p, q. Параметры a и b определить относительно легко: они устанавливают нижнюю и верхнюю max границы распределения, т. е. a = tmin ij , b = tij , их можно понимать как оптимистическую (optimistic performance time) и пессимистическую (pessimistic performance time) оценки длительности работы. С параметрами p и q дело обстоит значительно сложнее. Их влияние на форму кривой распределения неочевидно, поэтому необходимы вероятностные модели, которые позволяли бы восстанавливать эти параметры, основываясь на дополнительных, осязаемых экспертом оценках длительности работ. При этом важно заметить, что точные значения самих параметров не представляют особого интереса, так как нет нужды каждый раз строить кривую распределения. Значительно важнее иметь зависящие от них и определяемые формулами (20.7) — (20.8) важнейшие числовые характеристики распределения — математическое ожидание M и дисперсию D√ (либо среднеквадратичное отклонение (standard deviation) σ = D). Существуют несколько таких моделей, все они основываются на тех или иных допущениях.

56

Глава 20. Основы сетевого планирования и управления

Исторически первая, ставшая классической, вероятностная модель PERT предлагает эксперту для каждой работы наряду с оптимистической a и пессимистической b оценками длительности работы указать третью — наиболее вероятную длительность работы (most likely performance time), соответствующую моде m бета-распределения. Поскольку на основе трех оценок четыре параметра вычислить невозможно, необходимо иметь некоторую дополнительную связь между параметрами. Авторы этой модели, детально исследовав вид распределения в зависимости от параметров и проанализировав большой фактический материал, сделали допущение о том, что д л я в с е х работ p + q ≈ 6. Тогда из (20.9) немедленно следует a + b + 4m . (20.10) M= 6 Далее, принимая p + q − 2 = 4, из (20.6) получаем Трехоценочная вероятностная модель PERT

4(m − a) , b−a

4(m − a) , b−a

  4m − 4a 4m − 4a (b − a)2 1+ 5− = D= 62 · 7 b−a b−a   4 a+b 2 (a − b)2 − m− . = 28 63 2 p=1+

q =5−

(20.11)

Замечание. Во времена, когда создавалась технология PERT, все аналитические вычисления делались вручную, карандашом на бумаге. В наше время громоздкие выкладки быстрее и, главное, без ошибок можно выполнить с помощью компьютера, воспользовавшись специализированными пакетами. В частности, в популярной системе компьютерной математики MATLAB есть инструментальное расширение Symbolic Math Toolbox. В качестве простейшего упражнения предлагаем читателю с помощью этого пакета самостоятельно проверить справедливость формулы (20.11).

20.6. Анализ проекта со случайными длительностями работ

57

Рассматривая выражение (20.11), видим, что дисперсия распределения меняется в зависимости от положения моды, принимая наибольшее значение, когда она лежит в середине промежутка [a, b], т. е. m = (a + b)/2, и наименьшее, когда на его концах:

b−a 7.09

2

≈

(b − a)2 5 (b − a)2 D ≈ 252 28

b−a 5.29

2 .

На основании этой оценки разработчики PERT сделали еще одно допущение, предложив вместо точной, но громоздкой формулы (20.11) использовать приближенную, зато совсем простую: D≈

(b − a)2 , 36

т. е. σ ≈

b−a . 6

(20.12)

Таким образом, вероятностная модель PERT позволяет по трем оценкам (оптимистической aij , пессимистической bij и наиболее вероятной mij ) определить для каждой работы по формулам (20.10) и (20.12) математическое ожидание Mij и дисперсию Dij времени ее выполнения. Несмотря на большую популярность, вероятностная модель PERT неоднократно подвергалась критике. Требование к исполнителям работ задавать три временные оценки является весьма жестким, причем особые трудности вызывает необходимость задания моды распределения, особенно в случае работ, по которым не накоплена достаточная статистика. В связи с этим были разработаны многочисленные модификации классической модели. Одной из самых простых и удачных является вероятностная модель на основе д в у х оценок [5, с. 92], предложенная в середине 1960-х гг. известным советским математиком Д.И. Голенко (Голенко — Гинзбургом, см. исторические замечания в конце главы). Она также базируется на бета-распределении, однако предполагает еще более сильное по сравнению с PERT допущение: параметры Двухоценочная вероятностная модель Д.И. Голенко

58

Глава 20. Основы сетевого планирования и управления

p и q должны быть о д и н а к о в ы м и д л я в с е х работ проекта. Проведенные автором и его коллегами многочисленные эмпирические исследования показали, что величины p и q, усредненные по большому количеству сетевых проектов, концентрируются около постоянных значений p ≈ 2, p ≈ 3. Они были приняты в качестве стандартных степенных показателей, и тем самым был построен закон распределения с плотностью, зависящей лишь от двух параметров: f (t) = C(t − a)(b − t)2 , и нормирующим множителем C=

Γ(2 + 3) 4! 1 = = = 12. B(2, 3) Γ(2)Γ(3) 1! 2!

Подставляя эти значения параметров в формулы (20.6) — (20.8), получаем выражения для числовых характеристик: m=

2a + b , 3

M=

3a + 2b , 5

D=

(b − a)2 . 25

(20.13)

Легко убедиться, что данное бета-распределение асимметрично, имеет более пологий, затянутый правый край. Как следствие, ма2 тематическое ожидание M = a + (b − a) превышает наиболее 5 1 вероятное значение m = a + (b − a), однако обе эти величины 3 располагаются ближе к a, чем к b. Таким образом, модель Голенко скорее оптимистическая, чем пессимистическая. П р и м е р. Обратимся вновь к нашему проекту строительства домика, но теперь будем считать длительности работ случайными величинами. Для того чтобы не придумывать новых чисел, и tmах означали воспользуемся данными табл. 20.4. В ней tmin ij ij о б ъ е к т и в н ы е технологические границы длительности работ, сейчас же мы будем рассматривать их как с у б ъ е к т и в н ы е о ц е н к и (оптимистические и пессимистические), т. е. мы max полагаем aij = tmin ij и bij = tij .

20.6. Анализ проекта со случайными длительностями работ

59

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

i

j

aij

bij

Mij

Dij

Чертеж

0

1

1

3

1.8

0.16

Фундамент

1

2

3

3

3.0

0

Канава Стены Сантехника Крыша

1 2 5 3

5 3 6 4

1 3 2 3

3 5 4 5

1.8 3.8 2.8 3.8

0.16 0.16 0.16 0.16

Электрика Отделка Благоустройство Сдача

4 7 8 9

7 9 9 10

2 5 2 1

3 8 2 1

2.4 6.2 2.0 1.0

0.04 0.36 0 0

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

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

Оценка параметров проекта в целом. Методика PERT

60

Глава 20. Основы сетевого планирования и управления

случайные, то раннее время Ek наступления любого k-го события, равное длине длиннейшего пути из начальной вершины в k-ю, в том числе критическое время всего проекта T = En , становятся случайными. Основным допущением классической методики PERT (о его правомерности мы будем говорить далее) является предположение о том, что случайные вариации длительности работ вокруг средних значений не меняют конфигурацию длиннейших путей, т. е. множество дуг Lk = {(i, j)}, образующих длиннейший путь из начальной вершины в выбранную k-ю, остается неизменным, случайной является только длина пути Ek =



tij .

(20.14)

(i,j)∈Lk

Алгоритм построения множества Lk для некоторой k-й вершины следующий. Этап 1 (построение «усредненного» сетевого графика). Строится обычный, детерминированный сетевой график, в котором длительности работ устанавливаются равными м а т е м а т и ч е с к и м о ж и д а н и я м Mij случайных длительностей. Этап 2 (вычисление ранних сроков и отслеживание длиннейшего пути). Стандартным алгоритмом (см. с. 16) временн´ого анализа вычисляются ранние сроки всех событий. Список дуг длиннейшего пути Lk строится обратным движением от выбранной k-й вершины к началу сети (см. замечание 3 на с. 19). После нахождения Lk менеджер проекта может ставить вопросы о вычислении основных параметров, имеющих отношение к k-му событию: • среднее ожидаемое время наступления события M [Ek ]; • дисперсия времени наступления события D[Ek ]; • вероятность наступления события в установленные сроки.

20.6. Анализ проекта со случайными длительностями работ

61

Первые два параметра легко определить, используя свойства математического ожидания и дисперсии суммы случайных величин (в предположении, что они некоррелированы):   M [tij ] = Mij , M [Ek ] = (i,j)∈Lk

D[Ek ] =



(i,j)∈Lk

D[tij ] =

(i,j)∈Lk



(20.15)

Dij ,

(i,j)∈Lk

откуда среднеквадратичное (стандартное) отклонение ожидаемого времени наступления события от среднего значения  (20.16) σ[Ek ] = D[Ek ]. Для того чтобы узнать вероятность наступления k-го события в установленные сроки, нужно знать само распределение величины Ek . Здесь на помощь приходит центральная предельная теорема: поскольку Ek , согласно (20.14), представляет собой сумму случайных величин, то при достаточном числе слагаемых ее распределение близко к нормальному со средним значением и дисперсией, определяемыми формулами (20.15). Тогда вероятность того, что время наступления k-го события Tk не превысит фиксированного значения Tфикс , равна 

Tфикс − M [Tk ] , (20.17) P (Tk < Tфикс ) = Φ σ[Tk ] где Φ(x) — специальная, не выражающаяся через элементарные функция стандартного нормального распределения6 : 1 Φ(x) = √ 2π 6

x

t2

e− 2 dt.

−∞

Таблицы Φ(x) и обратной к ней функции Ψ(x) можно найти во многих книгах по теории вероятностей и статистике, например, в прекрасном справочнике: Большев А. Н., Смирнов Н. В. Таблицы математической статистики. М.: Наука, 1965. 464 с.

Глава 20. Основы сетевого планирования и управления

62

Иногда ставится обратная задача: определить срок Tгар , в течение которого k-е событие произойдет с гарантированной вероятностью P , достаточно близкой к 1, например 0.9 или 0.95. В этом случае искомое значение рассчитывается по формуле Tгар (P ) = M [Tk ] + Ψ(P )σ[Tk ],

(20.18)

где Ψ(P ) — функция, обратная функции стандартного нормального распределения. Вот ее несколько типичных значений: Ψ(0.9) = = 1.28, Ψ(0.95) = 1.64, Ψ(0.99) = 2.32. П р и м е р. Продолжая пример на с. 58, найдем: 1) среднее ожидаемое время окончания проекта M [T ]; 2) его стандартное отклонение σ[T ]; 3) вероятность того, что строительство дома будет закончено за 20 дней, т. е. P (T < 20); 4) гарантированный срок Tгар , в течение которого дом будет построен с вероятностью 0.9. На рис. 20.18 представлен «усредненный» сетевой график проекта, в котором выделен длиннейший путь для конечной 10-й вер-

0

Чер 1.8

1 1.8

Фун 3

Сте

2 4 .8

3.8

3 8.6

Кры

4

Эл

7

3.8 12.4

2.4 14 .8

6 11 .4 2.8

12 .4

6 .2

9 21

Сда 1

10 22

2

Ка н 1. 8

Отд

Бл а

0

5 8 .6

Сан

8

Рис. 20.18. «Усредненный» сетевой график по методике PERT. Ранние сроки событий и критический путь

шины, т. е. критический путь. Как видим, несмотря на изменение продолжительностей работ, множество работ критического пути не изменилось по сравнению с простейшим случаем, который мы рассматривали в самом начале главы (см. рис. 20.7). В него входят работы Чер, Фун, Сте, Кры, Эл, Отд, Сда. Выбирая соот-

20.6. Анализ проекта со случайными длительностями работ

63

ветствующие числа из табл. 20.5, получаем следующие значения: M [T ] = M [E10 ] = 1.8 + 3 + 3.8 + 3.8 + 2.4 + 6.2 + 1 = 22, D[T ] = D[E10 ] = 0.16 + 0 + 0.16 + 0.16 + 0.04 + 0.36 + 0 = 0.88. Таким образом, среднее ожидаемое время реализации проекта со√ ставляет 22 дня со стандартным отклонением σ[T ] = 0.88 ≈ ≈ 0.94 дня. При этом вероятность завершить проект за 20 дней равна 

20 − 22 = Φ(−2.12) ≈ 0.02, P (T < 20) = Φ 0.94 а гарантированное с вероятностью 0.9 время завершения Tгар (0.9) = 22 + 1.28 · 0.94 = 23.2. Как видим, в нашем численном, совершенно искусственном примере из-за небольшого размаха случайных длительностей работ среднеквадратичное отклонение критического времени проекта получилось очень малым, менее одного рабочего дня (см. замечание на с. 59). В реальных проектах цифры могут получиться совершенно другие.  Классическая аналитическая методика PERT Критика анализа проекта со случайными длительностяметодики PERT ми работ неоднократно подвергалась критике. Лежащее в ее основе предположение о неизменности конфигурации критических путей в графе представляется слишком сильным. Легко представить ситуацию, когда анализируемая k-я вершина связана с начальной несколькими путями, почти одинаковыми по длине. Тогда случайные вариации длин ребер могут привести к появлению новых путей, более длинных по сравнению с путем в «усредненном» графе. По этой причине методика PERT дает заниженные значения средних ожидаемых моментов времени наступления событий. В частности, проведенные Д. И. Голенко

64

Глава 20. Основы сетевого планирования и управления

эксперименты [5, с. 120] показали, что гарантированное время выполнения проекта в целом, вычисленное по формуле (20.18) при различных P , на 15–20 % меньше истинной оценки, полученной с помощью метода статистического моделирования. Принципиальные недостатки меСтатистическое моделиро- тодики PERT привели к появлевание сетевых графиков нию других аналитических методов оценки параметров сетевых проектов со случайными длительностями работ [5, гл. III], однако ни одну из них нельзя признать вполне удачной. По этой причине самым надежным и простым на сегодняшний день можно считать метод статистического моделирования (метод статистических испытаний, метод Монте-Карло7 ). Идея метода статистических испытаний состоит в имитации продолжительностей всех входящих в сеть работ в соответствии с выбранной вероятностной моделью с последующим расчетом интересующих параметров для теперь уже детерминированной сети. Такой «розыгрыш» многократно повторяется, накапливается выборка, строятся эмпирические распределения и статистические оценки. Современные компьютеры позволяют без особых проблем проводить численные эксперименты с сетями большой размерности и получать оценки параметров сетевых проектов с достаточной надежностью. В качестве рабочей среды такого моделирования удобно использовать пакет MATLAB, в котором можно найти полный набор инструментов для построения и анализа случайных сетевых графиков. Имитация случайных длительностей производится встроенными генераторами случайных чисел с разнообразными законами распределения, для статистической обработки результатов также имеются подходящие процедуры.

7

Краткую историю вычислительных методов, использующих случайные числа, см. в [4, ч. II, с. 151] .

20.6. Анализ проекта со случайными длительностями работ

65

П р и м е р 1. Для проверки адекватности методики PERT в примере на с. 62 проводилось статистическое моделирование нашего сетевого графика. Длительности работ считались подчиняющимися бета-распределению с параметрами p = 2, q = 3 (в системе MATLAB есть соответствующий генератор случайных чисел) и границами длительности aij , bij , взятыми из табл. 20.5. Для каждой реализации сгенерированной таким образом случайной сети матричным алгоритмом (см. замечание на с. 21), рассчитывалась длина критического пути. Статистические оценки рассчитывались по обычной методике:  ˆ [T ] = M Tk /N ;  ˆ [T ])2 /(N − 1); ˆ ]= D[T (Tk − M Pˆ (T < Tфикс ) = N [T < Tфикс ]/N. Всего было проведено N = 10 000 экспериментов, которые дали следующие усредненные результаты (табл. 20.6): Таблица 20.6. Экспериментальная проверка адекватности методики PERT для примера 1 Параметр M [T ] σ[T ] P (T < 20) P (T < 23.2)

Теоретическое значение 22 0.94 0.02 0.9

Экспериментальная оценка 21.99 0.932 0.011 0.895

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

66

Глава 20. Основы сетевого планирования и управления

П р и м е р 2. Возьмем простейший вариант сетевого графика с 6 вершинами и 8 работами случайной длительности (см. рис. 20.19). В качестве модельного опять выберем бетараспределение в двухоценочной модификации Голенко, что приводит к формулам (20.13) для вычисления математического ожидания и дисперсии длительности отдельных работ. i 1 1 2 2 3 3 4 5

j 2 3 4 5 4 5 6 6

aij 2 4 3 4 5 4 2 2

2

4.8

5.6

d

1 0

4 .4

Mij 4.4 4.8 4.6 5.6 6.6 5.6 3.2 4.0

g

11.4

3.2

b

h 3 4.8

Dij 1.44 0.16 0.64 0.64 0.64 0.64 0.36 1.00

4

c 4.6

4.4

6. 6

a

bij 8 6 7 8 9 8 5 7

e

Работа a b c d e f g h

f 5.6

5

6 14.6

4.0

10.4

Рис. 20.19. Пример проекта с вероятными альтернативными критическими путями. Параметры распределений длительностей работ и усредненный сетевой график

Построив усредненный сетевой график, видим, что критический путь составляют работы b, e, g. Таким образом, средняя ожидаемая длительность проекта по методике PERT составляет M [T ] = 4.8+6.6+3.2 = 14.6, а дисперсия ожидаемой длительности √ равна D[T ] = 0.16 + 0.64 + 0.36 = 1.16. Отсюда σ[T ] = D = 1.08.

20.6. Анализ проекта со случайными длительностями работ

67

На основе полученных расчетных значений определим теоретическую вероятность выполнения проекта за время Tфикс = 14. Используя формулу (20.17), имеем 



Tфикс − M [T ] 14 − 15.46 P (T < Tфикс ) = Φ =Φ = σ[T ] 1.08 = Φ(−1.35) = 1 − Φ(1.35) = 1 − 0.91 = 0.09. Статистическое моделирование с 10000 случайными реализациями сетевого графика дало в результате статистику, приведенную в табл. 20.7. Таблица 20.7. Экспериментальная проверка адекватности методики PERT для примера 2 Параметр M [T ] σ[T ] P (T < 15)

Теоретическое значение 14.6 1.08 0.09

Экспериментальная оценка 15.46 1.06 0.355

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

68

Глава 20. Основы сетевого планирования и управления

20.7. Исторические замечания Научная организация труда возникла в конце XIX – начале XX века в США. Ее достижения, помогавшие этой стране выйти в лидеры научно-технического прогресса, связаны в первую очередь с именами американского инженера и предпринимателя Фредерика Тейлора и его ученика Генри Ганта. «Отец научного менеджмента» Фредерик Тейлор (Taylor, Frederick Winslow; 1856–1915) родился в г. Филадельфии в известной и состоятельной семье. Получил разностороннюю фундаментальную подготовку по математическим, инженерным и гуманитарным наукам в учебных заведениях Европы и США. Несмотря на высокий социальный статус, Тейлор начал трудовую биографию простым рабочим, выдвинулся в мастера, затем в главные инженеры, стал совладельцем нескольких крупных компаний. Под конец жизни стал миллионером, известным всему миру исследователем и консультантом, преподавателем в лучших американских университетах и школах бизнеса.

Фредерик Тейлор

Генри Гант

Творческое наследие Тейлора многогранно, свои взгляды он изложил в книгах «Управление предприятием» (1903) и «Принципы научного управления» (1911). ∗ ∗ ∗ Ближайший ученик и последователь Тейлора Генри Гант (Gantt, Henry Laurence; 1861–1919) родился в семье плантатора,

20.7. Исторические замечания

69

разорившейся во время Гражданской войны 1861–1865 гг. В 1878 г. окончил Технологический институт Стивенса (Stevens Institute of Technology) в Нью-Джерси, некоторое время работал преподавателем и чертежником, затем судьба свела его с Фредериком Тейлором, в 1887 г. они попробовали применить научный подход к управлению крупными сталелитейными предприятиями. С 1890-х гг. Гант профессионально занялся консультационной деятельностью, вскоре были изобретены прославившие его диаграммы, они широко использовались при постройке военных кораблей в годы Первой мировой войны. Гант опубликовал более 150 научных трудов, включая три книги: «Труд, заработная плата и доход» (1910), «Промышленное руководство» (1916), «Организация труда» (1919), запатентовал больше десятка изобретений, читал лекции в университетах, оставаясь одним из наиболее успешных консультантов по управлению, диаграммы Ганта активно используются и по сей день. ∗ ∗ ∗ Электронные вычислительные машины, созданные в США сразу после окончания Второй мировой войны, дали мощный толчок развитию научных исследований, ориентированных на экономику и управление. Поэтому хоть и удивительным, но исторически закономерным является тот факт, что математические методы сетевого планирования совершенно независимо и практически одновременно появились в двух проектах, существенно различающихся по идеологии и масштабу. Первый проект зародился в недрах гигантской химической корпорации «Du Pont de Nemours». В 1954 г. компания приобрела один из первых экземпляров ЭВМ UNIVAC стоимостью более миллиона долларов (см. рис. 20.20) и решила использовать ее для целей планирования ремонтных и строительных работ, в которых время и последовательность операций строго регламентированы технологическими инструкциями. Рабочую группу возглавил Морган Уолкер (Walker, Morgan R.), который обратился за помощью к про-

70

Глава 20. Основы сетевого планирования и управления

изводителю машины8 . Идеолог компьютера и глава «UNIVAC Division» Джон Моучли пригласил своего ведущего математика Джима Келли и поручил ему «решить эту задачу для Уолкера». Так началось плодотворное сотрудничество двух компаний, приведшее к появлению метода критического пути (Critical Path Method — CPM) 9 . Джеймс (Джим) Келли, младший (Kelley, James Edward, Jr.; Рис. 20.20. ЭВМ UNIVAC 1929–2008) родился в г. Нью-Хейвен, штат Коннектикут, учился в колледже г. Провиденс — столице соседнего, самого маленького американского штата Род-Айленд, получил магистерскую степень по математике в American University, округ Колумбия. Прослушав курс программирования в «Eckert — Mauchly Corp.», он в конце концов остался там работать в математическом отделе под руководством Джона Моучли. В мае 1957 г. было заключено официальное соглашение между «Du Pont» и «Remingtin Rand UNIVAC», уже к осени были выполнены первые расчеты на ЭВМ. Важно подчеркнуть, что с самого начала предполагалась реализация алгоритма Келли для задачи об оптимизации стоимости проекта, которую мы рассмат8

Первая серийная ЭВМ UNIVAC была сконструирована Моучли (Mouchly, John Willam; 1907–1980) и Эккертом (Eckert, John Presper; 1919–1995) на базе созданной в 1945 г. первой ЭВМ ENIAC. Для ее производства они в 1946 г. организовали в Филадельфии «Eckert — Mauchly Computer Corporation», которая в 1950 г. вошла в состав компании «Remingtоn Rand» на правах «Remingtin Rand UNIVAC Division». 9 Сам термин «критический путь» появился не здесь, а в проекте PERT. Келли и Уолкер использовали словосочетание «главная цепь».

20.7. Исторические замечания

71

ривали в параграфе 20.5. . На рис. 20.21 приведена историческая фотография построенной на ЭВМ кусочно-линейной зависимости прямых затрат от длительности проекта, полученной в одном из тестовых расчетов в сентябре 1957 г.

Рис. 20.21. Зависимость прямых затрат от длительности проекта, рассчитанная 25 сентября 1957 г.

Первое испытание метода CPM в реальных условиях было проведено в процессе планового ремонта химического завода в г. Луисвилле, штат Кентукки. В результате вместо обычных 125 ч производство простаивало 93 ч, сэкономив компании немалые деньги. В 1959 г. результаты работы были опубликованы и стали достоянием научной общественности10 . Как часто случается с революционными технологиями, корпорация «Du Pont», так же как и «Remington Rand», не увидела перспектив в коммерциализации полученных результатов. Эту миссию взяла на себя образованная в 1959 г. компания «Mauchly & Associates», куда из «Du Pont» перешел работать Уолкер, а Келли 10

Kelley J., Walker M. Critical-Path Planning and Scheduling // Proceedings of the Eastern Joint Computer Conference. Boston, Massachussets, December 1-3, 1959. P. 160–173.

72

Глава 20. Основы сетевого планирования и управления

занял пост вице-президента по математике. Алгоритм и программа CPM были доведены до коммерческого состояния (стоимость вычислений была сравнима с ценой небольшого автомобиля), организованы обучение и техническая поддержка. Таким образом, программа расчета сетевых графиков по методу CPM стала одной из первых успешных прикладных программ на рынке программного обеспечения. Впоследствии Келли организовал собственную консалтинговую компанию, в 1980-е годы написал несколько популярных учебников по персональным компьютерам. Отойдя от дел, увлекся историей математики и звездной навигации, издал книгу о путешествии Колумба в Америку. ∗ ∗ ∗ Второй проект можно считать непосредственным детищем «холодной войны». В 1956 г. в США развернулась программа создания ракетной системы Polaris с базированием на атомных подводных лодках. Предстояло за короткое время (первую ракету предполагалось запустить в 1963 г.) выполнить более 60 000 исследовательских, конструкторских и испытательных работ. Кроме генерального подрядчика — компании «Lockheed» — в программе участвовали тысячи соисполнителей. Общее руководство программой осуществляло Бюро специальных проектов ВМС США (US Navy Special Project Office), руководимое будущим директором ЦРУ адмиралом Вильямом Раборном (Raborn, William Francis; 1905–1990). Проанализировав ситуацию, адмирал принял решение подключить к программе консультационную фирму «Booz Allen Hamilton»11 , имевшую богатый опыт управления крупномасштабными проектами. Была создана междисциплинарная рабочая группа по исследованию операций под руководством статистика Вилларда Фазара (Fazar, Willard; 1915–1997), которая начала разрабатывать научно обоснованную систему управ11

«Booz Allen Hamilton» — одна из старейших (основана в 1914 г.) и наиболее престижных консультационных компаний в мире. Число сотрудников в 2012 г. превышало 26000, годовой доход более 5 млрд долл.

20.7. Исторические замечания

73

ления проектом, получившую название Техника оценки и обзора программ (Program Evaluation and Review Technique — PERT). Основные концепции PERT оказались удивительно похожими на технологию CPM альянса «Du Pont» — «Remington Rand»: сетевой график на языке событий, критический путь (сам этот термин впервые появился в PERT). Фундаментальное отличие состояло в том, что PERT была изначально ориентирована не на рутинные производственные процессы, в которых продолжительности работ известны заранее, а на опытно-конструкторские проекты, допускающие лишь вероятностные оценки длительностей. К октябрю 1957 г. основные процедуры PERT были реализованы в виде компьютерных программ, в 1959 г. появилась первая открытая публикация12 . Успешное испытание ракеты Polaris произошло 20 июля 1959 г. (рис. 20.22), за три года до намеченного срока, существенная доля выигрыша во времени по праву принадлежала системе PERT.

Рис. 20.22. Президент США Джон Кеннеди наблюдает запуск ракеты Polaris

Инновационную технологию управления проектами ожидал оглушительный успех. Уже к 1964 г. библиография по CPM- и 12

Malcolm D.G., Roseboom J.H., Clark C.E., Fazar W. Application of a Technique for Research and Development Programm Evaluation // Operations Research, 1959. V. 7. P. 646–669.

74

Глава 20. Основы сетевого планирования и управления

PERT-подобным системам насчитывала более 1000 книг и статей. Технологию CPM/PERT в дальнейшем использовали все крупномасштабные программы, в том числе грандиозный проект полета человека на Луну, выполнявшийся в 1960-х гг. и увенчавшийся высадкой экипажа Apollo-11 на поверхность Луны 20 июля 1969 г. ∗ ∗ ∗ Для обобщения и распространения передового опыта управления проектами в 1969 г. в США на правах некоммерческой профессиональной организации был учрежден Институт управления проектами (Project Management Institute — PMI). Число индивидуальных членов PMI на начало 2013 г. составило более 340 тыс., отделения PMI имеются во многих странах, в том числе в России. Основными задачами института являются разработка профессиональных стандартов и сертификация специалистов. Стандарты PMI публикуются в виде свободно распространяемого и регулярно обновляемого Свода знаний по управлению проектами (Project Management Body of Knowledge — PMBOK), рис. 20.23. Первое издание вышло в 1987 г., книга доступна для скачивания с официального сайта института www.pmi.org. На базе модели PMBOK Международная организация по стандартизации (International Organization for Standardization — ISO) приняла станРис. 20.23. PMBOK дарт ISO-21500:2012, являющийся основой для разработки национальных стандартов проектного менеджмента. ∗ ∗ ∗ Отечественная история управления проектами начинается с 1960-х гг., когда на русский язык были переведены первые аме-

20.7. Исторические замечания

75

риканские публикации по сетевому планированию. Вскоре появились статьи отечественных ученых — математиков и экономистов, а в 1965 г. вышла в свет монография С.И. Зуховицкого и И.А. Радчик [8], которая до настоящего времени является одной из лучших по данному предмету. В середине 1960-х годов общественный интерес к проблеме был стимулирован важными политическими событиями. После отставки Н.С. Хрущева в октябре 1964 г. в Советском Союзе началась реформа планирования и управления народным хозяйством, которая по имени председателя Совета Министров СССP А. Н. Косыгина известна как Косыгинская реформа. Одним из ее направлений являлось внедрение научных методов управления на основе широкого использования вычислительной техники и экономикоматематических моделей. В августе 1966 г. вышло постановление Совета Министров СССР «О мерах по внедрению в народное хозяйство системы сетевого планирования и управления (СПУ) на основе комплексных сетевых графиков». Этим постановлением во многих научно-исследовательских и производственных организациях, прежде всего строительных, создавались специальные подразделения, занимающиеся разработкой и внедрением методов СПУ. Изучение основ сетевых методов управления стало обязательным во всех технических вузах. В ряде академических и отраслевых НИИ началась разработка оригинальных математических моделей и методов, развивающих классические подходы CPM/PERT. В частности в Институте экономики Сибирского отделения АН СССР были созданы алгоритмы и программы оптимального распределения ресурсов, более совершенные, чем простейшее выравнивание (leveling). ∗ ∗ ∗ Чрезвычайно большой вклад в теорию сетевого планирования со случайными факторами внесла научная школа, созданная Дмитрием Исааковичем Голенко-Гинзбургом (р. 1932). Он родился в Москве, в 1958 г. получил степень кандидата наук по математике в МГУ, в 1962 г. — степень доктора наук по

76

Глава 20. Основы сетевого планирования и управления

прикладной математике в Московском физико-техническом институте. В течение многих лет преподавал в ведущих высших учебных заведениях бывшего СССР. Опубликованная им в 1968 г. монография [5] являлась первым комплексным исследованием статистических методов сетевого планирования и не потеряла актуальности до настоящего времени. Предложенная в ней оригинальная двухоценочная модель бетаД.И. Голенко-Гинзбург распределения длительности работ основывалась не только на теоретических рассуждениях, но и на опыте практической работе в реальных проектах, накопленном, в частности, при взаимодействии с одним из самых передовых в СССР предприятий — Рижским (Латвия) электротехническим заводом ВЭФ, к сожалению, теперь разрушенным и заброшенным. После падения «железного занавеса» Голенко-Гинзбург в 1985 г. эмигрировал в Израиль, с тех пор его фамилия стала двойной. Он продолжает активную преподавательскую и научную работу, является автором 20 книг и более 500 статей в ведущих научных журналах по проблемам стохастического моделирования и планирования. Научный руководитель более 50 кандидатских и докторских диссертационных работ в России и Израиле. ∗ ∗ ∗ Несмотря на отдельные достижения, общий тренд отечественных работ в управлении проектами в последние десятилетия существования СССР постепенно стал расходиться с общемировым. Это было вызвано фактической изоляцией советских ученых от международных изданий, конференций и профессиональных сообществ. Отечественные исследования концентрировались в основном вокруг математических и технических вопросов, в то время как мировой тенденцией стал комплексный подход: сетевое планирование рассматривалось как одна из составных частей

20.7. Исторические замечания

77

пректного менеджмента, охватывающего все стороны, всех участников и все стадии проекта. После распада СССР и вхождения России в мировое информационное и экономическое пространство для отечественных специалистов открылся профессиональный «мир управления проектами». Вместе с США и странами Евросоюза Россия ввела в действие стандарт ISO-21500 и приступила к разработке серии национальных стандартов по управлению проектами13 , активно действует национальная Ассоциация управления проектами СОВНЕТ (http://www.sovnet.ru), издается специализированный журнал «Управление проектами» (http://www.pmmagazine.ru).

13

Первая группа таких стандартов была принята в 2011 г. Она включает в себя: ГОСТ Р 54869-2011 «Проектный менеджмент. Требования к управлению проектом»; ГОСТ Р 54870-2011 «Проектный менеджмент. Требования к управлению портфелем проектов»; ГОСТ Р 54870-2011 «Проектный менеджмент. Требования к управлению программой».

Глава 21 Элементы теории массового обслуживания Если попытаться перевести название этой главы на английский язык с помощью обычного словаря, ничего не получится. В специальной литературе принят термин Queueing Theory1 (Теория очередей), значительно реже используется словосочетание Waiting Theory (Теория ожидания). Однако русскоязычный термин более точен, потому что теория изучает не только процессы ожидания в очереди, но и другие явления, возникающие в специфических операциях массового обслуживания. Такая оригинальность терминологии не случайна, она объясняется тем, что вклад отечественных ученых в теорию массового обслуживания, особенно на первых этапах ее становления, был исключительно большим (см. исторические замечания в конце главы), как следствие, русская терминология развивалась совершенно независимо от иноязычной. Возникшая в начале XX века в связи с проблемами эффективной работы телефонных станций, теория массового обслуживания превратилась в мощный инструмент анализа и оптимизации са1

Слово queue [kju:] — очередь заимствовано из французского языка (от лат. cauda — хвост). В бытовом американском языке, в отличие от британского, чаще используется слово line.

21.1. Предмет теории массового обслуживания

79

мых различных технических и организационных систем — от компьютерных сетей до супермаркетов. В настоящей главе мы дадим самое элементарное введение в предмет, ограничившись рассмотрением простейших моделей. Полагаем, что для первоначального знакомства этого достаточно, а тем, кто заинтересован в углубленном изучении теории, можно порекомендовать литературу более высокого уровня, например [11].

21.1. Предмет теории массового обслуживания Теория массового обслуживания изучает широкий класс систем массового обслуживания — СМО, в которых поток некоторых объектов обрабатывается обслуживающими устройствами. Типичные примеры операций обслуживания: — — — — — —

обслуживание обслуживание обслуживание обслуживание обслуживание обслуживание

потока потока потока потока потока потока

вызовов телефонной станцией, посетителей в парикмахерской, автомобилей перекрестком, прерываний процессором, пакетов маршрутизатором, целей системой ПВО и т. д.

Из-за случайного, непредсказуемого наплыва объектов в системе могут возникать различные проблемные ситуации, в том числе: — образование недопустимо больших очередей; — отказы в обслуживании из-за нехватки обслуживающих приборов. Задача теории массового обслуживания состоит в предсказании возможности таких ситуаций и поиске путей их преодоления.

80

Глава 21. Элементы теории массового обслуживания

В самом общем случае система массового обслуживания (queueing system)2 может быть представлена моделью, состоящей из следующих основных элементов (рис. 21.1): Общая модель СМО

Накопитель

Прибор 1 Прибор 2

Источник повторных вызовов Входящий поток

Прибор n

Блок обслуживания

Выходящий поток

Рис. 21.1. Общая модель системы массового обслуживания

— входящий поток (input flow, incoming flow, incoming stream, arrival flow etc.) объектов, называемых разными авторами поразному: вызовами (calls), заявками, запросами (requests, queries), требованиями (claims), транзактами (transactions), клиентами (customers) и т. п.; — блок обслуживания (service facility), состоящий из одного или нескольких обслуживающих приборов (servers). В другой терминологии приборы называются каналами (channels) или линиями (lines); — накопитель (storage) или бункер, в котором размещается очередь (queue) заявок, ожидающих обслуживания. Накопитель может отсутствовать (система без ожидания), тогда заявка, пришедшая в момент, когда все приборы заняты, получает отказ в обслуживании (теряется); — источник повторных вызовов (Repeat Query или Repeat reQuest — RQ), который может заменить накопитель в системе 2

В специальной литературе иногда вместо queueing system употребляют queue system или просто queue.

21.1. Предмет теории массового обслуживания

81

без ожидания. При отказе в обслуживании заявка не теряется, а запоминается специальным устройством, который через некоторое, обычно случайное, время автоматически повторяет ее до тех пор, пока не состоится обслуживание; — выходящий поток (outgoing flow, output) объектов. Общая модель допускает множество вариаций, Классификация отражающих реальное разнообразие процессов моделей СМО обслуживания. В связи с этим модели массового обслуживания могут быть классифицированы по разным основаниям. По входному потоку: — с детерминированным потоком (deterministic input). Предполагается, что источник генерирует заявки через известные, в частности, равные, интервалы времени. Таким, например, является поток поездов в идеально работающей железнодорожной компании; — со случайным потоком (random input). Если время поступления отдельных заявок заранее предсказать невозможно, используется модель случайного потока с теми или иными вероятностными характеристиками. По количеству приборов: — однолинейная, одноканальная (one-line, one-channel) система; — многолинейная, многоканальная (multi-line, multi-channel) система. По возможности ожидания: — системы с потерями (loss systems), когда накопитель отсутствует, при занятости всех приборов происходит отказ в обслуживании (denial of service); — системы с ожиданием (waiting systems), когда в накопителе образуется очередь заявок, ждущих обслуживания. Число мест

82

Глава 21. Элементы теории массового обслуживания

для ожидания может быть либо конечным (парковочные места на стоянке, объем буфера в памяти маршрутизатора), либо потенциально бесконечным. При ограниченном объеме накопителя, если все места для ожидания заняты, происходят отказы в обслуживании; — системы с автоматическими повторными вызовами (RQ-системы), занимающие некоторое промежуточное положение3 . По дисциплине очереди: — заявки обслуживаются в порядке поступления (First-InFirst-Out — FIFO); — заявки обслуживаются в обратном порядке (Last-In-FirstOut — LIFO); — заявки обслуживаются с учетом приоритетов (priorities); — полнодоступная или неполнодоступная (full or limited available) очередь. В полнодоступном случае (общая очередь) очередной клиент может быть обслужен любым освободившимся прибором, в неполнодоступном прибор обслуживает только «своих» клиентов. По дисциплине ожидания: — с терпеливыми клиентами (готовыми ждать до бесконечности); — с нетерпеливыми клиентами (impatient customers): с ограниченным временем ожидания либо покидающими очередь с вероятностью, возрастающей по мере ожидания. По времени обслуживания: — детерминированное время обслуживания (deterministic service time); — случайное время обслуживание (random service time) с тем 3

Системы с автоматическими повторными вызовами широко используются в беспроводных коммуникационных системах (Wi-Fi и им подобных).

21.1. Предмет теории массового обслуживания

83

или иным законом распределения, например экспоненциальным или равномерным. По виду обслуживания: — однофазная модель. Предполагается, что заявка обслуживается единственным прибором с начала до конца; — многофазная модель. Выполнив первую фазу, прибор передает заявку другому, который выполняет вторую фазу, и т. д.; — сети обслуживания (queueing networks), обобщающие многофазную модель. Траектория обслуживания может зависеть от вида заявки, приоритетов, складывающейся ситуации. Типичный пример — сеть пакетной коммутации, лежащая в основе интернета. По общему количеству заявок: — открытая система, когда число клиентов в системе не ограничено. Пример — общедоступная станция технического обслуживания, куда автомобили приходят из потенциально бесконечного внешнего мира; — замкнутая система, в которой общее число клиентов во входном и выходном потоке постоянно. Тот же пример с техническим обслуживанием автомобилей, но в масштабах небольшой транспортной компании. Отремонтированный автомобиль не покидает систему, а перемещается из выходного потока во входной. Уже это, далеко не полное, перечисление показывает, сколь разнообразными могут быть модели массового обслуживания, библиография по этому предмету насчитывает многие тысячи наименований. Согласно общим принципам исследования операций, перед исследователем, изучающим систему массового обслуживания, могут быть поставлены задачи двух типов. Основные задачи теории

84

Глава 21. Элементы теории массового обслуживания

Анализ. Задана конкретная система, требуется оценить эффективность ее функционирования. В зависимости от обстоятельств она может измеряться различными критериями (операционными характеристиками), например: — временем ожидания либо длиной очереди (для систем с ожиданием); — вероятностью отказа в обслуживании (для систем с отказами); — пропускной способностью системы; — доходом от предоставления сервиса и т. д. Оптимизация. Требуется подобрать такие значения управляемых параметров, при которых эффективность системы с точки зрения выбранного критерия была бы наилучшей, или хотя бы приемлемой. Практических примеров можно привести очень много: подбор параметров протоколов в сетях пакетной коммутации, оптимизация обслуживания клиентов в крупных магазинах, улучшение системы управления лифтами в небоскребах и т. п. В наиболее сложных случаях речь может идти не только о выборе параметров, но и о совершенствовании структуры самой системы, например оптимизации топологии сети обслуживания. В связи с большим разнообразием моделей массового обслуживания понадобилась система условных обозначений, позволяющая легко узнать, о каком классе систем идет речь. Такая система, состоящая из трех символов, была предложена в 1953 г. английским математиком Кендаллом (Kendall, David George; 1918–2007), впоследствии она была дополнена еще несколькими символами. Краткое обозначение Кендалла имеет следующий синтаксис: Обозначения Кендалла

A/B/n, где A характеризует входящий поток; B — время обслуживания; n определяет число обслуживающих приборов (каналов, линий),

21.1. Предмет теории массового обслуживания

85

при этом в позициях A и B могут стоять, в частности, такие символы: D (Deterministic) — детерминированный, т. е. регулярный входной поток (если в позиции A) либо постоянное время обслуживания (если в позиции B ); M (Markovian) — соответственно пуассоновский входной поток либо экспоненциальное время обслуживания; G (General ) — произвольный входной поток либо произвольное время обслуживания. Расширенное обозначение может содержать дополнительно к предыдущим еще от одного до трех символов: m/N/D, где m — число мест в накопителе. Если все места звняты, то последующие приходящие заявки теряются. Когда символ опущен, то предполагается m = ∞, т. е. имеется в виду система с потенциально бесконечной очередью; N — общее число заявок (клиентов) в системе. Когда этот символ опущен или равен ∞, то система предполагается открытой, в противном случае замкнутой; D — дисциплина очереди. Могут использоваться знакомые нам обозначения FIFO, LIFO, а также некоторые другие. П р и м е р. Приведем расшифровку обозначений нескольких моделей, некоторые мы подробно рассмотрим в дальнейшем. M/M/1 = M/M/1/∞ — простейшая однолинейная (одноканальная) модель с пуассоновским входящим потоком, экспоненциальным временем обслуживания и бесконечным числом мест для ожидания. M/M/n = M/M/n/∞ — многолинейная (многоканальная) модель с теми же характеристиками входного потока, времени обслуживания и очереди. M/M/n/0 — многолинейная (многоканальная) модель с пуассоновским входящим потоком и экспоненциальным временем обслуживания. Накопитель отсутствует, т. е. данная система допускает потери заявок.

86

Глава 21. Элементы теории массового обслуживания

M/G/n/0 — аналогичная система, но время обслуживания предполагается произвольным. 

21.2. Описание и основные свойства случайных потоков В соответствии с методологией операционного исследования [4, ч. I, с. 18] построение математической модели любой операции начинается с выделения с у щ е с т в е н н ы х с точки зрения цели операции элементов, свойств, отношений и отбрасывания несущественных. В реальности каждая приходящая в систему массового обслуживания заявка индивидуальна, кроме времени поступления она имеет множество дополнительных характеристик. Например, клиент, заходящий в парикмахерскую, имеет с точки зрения мастера ряд отличительных признаков: возраст, пол, длину и цвет волос и т. д. Однако с т о ч к и з р е н и я т е о р и и м а с с о в о г о о б с л у ж и в а н и я все характеристики клиента, кроме времени прихода, являются несущественными и могут быть отброшены. Таким образом, математической моделью потока реальных объектов является поток однородных событий на временн´ой оси (точечный поток), при этом, разумеется, нас будут интересовать нерегулярные, случайные потоки. Рассмотрим временную ось и выделим на ней промежуток длины t, начинающийся в момент времени t0 (рис. 21.2). Для случайного потока конкретное расположение событий является непредсказуемым, и мы можем говорить лишь о вероятности того, что в данном промежутке окажется ровно k событий. Обозначив эту вероятность через pk (t0 , t), видим, что для описания произвольного случайного потока необходимо задать функцию т р е х аргументов k, t0 , t. В общем случае это сделать очень сложно, поэтому интересно рассмотреть такие свойства потоков, которые, с одной стороны, наблюдались бы в жизни, а с другой — облегчали бы их математическое описание.

Как описать случайный поток

21.2. Описание и основные свойства случайных потоков

87

Рис. 21.2. Поток случайных событий

Если поток не меняет свои статистические свойства на протяжении времени, то он называется стационарным (homogeneous, stationary). Формально это означает, что вероятность получить k событий на некотором промежутке не зависит от начальной точки, а определяется только длиной промежутка: pk (t0 , t) = pk (t). В дальнейшем мы будем иметь дело только со стационарными потоками и для их описания пользоваться функцией pk (t) д в у х аргументов. Стационарность

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

Ординарность (ordinary) на бытовом уровне означает, что события в потоке происходят поодиночке, а не группами. Например, поток вызовов на телефонную станцию можно считать ординарным, а поток посетителей в театр — едва ли. Для строгого определения ординарности сделаем длину промежутка бесконечно малой (t = Δt) и посмотрим, как при этом ведет себя вероятность pk (Δt). Разумеется, в случайном Ординарность

88

Глава 21. Элементы теории массового обслуживания

потоке вероятность поймать события на промежутке убывает при его сокращении, т. е. при любом k > 0 pk (Δt) −−−−→ 0, весь воΔt→0

прос в том, какова с к о р о с т ь убывания этой величины. Если при Δt → 0 вероятность прихода группы (k  2) убывает быстpk (Δt) → 0, иными словами, рее, чем длина промежутка, т. е. Δt pk (Δt) = 0, то поток называется ординарным. Пользуясь lim Δt→0 Δt понятием бесконечной малости более высокого порядка, условие ординарности можно записать в виде ∀k  2 pk (Δt) ∼ o(Δt). Последнее полезное свойство потока, которое мы рассмотрим, — отсутствие последействия. Оно проявляется в том, что вероятность наступления событий в будущем на зависит от предыстории, т. е. случайный процесс совершенно не имеет памяти (memorylessness). Это свойство довольно сильное и выполняется далеко не всегда. Например, вероятность прихода автобуса определенного маршрута сильно зависит от того, когда прошел предыдущий. Однако эта зависимость сильно слабеет, если нас устраивает автобус л ю б о г о маршрута, идущий через данную остановку (если маршрутов достаточно много). Точно так же ведет себя поток вызовов на телефонную станцию от большого числа абонентов. Отсутствие последействия

Важнейшей характеристикой случайного потока является его интенсивность (rate), которая определяется как с р е д н е е число событий, приходящихся на единицу времени. Для нестационарного потока можно говорить о мгновенной интенсивности Интенсивность потока

λ(t0 ) = lim

Δt→0

m(t0 , Δt) , Δt

где m(t0 , Δt) — математическое ожидание числа событий на промежутке [t0 , t0 + Δt]. Для стационарного потока зависимость от начальной точки промежутка пропадает: m(t0 , Δt) = m(Δt), в ре-

21.3. Простейший (пуассоновский) поток

89

зультате чего мгновенная интенсивность постоянна: λ(t0 ) = λ. Если поток стационарный и ординарный, математическое ожидание числа событий равно m(Δt) =

∞ 

kpk (Δt) = 0 · p0 (Δt) + 1 · p1 (Δt) +

k=0

∞ 

kpk (Δt).

k=2

Деля на Δt, переходя к пределу Δt → 0 и применяя свойство ординарности потока4 , получаем ∞

p1 (Δt)  pk (Δt) + = p1 (0). k lim λ = lim Δt→0 Δt→0 Δt Δt k=2

Отсюда получаем вероятность появления р о в н о одного события на бесконечно малом промежутке (имея в виду, что вероятность попадания события в промежуток н у л е в о й длины, т. е. в точку, в точности равна нулю): p1 (Δt) = p1 (0) + p1 (0)Δt + o(Δt) = λΔt + o(Δt). Вспоминая, что  при k  2 pk (Δt) ∼ o(Δt) и учитывая условие нормировки pk (Δt) = 1, для стационарного ординарного потока получаем соотношения, которые нам пригодятся в дальнейшем: p0 (Δt) = 1 − λΔt + o(Δt), p1 (Δt) = λΔt + o(Δt), pk (Δt) = o(Δt),

(21.1)

k  2.

21.3. Простейший (пуассоновский) поток Если поток обладает сразу всеми тремя основными свойствами: стационарностью, ординарностью и отсутствием после4

В этом месте скрыта некоторая нестрогость, поскольку суммируется бесконечное число бесконечно малых величин.

Глава 21. Элементы теории массового обслуживания

90

действия, то он называется простейшим или пуассоновским5 (Poisson flow). Оказывается, этих, и только этих, свойств достаточно для того, чтобы получить полное описание потока. Для нахождения множества ф у н к ц и й pk (t), k = 0, 1, 2, . . . , описывающих поток, требуется составить и решить соответствующую бесконечную систему д и ф ф е р е н ц и а л ь н ы х уравнений. Для того чтобы записать эти уравнения, исходя только из свойств простейшего потока, выберем в любом месте временной оси (свойство стационарности!) промежуток t с примыкающим к нему бесконечно малым промежуточком Δt (рис. 21.3). Исходные уравнения

Рис. 21.3. К выводу уравнений для простейшего потока

Начнем с k = 0. Величина p0 (t+Δt) есть вероятность того, что на объединенном промежутке не произойдет ни одного события. В силу статистической независимости (свойство отсутствия последействия!) вероятность сложного события равна произведению вероятностей составляющих событий: p0 (t + Δt) = p0 (t) · p0 (Δt). Подставляя сюда p0 (Δt) из (21.1), где мы предполагали выполнение свойства ординарности, получаем p0 (t + Δt) = p0 (t)[1 − λΔt + o(Δt)] = p0 (t) − λp0 (t)Δt + p0 (t)o(Δt). 5

Часто в определение пуассоновского потока не включают требование стационарности, однако мы договорились в нашем элементарном изложении рассматривать только стационарные потоки, поэтому термины «простейший» и «пуассоновский» будем рассматривать как синонимы. Само название простейший было предложено А. Я. Хинчиным (см. исторические замечания в конце главы), оно используется только в русскоязычной литературе.

21.3. Простейший (пуассоновский) поток

91

Отсюда o(Δt) p0 (t + Δt) − p0 (t) = −λp0 (t) + p0 (t) . Δt Δt Переходя к пределу при Δt → 0, получаем нулевое уравнение: p0 (t) = −λp0 (t). Перейдем к k  1. Появление на объединенном промежутке длины t + Δt такого числа событий может произойти по нескольким вариантам: — на основном промежутке t произошло k − 1 событие, на дополнительном промежуточке Δt одно; — все события произошли на основном промежутке, на дополнительном ни одного; — на основном промежутке произошло k − i событий (i  2), на дополнительном i. Эти варианты несовместны и образуют полную группу, следовательно, вероятность результата вычисляется по формуле полной вероятности. Тогда с учетом ординарности потока можно записать k  pk−i (t)pi (Δt) = pk (t + Δt) = pk−1 (t) · p1 (Δt) + pk (t) · p0 (Δt) + i=2

= pk−1 (t)[λΔt + o(Δt)] + pk (t)[1 − λΔt + o(Δt)] + o(Δt) = = λpk−1 (t)Δt + pk (t) − λpk (t)Δt + o(Δt), откуда o(Δt) pk (t + Δt) − pk (t) = λ[pk−1 (t) − pk (t)] + . Δt Δt Переходя к пределу при Δt → 0, получаем уравнения для k  1. Объединяя их с уравнением для k = 0, имеем бесконечную систему линейных дифференциальных уравнений для нахождения

92

Глава 21. Элементы теории массового обслуживания

функций pk (t): ⎧ ⎨ p (t) = −λp0 (t), 0 ⎩ p (t) = λ[p (t) − p (t)], k−1 k k

k  1.

(21.2)

Начальные условия говорят о том, что на промежутке точно нулевой длины события невозможны, т. е. p0 (0) = 1, pk (0) = 0,

k  1.

(21.3)

Решать эту систему можно разными способами, мы воспользуемся наиболее простым, основанным на интегральном преобразовании, носящем имя Пьера-Симона Лапласа (Laplace, PierreSimon; 1749–1827) — великого французского математика и астронома, жившего в наполеоновскую эпоху. О его необычной судьбе мы уже говорили в исторических замечаниях [4, ч. III, с. 199]. Преобразование Лапласа играет в исчислении Преобразование функций примерно такую же роль, какую сыгЛапласа рало изобретение логарифмов в элементарной математике. Оно сводит функциональные операции (дифференцирование и интегрирование) к алгебраическим — умножению и делению. На преобразовании Лапласа и его разнообразных вариантах (Лапласа — Карсона, Карсона — Хэвисайда)6 основано операционное исчисление (operational calculus), незаменимое при расчете электрических цепей. Преобразование Лапласа (прямое и обратное) каждой функции — оригиналу f (t), определенной на неотрицательной в е щ е с т в е н н о й полуоси, ставит в соответствие ее образ — функцию 6

Оливер Хэвисайд (Heaviside, Oliver; 1850–1925) — английский инженер и ученый-самоучка. Впервые применил комплексные числа для изучения электрических цепей, разработал технику преобразования Лапласа для решения дифференциальных уравнений. Джон Карсон (Carson, John Renshaw; 1886— 1940) — известный американский специалист в области радиосвязи.

21.3. Простейший (пуассоновский) поток

93

F˜ (s) к о м п л ´е к с н о й переменной s, и наоборот: ∞ σ+i∞ 1 F˜ (s) −st ˜ ds. e f (t)dt, f (t) = est F (s) = s 2πi σ−i∞ s 0 Для указания взаимно однозначного соответствия оригинала и образа в математике имеется специальный символ: f (t)  F˜ (s). Существуют справочники по преобразованию Лапласа, охватывающие большое число элементарных и специальных функций7 . Приведем самые простые примеры соответствия оригиналов и образов, которые нам понадобятся в дальнейшем: s e−at  ; (21.4) s+a s tk −at e  . (21.5) k! (s + a)k+1 Сущность преобразования Лапласа раскрывают его основные свойства: — линейность:   ci fi (t)  ci F˜i (s); i

i

— дифференцирование оригинала: f  (t)  s[F˜ (s) − f (0)]; — интегрирование оригинала: t F˜ (s) . f (t)dt  s 0 Видим, что операции дифференцирования и интегрирования оригинала приводят к простому умножению или делению на аргумент. Вместе со свойством линейности это дает замечательный инструмент для решения линейных дифференциальных уравнений. 7

См., например: Диткин В. А., Прудников А. П. Справочник по операционному исчислению. М.: Высшая школа, 1965. 467 с.

94

Глава 21. Элементы теории массового обслуживания

Вооружившись преобразованием Лапласа, приРаспределение ступим к решению системы уравнений (21.2). числа событий Обозначим образы интересующих нас функций pk (t) через P˜k (s). Тогда по свойству дифференцирования оригинала pk (t)  s[P˜k (s) − pk (0)]. Поскольку уравнения (21.2) содержат только линейные операции с постоянными коэффициентами, их можно взаимно однозначно отобразить в комплексную область; соответствующие образы уравнений имеют следующий вид (значения p0 (0), pk (0) подставлены из начальных условий (21.3)): ⎧ ⎨ s[P˜0 (s) − 1] = −λP˜0 (s), (21.6) ⎩ sP˜ (s) = −λ[P˜ (s) − P˜ (s)], k  1. k k k−1 Проведя простейшие преобразования, получаем соотношения s , P˜0 (s) = s+λ λ ˜ Pk−1 (s), k  1, P˜k (s) = s+λ откуда рекурсивно получается P˜k (s) =

sλk . (s + λ)k+1

Пользуясь обратным преобразованием Лапласа (21.4), получаем окончательный результат: (λt)k −λt ak −a e = e , (21.7) k! k! где обозначено a = λt. Видим, что число событий простейшего потока, происходящих на промежутке длиной t, подчиняется хорошо известному в теории вероятностей распределению Пуассона 8 pk (t) =

8

Пусассон (Poisson, Sim´ eon Denis; 1781–1840) — выдающийся французский физик и математик, ученик Жозефа Луи Лагранжа (1736–1813) и ПьераСимона Лапласа (1749–1827).

21.3. Простейший (пуассоновский) поток

95

(отсюда второе название потока), в котором a = λt есть с р е д н е е число событий в этом промежутке. П р и м е р. Поток посетителей в гардероб можно считать простейшим с интенсивностью 60 чел./ч. Какова вероятность того, что: а) в течение 5 мин не будет ни одного посетителя; б) в течение 1 мин придут 3 человека? а) Если установить временной масштаб равным 1 мин, интенсивность потока λ = 1 чел./мин. При t = 5 мин среднее ожидаемое число посетителей a = λt = 5 чел. Тогда при k = 0 получаем p0 (5) =

ak −a 50 −5 e = e = e−5 ≈ 0.0067. k! 0!

б) При t = 1 мин, среднее значение a = λt = 1 чел. Для k = 3 искомая вероятность p3 (1) =

13 −1 e ≈ 0.0613.  3!

Так как события в потоке наступают в случайРаспределение ные моменты, временные ´ интервалы между современн´ ых бытиями также случайные. Их вероятностное интервалов распределение может быть легко получено, если известна функция p0 (t). Действительно, пусть T — случайная величина, равная интервалу времени между двумя событиями. Обозначим функцию распределения этой величины через FT (τ ), а плотность через fT (τ ). Тогда по определению (интегральной) функции распределения FT (τ ) = P {T < τ } = 1 − P {T  τ }. Здесь P {T  τ } есть вероятность того, что в промежутке длины τ не произойдет ни одного события п р и у с л о в и и, что оно произошло в начале промежутка. Но так как наш поток без последействия, то эта вероятность равна б е з у с л о в н о й

96

Глава 21. Элементы теории массового обслуживания

вероятности наступления k = 0 событий в промежутке τ , т. е. величине p0 (τ ). Следовательно, FT (τ ) = 1 − p0 (τ ) = 1 −

(λτ )0 −λτ e = 1 − e−λτ . 0!

(21.8)

Отсюда находится плотность распределения временных промежутков, равная, как известно, производной от функции распределения: f (τ ) = F  (τ ) = λe−λτ . (21.9) Таким образом, случайные интервалы времени в простейшем потоке подчинены экспоненциальному распределению вероятностей. Математическое ожидание в этом распределении можно определить, взяв по частям интеграл ∞ ∞ 1 M [T ] = τ¯ = τ fT (τ )dτ = λ τ e−λτ dτ = . λ 0 0 Результат получился вполне ожидаемый: среднее время между событиями обратно пропорционально их интенсивности. Замечание 1. Экспоненциальное распределение интервалов обладает уникальным свойством, выделяющим его из всех других. Если промежуток времени у ж е длился некоторое время τ , то это никак не влияет на закон распределения о с т а в ш е й с я части промежутка: он будет таким же, как и закон распределения всего промежутка T . В этом наглядно проявляется отсутствие последействия в потоке. Для доказательства предположим, что промежуток уже продолжается некоторое время τ , т. е. произошло событие T > τ , вероятность которого равна 1 − FT (τ ). Найдем при этом предположении условную функцию распределения оставшейся части промежутка Z = T − τ FZ|T (t, τ ) = P {Z < t | T > τ } и покажем, что она не зависит от τ и равна FT (t). Сначала найдем вероятность произведения двух событий: T > τ и Z = T − τ < t. По теореме умножения вероятностей P {(T > τ ), (Z < t)} = P {T > τ }P {Z < t | T > τ } = P {T > τ }FZ|T (t, τ )}.

21.3. Простейший (пуассоновский) поток

97

 Но событие (T > τ ) (Z = T −τ < t) равносильно событию τ < T < t+τ , вероятность которого равна FT (t + τ ) − FT (τ ). С другой стороны, P {T > τ } = 1 − FT (τ ), следовательно, FZ|T (t, τ ) =

FT (t + τ ) − FT (τ ) . 1 − FT (τ )

Подставляя функцию распределения FT из (21.8), получаем FZ|T (t, τ ) =

e−λτ − e−λ(t+τ ) = 1 − e−λt = FT (t). e−λτ



На свойстве экспоненциального распределения основано решение задач такого типа. Пусть среднее время между пролетами метеоров безлунной ночью составляет, например, 10 мин. Наблюдатель уже простоял 5 мин (варианты: 10, 20, 30 мин) и ничего не заметил. Каково среднее ожидаемое время появления очередного метеора? Правильный ответ: те же самые 10 мин. Замечание 2. Важно заметить, что имеет место обратное утверждение: если временные промежутки в некотором потоке независимы и их распределение экспоненциальное, то этот поток является простейшим. На этом свойстве основана стандартная техника компьютерного моделирования простейших потоков. Момент наступления следующего события tk+1 получается сложением предыдущего момента tk со случайной величиной τ , созданной генератором случайных чисел, дающим экспоненциальное распределение с заданным параметром λ.

Хотя простейший поток является некоПредельное свойство торой абстракцией, многие реальные попростейшего потока токи достаточно близко приближаются к нему по своим свойствам, что дает возможность при теоретическом анализе воспользоваться такой удобной моделью. В теории массового обслуживания простейший (пуассоновский) поток занимает такое же важное место, как нормальное

98

Глава 21. Элементы теории массового обслуживания

(гауссовское) распределение в теории вероятностей, причем это происходит по схожей причине. Как мы знаем из теории вероятностей, центральная предельная теорема гласит, что если некоторая случайная величина представляет собой сумму независимых «одинаково малых» случайных величин, то ее распределение с увеличением числа слагаемых стремится к нормальному. Аналогично, если случайный поток представляет собой результат слияния многих независимых малых потоков (среди которых нет доминирующего, навязывающего свои статистические характеристики), то он в пределе стремится к простейшему. Соответствующая предельная теорема (теорема Пальма — Хинчина) была доказана А. Я. Хинчиным, опиравшимся на результаты шведского математика Пальма (см. исторические замечания в конце главы). Именно это предельное свойство объясняет тот факт, что реальные потоки часто близки к пуассоновским. Примеров можно привести множество. Поток звонков на телефонную станцию представляет собой сумму очень редких потоков вызовов от большого числа отдельных абонентов. Поток транспорта на шоссе складывается из большого числа потоков автомобилей между отдельными пунктами и т. п. Когда же имеется доминирующий поток, он подавляет все остальные, в результате приходится иметь дело с потоками, существенно отличающимися от простейшего (нестационарными, неординарными, с последействием), их классификации и описанию посвящена специальная литература.

21.4. Марковские процессы Прежде чем перейти к изучению самих моделей массового обслуживания, нам потребуется хотя бы элементарные знания по теории специфических случайных процессов, называемых марковскими (Markovian). Они названы так по имени выдающегося русского математика Андрея Андреевича Маркова-старшего (1856–1922) (см. исторические замечания в конце главы).

21.4. Марковские процессы

99

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

Определение. Стохастический процесс смены состояний называется марковским, если в е р о я т н о с т ь перехода в следующее состояние определяется только текущим состоянием и не зависит от предыстории. Классический образный пример — хаотические прыжки лягушки по листьям кувшинки в пруду в предположении, что животное совершенно лишено памяти, в результате чего цель путешествия отсутствует, вероятность перепрыгнуть с текущего листа на соседний зависит только от расстояния между ними. Другой пример — случайное блуждание броуновской частицы под влиянием молекулярных соударений. Марковские процессы представляют собой удобную абстракцию для описания многих реальных явлений и широко используются в различных областях науки, их классификация возможна по двум независимым основаниям: по числу состояний и по времени (табл. 21.1): — дискретные по состояниям процессы подразумевают конечное (пример с лягушками) или счетное число возможных состояний в отличие от процессов, где пространство состояний непрерывно; — дискретные по времени процессы моделируют ситуации, в которых переходы происходят только в разрешенные, тактовые моменты времени (переход крестьян от одного помещика к другому был возможен только в «юрьев день»); непрерывные по времени процессы описывают непрерывную эволюцию исследуемой системы. Для каждого варианта разработан адекватный математический аппарат, в теории массового обслуживания нас будут интересовать процессы, дискретные по состояниям и непрерывные во времени (марковские цепи с непрерывным временем).

100

Глава 21. Элементы теории массового обслуживания Таблица 21.1. Классификация марковских процессов По состояниям Дискретные

Непрерывные

По времени Дискретные Непрерывные Дискретные по вре- Дискретные по сомени и состояниям стояниям, непрерыв(дискретная цепь ные по времени (цепь Маркова) Маркова с непрерывным временем) Непрерывные по со- Непрерывные по врестояниям, дискрет- мени и состояниям ные по времени

Рассмотрим цепь Маркова с состояниями E1 , E2 , . . . и непрерывным временем. Вероятность перехода Ei → Ek , i = k за бесконечно малый промежуток времени Δt можно разложить в ряд и считать равной Pik (Δt) = πik Δt + o(Δt). ВелиPik (Δt) , где i = k, называются интенсивночины πik = lim Δt→0 Δt стями переходов, из них можно составить квадратную матрицу интенсивностей, порядок которой равен числу состояний системы. Эту матрицу удобно визуально представить с помощью о р и е н т и р о в а н н о г о графа переходов, в котором вершины соответствуют состояниям, а дуги с соответствующими весами отображают н е н у л е в ы е интенсивности. Матрица и граф интенсивностей переходов

П р и м е р. На рис. 21.4 представлена простейшая марковская цепь с тремя состояниями в виде матрицы и графа интенсивностей переходов. В данном примере все πik < 1, но в общем случае, так как интенсивности сами по себе не являются вероятностями, на них не накладывается ограничение πik ≤ 1. 

21.4. Марковские процессы ⎞ − 0.2 0 ⎜ ⎟ ⎝0.1 − 0.3⎠ 0.5 0 −

101

⎛

0.5

0.3

0.1

0.2

Рис. 21.4. Пример матрицы и графа интенсивностей переходов

Предположим, что состояние системы в начальный момент известно и равно E(t0 ). Впоследствии оно будет случайным, можно говорить лишь в вероятности pk (t) того, что E(t) = Ek , т. е. в момент времени t система будет находиться в состоянии k. Для нахождения неизвестных функций pk (t), k = 1, 2, . . . необходимо решить систему дифференциальных уравнений, к построению которой мы приступаем. Пусть, как и прежде, Pik (Δt), i = k, обозначает вероятность перехода системы из состояния i в состояние k за бесконечно малый промежуток времени t. Оказаться в момент времени t + Δt в состоянии Ek система может разными способами: либо перейдя за время Δt из некоторого состояния Ei , где она находилась в предыдущий момент времени t, либо сохранив предыдущее состояние Ek , не перейдя ни в какое другое. Все варианты являются взаимоисключающими и образуют полную группу. Следовательно, мы имеем право воспользоваться формулой полной вероятности и записать вероятность pk (t + Δt) нахождения системы в состоянии Ek в момент t + Δt: Уравнения Чепмена — Колмогорова

pk (t + Δt) =



pi (t)Pik (Δt) + pk (t)Pkk (Δt) =

i i=k

=

 i i=k

pi (t)Pik (Δt) + pk (t)[1 −

 i i=k

Pki (Δt)].

102

Глава 21. Элементы теории массового обслуживания

Переносим pk (t) в левую часть и делим на Δt:  Pki (Δt) Pik (Δt) pk (t + Δt) − pk (t)  = − pk (t) . pi (t) Δt Δt Δt i i=k

i i=k

Переходя к пределу при Δt → 0, получаем   pi (t)πik − pk (t) πki , k = 1, 2, . . . pk (t) = i i=k

(21.10)

i i=k

Уравнения (21.10) называются уравнениями Чепмена — Колмогорова, их нужно решать с начальными условиями: ⎧ ⎪ ⎨ 1, если в начальный момент времени система pk (t0 ) = находилась в состоянии E(t0 ) = Ek , ⎪ ⎩ 0 в противном случае. Уравнения (21.10) дают принципиальную возможность найти вероятность нахождения системы в нужном состоянии в любой момент времени. Для практического составления уравнений удобно пользоваться графом интенсивностей переходов. При этом для каждой вершины первая сумма (со знаком плюс) соответствует в х о д я щ и м дугам, а вторая (со знаком минус) — и с х о д я щ и м. Замечание. Общая теория марковских случайных процессов с непрерывным временем была опубликована А. Н. Колмогоровым в 1931 г. (см. исторические замечания в конце главы). Независимо от него в 1928 г. известный английский геофизик Сидни Чепмен (Chapman, Sydney; 1888–1970) получил уравнения для частного случая непрерывных по состояниям процессов диффузии. По этой причине в самом общем случае дифференциальные уравнения для вероятностей состояний чаще всего называют уравнениями Чепмена — Колмогорова, хотя, по свидетельству очевидцев, сам Чепмен об этом не знал.

21.4. Марковские процессы

103

П р и м е р. Для простейшей марковской цепи, представленной на рис 21.4, система Чепмена — Колмогорова состоит из трех линейных дифференциальных уравнений первого порядка: p1 (t) = −0.2 p1 (t) +0.1 p2 (t) +0.5 p3 (t), 0.2 p1 (t) −0.4 p2 (t), p2 (t) =  0.3 p2 (t) −0.5 p3 (t). p3 (t) =

(21.11)

При известных начальных условиях эту систему легко решить любым подходящим численным методом. На рис. 21.5, построенном с помощью пакета MATLAB, показано, как меняются со временем вероятности пребывания системы в состояниях E1 , E2 , E3 , если при t = 0 она находилась в том или ином состоянии.  1 0.8

p1 (t) 0.6

p2 (t)

0.4 0.2

p3 (t) 0 0

2

4

6

8

t

10

Рис. 21.5. Численное решение уравнений Чепмена — Колмогорова для примера простейшей марковской цепи с тремя состояниями при различных начальных усло-. виях. Сплошная линия: p1 (0) = 1, p2 (0) = 0, p3 (0) = 0; штриховая линия: p1 (0) = 0, p2 (0) = 1, p3 (0) = 0; штрих-пунктирная линия: p1 (0) = 0, p2 (0) = 0, p3 (0) = 1

104

Глава 21. Элементы теории массового обслуживания

Наблюдая графики, аналогичные приведенным Эргодическое на рис. 21.5, нельзя не заметить характерную засвойство кономерность: при t → ∞ функции вероятностей pk (t) перестают зависеть от времени и стремятся к постоянным асимптотическим значениям pk , причем предельные значения не зависят от начального состояния системы. Другими словами, система после некоторого переходного нестационарного периода приходит в стационарный режим, который можно назвать стохастическим равновесием. Асимптотические значения pk , k = 1, 2, . . . образуют предельное или финальное распределение вероятностей состояний. Указанное свойство марковского процесса называется эргодическим, однако оно наблюдается не всегда. Для того чтобы цепь Маркова была эргодической, ее интенсивности переходов должны обладать определенными свойствами, устанавливаемыми эргодической теоремой [11, с. 80]. На языке матриц условия эргодичности формулируются довольно сложно, но на графе переходов их можно наглядно интерпретировать как условие сильной связности, при котором для каждой пары вершин существует ориентированный путь из одной вершины в другую и обратно. Это условие гарантирует при бесконечном случайном блуждании по вершинам сохранять ненулевую вероятность вернуться в любое состояние и не оказаться в ситуации, из которой нет возврата. Шутливым примером н е э р г о д и ч е с к о г о марковского процесса является бесцельное движение абсолютно пьяного прохожего по улицам воображаемого города, где расставлены «ловушки». Попав на очередной перекресток, он продолжает путь в случайном направлении до тех пор, пока не наткнется на полицейского или не свалится в открытый колодец. Эргодическое свойство марковских процессов является проявлением общего эргодического свойства динамических стохастических систем9 . В эргодических системах нет фатальной зависимо9

Эргодичность (от греч. ergon — работа и hodos — путь) — понятие, введенное выдающимся австрийским физиком-теоретиком Людвигом Больцма-

21.4. Марковские процессы

105

сти будущего от прошлого, в результате каждая индивидуальная траектория является типичным представителем процесса в целом и может быть использована для набора статистики (см. с. 106). Как правило, нестационарный режим функционирования системы представляет значительно меньший интерес для исследователя, чем стационарный, полностью характеризующийся предельным распределением {pk }. Когда исследуемая марковская цепь удовлетворяет условиям эргодичности, предельное распределение может быть получено из уравнений Чепмена — Колмогорова (21.10). Предельные вероятности

Действительно, если при t → ∞ pk (t) → const, то pk (t) → 0, и система д и ф ф е р е н ц и а л ь н ы х уравнений (21.10) чудесным образом превращается в систему л и н е й н ы х а л г е б р а и ч е с к и х уравнений относительно предельных вероятностей pk : 

pi πik − pk

i i=k



 i i=k

πki = 0,

k = 1, 2, . . . , (21.12)

pk = 1.

k

Условие нормировки добавлено к системе для того, чтобы решение было единственным, в противном случае первые уравнения дают решение с точностью до произвольного множителя. П р и м е р. Для простейшей марковской цепи система линейных алгебраических уравнений для нахождения финальных вероятностей получается из соответствующих уравнений Чепмена — Колмогорова (21.11): ном (Boltzmann, Ludwig Eduard; 1844–1906) для обоснования статистической физики. Динамическая стохастическая система, в которой средние по реализациям совпадают со средними по времени, называется эргодической.

106

Глава 21. Элементы теории массового обслуживания −0.2p1 +0.1p2 +0.5p3 0.2p1 −0.4p2 +0.3p2 −0.5p3 +p2 +p3 p1

= 0, = 0, = 0, = 1.

Решая систему (если не хочется считать вручную, можно использовать надстройку «Поиск решения» в пакете Excel), получаем p1 ≈ 0.5555, p2 ≈ 0.2777, p3 ≈ 0.1666. Легко убедиться, что именно к этим значениям асимптотически приближались функции p1 (t), p2 (t), p3 (t) на рис. 21.5.  Предположим, у нас имеется реальная система, случайным образом меняющая состояния во времени, и мы хотим экспериментально оценить вероятность пребывания ее в некотором состоянии Ek в момент времени t. Для этого необходимо многократно запустить исследуемый случайный процесс с самого начала, получить набор (выборочный ансамбль) реализаций E(t) и подсчитать, сколько раз в момент t система была в состоянии Ek , т. е. произошло случайное событие E(t) = Ek (см. рис. 21.6, a). Если это число равно Nk (t), а общее число реализаций N , то отношение Оценивание и физический смысл вероятностей состояний

pˆk (t) =

Nk (t) N

даст оценку искомой вероятности. Когда объем выборочного ансамбля реализаций N → ∞, то в силу закона больших чисел pˆk (t) → pk (t) (тонкие вопросы сходимости мы здесь не рассматриваем, они изучались в курсе теории вероятностей). Такой способ оценивания характеристик случайного процесса называется усреднением по ансамблю. Если оцениваются предельные вероятности pk , то момент t следует выбрать достаточно далеко от начала процесса, чтобы система успела перейти в стационарный режим.

21.4. Марковские процессы

107

a)

б)

Рис. 21.6. Оценивание предельных вероятностей усреднением по ансамблю реализаций (а) и по времени (б)

Указанный способ оценки вероятностей на практике оказывается крайне неудобным, так как требует многократного генерирования и регистрации большого количества реализаций случайного процесса. Однако если нас интересуют только предельные вероятности, а исследуемый процесс эргодический, то усреднение по ансамблю можно заменить усреднением по времени (рис. 21.6, б ). При таком способе рассматривается е д и н с т в е н н а я реализация уже перешедшего в стационарный режим случайного процесса. Выбирается некоторый промежуток времени T и подсчитывается суммарное время пребывания системы в интересую (i) Tk . В качестве оценки вероятности щем состоянии Ek : Tk = i

принимается д о л я в р е м е н и, в течение которого система находилась в состоянии Ek : Tk . p¯k = T Если T → ∞, то p¯k → pk и (в этом суть эргодичности!) результаты усреднения по времени и по ансамблю совпадают: lim pˆk = lim p¯k .

N →∞

T →∞

108

Глава 21. Элементы теории массового обслуживания

Таким образом, для эргодического стационарного процесса величину pk мы можем трактовать двояким образом: 1) как вероятность застать систему в состоянии Ek в любой случайно взятый момент времени; 2) как относительную долю времени, в течение которого система пребывает в состоянии Ek .

21.5. Система M/M/n/0 (с потерями) Теперь мы имеем математический аппарат, достаточный для аналитического решения простейших задач теории массового обслуживания. Начнем с анализа классической модели, которая, собственно, и привела к возникновению самой теории. Речь идет о многолинейной системе, на вход которой поступает простейший поток заявок, а время обслуживания является случайным и распределено по экспоненциальному закону. Мест для ожидания в накопителе нет, поэтому заявка, пришедшая, когда все приборы заняты, получает отказ (теряется). Эта модель довольно адекватно описывает работу старинной автоматической телефонной станции, где обслуживающие приборы, называемые шаговыми искателями, принимали вызов и соединяли абонентов друг с другом. Каждый такой прибор представлял собой весьма сложное электромеханическое устройство, их количество на телефонной станции было небольшим, в результате чего потери вызовов происходили довольно часто. Итак, пусть имеется система массового обслуживания Модель без очереди, на вход которой поступает простейший поток заявок с интенсивностью λ (рис. 21.7). Блок обслуживания состоит из n идентичных приборов, время обслуживания одним прибором распределено по экспоненциальному закону с плотностью распределения f (τ ) = μe−μτ , где величину μ по аналогии с интенсивностью потока заявок (см. с. 96) можно понимать как интенсивность обслуживания одним прибором, связанную 1 со средним временем обслуживания τ¯ соотношением μ = . τ¯

21.5. Система M/M/n/0 (с потерями)

109

Прибор 1 Прибор k Прибор n Входной поток

Блок обслуживания

Выходной поток

Рис. 21.7. Модель системы массового обслуживания с потерями

Для построения математической модели заметим, что состояние этой системы в момент t времени полностью определяется числом занятых приборов k, т.е. E(t) = k(t), k = 0, 1, 2, . . . n, при этом смена состояния происходит в непрерывном времени. Переход системы из состояние в состояние происходит под воздействием двух потоков событий: простейшего потока заявок и потока освобождений приборов. В силу отсутствия последействия в обеих потоках вероятность перехода в следующее состояние не зависит от предыстории, таким образом, моделью исследуемой системы является марковская цепь с конечным числом состояний и непрерывным временем. Первый этап анализа марковской цепи — построение графа интенсивностей переходов. В нашем случае он будет иметь n + 1 вершину E0 , . . . , En по числу занятых приборов. Далее замечаем, что поскольку потоки заявок и освобождений простейшие, то в силу их ординарности за бесконечно малый промежуток времени может прийти только одна заявка либо освободиться только один прибор. Следовательно, ненулевые интенсивности переходов возможны только между соседними состояниями10 . Таким образом, граф переходов имеет

Граф переходов

10

Подобные марковские процессы с дискретными состояниями и непрерывным

110

Глава 21. Элементы теории массового обслуживания

линейную структуру, показанную на рис. 21.8.

...

...

Рис. 21.8. Граф интенсивностей переходов системы M/M/n/0. Заливкой выделены начальная E0 , общая Ek и конечная En вершины. Входящие в них дуги изображены сплошными, исходящие — штриховыми линиями

Для вычисления интенсивностей переходов следует подробно рассмотреть вероятности событий, которые приводят к данным переходам в течение бесконечно малого промежутка времени Δt. E0 → E1 . Этот переход соответствует событию, когда в пустую систему в течение времени Δt поступит одна заявка. Согласно (21.1), вероятность такого события равна P01 (Δt) = p1 (Δt) = λΔt + o(Δt), P01 (Δt) = λ. Δt E1 → E0 . В состоянии E1 занят только один прибор. Переход соответствует сложному событию, когда этот прибор освободится, при этом в систему не поступит ни одна заявка. Вероятность того, что в течение времени Δt не поступит ни одна заявка, согласно (21.1), равна p0 (Δt) = 1 − λΔt + o(Δt). Вероятность освобождения прибора за время Δt может быть получена из следующих соображений. Как следует из следовательно, π01 = lim

Δt→0

временем называются процессами размножения и гибели (birth and death processes). Номер состояния соответствует количеству особей в популяции, при этом предполагается, что особи могут рождаться и гибнуть только поодиночке.

21.5. Система M/M/n/0 (с потерями)

111

свойств экспоненциального распределения времени обслуживания T (см. с. 96), вероятность того, что обслуживание закончится за время Δt, независимо от того, сколько оно уже длится, равна P {T < Δt} = FT (Δt) = 1 − e−μΔt . Считая Δt бесконечно малой величиной и раскладывая это выражение в ряд, получаем искомую вероятность: P {T < Δt} = μΔt + o(Δt). События независимы, следовательно, вероятность их совместного осуществления равна произведению соответствующих вероятностей: P10 (Δt) = [1 − λΔt + o(Δt)][μΔt + o(Δt)] = μΔt + o(Δt). P10 (Δt) = μ. Δt→0 Δt Ek → Ek−1 . В состоянии Ek занято k приборов. Переход в предыдущее состояние соответствует сложному событию, когда заявка не поступит (вероятность этого, как мы уже знаем, равна p0 (Δt) = 1 − λΔt + o(Δt), при этом освободится любой из k приборов. Вероятность освобождения одного из k приборов за время Δt по формуле сложения вероятностей в k раз больше, чем вероятность освобождения одного прибора, которая, как мы выяснили ранее, равна μΔt + o(Δt). Таким образом, вероятность сложного события, соответствующего анализируемому переходу, равна

Отсюда интенсивность перехода π10 = lim

Pk,k−1 (Δt) = [1 − λΔt + o(Δt)][kμΔt + o(Δt)] = kμΔt + o(Δt), откуда πk,k−1 = kμ. Ek+1 → Ek . Ситуация аналогична предыдущей, но поток освобождений имеет суммарную интенсивность (k +1)μ. Следовательно, πk+1,k = (k + 1)μ.

Глава 21. Элементы теории массового обслуживания

112

Ek → Ek+1 . Переход соответствует сложному событию, когда в промежутке Δt придет ровно одна заявка и не освободится ни один из k приборов. С учетом всего предыдущего Pk,k+1 (Δt) = [λΔt + o(Δt)][1 − kμΔt + o(Δt)] = λΔt + o(Δt), соответствующая интенсивность перехода πk,k+1 = λ. Подводя итог, видим, что интенсивности всех прямых переходов равны πk,k+1 = λ (k = 0, . . . , n − 1), а всех обратных переходов πk,k−1 = kμ (k = 1, . . . , n), что показано на графе (см. рис.21.8). Вычислив интенсивности переходов, можно записать систему дифференциальных уравнений Чепмена — Колмогорова (21.10) для соответствующей марковской цепи. В нашем случае система состоит из конечного числа уравнений:   pk (t) = pi (t)πik − pk (t) πki , k = 0, . . . , n. Уравнения Чепмена — Колмогорова

i i=k

i i=k

Глядя на граф переходов, легко записать уравнения для начального, общего k-го (k = 1, . . . , n − 1) и конечного состояний: p0 (t) = −λp0 (t) + μp1 (t),

pk (t) = λpk−1 (t) − (kμ + λ)pk (t) + (k + 1)μpk+1 (t), pn (t)

(21.13)

= λpn−1 (t) − nμpn (t).

Начальные условия показывают, что в начальный момент все приборы свободны: p0 (0) = 1, ∀k > 0 pk (0) = 0. П р и м е р. Парикмахерская имеет два кресла (n = 2), места для ожидания не предусмотрены. Поток посетителей простейший, его интенсивность составляет λ =8 клиентов в час. Среднее время обслуживания одного клиента 15 мин (интенсивность обслуживания μ = 4 чел./ч). Требуется выяснить поведение системы в нестационарном режиме, сразу после начала работы.

21.5. Система M/M/n/0 (с потерями)

113

Граф переходов для этой задачи имеет три вершины, интенсивности переходов указаны на рис. 21.9, а. Соответствующая система уравнений Чепмена — Колмогорова имеет вид p0 (t) = −8p0 (t) +4p1 (t), 8p0 (t) −12p1 (t) +8p2 (t), p1 (t) =  8p1 (t) −8p2 (t). p2 (t) = Численное решение уравнений с помощью пакета MATLAB дает результат, приведенный на рис. 21.9, б. Хорошо видно, что нестационарный режим продолжается очень недолго, уже через полчаса после открытия наступает стохастическое равновесие, вероятности состояний достаточно близко приближаются к предельным значениям.  1

0.8

p0 (t) 0.6

p1 (t)

0.4

a)

0.2

p2 (t) 0 0

0.2

0.4

0.6

t

0.8

б) Рис. 21.9. Граф интенсивностей переходов (а) и функции вероятности состояний (б) для примера о парикмахерской

Перед тем как найти предельПредельное распределение. ное распределение вероятностей Формула Эрланга состояний, нужно убедиться, что оно существует, т. е. исследуемая марковская цепь является эргодической. Рассматривая граф переходов нашей системы на рис. 21.8, видим, что он является силь-

Глава 21. Элементы теории массового обслуживания

114

но связным, из каждой вершины находится путь в любую другую. Следовательно, предельное распределение существует, и его можно найти, превратив дифференциальные уравнения Чепмена — Колмогорова (21.13) в алгебраические. Устремив t → ∞ и приравняв производные нулю, получаем систему линейных алгебраических уравнений относительно предельных вероятностей: −λp0 + μp1 = 0, λpk−1 − (kμ + λ)pk + (k + 1)μpk+1 = 0,

k = 1, . . . , n − 1,

λpn−1 − nμpn = 0. Сделаем подстановку zk = λpk−1 − kμpk , в результате система примет следующий вид: −z1 = 0, − kμpk ] − [λpk − (k + 1)μpk+1 ] = 0, [λp

 

 k−1 zk

k = 1, . . . , n − 1,

zk+1

zn = 0. Ее очевидное решение zk = 0, т. е. λpk−1 − kμpk = 0, k = 1, . . . , n, откуда λ pk = pk−1 . kμ В результате рекуррентно получаем p1 =

( μλ )

( μλ )2

p 0 , p2 = p0 , 1 1·2 Если ввести величину ρ=

...

pk =

( μλ )k k!

p0 .

λ Интенсивность потока заявок = , nμ Интенсивность обслуживания всеми приборами

которую можно понимать как коэффициент загрузки системы, то формулы для расчета вероятности состояния в предельном распределении примут вид pk =

(nρ)k p0 , k!

(21.14)

21.5. Система M/M/n/0 (с потерями)

115

где вероятность p0 вычисляется из условия нормировки

n 

pk = 1:

k=0

 p0 =

n  (nρ)k k=0

k!

−1 .

(21.15)

Выражения (21.14) — (21.15) называются формулой Эрланга в честь впервые получившего ее в 1917 г. датского инженера Агнера Эрланга (см. исторические замечания в конце главы). Мы вывели формулу Эрланга в предположении, что время обслуживания распределено по экспоненциальному закону, однако сам Эрланг получил ее для постоянного времени обслуживания. Это наводит на мысль, что формулу можно распространить на другие типы распределений времени обслуживания (но не на любые потоки заявок!). И это действительно так, соответствующая теорема была доказана в 1956 г. советским математиком Б. А. Севастьяновым11 . Она утверждает, что для системы с потерями при простейшем входном потоке заявок предельные вероятности состояний сохраняются при любом распределении времени обслуживания, если его среднее значение остается неизменным и равным M [τ ] = τ¯ = 1/μ. Это утверждение можно записать в виде символического равенства Теорема Севастьянова

M/M/n/0 ∼ M/G/n/0. Формула Эрланга исчерпывающим образом описывает поведение исследуемой системы с потерями в стационарном режиме. Из нее могут быть получены различные операционные характеристики, измеряющие качество обслуживания. Операционные характеристики

11

Севастьянов Б. А. Формула Эрланга в телефонии при произвольном законе распределения длительности разговора // III Всесоюзный математический съезд. Т. 4. М.: ВЦ АН СССР, 1956.

116

Глава 21. Элементы теории массового обслуживания

1. Вероятность отказа (потери заявки). Отказ происходит, когда заняты все приборы, т. е. pотк = pn =

(nρ)n p0 . n!

(21.16)

2. Среднее число занятых приборов M [k] =

n 

kpk .

(21.17)

k=0

3. Коэффициент использования приборов M [k] · 100 %. n В силу свойства эргодичности (см. с. 106) это отношение мы можем трактовать двояким образом: 1) как долю занятых приборов в любой случайно взятый момент времени; 2) как полезную долю времени, в течение которого приборы обслуживают заявки. Уже эти простые формулы дают возможность сделать глубокие выводы, позволяющие оптимизировать работу систем с потерями. В частности, иногда можно получить неожиданную выгоду, просто объединяя малые системы обслуживания в одну большую. Для того чтобы избежать абстрактных рассуждений, рассмотрим простейшие примеры обслуживания клиентов в парикмахерской (см. с. 112). Если отказаться от экспоненциального распределения времени обслуживания, то поведение системы в начальный период, описываемое дифференциальными уравнениями Чепмена — Колмогорова, будет отличаться от приведенного на рис. 21.9, однако в стационарном режиме в соответствии с теоремой Севастьянова можно пользоваться формулой Эрланга. П р и м е р 1. Пусть парикмахерская на вокзале имеет два специализированных зала – мужской и дамский (в недавнем прошлом эта была общепринятая практика), каждый из которых работает в условиях примера на с. 112, а именно: 2 кресла,

21.5. Система M/M/n/0 (с потерями)

117

поток посетителей в каждый зал простейший с интенсивностью λ = 8 чел./ч, среднее время обслуживания 15 мин (μ = 4 чел./ч). Коэффициент загрузки каждого зала равен ρ = λ/(nμ) = 1, т. е. пропускная способность в точности равна интенсивности входящего потока. В этих условиях вероятность отказа, казалось бы, должна быть небольшой. Однако расчет предельных вероятностей для одного зала по формуле Эрланга дает совсем другие результаты (заметим, что именно такие значения предельных вероятностей (см. рис. 21.9) получились при решении соответствующих дифференциальных уравнений): k

(nρ)k /k!

pk

kpk

0 1 2

1 2 2

0.2 0.4 0.4

0 0.4 0.8

Σ

5

1

1.2

Из получившихся чисел видно, что вероятность потери клиента по причине занятости мастеров pотк = p2  = 0.4. В то же время среднее число занятых приборов M [k] = kpk = 1.2, т. е. коэффициент полезного времени загрузки мастеров составляет всего 60 %. В этом проявляется особенность операции массового обслуживания при случайном потоке заявок: клиенты получают отказ, а приборы простаивают. Оценим экономические показатели нашего предприятия в предположении, что выручка от одного обслуженного клиента в среднем равна 10 у. е., а заработная плата одного мастера вместе с сопутствующими расходами составляет 20 у. е. В каждом из двух залов в среднем за час: пришло клиентов — 8, из них обслужено 8 · (1 − 0.4) = 4.8, выручка 4.8 · 10 = 48 у. е., расходы 2 · 20 = = 40 у. е., прибыль 8 у. е. Суммарная прибыль от двух залов составляет 16 у. е. 

118

Глава 21. Элементы теории массового обслуживания

П р и м е р 2. Продолжим пример с парикмахерской и покажем, как можно делать деньги «из воздуха», если воспользоваться знаниями теории массового обслуживания. Объединим два специализированных зала по два кресла в каждом в один с четырьмя креслами. Входящие потоки также сольем в один поток с суммарной интенсивностью λ = 16 чел./ч, в результате коэффициент загрузки системы останется прежним: ρ = λ/(nμ) = 16/(4 · 4) = 1. Расчет предельных вероятностей по формуле Эрланга для новых условий следующий: k

(nρ)k /k!

pk

kpk

0 1 2 3 4

1 4 8 10.67 10.67

0.029 0.116 0.233 0.311 0.311

0 0.116 0.466 0.933 1.244

Σ

34.34

1

2.643

Отсюда видно, что при той же загрузке вероятность отказа уменьшилась до величины pотк = p4 = 0.311. Как следствие, улучшились экономические показатели. В среднем за один час работы: пришло клиентов — 16, из них обслужено 16 · (1 − 0.311) = 11.02, выручка 11.02 · 10 = 110.2 у. е., расходы 4 · 20 = 80 у. е., прибыль 30.2 у. е. Таким образом, прибыль от укрупнения системы при прочих равных условиях увеличилась почти в 2 раза.  Приведенные примеры наглядно показывают выгоду от укрупнения систем, обслуживающих случайный поток заявок. Наряду с другими экономическими факторами это приводит к повсеместному вытеснению с рынка слабых поставщиков услуг: мелкие интернет-провайдеры и телефонные компании поглощаются крупными, создаются мощные call-центры с десятками операторов, организуются объединенные службы вызова такси и т. п.

21.6. Система M/M/n/∞ (с ожиданием)

119

21.6. Система M/M/n/∞ (с ожиданием) Система, к анализу которой мы приступаем, отличается от рассмотренной выше наличием накопителя, где заявки, заставшие все приборы занятыми, ожидают начала обслуживания (см. рис. 21.1). Для упрощения модели число мест в накопителе можно считать бесконечным, а клиентов предполагать бесконечно терпеливыми. Как и в предыдущей модели, состояние системы полностью определяется числом k находящихся в ней заявок, однако сейчас число состояний бесконечно, следовательно, 0  k < ∞. Если k  n, то очередь отсутствует, поведение системы ничем не отличается от рассмотренного в предыдущем параграфе. При k > n имеется очередь длиной m = k − n. Соответственно числу состояний граф переходов содержит бесконечное число вершин (рис. 21.10), причем его левая часть от E0 до En−1 полностью совпадает с графом переходов системы с потерями, приведенным на рис. 21.8. Отличия имеются в правой Граф переходов и уравнения Чепмена — Колмогорова

...

...

Рис. 21.10. Граф интенсивностей переходов системы M/M/n/∞. Заливкой выделены вершины, отвечающие за очередь

хвостовой части, соответствующей наличию очереди. Поскольку число занятых приборов в этом случае равно n, то поток освобождений не зависит от номера состояния и равен всегда nμ. Глядя на граф переходов, легко записать модифицированные уравнения Чепмена — Колмогорова:

120

Глава 21. Элементы теории массового обслуживания

p0 (t) = −λp0 (t) + μp1 (t),

pk (t) = λpk−1 (t) − (kμ + λ)pk (t) + (k + 1)μpk+1 (t), k = 1, . . . , n − 1, pk (t) = λpk−1 (t) − (nμ + λ)pk (t) + nμpk+1 (t), k  n.

Когда после переходного процесса система перейдет в стационарный режим, вероятности состояний стабилизируются, очередь придет в состояние стохастического равновесия. Система линейных уравнений для предельных вероятностей получается из дифференциальных уравнений Чепмена — Колмогорова предельным переходом при t → ∞, pk (t) → pk , pk (t) → 0: Предельные вероятности

−λp0 + μp1 = 0, λpk−1 − (λ + kμ)pk + (k + 1)μpk+1 = 0, λpk−1 − (λ + nμ)pk + nμpk+1 = 0,

k = 1, . . . , n − 1,

k  n.

Способ решения при k = 1, . . . n прежний: делается подстановка zk = λpk−1 − kμpk . Решение z1 = · · · = zn = 0, откуда (nρ)k p0 , где, как и прежде, ρ = λ/(nμ) обозначает коэффиpk = k! циент загрузки системы. Решение при k  n находится чуть другой подстановкой: zk = λpk−1 − nμpk . Тогда последняя группа уравнений перепишется в виде λpk−1 − (λ + nμ)pk + nμpk+1 = [λpk−1 − nμpk ] − [λpk − nμpk+1 ] = 0,  

 

zk

zk+1

откуда zk = 0, что приводит к рекуррентному соотношению pk =

λ pk−1 = ρpk−1 , nμ

k  n.

Собирая решения при k  n и k  n, получаем окончательно pk =

(nρ)k p0 , k!

k = 1, . . . , n;

(21.18)

21.6. Система M/M/n/∞ (с ожиданием) pn+m = ρm pn =

ρm (nρ)n p0 , n!

121

m = 0, 1, . . . , ∞.

(21.19)

На границе диапазонов индексов (k = n и m = 0) решения, как и должно быть, совпадают. Вероятность p0 находится из условия нормировки n 

pk +

∞ 

pn+m = p0 [Σ1 + Σ2 ] = 1,

m=1

k=0

где обозначено Σ1 =

n  (nρ)k k=0

k!

,

∞ (nρ)n  m Σ2 = ρ . n! m=1

Первая сумма имеет конечное число слагаемых, вторая есть сумма бесконечной геометрической прогрессии. Она сходится, если знаменатель прогрессии ρ < 1. Отсюда следует очень важный вывод: система с ожиданием работоспособна (очередь имеет конечную длину) только тогда, когда она недогружена. При выполнении этого условия Σ2 =

(nρ)n ρ , n! 1 − ρ

и для входящей в формулы (21.18) — (21.19) нормирующей вероятности p0 получается выражение −1  n  (nρ)k (nρ)n ρ −1 + . p0 = [Σ1 + Σ2 ] = k! n! 1 − ρ k=0

Операционные характеристики

Для системы с ожиданием можно предложить ряд характеристик, определяющих эффективность ее функционирования.

1. Вероятность немедленного обслуживания pn ρ =1− . 1 − P {k  n} = 1 − pn − p0 Σ2 = 1 − pn − pn 1−ρ 1−ρ

122

Глава 21. Элементы теории массового обслуживания

2. Средняя длина очереди вычисляется суммированием так называемой арифмо-геометрической прогрессии 12 : M [m] =

∞  m=0

mpn+m = pn

∞ 

mρm = pn

m=1

ρ . (1 − ρ)2

3. Среднее время пребывания в очереди находится из условия статистического равновесия очереди. Среднее время, за которое убывает и прибывает одна заявка, равно 1/λ, в результате очередь продвигается на одно место13 : M [m] . t¯ожид = λ 4. Среднее время пребывания в системе складывается из среднего времени пребывания в очереди и среднего времени обслуживания: 1 t¯ожид + τ¯ = t¯ожид + . μ ¯ находится из условия 5. Среднее число занятых приборов N статистического равновесия в системе: поток поступающих заявок ¯ · μ. Отуравновешивается потоком освобождений приборов λ = N сюда следует ¯ = λ. N μ П р и м е р. Поток посетителей в гардероб идет с интенсивностью λ = 60 чел./ч (1 человек в минуту). В гардеробе два 12

См.: Градштейн И. С., Рыжик И. М. Таблицы интегралов, сумм, рядов и произведений. Формула 0.231.2. 13 Хотя этот результат интуитивно понятен, его строгое доказательство для различных условий составляет предмет так называемой Теоремы Литтла, доказанной профессором Массачусетсского технологического института Джоном Литтлом (Little, John Dutton Conant; р. 1928), отцом одного из создателей системы MATLAB Джека Литтла (см. с. 159).

21.6. Система M/M/n/∞ (с ожиданием)

123

работника, каждый обслуживает посетителя в среднем за 1.5 мин (μ = 40). Считая входной поток простейшим, а время обслуживания распределенным по экспоненциальному закону, определим операционные характеристики гардероба как системы массового обслуживания. Коэффициент загрузки равен ρ = λ/(nμ) = 60/(2 · 40) = 0.75, следовательно, рассматриваемая система работоспособна. Расчет предельных вероятностей приведен в табличке: k

(nρ)k /k!

pk

0 1 2 Σ1 Σ2 Σ1 + Σ2

1 1.5 1.125 3.625 3.375 7

0.1428 0.2143 0.1607

Отсюда можно получить операционные характеристики: p2 = 0.36; — вероятность немедленного обслуживания 1 − 1−ρ — средняя длина очереди M [m] = Π/(1 − ρ) = 1.93; — среднее время ожидания в очереди M [m]/λ = 1.93 мин; — среднее время пребывания в гардеробе 1.93 + 1.5 = 3.43 мин; — среднее число занятых работников λ/μ = 1.5.  Замечание. К сожалению, для системы с ожиданием нет аналога теоремы Севастьянова, поэтому предельные вероятности и основанные на них операционные характеристики системы будут отличаться от приведенных выше при отклонении распределения времени обслуживания от экспоненциального. Насколько — это другой вопрос, он требует самостоятельного исследования.

124

Глава 21. Элементы теории массового обслуживания

21.7. Исторические замечания Как мы отмечали во введении, теория массового обслуживания возникла в начале XX века в связи с проблемами организации работы телефонных станций. Первые попытки применить точные методы к анализу телефонных разговоров принадлежат датскому математику и инженеру Агнеру Эрлангу (Erlang, Agner Krarup; 1878–1929). В течение 20 лет Эрланг работал в Копенгагенской телефонной компании в качестве сотрудника, а впоследствии руководителя психофизической лаборатории. По совету своего коллеги Людвига Иенсена, известного нам по одноименному неравенству [4, ч. II, с. 26], Эрланг использовал для этого методы теории вероятностей. В первой статье «Теория вероятностей и телефонные разговоры», опубликованной в 1909 г., он доказал, что телефонные звонАгнер Эрланг ки случайно распределены во времени и подчиняются закону Пуассона и вывел формулу для времени ожидания в однолинейной системе при постоянном времени обслуживания (в нотации Кендалла M/D/1). В 1917 г. он получил классическую формулу для вероятности потерь в модели M/D/n/0, в 1920 г. исследовал модель M/D/n/∞. Именем Эрланга названа единица интенсивности трафика в коммуникационных сетях, а в 1991 г. в компании «Ericsson» был создан язык Erlang, специально предназначенный для программирования устройств телекоммуникации. Следующий шаг в теории был сделан в Берлине, где на центральном почтамте работал молодой математик австрийского происхождения Феликс Полачек (Pollaczek, Felix; 1892–1981). В работе, опубликованной в 1930 г., ему удалось исследовать модель M/G/1. Важно подчеркнуть, что Эрланг и, особенно, Полачек получили свои результаты путем сложных манипуляций с интегральными уравнениями. Им не удалось продвинуться дальше,

21.7. Исторические замечания

125

потому что они не были знакомы с теорией марковских случайных процессов, которая создавалась великими русскими математиками Марковым, Колмогоровым и Хинчиным. Андрей Андреевич Марков-старший14 (1856–1922) родился в Рязани в семье чиновника Лесного департамента. Еще в школе был очень увлечен математикой и изучал ее самостоятельно. После окончания гимназии поступил в Петербургский университет, где слушал лекции выдающегося математика и механика Пафнутия Львовича Чебыш¨ ева (1821– 1894), влияние которого отразилось на всей его научной деятельности. В 1886 г. по предложению Чебыш¨ева избран в Академию наук, в 1886 г. был назначен профессором Петербургского университета. В 1905 г. вышел в отставку со званием заслуженного профессора, но продолжал читать курс теории А. А. Марков вероятностей. Как и все выдающиеся русские математики, А. А. Марков занимался многими разделами этой науки: математическим анализом, теорией чисел, теорией вероятностей. Особую славу принесло ему исследование случайных процессов, названных впоследствии марковскими15 . В то время, когда эта теория была построена, она считалась чисто умозрительной, однако в настоящее время имеет множество приложений. Академик Марков отличался принципиальностью и независимостью суждений. В 1901 г. резко выступил против решения Синода об отлучении от Русской православной церкви Льва Толстого и в знак протеста потребовал отлучить от церкви себя самого. 14

Его сын, Андрей Андреевич Марков-младший (1903–1979), пошел по стопам отца, стал известным советским математиком. Член-корреспондент Академии наук СССР, основатель школы конструктивной математики, автор понятия нормального алгоритма. 15 Это название предложил А. Я. Хинчин.

126

Глава 21. Элементы теории массового обслуживания

Андрей Николаевич Колмогоров (урожденный Катаев) (1903–1987) по праву считается одним из величайших математиков XX века. Один из основоположников современной теории вероятностей, кроме того, им получены фундаментальные результаты в топологии, геометрии, математической логике, теории информации, теории функций, теории дифференциальных уравнений, других областях фундаментальной и прикладной математики. Имя Колмогорова носит множество уравнений, формул и теорем.

А. Н. Колмогоров

Отец Колмогорова по образованию был агрономом, принадлежал к партии правых эсеров и был выслан из Петербурга в Ярославль за политическую деятельность. Мать — дочь попечителя народных училищ Ярославской губернии — умерла при родах. Ребенка воспитывала одна из сестер матери, она официально усыновила Андрея, дала ему фамилию деда по матери и в 1910 г. переехала с ним в Москву для учебы. В гимназии Колмогоров увлекался историей и биологией, отдав предпочтение математике только в студенческие годы. Вся последующая жизнь Колмогорова связана с Московским университетом. Окончив механико-математический факультет (к моменту получения диплома список его научных работ насчитывал уже 10 серьезных публикаций), он в 28-летнем возрасте стал там профессором, основал кафедру теории вероятно-

21.7. Исторические замечания

127

стей, многие годы руководил ею и Межфакультетской лабораторией статистических методов. В 1939 г. в возрасте 35 лет Колмогорова избирают сразу действительным членом (пропуская звание члена-корреспондента) Академии наук СССР и академиком-секретарем Отделения физико-математических наук. Впоследствии он стал Героем Социалистического Труда, лауреатом Сталинской и Ленинской премий, почетным членом многих иностранных академий. Много сил и энергии Колмогоров отдал научно-просветительской работе. Он возглавлял математический отдел Большой Советской Энциклопедии и сам написал много статей для нее. Вместе с другими выдающимися учеными — академиками А. И. Бергом, В. М. Глушковым, А. А. Ляпуновым — боролся за реабилитацию кибернетики, долгое время считавшейся в Советском Союзе «буржуазной лженаукой». В 1970-е гг. на волне всеобщей компьютеризации выдвинул программу перестройки математического образования в стране. Под руководством Колмогорова были разработаны новые школьные программы и написаны современные учебники по элементарной математике. Многие годы тесного и плодотворного сотрудничества связывали его со старшим товарищем и коллегой А. Я. Хинчиным, который начал разработку теории случайных процессов. Она стала областью совместной деятельности двух выдающихся ученых. Общая методика исследования непрерывных во времени марковских случайных процессов с помощью дифференциальных уравнений была изложена Колмогоровым в знаменитой статье16 , опубликованной в 1931 г. на немецком языке и в русском переводе в 1932 г. Эта методика стала классической, она определила всю дальнейшую судьбу теории массового обслуживания. Об этой статье Хинчин отзывался так: «Во всей теории вероятностей ХХ сто16

¨ Kolmogoroff A. Uber die analitischen Methoden in der Wahrscheinlichkeitsrachung // Math. Ann. 1931. Bd 104. S. 415-458; Колмогоров А. Н. Об аналитических методах в теории вероятностей // Успехи математических наук. 1932. Вып. 5. С. 5–41.

128

Глава 21. Элементы теории массового обслуживания

летия трудно указать другое исследование, которое оказалось бы столь основополагающим для дальнейшего развития науки и ее приложений, как эта работа Андрея Николаевича». Александр Яковлевич Хинчин (1894–1959) родился в Калужской области в семье видного инженера-технолога, впоследствии управляющего Кондровскими бумажными фабриками, а затем ставшего профессором и заведующим отделом Института народного хозяйства. В юные годы увлекался театром и поэзией, издал несколько сборников стихов, организовал театральную труппу, в которой выступал актером и режиссером. Литературные интересы долго боролись в нем с математическими, математика победила только в последнем классе реального училища. Увлечение театром и литературой сформировало впоследствии Хинчина как одного из самых блестящих лекторов и авторов математической литератуА. Я. Хинчин ры. И в устной, и в письменной речи он сочетал научность и глубину мысли с легким и изящным стилем изложения. После окончания реального училища Хинчин поступил на физико-математический факультет Московского университета, где сразу занялся научной работой в области функционального анализа, получил ряд наград. Окончив в 1916 г. университет, несколько лет работал на преподавательских должностях в разных вузах. С 1927 г. его деятельность связана с МГУ: он заведовал кафедрой теории вероятностей, кафедрой математического анализа (вплоть до 1957 г.), в 1932–1934 гг. был директором НИИ математики и механики МГУ . Хинчин — один из самых ярких представителей советской математической школы. Им получены основополагающие результаты в теории функций действительного переменного, теории чисел,

21.7. Исторические замечания

129

статистической физике. Вместе с Колмогоровым является создателем теории случайных процессов, за эти работы в 1941 г. им была присуждена Сталинская премия. «Отец кибернетики» Норберт Винер писал: «. . . Хинчин и Колмогоров, два наиболее видных русских специалиста по теории вероятностей, долгое время работали в той же области, что и я. Более двадцати лет мы наступали друг другу на пятки: то они доказывали теорему, которую я вот-вот готовился доказать, то мне удавалось прийти к финишу чуть-чуть раньше их». С задачами анализа телефонного трафика Хинчин впервые столкнулся в 1930 г. по воле случая, когда был избран депутатом Моссовета и вошел в секцию связи, которая в те годы занималась проблемой внедрения в Москве автоматических телефонных станций. По просьбе работников московской телефонной сети он выполнил ряд расчетов, которые дали возможность ввести много технических усовершенствований. В 1932–1933 гг. вышли две его статьи, в которых, в частности, более простым способом, чем у Полачека17 , была получена формула для расчета времени ожидания в системе M/D/1 (формула Хинчина — Полачека). Долгое время Хинчин не занимался этой проблемой, но интерес к ней не пропал. Через 20 лет, в 1955 г., вышла в свет небольшая по объему, но чрезвычайно содержательная монография «Математические методы теории массового обслуживания» [17], которая переиздавалась несколько раз и была переведена на многие иностранные языки. Написанная с несомненным литературным талантом, это книга подвела итог всем исследованиям, которые были выполнены за прошедшее время, она ознаменовала рождение новой области прикладной математики, которой Хинчин дал оригинальное и очень удачное название. С легкой руки Хинчина получили русскоязычные имена и другие понятия, в частности простейший поток, для которого Хинчин, опираясь на раннюю работу шведского инженера и статистика Конни Паль17

Хинчин А. Я. Математическая теория стационарной очереди // Матем. сб. 1932. Т. 39. Вып. 4. С. 73–84.

130

Глава 21. Элементы теории массового обслуживания

ма (Palm, Conrad «Conny»; 1907–1951), доказал предельную теорему (теорема Пальма — Хинчина). ∗ ∗ ∗ Над обобщением классической формулы Эрланга бились многие исследователи. В частности, Хинчин высказал предположение, что она может быть распространена на произвольное время обслуживания, но строго доказать этот факт ему не удалось. Успешное решение проблемы нашел ученик А. Н. Колмогорова Борис Александрович Севастьянов (р. 1923) — членкорреспондент РАН по Отделению матемаБ. А. Севастьянов тики с 1984 г. Окончил Московский университет в 1948 г., с 1969 г. профессор там же. С 1948 г. работает в Математическом институте имени В. А. Стеклова РАН. Лауреат Государственной премии СССР.

Глава 22 Имитационное моделирование систем массового обслуживания За 100 лет существования (если вести отсчет от первой публикации Эрланга) теория массового обслуживания добилась очень больших успехов. Революционные идеи Колмогорова, развитые впоследствии Хинчиным и другими учеными, среди которых большое число соотечественников, позволили найти решение многих задач, важных для практики. Вместе с тем аналитические методы исследования имеют существенные ограничения, уравнения статистической динамики в реальных условиях получаются очень сложными и, как правило, не решаются в конечном виде. По этой причине особую роль в теории массового обслуживания играют методы компьютерного моделирования, при котором работа исследуемой системы имитируется со всеми необходимыми деталями. Как мы отмечали во введении в курс [4, ч. I, с. 24], на этом пути нет принципиальных ограничений по сложности и точности, все определяется мощностью компьютера. Задачей этой главы является первоначальное знакомство с моделированием массового обслуживания на примере двух технологических компьютерных систем: исторически первой, но не потерявшей актуальности GPSS, и вполне современной системы Simulink/SimEvents, расширяющей возможности пакета

132

Глава 22. Имитационное моделирование систем...

MATLAB. Подробное изучение проблем и технологий имитационного моделирования составляет содержание отдельного учебного курса1 .

22.1. Общие вопросы имитационного моделирования Прежде чем рассматривать конкретные системы имитационного моделирования систем массового обслуживания, следует сказать несколько слов о месте, которое они занимают в общей теории моделирования. Моделирование (simulation) — средство изучения системы путем ее замены более удобной для исследования системой (моделью), сохраняющей существенные (c точки зрения цели исследования) черты оригинала. Моделирование является наиболее общим методом научного познания, модели можно классифицировать по-разному, мы будем придерживаться схемы, приведенной на рис. 22.1. Выделенные заливкой узлы иерархии показывают путь от наиболее общего до интересующего нас конкретного класса моделей. На первой развилке мы оставляем в стороне физические модели, где один физический процесс моделируется другим той же (в случае прямой аналогии) или иной (при непрямой аналогии) природы. В отличие от физических математические модели оперируют абстрактными понятиями — числами, выражениями, уравнениями, графами, схемами, алгоритмами и т. д. Следующая развилка предлагает выбор между моделями структуры и моделями поведения. Модели структуры (structure) являются с т а т и ч е с к и м и, они отражают существенМодели и их классификация

1

Автор выражает благодарность коллегам — доцентам факультета информатики А. В. Приступе и Е. А. Червонной за помощь в подготовке демонстрационных примеров.

22.1. Общие вопросы имитационного моделирования

133

Модели Физические (реальные)

Математические (знаковые, абстрактные) Модели структуры

Непрерывные

Модели поведения

Дискретно - событийные

Детерминированные

Стохастические

Аналитические

Имитационные

Рис. 22.1. Классификация моделей

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

Рис. 22.2. Общая модель поведения динамической системы

− → S (t) — внутренние (эндогенные) переменные, описывающие состояние системы в определенный момент времени (их набор определяется целью исследования);

Глава 22. Имитационное моделирование систем...

134

− → − → X (t), Y (t) — входные и выходные внешние (экзогенные) наблюдаемые переменные (они часто называются входными и выходными сигналами); → − ξ (t) — неконтролируемые (случайные) экзогенные переменные. Если они отсутствуют, модель является детерминированной (deterministic), а если присутствуют — стохастической (stochastic); − →  − → − → → − S (t + Δt) = G X (t), S (t), ξ (t) — уравнение (обычно многомерное, т. е. система уравнений), описывающее динамику системы — уравнение состояния. Как видим, будущее состояние зависит не только от экзогенных переменных, но и от текущего внутреннего состояния системы; − → − →  → − Y (t) = F X (t), S (t) — функция, определяющая наблюдаемые выходные переменные (сигналы).

Состояния

Состояния

Изменение состояния системы во времени может вести себя по-разному (рис. 22.3), в соответствии с этим модели поведения делятся на две большие группы: непрерывные и дискретнособытийные.

События

a)

б)

Рис. 22.3. Эволюция состояний системы во времени: непрерывная модель (а); дискретно-событийная модель (б)

В непрерывных (continuous) моделях переменные состояния являются непрерывными функциями времени (рис. 22.3, а).

22.1. Общие вопросы имитационного моделирования

135

В этом случае в уравнениях, описывающих динамику системы, обычно полагают Δt → 0, что приводит к дифференциальным уравнениям. В качестве примера можно привести разнообразные компьютерные игры, в основе которых лежат механические модели, описывающие движение автомобиля, полет снаряда, посадку лунного модуля и т. п. В дискретно-событийных (discrete events) моделях изменения состояния, называемые событиями, происходят скачкообразно (см. рис. 22.3, б ). Сами события считаются мгновенными, их длительность полагается равной нулю. Динамику дискретно-событийной модели нельзя описать дифференциальными уравнениями, состояние системы после события задается некоторым алгоритмом. Замечание. Разумеется, в природе ничто не происходит мгновенно. Дискретно-событийная модель является абстракцией, которая может быть успешно применена, если с т о ч к и з р е н и я ц е л и исследования длительностью событий можно пренебречь. Интересующие нас модели массового обслуживания по своей сути относятся к дискретно-событийным стохастическим моделям, ибо они абстрагируются от детального описания процессов, происходящих в системе при наступлении события. К примеру, вместо непрерывных действий «клиент открывает дверь, подходит к стойке, подает пальто и т. д.» рассматривается обобщающее мгновенное событие «клиент пришел в гардероб».

Последняя развилка обозначает выбор между построением аналитических моделей и компьютерной имитацией (simulation). Типичным примером аналитической дискретно-событийной стохастической модели являются уравнения Чепмена — Колмогорова для системы массового обслуживания. Поскольку в модели присутствуют случайные факторы, то точно предсказать траекто→ − рию изменения состояния во времени S (t) невозможно, эти уравнения являются не обычными уравнениями динамики, а уравнениями стохастической динамики, описывающими эволюцию во → (t). времени в е р о я т н о с т е й состояний P− S

136

Глава 22. Имитационное моделирование систем...

В отличие от аналитического подхода имитация воспроизво→ − дит на компьютере сам процесс S (t), шаг за шагом передвигаясь по временной оси и вычисляя новое состояние с помощью соот− → → − → − → − ношения S (t + Δt) = G( X (t), S (t), ξ (t)), в котором стохасти→ − ческие воздействия ξ (t) моделируются генераторами случайных → (t) производятся многократчисел. Для оценки распределений Pˆ− S → − ные прогоны модели при случайных реализациях ξ (t), называемые статистическими испытаниями (statistical test). Несмотря на различие подходов, аналитическое и имитационное моделирование имеют много общего. На рис. 22.4 приведена общая методологическая схема исследования стохастических динамических систем, в которой левый столбец соответствует аналитическому подходу, а правый — имитационному. Сравнение аналитического моделирования с имитационным

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

22.1. Общие вопросы имитационного моделирования

Системный анализ

137

Выявление существенных переменных (эндогенных, экзогенных) Описание алгоритма функционирования системы

Построение модели системы

Иссле дование модели

Составление уравнений стохастической динамики

Создание имитационной модели

Решение уравнений стохастической динамики

Статистические испытания

Определение операционных характеристик системы Аналитическое или численное

Оптимизация модели

Статистическое

Оптимизация управляемых переменных Аналитическая или численная

Стохастическая

Рис. 22.4. Сравнение аналитического метода исследования стохастических систем с имитационным

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

Глава 22. Имитационное моделирование систем...

138

лирования содержится в книге [9], которая по праву может считаться лучшим введением в предмет. Механизм дискретнособытийного моделирования

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

Описание модели на входном языке

Транслятор

t1 Блок 1

...

t2 Блок 2

...

t3

t

Блок 3

Рис. 22.5. Общая структура системы дискретно-событийного моделирования

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

22.1. Общие вопросы имитационного моделирования

139

может происходить по истечении заданного времени либо при наступлении иного специально предусмотренного события. На время обработки любого события системные часы останавливаются, в модельном времени событие считается мгновенным. Обработка событий. Каждому типу события в рабочей модели сопоставлен специализированный блок программного кода. Обработка события состоит в изменении переменных состояния модели, в том числе переменных, накапливающих статистику для будущего отчета. Запуск блока обработки события производится управляющей программой, которая рассчитывает типы и моменты наступления очередных событий t1 , t2 , t3 , . . . и осуществляет движение модельного времени. Движение модельного времени. Движение модельного времени можно проводить двумя способами: 1) равномерными приращениями; 2) шагами до следующего события. Процесс управления моделированием при равномерных приращениях предельно прост: управляющая программа циклически производит приращение модельного времени на один квант (t = t + Δt) и проверяет, имеются ли события, которые должны произойти в данный момент. Если нет, то цикл пустой, а если таковые есть, то запускаются соответствующие блоки обработки, после чего управление возвращается управляющей программе. Однако подобный механизм приводит к таким потерям ресурсов компьютера при переборе пустых циклов (их подавляющее большинство), что на практике он не используется. При движении шагами до следующего события создается и постоянно обновляется упорядоченный во времени список ждущих событий. После обработки текущего события модельное время сдвигается сразу до момента, соответствующего следующему событию. Потерь производительности не происходит, но за это приходится расплачиваться более сложным алгоритмом актуализации списка событий.

140

Глава 22. Имитационное моделирование систем...

22.2. Система моделирования GPSS Система GPSS (General Purpose Simulation System — Система моделирования общего назначения) достойна включения в Книгу рекордов Гиннеса2 как долгожитель среди проблемно ориентированных систем программирования. Первая версия системы была разработана основателем дискретно-событийного подхода Джефри Гордоном еще в 1961 г. для ЭВМ первого поколения IBM–704 (см. исторические замечания в конце главы). В те годы общение программиста с компьютером происходило на уровне перфокарт, поэтому синтаксис входного языка весьма архаичен. Однако глобальные идеи, положенные в основу системы, оказались столь удачными, что она пережила все поколения ЭВМ и продолжает благополучно существовать, опережая по популярности самые модные и современные системы дискретно-событийного моделирования. В эпоху мейнфреймов GPSS развивалась в недрах корпорации IBM, начиная с середины 1980-х гг. разработкой версий для персональных компьютеров занимается американская компания «Minuteman Software». С 1993 г. она регулярно выпускает версии системы GPSS World, совместимые по входному языку с классическими, но значительно более удобные для пользователя3 . Система пользуется популярностью в России, изданы учебники [3, 13, 15, 16], для обмена опытом имеется специальный портал www.gpss.ru. 2

Книга рекордов Гиннеса (The Guinness Book of Records) — ежегодный сборник экстремальных природных величин, достижений человека и животных. Впервые опубликована в 1955 г., идея принадлежала управляющему пивоваренной компании Guinness Brewery, посчитавшему, что издание будет полезным для завсегдатаев пабов при поисках ответов на вопросы всевозможных викторин. Издается на многих языках, общий тираж в 2003 г. превысил 100 млн экз. 3 На официальном сайте компании www.minutemansoftware.com доступна для скачивания бесплатная студенческая версия (полнофункциональная, но с ограниченным числом блоков).

22.2. Система моделирования GPSS

141

Реальным заявкам (клиентам, требованиям) в модели GPSS соответствуют динамические объекты — транзакты. В процессе моделирования они генерируются и уничтожаются программой. С каждым транзактом могут быть связаны параметры (например, приоритеты заявок). Обслуживающие устройства моделируются двумя видами статических объектов — одноканальными (FACILITIES) и многоканальными (STORAGES) устройствами. Для накопления статистики существуют специальные статистические объекты — очереди (QUEUES) и таблицы (TABLES). Процесс моделирования обслуживания в GPSS описывается как процесс прохождения транзактов через блок-схему (flowchart), построенную из стандартных блоков. Их набор сконструирован таким образом, чтобы отразить наибольшее число ситуаций, возникающих в процессе функционирования реальной системы массового обслуживания. Общее число типов блоков более сотни, они делятся на несколько специфических групп. В качестве примера в табл. 22.1 приведены несколько наиболее употребительных блоков, которые нам встретятся в примерах. Основные понятия

Поскольку графических средств изображения блок-схемы в классической GPSS нет4 , она изображается линейной последовательностью операторов входного языка. Как уже отмечалось, его синтаксис весьма старомодный, он восходит к перфокарточным временам, когда каждый оператор программы записывался на новой строке и переносился на отдельную перфокарту. Оператор идентифицируется уникальным именем и может содержать несколько операндов, разделенных запятыми; набор операндов строго фиксирован для каждого типа блока. Оператор может иметь метку.

Формат программы

4

В новейших реализацияx GPSS World можно воспользоваться графическими редакторами блок-схем.

Глава 22. Имитационное моделирование систем...

142

Таблица 22.1. Примеры блоков в системе GPSS Тип блока

Функция

Блоки для работы с транзактами GENERATE Создать транзакт TERMINATE Уничтожить транзакт ADVANCE Задержать транзакт в блоке Блоки для работы с обслуживающими устройствами SEIZE Занять одноканальное устройство RELEASE Освободить одноканальное устройство STORAGE Описать многоканальное устройство ENTER / LEAVE Занять / освободить канал в многоканальном устройстве Блоки, изменяющие маршруты движения транзактов TRANSFER Безусловный переход к другому блоку GATE Проверка, есть ли в многоканальном устройстве свободные каналы Блоки для работы с переменными, функциями, массивами SAVEVALUE Изменить значение переменной Блоки для сбора статистики QUEUE Отметить время вхождения в очередь DEPART Отметить время выхода из очереди QTABLE Расширенный сбор данных о времени ожидания в очереди

22.2. Система моделирования GPSS

143

В качестве примера рассмотрим оператор Метка Label1

Оператор (имя блока) GENERATE

Операнды 16,8

Комментарий ;Создание транзакта

Он определяет блок непрерывной генерации транзактов, причем каждый последующий отстоит от предыдущего на время, распределенное по р а в н о м е р н о м у закону в границах (16 ± 8) единиц модельного времени. Если промежутки времени должны быть распределены по другому закону, на место операндов в операторе GENERATE должно быть подставлено выражение, написанное на вспомогательном языке PLUS (Programming Language Under Simulation), расширяющем возможности GPSS World по сравнению со стандартным GPSS. В частности, для моделирования экспоненциального распределения используется встроенная PLUS-функция EXPONENTIAL(N,a,m), где первый оператор задает номер генератора случайных чисел (всего их 8), а второй и третий — параметры сдвига и масштаба линейного преобразования, превращающего стандартное экспоненциальное распределения (с единичным математическим ожиданием) в требуемое. Для того чтобы продемонстрировать основные возможности системы GPSS World, рассмотрим несколько примеров. Они полностью соответствуют простейшим системам массового обслуживания с потерями и ожиданием, которые мы рассматривали при построении аналитических моделей, поэтому у нас имеется замечательная возможность сравнить теоретические операционные характеристики с экспериментальными, полученными в результате имитационного моделирования. П р и м е р 1 (парикмахерская). В качестве первого примера рассмотрим многоканальную систему M/M/4/0, моделирующую работу парикмахерской с одним общим залом и четырьмя креслами без мест для ожидания (см. с. 118). Листинг этой модели на входном языке GPSS World с достаточными для понимания комментариями приведен на рис. 22.6. На вход системы поступает простейший поток клиентов с ин-

144

Глава 22. Имитационное моделирование систем...

;МОДЕЛЬ ПАРИКМАХЕРСКОЙ С ЧЕТЫРЬМЯ КРЕСЛАМИ ;Описания Barber STORAGE 4 ;4-канальное устройство обслуживания Barber ;Алгоритм моделирования GENERATE (EXPONENTIAL(1,0,3.75)) ;Генерируем заявку с ;интервалом, распределенным по экспоненци;альному закону со средним значением 3.75 мин. SAVEVALUE Arrived+,1 ;Счетчик числа пришедших клиентов. GATE SNF Barber,Reject ;Проверка (Storage Not Full), ;есть ли в устройстве Barber свободные ;каналы (кресла). Если нет, переход на ;метку Reject. ENTER Barber ;Если есть, то занятие свободного канала ;в устройстве Barber. ADVANCE (EXPONENTIAL(2,0,15)) ;Обслуживание в течение ;времени, распределенного по экспоненци;альному закону со средним значением 15 мин. LEAVE Barber ;Освобождаем канал (кресло). SAVEVALUE Served+,1 ;Счетчик числа обслуженных клиентов. Reject TERMINATE ;Уничтожаем заявку. ;Таймер продолжительности моделирования 10 ч GENERATE (60#10) ;Единственная заявка в этом сегменте ;программы будет сгенерирована на 600-й мин, ;символ # в GPSS означает умножение. TERMINATE 1 ;Сгенерированная заявка тут же уничтожится, ;процесс моделирования остановится.

Рис. 22.6. Листинг программы моделирования парикмахерской на входном языке GPSS World

тенсивностью λ = 16 чел./ч, т. е. время между последовательными заявками распределено по экспоненциальному закону со средним значением m = 60/16 = 3.75 мин. Время обслуживания также распределено по экспоненциальному закону со средним значением 15 мин. Единицу модельного времени выбрали равной 1 мин, общее время моделирования установили равным 10-часовому рабочему дню. После трансляции и запуска скомпилированной модели система выдаст стандартный отчет (рис. 22.7). Из него следует, что за

22.2. Система моделирования GPSS

145

GPSS World Simulation Report - Barber4.1.1 Wednesday, March 06, 2013 14:19:17 START TIME 0.000 LABEL

REJECT

STORAGE BARBER SAVEVALUE ARRIVED SERVED

LOC 1 2 3 4 5 6 7 8 10

END TIME 600.000 BLOCK TYPE GENERATE SAVEVALUE GATE ENTER ADVANCE LEAVE SAVEVALUE TERMINATE TERMINATE

CAP. REM. MIN. MAX. 4 0 0 4 RETRY 0 0

BLOCKS 10

FACILITIES 0

STORAGES 1

ENTRY COUNT CURRENT COUNT RETRY 157 0 0 157 0 0 157 0 0 99 0 0 99 4 0 95 0 0 95 0 0 153 0 0 1 0 0

ENTRIES AVL. 99 1

AVE.C. UTIL. RETRY DELAY 2.873 0.718 0 0

VALUE 157.000 95.000

Рис. 22.7. Стандартный отчет GPSS о моделировании парикмахерской. Для каждого блока указаны: LABEL — метка, LOC(ATION) — порядковый номер в блок-схеме, BLOCK TYPE —тип; ENTRY COUNT — счетчик транзактов, прошедщих через блок; CURRENT COUNT — текущее число транзактов в блоке в момент окончания моделирования. Для многоканальных устройств (STORAGES) указаны: CAP(ACITY) – емкость (число каналов); REM(AIN) — число оставшихся свободных каналов в момент окончания моделирования; MIN, MAX, AVE(RAGE).C. — наименьшее, наибольшее и среднее число занятых каналов в процессе моделирования; UTIL(IZATION) — коэффициент использования каналов

146

Глава 22. Имитационное моделирование систем...

время моделирования в парикмахерскую пришло N = 157 клиентов, из них уже обслужено 95, находятся на обслуживании еще 4, остальные m = N − 99 = 58 получили отказ, т. е. экспериментально измеренная вероятность отказа равна pˆотк = m/N = 0.369. Как следует из формулы Эрланга, теоретическая вероятность отказа для данного случая составляет 0.311. Расхождение на первый взгляд существенное, но нельзя забывать, что полученное экспериментальное значение с л у ч а й н о е, оно всегда будет отличаться от теоретического. Для того чтобы грамотно ответить на вопрос, согласуются ли результаты эксперимента с теорией, следует не только найти точечную оценку вероятности отказа, но и построить доверительный интервал (confidence interval) 5 для полученной оценки. Как известно, число появлений события m в схеме независимых испытаний с N повторениями подчиняется биномиальному закону со средним значением M [m] = N p и дисперсией D[m] = N p(1 − p), где p — вероятность события. Следовательно, дисперсия оценки D[m/N ] = p(1 − p)/N , а ее среднеквадратичное отклонение σ[ˆ p] = pˆ(1 − pˆ)/N . При большом числе испытаний N (N > 100) оно хорошо аппроксимируется нормальным распределением (рис. 22.8). Таким образом, если задаться доверительной вероятностью P Рис. 22.8. Довери- попадания оценки в симметричный доверительный интервал тельный интервал с границами pˆ ± Δ, то эти для точечной оценки границы могут быть вычислены по формуле 

pˆ(1 − pˆ) 1+P , Δ=Ψ 2 N 5

Живое и популярное изложение теории статистического оценивания можно прочитать в гл. 14 классического учебника «Теория вероятностей» выдающегося педагога профессора Елены Сергеевны Вентцель, о которой мы уже упоминали ранее [4, ч. III, с 114.]. Начиная с первого издания 1962 г. книга выдержала множество перепечаток различными издательствами.

22.2. Система моделирования GPSS

147

где Ψ(P ) — функция, обратная функции стандартного нормального распределения (см. с. 61).  В нашем случае σ[ˆ p] = 0.369(1 − 0.369)/157 = 0.039. Если принять доверительную вероятность P = 0.9, то Ψ((1 + 0.9)/2) = = Ψ(0.95) = 1.64. Тогда Δ = 1.64 · 0.039 = 0.063, следовательно, интервальная оценка вероятности pˆ = 0.369 ± 0.063. Как видим, теоретическое значение 0.311 попадает в этот интервал, следовательно, при данном объеме экспериментальных данных и выбранной доверительной вероятности расхождение теории и практики следует признать несущественным. Попытаемся повысить точность эксперимента, увеличив время моделирования. Как видно из табл. 22.2, оценка вероятности отказа сходится к теоретической величине, вычисленной по формуле Эрланга.  Таблица 22.2. Интервальные оценки вероятности отказа при различном времени моделирования. Доверительная вероятность P = 0.9 Время 10 ч 24 ч 1 мес.

Arrived (N ) 157 370 11345

Served (N − m) 95 253 7816

pˆ 0.395 0.316 0.311

±Δ 0.064 0.024 0.004

П р и м е р 2 (очередь в гардероб). Второй пример использования GPSS World моделирует систему с ожиданием, которую мы также исследовали аналитически (см. с. 122). На рис. 22.9 приведен листинг модели на входном языке, а на рис 22.10 — стандартный отчет о моделировании. Общая схема модели достаточна ясна из комментариев к программе, ее особенностью является то, что для подробного описания очереди (ей присвоено имя Line) оператором QTABLE введена таблица частот (гистограмма), описывающая статистическое распределение времени ожидания в данной очереди. Параметры

148

Глава 22. Имитационное моделирование систем... ;МОДЕЛЬ ГАРДЕРОБА С ДВУМЯ РАБОТНИКАМИ

;Описания Cloakroom Waiting

STORAGE 2 ;2-канальное устройство Cloakroom QTABLE Line 0,1,12 ;Таблица частот с именем Waiting ;для очереди Line, имеющая ;12 интервалов по 1 мин каждый. ;Процесс обслуживания в гардеробе GENERATE (EXPONENTIAL(1,0,1)) ;Время между приходами ;клиентов распределено по экспоненциаль;ному закону со средним значением 1 мин. QUEUE Line ;Отмечаем время постановки в очередь ;с именем Line. ENTER Cloakroom ;Занимаем гардеробщика. DEPART Line ;Отмечаем время выхода из очереди. ADVANCE (EXPONENTIAL(2,0,1.5)) ;Обслуживание в течение ;времени, распределенного по экспонен;циальному закону со средним ;значением 1.5 мин. LEAVE Cloakroom ;Освобождаем гардеробщика. TERMINATE ;Уничтожаем заявку. ;Таймер времени моделирования GENERATE (10#60) ;Время моделирования 10 ч. TERMINATE 1

Рис. 22.9. Листинг модели гардероба с очередью на входном языке GPSS World

0, 1, 12 означают, что нижняя граница измеряемой величины равна 0 (имеются в виду минуты), ширина каждого разряда гистограммы 1 мин, наибольшее число разрядов 12. Анализируя стандартный отчет о моделировании (рис. 22.10), видим, что за 10-часовой рабочий день в гардероб пришли 579 посетителей, на момент окончания работы осталось два, оба обслуживаются (в блоке ADVANCE есть два текущих транзакта). Краткая статистика очереди (QUEUE) с именем Line показывает, что ее наибольшая длина MAX равнялась 10, в момент окончания работы очереди нет (CONT=0). Всего в очередь пришло ENTRY = 579 транзактов, из них ENTRY(0) = 224 были обслуже-

22.2. Система моделирования GPSS

149

GPSS World Simulation Report - Model_3.39.1

Wednesday, March 13, 2013 15:57:28 START TIME 0.000

LABEL

END TIME 600.000

LOC 1 2 3 4 5 6 7 8 9

BLOCK TYPE GENERATE QUEUE ENTER DEPART ADVANCE LEAVE TERMINATE GENERATE TERMINATE

BLOCKS 9

FACILITIES 0

ENTRY COUNT CURRENT COUNT RETRY 579 0 0 579 0 0 579 0 0 579 0 0 579 2 0 577 0 0 577 0 0 1 0 0 1 0 0

QUEUE LINE

MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME 10 0 579 224 1.184 1.227

STORAGE CLOAKROOM

CAP. REM. MIN. MAX. 2 0 0 2

TABLE WAITING

MEAN 1.227

ENTRIES AVL. 579 1

STD.DEV. 1.644

-

AVE.(-0) RETRY 2.001 0

AVE.C. UTIL. RETRY DELAY 1.481 0.740 0 0

RANGE _ 0.000 1.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000

STORAGES 1

0.000 1.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000 10.000

RETRY FREQUENCY CUM.% 0 224 38.69 119 59.24 88 74.44 74 87.22 38 93.78 14 96.20 10 97.93 5 98.79 1 98.96 5 99.83 1 100.00

Рис. 22.10. Стандартный отчет о моделировании работы гардероба

150

Глава 22. Имитационное моделирование систем...

ны немедленно. Средняя длина очереди AVE.CONT равна 1.481, среднее время ожидания с учетом всех транзактов AVE.TIME = = 1.227 мин, среднее время ожидания без учета случаев, когда обслуживание начиналось немедленно AVE.(-0) = 2.001 мин. Подробная статистика времени ожидания t в очереди приведена в распечатке таблицы Waiting в конце отчета. Кроме известного уже значения среднего времени ожидания приводится среднеквадратичное отклонение этой величины STD.DEV равное 1.644, а также гистограмма выборочного распределения. В гистограмме для каждого диапазона RANGE указаны его границы: левая граница < t  правая граница, число попаданий в диапазон FREQUENCY и накопленный процент попаданий, начиная с начального диапазона CUM.%. Отсюда, в частности, еще раз видно, что в 38.69 % случаев время ожидания равно 0, т. е. обслуживание производится немедленно (теоретическое значение этой вероятности, как мы знаем, равно 0.36), а в 96.20 % случаев время ожидания в гардеробе не превышает 5 мин. В отчете также имеется краткая статистика работы многоканального устройства STORAGE с именем Cloakroom. Среднее число занятых каналов AVE.C составляет 1.481, откуда коэффициент использования каналов UTIL равен 0.740 (теоретическое значение 0.75).  Полезным свойством GPSS является возможность автоматизации экспериментирования с построенной моделью с целью выявления существенных управляемых переменных и их оптимизации, т. е. возможность поддержки последнего приведенного на рис. 22.4 этапа моделирования. Поскольку экспериментальные оценки операционных характеристик всегда случайные, применяются методы многомерного статистического анализа, в первую очередь дисперсионный анализ (ANalysis Of VAriance — ANOVA). Методика экспериментирования, а также многочисленные Экспериментирование с моделями в GPSS

22.3. Дискретно-событийное моделирование в MATLAB

151

примеры моделирования разнообразных систем массового обслуживания с подробными объяснениями приведены в фирменном учебном пособии по системе GPSS World [16].

22.3. Дискретно-событийное моделирование в MATLAB/Simulink Разработанная компанией «MathWorks» и получившая широкое распространение система компьютерной математики MATLAB (см. исторические замечания в конце главы) поставляется вместе с пакетом расширений Simulink, который обладает богатейшими возможностями для имитационного моделирования самых различных систем — как непрерывных, так и дискретно-событийных. Механизм работы Simulink основан на общей модели динамической системы, представленной на рис. 22.2: на фазе раз→ − работки модели составляются уравнения динамики S (t + Δt) =  − → − → → − = G X (t), S (t), ξ (t) , на фазе моделирования встроенный в систему решатель (solver) производит их решение, передвигаясь по временной оси с малыми (для моделирования непрерывных процессов) или существенными (для дискретно-событийного моделирования) приращениями времени Δt. Попутно вычисляются вы− → − → →  − ходные сигналы Y (t) = F X (t), S (t) , по которым можно судить о поведении системы. Вся мощь и оригинальность системы Simulink состоит в том, что составление уравнений динамики происходит автоматически средствами визуального объектно-ориентированного проектирования. Модель строится в графическом окне из визуальных объектов — блоков, которые берутся из библиотеки. Каждый блок представляет собой типовую модель подсистемы нижнего уровня со входами, выходами и внутренними состояниями. Щелкнув мышью по блоку, можно просмотреть его свойства (параметры) и при необходимости изменить их. Блоки соединяются линиями,

152

Глава 22. Имитационное моделирование систем...

передающими сигналы с выходов одних блоков на входы других. Для наглядного отображения сигналов имеется набор блоков, моделирующих виртуальные измерительные устройства — счетчики, осциллографы, графопостроители и т. п. При запуске модели они «оживают», возникает иллюзия реального функционирования системы. Функциональные возможности системы Simulink определяются богатством библиотеки стандартных блоков. В этом отношении с ней трудно конкурировать: в стандартной поставке есть десятки специализированных библиотек для моделирования самых различных систем — механических, гидравлических, электрических, систем связи, сигнализации, управления и т. д. Пакет MATLAB/Simulink является неограниченно расширяемым, возможна разработка специализированных блоков для нужд пользователей. Для дискретно-событийного моделирования в пакете Simulink имеется специализированная библиотека SimEvents, ориентированная на модели массового обслуживания и работающая с решателем, передвигающим системное время шагами до будущего события. В целом идеология построения модели в SimEvents похожа на GPSS: транзакты, называемые здесь сущностями (entities), создаются генераторами (entity generators), затем проходят через блок-схему и в конце концов учичтожаются, попадая в сточные устройства (entity sinks). Как и в GPSS, блок-схема строится из стандартных блоков, однако, в отличие от GPSS, работа с блоксхемой происходит с помощью удобного графического редактора. У каждого блока есть входы (IN) и выходы (OUT) для транзактов, соединяя их стрелками, можно легко задавать и изменять алгоритм моделирования. Набор (палитра) стандартных блоков SimEvents включает одно- и многоканальные обслуживающие устройства, накопители для очередей с различной дисциплиной обслуживания, переключатели и т. п. Кроме основных входов и выходов для транзактов SimEvents

22.3. Дискретно-событийное моделирование в MATLAB

153

блоки могут иметь дополнительные управляющие входы, например, для генераторов случайных чисел, а также дополнительные сигнальные выходы для подключения виртуальных измерительных устройств. В качестве простейших примеров, иллюстрирующих основные возможности MATLAB/SimEvents, рассмотрим те же модели, которые мы ранее исследовали аналитически и реализовывали в GPSS. П р и м е р 1 (парикмахерская). На рис. 22.11 приведена

Рис. 22.11. Модель парикмахерской с четырьмя креслами в системе MATLAB/SimEvents

модель парикмахерской с четырьмя креслами, построенная в графическом редакторе Simulink. Структура и параметры модели полностью соответствуют тем, которые были выбраны при GPSSмоделировании (см. с. 143). Переключатель выхода аналогичен блоку GATE, он направляет транзакт на OUT2, если устройство, подключенное к OUT1, занято. Для измерения операционных характеристик к контрольным выходам некоторых блоков подключены счетчики. Продолжительность моделирования установлена равной 10 ч, счетчики на рисунке показывают выходные сигналы в момент окончания моделирования.

154

Глава 22. Имитационное моделирование систем...

Численные результаты эксперимента оказались, разумеется, отличными от результатов GPSS, но достаточно близкими к ним с точки зрения статистики. Действительно, из 159 пришедших клиентов обслужено 118, в момент окончания моделирования еще 2 человека находятся на обслуживании. Интервальная оценка вероятности потери клиента (при доверительной вероятности 0.9) равна pˆ = 39/159 ≈ 0.258 ± 0.057. При увеличении продолжительности моделирования до 24 ч, получается pˆ = 0.293 ± 0.039.  П р и м е р 2 (очередь в гардероб). На рис. 22.12 приведена графическая блок-схема модели для гардероба с двумя

Рис. 22.12. Модель гардероба с двумя работниками в системе MATLAB/SimEvents

работниками, аналогичная GPSS-модели в примере на с. 147. Условные обозначения и логика функционирования этой простейшей модели вполне ясны из рисунка, более подробные сведения о системе SimEvents можно почерпнуть из справочной литературы и фирменного руководства [18].  Как видим, простые модели систем массового обслуживания

22.3. Дискретно-событийное моделирование в MATLAB

155

могут создаваться с помощью нескольких щелчков мышью, но эта простота имеет и обратную сторону: стандартные отчеты SimEvents в целом беднее, чем у GPSS, к тому же моделирование идет значительно медленнее. Принципиальной особенностью Simulink является тесная интеграция с окружающей средой MATLAB. Построенная модель может запускаться из MATLAB-программы, принимать из нее параметры и возвращать в рабочую среду результаты моделирования. Тем самым предоставляется возможность воспользоваться всей мощью пакета MATLAB для обработки результатов экспериментов. Поясним механизм взаимодействия Simulink со средой MATLAB на простейшем примере. Экспериментирование с моделями в Simulink

П р и м е р. В качестве объекта эксперимента возьмем знакомую нам модель парикмахерской без мест для ожидания. Условия функционирования прежние (см. пример на с. 118): поток клиентов простейший с интенсивностью 16 чел./ч (средний интервал времени между клиентами 3.75 мин), среднее время обслуживания 15 мин, выручка от обслуживания одного клиента 10 у. е., расходы на содержание одного обслуживающего прибора (зарплата мастера и сопутствующие расходы) составляют 20 у. е. в час. Поставим в этих условиях задачу оптимизации числа приборов (кресел) по критерию среднесуточной прибыли. При малом числе следует ожидать потерю выручки из-за отказов в обслуживании, а при большом — непомерно возрастают расходы на заработную плату мастеров. Графическая модель системы с именем Hairdressing приведена на рис. 22.13. Она спроектирована на основе модели, представленной на рис. 22.11, но имеет некоторые отличия. Во-первых, так как процесс моделирования запускается из программы MATLAB и будет невидимым, убраны визуальные счетчики, вместо них вставлены блоки, передающие число обслуженных и потерянных

Глава 22. Имитационное моделирование систем...

156

Event-Based Random Number Distribution = Exponential Mean = 15

t IN

OUT OUT1 OUT

OUT2 Time-Based Entity Generator

#a

IN

IN

N1 To Workspace1

Entity Sink1

n-line Barber rejected

Переключатель выхода

Distribution = Exponential Mean = 3.75

IN

#a

N0 To Workspace

Entity Sink

% Установка времени моделирования (в минутах) Time=7*24*60; % 7 суток % Цикл по числу обслуживающих приборов for n=1:6; sim(’Hairdressing’); served=N1.signals.values(end); rejected=N0.signals.values(end); arrived=served+rejected; income=served*10; salary=20*n*Time/60; profit(n)=(income-salary)/Time*1440; Delta(n)=1.64*sqrt(served*rejected... /arrived)*10/Time*1440; end;

% % % % % % % % %

Запуск модели Обслужено клиентов Потеряно клиентов Пришло клиентов всего Выручка Зарплата Среднесуточная прибыль 90% доверительный интервал для прибыли

% Построение графика hold plot([1:6], profit,’-ro’) grid on plot([1:6],profit-Delta,’k^’) plot([1:6],profit+Delta,’kv’)

Рис. 22.13. Графическая Simulink-модель Hairdressing и MATLABпрограмма эксперимента по исследованию зависимости среднесуточной прибыли парикмахерской от числа кресел. Из программы в модель передаются параметры: время моделирования Time и число кресел n. Из модели в рабочую область (To Workspace) передаются значения сигналов: число обслуженных N1 и потерянных N0 заявок в момент окончания моделирования (end)

22.3. Дискретно-событийное моделирование в MATLAB

157

клиентов в рабочую область (workspace) MATLAB. Во-вторых, число 4, определяющее число приборов в блоке обслуживания, заменено на переменную (параметр модели) n, кроме того, введена переменная (параметр решателя) Time, задающая время моделирования. На этом же рисунке приведена главная MATLAB-программа, устанавливающая недоопределенные параметры модели, запускающая процесс моделирования и принимающая его сигналы. Обработка результатов состоит в построении графика среднесуточной прибыли с доверительными интервалами, рассчитанными по методике, изложенной на с. 146. Результаты эксперимента приведены на рис. 22.14. Среднесуточная прибыль действительно имеет максимум, оптимальное число кресел в заявленных условиях равно четырем.  800 700 600 500 400 300 200

1

2

3

4

5

6

Рис. 22.14. Зависимость суточной прибыли парикмахерской от числа кресел (средние значения и доверительные интервалы с доверительной вероятностью 0.9). Время моделирования 7 сут

158

Глава 22. Имитационное моделирование систем...

22.4. Исторические замечания Основатель дискретно-событийного моделирования Джеффри Гордон (Gordon, Geoffrey; 1924–1989) родился в Англии. В самом начале 1950-х гг. стал заниматься моделированием на аналоговых компьютерах, а с 1954 г. — на цифровых. Перебравшись в Соединенные Штаты в 1955 г., продолжил работу по цифровому моделированию сначала в корпорации «Westinghouse», затем в знаменитой «Bell Telephone Laboratories», где написал программу моделирования переключательных систем, основанную на «диаграммах последовательностей», использующих символику теории графов. В 1960 г. Гордон перешел на работу в Отделение разработки перспективных систем компании IBM, где велись интенсивные работы по проектированию систем телеобработки — предшественников современных компьютерных сетей. Создание реалистичных симуляторов таких систем сулило большую пользу, поэтому компания поддержала идею Гордона разработать язык блок-схем для описания сложных систем, развивающий идеи диаграммы последовательностей. Гордон был чистым программистом, но он тесно взаимодействовал с инженерами-разработчиками моделируемых систем, которые постоянно давали ему новые идеи. Работа продвигалась быстро, к октябрю 1960 г. была готова версия программы с руководством пользователя, имевшая статус внутрифирменного конфиденциального продукта. В то время она не имела официального имени и между собой ее называли Gordon Simulator. В 1961 г. система была полностью переработана и выпущена в свет как официальный продукт GPSS-I, работающий на IBM–704 — первой массовой ЭВМ с плавающей арифметикой. Гордон проработал в компании IBM много лет, за это время было выпущено несколько версий GPSS для различных поколений

22.4. Исторические замечания

159

ЭВМ, система и ее автор стали широко известными в компьютерном мире. Он написал ряд книг по теории моделирования, после ухода на пенсию несколько лет преподавал в университете. ∗ ∗ ∗ Самая престижная награда в области компьютерных наук Computer Pioneer 6 за 2012 г. с формулировкой «За улучшение качества программ компьютерной математики, повышение их доступности и создание MATLAB» была присуждена математику и программисту, одному из основателей компании «MathWorks» Кливу Молеру. Этим подчеркнута выдающаяся роль, которую в настоящее время играют в исследованиях и обучении система MATLAB и ее самое значительное расширение Simulink. Клив Молер (Moler, Cleve Barry; р. 1939) вырос в семье журналистов в г. Солт Лейк Сити, штат Юта, учился в Калифорнийском технологическом институте. После защиты диссертации по математике в Стенфордском университете стажировался в Швейцарии, где, в частности, разработал новый численный метод расчета вибраций той самой L-образной мембраны, которая Логотип «MathWorks» впоследствии стала логотипом компании «MathWorks». В течение ряда лет он занимал должность профессора математики в Мичиганском и Стенфордском университетах, 12 лет 6

Медаль Computer Pioneer была учреждена в 1981 г. международным Институтом инженеров по электротехнике и электронике (Institute of Electrical and Electronics Engineers — IEEE), самой авторитетной организацией в этой области. IEEE объединяет более 170 стран, издает третью часть мировой технической литературы, касающейся применения радиоэлектроники. Из отечественных ученых в разное время эту награду получили: пионер отечественной кибернетики А.А. Ляпунов, создатель первой советской ЭВМ С.А. Лебедев и идеолог АСУ В. М. Глушков (1996), разработчики ЭВМ серии «Минск» Г. П. Лопато и Г. К. Столяров (2000).

160

Глава 22. Имитационное моделирование систем...

проработал профессором и заведующим кафедрой информатики в Университете Нью-Мексико. В период работы в Нью-Мексико Молер тесно сотрудничал со знаменитой Argonne National Laboratory7 , участвуя в разработке LINPACK и EISPACK — высококачественных, хорошо документированных библиотек программ на Фортране для решения стандартных задач линейной алгебры на суперкомпьютерах (с тех пор производительность суперкомпьютеров традиционно измеряется на пакете LINPACK). Система MATLAB начала свою жизнь в 1976 г. как небольшой, чисто учебный матричный калькулятор, обеспечивающий вызов базовых подпрограмм LINPACK и EISPACK. Она предназначалась для студентов, которые интересовались математической стороной решаемых задач и не желали отвлекаться на вопросы программирования на Фортране. Для этих целей Молер разработал простой входной язык, написал компилятор, все это в порядке личной инициативы. В 1979–1980 гг. Молер провел годичный творческий отпуск в Стенфордском университете, где использовал MATLAB на курсах повышения квалификации инженеров-электронщиков и специалистов по управлению. Они нашли систему исключительно удобной для использования, некоторые взяли ее в свои фирмы и на ее базе создали аналогичные программы. Одна из них называлась Control C, она была написана молодым программистом Джеком Литтлом из маленькой компании SCT, входившей в «пояс внедрения» Стенфордского университета. Джек Литтл (Little, John N. (Jack); р. 1956) — сын знаменитого математика Джона Литтла, классика исследования операций (см. с. 122), первым во всем мире получившим ученую степень в 7

Argonne National Laboratory — расположенная близ Чикаго крупнейшая научная организация, внесшая большой вклад в реализацию американской ядерной программы. Известна своими достижениями в области численных методов и суперкомпьютерных вычислений. Именно там был создан революционный квазиньютоновский метод нелинейной оптимизации [4, ч. II, с. 148].

22.4. Исторические замечания

161

этой отрасли науки. Литтл-младший получил степень бакалавра электротехники и информатики в Массачусетсском технологическом институте (1978 г.), затем магистра электротехники в Стенфордском университете (1980 г.).

Клив Молер

Джек Литтл

В 1983 г. во время одной конференции Джек Литтл подошел к Молеру и предложил создать коммерческую версию MATLAB для нового и чрезвычайно популярного персонального компьютера IBM PC. Так родилась компания «MathWorks», в которой Литтл стал президентом, взявшим на себя все тяготы повседневного управления делами, а Молер — соучредителем и главным математиком. Сначала бизнес развивался медленно, но система постоянно совершенствовалась и через некоторое время стала лидером на рынке программ компьютерной математики. Более того, реализованные в MATLAB эффективные алгоритмы матричной арифметики оказались идеальным инструментом для реализации дочернего пакета моделирования Simulink, неразрывно связанного с родительской системой. В 1986 г. компания переместилась в штат Массачусетс, стала быстро расти и развиваться. По состоянию на 2012 г. в ней работали 2400 сотрудников, организованы представительства в других странах, годовой доход составил около 700 млн долл. В последнее время «MathWorks» стала приобретать независимых разработчиков научного программного обеспечения, расширяя таким образом функциональность своих продуктов.

Литература 1.

Арчибальд Р. Управление высокотехнологичными программами и проектами. — М.: Академия АйТи, 2004. — 472 с.

2.

Ахьюджа Х. Сетевые методы управления в проектировании и производстве: пер. с англ. — М.: Мир, 1979 –— 639 с.

3.

Боев В. Д. Моделирование систем. Инструментальные средства GPSS World. — СПб.: БХВ-Петербург, 2004. — 368 с.

4.

Гладких Б. А. Методы оптимизации и исследование операций для бакалавров информатики: учеб. пособие. — Томск: Изд-во НТЛ, 2009. — Ч. I. Введение в исследование операций. Линейное программирование — 200 с.; 2011. — Ч. II. Нелинейное и динамическое программирование. — 264 с.

5.

Голенко Д. И. Статистические методы сетевого планирования и управления. — М.: Наука, 1968. — 400 с.

6.

Гольштейн Е. Г., Юдин Д. Б. Новые направления в линейном программировании. — М.: Сов. радио, 1966. — 524 с.

7.

Гультяев А. К. Microsoft Office Project Professional 2007. Управление проектами: практич. пособие. — СПб.: КОРОНА-Век, 2008. — 480 с.

8.

Зуховицкий С. И., Радчик И. А. Математические методы сетевого планирования. — М.: Наука, 1965. — 296 с.

Литература

163

9.

Кельтон В., Лоу А. Имитационное моделирование. Классика CS: пер. с англ. — 3-е изд. — СПб.: Питер; Киев: Издательская группа BHV, 2004. — 847 с.

10.

Кофман А., Дебазей Г. Сетевые методы планирования. Применение системы ПЕРТ и ее разновидностей при управлении производственными и научно-исследовательскими проектами: пер. с фр. — М.: Прогресс, 1968. — 182 с.

11.

Назаров А. А., Терпугов А. Ф. Теория массового обслуживания: учеб. пособие. — Томск: Изд-во НТЛ, 2004. — 228 с.

12.

Портни С. Управление проектами для «чайников». — М.: Диалектика, 2006. — 368 с.

13.

Приступа А. В. Имитационное моделирование в среде GPSS World: учеб.-методич. пособие. — Томск: Изд-во НТЛ, 2013. — 84 с.

14.

Таха Х. А. Введение в исследование операций: пер. с англ. — 7-е изд. — М.: Изд. дом «Вильямс», 2005. — 912 с.

15.

Томашевский В. Н., Жданова Е. Г. Имитационное моделирование в среде GPSS. — М.: Бестселлер, 2003. — 416 с.

16.

Учебное пособие по GPSS World: пер. с англ. — Казань: Издво «Мастер Лайн», 2002. — 272 с.

17.

Хинчин А., Я. Математические методы теории массового обслуживания // Труды Математического института им. В.А. Стеклова. Т. XLIX. — М.: Изд-во АН СССР, 1955. — 123 с.

18.

SimEvents User’s Guide. — The MathWorks Inc., 2013. — http://www.mathworks.com/help/pdf_doc/allpdf.html #simevents

Учебное пособие

ГЛАДКИХ Борис Афанасьевич

МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ ДЛЯ БАКАЛАВРОВ ИНФОРМАТИКИ Часть IV. Сетевое планирование и массовое обслуживание

Редактор Н.И. Шидловская Верстка Б.А. Гладких Дизайн Д.В. Фортеса

ООО «Издательство научно-технической литературы» 634050, г. Томск, пл. Новособорная, 1, тел. (3822) 533-335 Подписано к печати 23.05.2013. Формат 60 × 84 1/16. Бумага офсетная. Печать офсетная. Гарнитура «Computer Modern Super». Усл. п. л. 9,53. Уч.-изд. л. 10,68. Тираж 200 экз. Заказ № 29. Отпечатано в типографии «М-Принт», г. Томск, пер. Добролюбова, 10, ст. 3, тел. (3822) 258-279