<< Предыдущая

стр. 5
(из 5 стр.)

ОГЛАВЛЕНИЕ

2



Рис. 6. Поиск критического пути


Операции, принадлежащие критическому пути, называются
критическими. Остальные (некритические) операции имеют резерв
времени, характеризуемый максимальной задержкой операции, при
которой продолжительность проекта не изменяется. Критические
операции имеют нулевой резерв. Приведем соответствующие
формулы.
Алгоритм 9. Предположим, что выполнение комплекса опера-
ций (проекта) начинается в нулевой момент времени. Обозначим
Q0 – множество событий, не требующих выполнения ни одной из
операций, то есть входы сети; Qi – множество событий, непосред-
ственно предшествующих событию i, то есть множество вершин j
сети, для которых существует дуга (j; i).
Положим
(1) ti? = max tji, ti? = max ( t ? + tji).
j
j?Q0 j?Qi

Величина ti? называется ранним моментом (временем) свер-
шения i-го события и характеризует время, раньше которого это
событие произойти не может. Длина критического пути
(2) T = max ti?
i
определяется ранним временем свершения конечного события, то
есть события, заключающегося в завершении всех операций.
Поздним моментом ti+ свершения события называется мак-
симальное время его наступления, не изменяющее продолжитель-
ности проекта. Обозначим Ri – множество событий, непосредст-

24
венно следующих за событием i, то есть множество вершин j сети,
для которых существует дуга (i; j). Вычислим для каждой верши-
ны-события i длину li максимального пути от этой вершины до
выхода сети – события, заключающегося в завершении всего ком-
плекса операций:
(3) li = max (lj + tij).
j?Ri

Положим ti+ = T – li, i = 1, n .
Для завершения проекта за время T необходимо и достаточно,
чтобы событие i произошло не позднее момента ti+ , i = 1, n .
Полным резервом ?ti события i называется разность между его
поздним и ранним моментами свершения, то есть
(4) ?ti = ti+ – ti? , i = 1, n .
Очевидно, полный резерв критических событий (событий, принад-
лежащих критическому пути) равен нулю.
Задачи распределения ресурса на сетях удобно рассматри-
вать, изображая операции вершинами сети, а зависимости – дугами
(представления «операции-дуги, события-вершины» и «зависимо-
сти-дуги, операции-вершины» эквивалентны [10]). Пунктиром
могут быть отражены ресурсные зависимости – когда для выпол-
нения одних и тех же операций должны быть использованы одни и
те же ресурсы. Примером могут являться сети, изображенные на
рисунках 6 и 7. Полным резервом операции (i; j) называется вели-
п р п
чина ?ij = tij – tij , где tij – поздний срок начала (окончания) опе-
рации, а tijр – ранний срок начала (окончания) операции.

11
14
1-3 [10]
0-1 16
[7]
3-5 [12]
[11]
1-4
15
[22]
[11] 4-5
0-2 10 20
2-4
4 [17]


Рис. 7. Представление «операции-вершины»
для сети рисунка 6

25
Для определения оптимального распределения ресурса необ-
ходимо найти критические пути для каждого из вариантов распре-
деления ресурса и сравнить длины этих путей (в сети, приведенной
на рисунке 7, существует общий для операций «0-1» и «0-2» ре-
сурс; потенциалы вершин, соответствующие различным способам
использования этого ресурса – сначала выполняется операция «0-
1», затем «0-2» и наоборот, приведены на рисунке 7 соответствен-
но в квадратных скобках и без скобок).
Универсальных эффективных точных методов решения задач
распределения ресурсов на сетях не существует. В качестве част-
ного случая, для которого существует простой алгоритм, приведем
следующий пример.
В сети, изображенной на рисунке 8, для трех операций извест-
ны поздние времена окончания ?i. Требуется определить очеред-
ность выполнения этих трех операций при условии, что все опера-
ции выполняются одной единицей ресурса и поэтому не могут
выполняться одновременно.


7

23
8 20
z
15
4



Рис. 8. Пример распределения ресурса

Легко показать, что в рассматриваемом примере оптимально
выполнять первой операцию с минимальным ?i.
Если для выполнения проекта выделено ограниченное количе-
ство ресурса, то возникает задача наилучшего его использования.
Обозначим wi – объем i-ой операции, fi(vi) – скорость ее выполне-
ния в зависимости от количества ресурса vi. Предположим, что fi(?)
– непрерывная справа неубывающая функция, причем fi(0) = 0.
Если vi(t) – количество ресурса на i-ой операции в момент времени

