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

В матричных моделях календарного планирования [99] предполагается, что i=1, ..., N - множество исполнителей, j=1, ..., M виды работ по проекту. Если Pij j-я работа, выполняемая i-м исполнителем, то непосредственно предшествующие работы будем обозначать Pih (h=1, ..., j-1), а последующие Pik

(k=1, ..., M).

Поток считается заданным, если для любой работы Pij известны предшествующие ей Pih (h=1, ..., j-1), а также:

tij − продолжительность работы Pij;

t ij (k) − минимальная продолжительность работы Pij, после которой должна начаться работа Pik;

tij (h) − минимальная продолжительность работы Pij, которая должна

быть выполнена к окончанию работы Pih.

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

В настоящее время для моделирования процесса календарного планирования применяются обобщенные сетевые модели (ОСМ), которые могут строиться как в терминах "событий", так и в терминах "работ" [99]. Последний способ хорошо зарекомендовал себя при совмещенном выполнении работ.

Пусть а и b - две связанные работы. Для них выполняется соотношение a<b (a предшествует b). Обозначим через Taн, Tbн − время начала работ a и b,

Taо, Tbо- время окончания этих работ. Если ta и tb − продолжительности работ,

то Taо =Taн+ta, Tbо =Tbн+tb.

Связь между двумя работами может быть задана следующим образом

(табл. 1.4.2).

Можно построить более сложную связь между двумя произвольными точками работ xa и xb (рис. 1.4.2). Это может быть связь типа "не ранее" или "не

позднее".

Tbн +nb>Taн+na+t1(xa, xb); Tbн +nb<Taн+na+t2(xa, xb),

где na (nb) продолжительность части работы a (b) от ее начала до момента xa(xb), t1(xa, xb)и t2(xa, xb) − параметры временных связей, обозначающие, что момент xbработы b может наступить не ранее чем через t1(xa, xb) и не позднее чем через t2(xa, xb) единиц времени от момента xa работы a.

41

								Таблица 1.4.2
N			Пример связи					Описание
1								Начало-Начало (начало последующей
								работы связано с началом предыдущей)
2								Начало-Конец (конец последующей
								работы связан с началом предыдущей)
3								Конец-Начало (начало последующей
								работы связано с концом предыдущей)
4								Конец-Конец (конец последующей
								работы связан с концом предыдущей)
	na			xa
Taн								Taо
				nb			xb
			Tbн					Tbо
							Рис. 1.4.2

Определенный интерес представляет вариационная постановка задачи календарного планирования [17]. Состояние каждой работы будем представлять в виде фазового вектора, координатами которого будут параметры процесса (обеспеченность материалами, степень подготовки, рабочие кадры и т. д.).

Запишем уравнение в виде

Xi=f(Xit, Ui, t) i=1, ..., n,

где Xi − фазовый вектор состояния i-й СМР, Ui − ресурс, требуемый для выполнения этой работы, Xit − производная фазового вектора по времени,

n − число работ по проекту.

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

42

n	T
ui	U , ui (t ) U ,
i 1	0

где U − общее количество ресурсов, T − период потребления.

Обычно предполагается, что работы надо так расставить во времени, чтобы общая продолжительность строительства была бы минимальной:

JTi min ,

i1n

где Ti − время выполнения i-й работы.

Если предположить, что состояние работы будет определяться только долей ее выполнения, то Xi − скалярная величина, определяемая как Xi=Uit/Qi, где Ui − количество рабочих, Qi − трудоемкость i-й СМР.

Граничные условия могут быть представлены в виде Xi(0)=0 Xi(T)=1. Если работы i и j связаны друг с другом, то это условие записывается в

виде Xi(t)=0 если Xj(t)<1. Такие условия могут быть учтены в функционале методом штрафных функций:

T n
I J xi	2 (t)(1 x j (t))2 dt .
0 i, j 1

Решение подобной задачи может быть получено с помощью метода максимума А. С. Понтрягина [75].

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

Исходя из этих предпосылок процесс календарного планирования был формализован с помощью аппарата нечетких множеств. Основой исходных данных построения календарного плана является набор последовательных событий, для которых указаны моменты их наступления t1, t2, ..., tn. В выражения могут также участвовать и идентификаторы временных отношений [9]:

r0 – быть одновременно;

r1 – быть раньше;

r2 – быть позже;

r3n – быть раньше на n дискретных единиц;

r4n – быть позже на n дискретных единиц;

r5n – быть раньше не более чем на n дискретных единиц;

r6n – быть раньше не менее чем на n дискретных единиц;

r7n – быть позже не более чем на n дискретных единиц;

r8n – быть позже не менее чем на n дискретных единиц;

r9– быть не позже;

r10 – быть не раньше.

43

Формально эти отношения могут быть заданы как функции на декартовом произведении TxT:

			1, 2		= 1, если 1			= 2, и 0, если нет;
	0
			1, 2		= 1, если 1			< 2, и 0, если нет;
	1
			1, 2		= 1, если 1			> 2, и 0, если нет;
	2
			,	= 1, если			+ = , и 0, если нет;
	3	1	2			1				2
			,	= 1, если			− = , и 0, если нет;
	4	1	2			1				2
	,		= 1, если			−		<		< , и 0, если нет;
5	1	2			2				1	2
	,		= 1, если			≤		<		+ , и 0, если нет;
6	1	2			2		1		2
		,		= 1, если			≤		− , и 0, если нет;
	7	1	2			1		2
			,	= 1, если			≥		+ , и 0, если нет;
	8	1	2			1		2
			1, 2		= 1, если 1			≤ 2, и 0, если нет;
	9
			1, 2		= 1, если 1			≥ 2, и 0, если нет.
	10

Эти функции представляют собой характеристические функции отношений.

В качестве квантификаторов могут выступать и нечеткие временные отношения, которые получаются из соответствующих им четких с использованием добавления ―быть примерно‖, то есть ―быть примерно одновременно‖, ―быть примерно раньше на n дискретных единиц‖ и т. д.

Поставим в соответствие каждому событию x функцию распределения Пx – величину, характеризующую возможность наступления x в различных точках временной шкалы. Тогда возможность того, что x произойдет в момент t, будет равняться величине r0 (t, ) для всех t из T.

Используя подобную методу, можно построить сложные предикаты, характеризующие нечеткие временные зависимости между СМР.

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

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

44

Такое преобразование может быть выполнено одним из следующих способов:

сверткой множества критериев в один, интегральный;

выделение одного критерия в качестве критерия оптимальности, при этом остальные будут играть роль ограничений;

ранжирование критериев с использованием лексиграфических предпочтений;

использование метода последовательных уступок в целях нахождения множества компромиссных решений.

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

K	P1 P2 Pn			,
	P	P	P
	n 1	n 2	m

где P1 , P2 ,..., Pn - показатели, которые необходимо увеличить; Pn 1 , Pn 2 ,..., Pm −

показатели, которые необходимо уменьшить. Естественно, что все используемые в данном подходе критерии должны быть приведены к безразмерному виду и пронормированы.

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

K1P1 2 P2 ... m Pm .

Вданном случае используемые здесь критерии должны быть не только

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

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

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

45

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

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

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

P1 (x) P1 (y),

P1 (x) P1 (y), P2 (x) P2 (y),

P1 (x) P1 (y), P2 (x) P2 (y), P3 (x) P3 (y).

Такая задача получила название лексиграфической задачи оптимизации. Но использование данного алгоритма может быть затруднено тем

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

встроительном производстве.

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

его оптимальное значение P1* . Затем задают величину возможного ухудшения этого критерия P1 , добавляют к системе ограничений исходной задачи новое ограничение вида P1* P1 P1 и решают полученную задачу оптимизации, но уже по критерию P2 . Аналогично, осуществляется решение задачи оптимизации

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

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

46

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Сформулируйте понятие проекта.

2.Какие характеристики отличают проекты от других видов деятельности?

3.Классифицируйте проекты.

4.Какие факторы влияют на проект?

5.Кто может входить в состав участников проекта?

6.На какие фазы можно разбить цикл жизни проекта?

7.Сформулируйте определение управления проектом.

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

9.В чем заключается алгоритм решения задачи оптимизации комплексов работ по стоимости?

10.Назовите три формы представления календарных графиков.

ГЛАВА 2. ЗАДАЧИ ОПТИМИЗАЦИИ ОБЪЕМОВ РАБОТ

ВУПРАВЛЕНИИ ПРОЕКТАМИ

2.1.Методы решения задач оптимизации объемов работ

2.1.1.Линейный случай

Задан сетевой график с объемами работ Wij , (i, j) U (U – множество дуг

(работ) графа). Примем, что продолжительность работы ij		является линейной
функцией объема работ xij	:
ij Kij	xij , 0 xij Wij	(2.1.1.1)
Если при продолжительностях работ Dij Kij Wij		продолжительность

проекта превышает требуемую величину Т, то в случае невозможности увеличения ресурсов часть объемов работ выполняется сторонними организациями (субподряд). Если объем ( Wij xij ) работы (i, j) выполняется

сторонними организациями, то дополнительные затраты составят

Sij (xij ) Cij (Wij xij ),

(2.1.1.2)

где Cij – оплата единицы объема.

Задача. Определить объемы xij	(i, j) U , так чтобы продолжительность проекта
не превышалаТ, а суммарные затраты
S(x)	Cij (Wij xij )	(2.1.1.3)

(i,j) U

были минимальными.

47

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

ij qij (Wij xij )

Очевидно, что сокращение продолжительности работы (i, j) определяется

выражением

ij max[ Kijxij ;qij (Wij xij )].

Эта величина минимальна при условии

Kijxij

qij (Wij

xij )

или

xij

qij Wij

Bij

Kij qij

и равна

d

Kij

qij Wij