26
t, то момент ti ее окончания определяется как минимальное время,
удовлетворяющее уравнению:
ti

? f (v (t ))dt
(5) = wi.
i i
0
Если количество ресурса, используемое при выполнении неко-
торой операции, не изменяется во времени, то говорят, что она
выполняется с постоянной интенсивностью. Тогда продолжи-
тельность операции определяется выражением
(6) ti(vi) = wi / fi(vi).
В настоящее время общих алгоритмов поиска распределения
ограниченных ресурсов между операциями, минимизирующего
время завершения проекта, не существует. Поэтому рассмотрим
несколько частных случаев.
Пусть все операции независимы и выполняются ресурсом од-
ного вида, количество которого равно R, а fi(vi) – непрерывные
строго монотонные вогнутые функции. Тогда существует опти-
мальное решение, в котором каждая операция выполняется с по-
стоянной интенсивностью и все операции заканчиваются одновре-
менно в момент времени T, определяемый как минимальное время,
удовлетворяющее следующему неравенству:
n
wi
? fi ?1 ( ) ? R,
(7)
T
i =1

где f i ?1 (?) – функция, обратная функции fi(?), i = 1, n [7, 10].
Эвристические алгоритмы определения оптимального распре-
деления ресурса для ряда случаев «невогнутых» функций интен-
сивности рассматриваются в [1-4].
Обширный класс задач КСПУ составляют задачи агрегирова-
ния – представления комплекса операций (проекта) в виде одной
операции и исследования свойств таких представлений, для кото-
рых оптимизация в рамках агрегированного описания дает реше-
ние, оптимальное для исходного (детального) описания. Основные
подходы к постановке и решению задач агрегирования рассматри-
ваются в [1, 2, 10, 16].




27
Литература

1 Баркалов С.А., Бурков В.Н., Новиков Д.А., Шульженко Н.А. Модели и меха-
низмы в управлении организационными системами. М.: Издательство «Тульский
полиграфист», 2003. Том 1. – 560 с., Том 2 – 380 с., Том 3 – 205 с.
2 Баркалов С.А., Бурков В.Н., Гилязов Н.М. Методы агрегирования в управле-
нии проектами. М.: ИПУ РАН, 1999. – 55 с.
3 Баркалов С.А., Бурков В.Н. Минимизация упущенной выгоды в задачах
управления проектами. М.: ИПУ РАН, 2001. – 56 с.
4 Баркалов С.А., Бурков В.Н., Курочка П.Н., Образцов Н.Н. Задачи управления
материально-техническим снабжением в рыночной экономике. М.: ИПУ РАН,
2000. – 58 с.
5 Берж К. Теория графов и ее применения. М.: Иностранная литература, 1962. –
319 с.
6 Бурков В.Н., Багатурова О.С., Иванова С.И. Оптимизация обменных производ-
ственных схем в условиях нестабильной экономики. М.: ИПУ РАН, 1996. – 48 с.
7 Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов.
Тбилиси: Мецниереба, 1974. – 234 с.
8 Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении
организационными системами. М.: Синтег, 2001. – 124 с.
9 Бурков В.Н., Зинченко В.Н., Сочнев С.В., Хулап Г.С. Механизмы обмена в
экономике переходного периода. М.: ИПУ РАН, 1999. – 70 с.
10 Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые
модели и задачи управления. М.: Советское радио, 1967. – 144 с.
11 Бурков В.Н., Новиков Д.А. Как управлять проектами. М.: Синтег, 1997. – 188 с.
12 Вагнер Г. Основы исследования операций. М.: Мир, 1972. Т. 1–4.
13 Воронин А.А., Мишин С.П. Оптимальные иерархические структуры. М.: ИПУ
РАН, 2003. – 210 с.
14 Егоршин А.П. Управление персоналом. Н. Новгород: НИМБ, 1997. – 607 с.
15 Емеличев В.А,, Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по
теории графов. М.: Наука, 1990. – 384 с.
16 Колосова Е.В., Новиков Д.А., Цветков А.В. Методика освоенного объема в
оперативном управлении проектами. М.: Апостроф, 2001. – 156 с.
17 Коргин Н.А. Механизмы обмена в активных системах. М.: ИПУ РАН, 2003.
18 Новиков Д.А. Сетевые структуры и организационные системы. М.: ИПУ РАН,
2003. – 102 с.
19 Оре О. Теория графов. М.: Наука, 1968. – 352 с.




28

<< Предыдущая

стр. 5
(из 5 стр.)

ОГЛАВЛЕНИЕ