D

K

W .

(2.1.1.4)

ij

ij

ij

Kij qij

ij

Понятно, что уменьшение объемов ниже Bij , а значит, уменьшение

продолжительности

ниже

dij

нецелесообразно.

Таким

образом,

продолжительности xij

лежат в пределах dij

xij Dij .

Обозначим pij

cij

, (i, j) U – пропускные способности дуг сети.

Kij

Описание алгоритма

1. Полагаем

продолжительности работ xij

Dij , (i, j) U и

определяем

критический путь (пути) в сети. Если его длина T(W) T , то определяем сеть критических путей (сеть КП).

2.В сети КП находим разрез минимальной пропускной способности. Для этого определяем поток максимальной величины и соответственно разрез минимальной пропускной способности.

3.Сокращаем продолжительности дуг, заходящих в разрез (обозначим

множество таких дуг V(W)) на величину Δ>0. Величина определяется из двух условий:

а) в сети КП появился новый критический путь,

б) продолжительность хотя бы одной работы сети КП стала равной dij . В

этом случае полагаем пропускную способность соответствующей дуги равной ∞ (или просто достаточно большому числу).

4. Сокращаем продолжительности дуг, заходящих в разрез, на величину, равную

min( ;T(W) T) ,
а объемы работ (i, j) V(W) полагаем равными x		W		.
	ij
		ij	Kij
48

5. Если T(x) T, то алгоритм закончен. Если T(x) T, то повторяем шаги алгоритма.

Обоснование алгоритма

Сокращение продолжительности проекта возможно только при сокращении продолжительностей работ, заходящих в какой-либо разрез. Выбирая разрез с минимальной пропускной способности, сокращаем продолжительности (а следовательно, и объемы) работ с минимальными затратами.

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

Пример 2.1.1.1. Рассмотрим сеть на рис. 2.1.1.1.

1 3

0	4	6

2 5

Рис. 2.1.1.1

Данные о работах приведены в табл. 2.1.1.1.

Таблица 2.1.1.1

(i, j)	(0,1)	(0,2)	(1,3)	(1,4)	(2,4)	(2,5)	(3,6)	(4,6)	(5,6)
Wij	6	9	5	3	6	8	4	7	3
Kij	1	2	3	2	4	1	3	5	6
qij	1	1	2	1	2	1	1	2	3
cij	5	4	9	8	4	3	6	10	6

На основе этой таблицы определяем Dij , dij и pij , (i, j) U (табл. 2.1.1.2).

Таблица 2.1.1.2

(i, j)	(0,1)	(0,2)	(1,3)	(1,4)	(2,4)	(2,5)	(3,6)	(4,6)	(5,6)
Dij	6	18	15	6	24	8	12	35	18
dij	3	6	6	23	8	4	3	10	6
pij	5	2	3	4	1	3	2	2	1

49

Пусть Т=30.

1. Определяем критический путь в сети (на рис. 2.1.1.2 продолжительности Dij указаны у дуг, пропускная способность дуг в скобках).

			[6]		[21]
			1	15(3)	3
	6(5)					12(2)
					[42]
			6(4)
[0]	0		24(1		4	35(2)	6 [77]
	18(2)		2		5	18(1)
				8(3)
		[18]			[26]
				Рис 2.1.1.2

Критический путь выделен толстыми дугами. Его длина Т1=77>30.

2. Множество работ, заходящих в разрез минимальной пропускной способности, V(w) (2,4) , p24 1.

3. Определяем . Заметим, что если взять 24 d24 8 , то критический путь не изменится. Поэтому берем 24 8 16 . Полагаем p 24 .

4. Сокращаем продолжительность работы (2,4) на 16 единиц. Соответственно ее объем на 16/4=4 единицы. Остается объем x124 2 . Затраты на субподрядные

работы равны (W24 x24 ) c24 4 4 16 .

5. Имеем Т(х1)=61>40.

Повторяем шаги алгоритма.

1.Критический путь (0,2,4,6).

2.Множество V(x1 ) (0,2) (можно взять (4,6)).

3. Определяем . Заметим, что при 02 d02 6 критический путь остается

прежним. Поэтому берем D02 d02 12 . Полагаем p02 .

4. Сокращаем продолжительность работы (0,2) на 12 единиц. Соответственно ее объем на 6 единиц, x022 3 . Затраты на субподрядные работы увеличились на

6 4 24 и составили c(x2 ) 16 24 40.

5. Поскольку Т(х2)=46>40, то повторяем шаги алгоритма.

1.Критический путь (0,2,4,6).

2.Множество V(x2 ) (4,6).

3. Определяем . Заметим, что при 46					19		в сети появится еще один
критический путь (0,1,3,6), рис. 2.1.1.3, Поэтому 35 19 16 .
	1		15(3)		3
6(5)							12(2)
	6(4)
0	8(∞)				4	19(2)		6
6(∞)	2				5		18(1)
			8(3)

Рис. 2.1.1.3

50