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

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

Это многообразие сводится к двум основным типам.

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

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

ит.д.).

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

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

n

ui t N t ,

i 1

где ui(t) – количество ресурса на работе i, n – число работ проекта. Довольно часто работы проекта разбиваются на классы, так что работы одного класса выполняются ресурсами одного вида. Если обозначить Pj – множество работ, выполняемых ресурсами j-го вида, Nj(t) – функцию наличия ресурсов j-го вида, то ограничения на распределение ресурсов записываются следующим образом:

31

ui t N j t ,
	j 1, m .
i Pj

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

n t

ui d S t .

i 1 0

Если ограничены общие затраты S на проект (или ограничена стоимость проекта), то ограничения на ресурсы определяются следующим неравенством:

n

si S ,

i 1

где si – затраты ресурса на i-й работе (или стоимость i-й работы). Задача оптимального распределения ресурсов заключается в определении допустимого по ограничениям распределения ресурсов, минимизирующего заданный критерий оптимальности. Если ограничены ресурсы, то, как правило, ставится задача минимизации продолжительности T проекта, либо задача минимизации упущенной выгоды:

Фci ti ,

i1n

где ti – момент окончания i-й работы, ci – коэффициент упущенной выгоды. Если задан срок завершения проекта либо допустимая величина упущенной выгоды, то решается в определенном смысле обратная задача – минимизации ресурсов либо затрат.

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

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

Случай сети с упорядоченными событиями соответствует ситуации, когда задана некоторая очередность свершения событий сети. В сетях с упорядоченными событиями естественно использовать представление сети в виде «вершина – событие», рис. 1.3.5.

		(2)		(4)
0	(1)	1	2	3
			(3)

Рис. 1.3.5

Однако можно определить аналог таких сетей и в представлении «вершина – работа», рис. 1.3.6.

32

Для этого определим понятие «фронта работ» как максимального множества независимых работ, то есть таких, которые могут выполняться одновременно.

В сети рис. 1.3.6 можно выделить три различных фронта работ: (1; 2), (3;2), (3;4). Заметим, что эти фронты в определенном смысле упорядочены, а именно фронт (1;2) расположен «левее» фронта (3;2), а последний – «левее» фронта (3;4). Другими словами, для любых двух фронтов работы одного из них либо совпадают, либо предшествуют работам другого. Таким образом, сетям с упорядоченными событиями соответствуют сети с упорядоченными фронтами.

1 3

2 4

Рис. 1.3.6

Оптимизация по стоимости

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

Si( i) = ai – ki i, di i Di, i 1, n ,

где di – минимально возможная продолжительность работы, Di – максимальная. Примем продолжительности всех работ равными максимальным i = Di. При этом продолжительность проекта

TDi .

i1n

Если мы хотим сократить продолжительность проекта с минимальным увеличением стоимости, то очевидно, что в первую очередь необходимо сокращать продолжительность работы, имеющей минимальную величину коэффициента ki. Действительно, величина ki определяет увеличение стоимости проекта при уменьшении продолжительности i-й работы на единицу. Продолжая таким образом, получим зависимость стоимости проекта от его продолжительности. Рассмотрим на примере обобщение этого алгоритма на случай произвольного сетевого графика [2].

Пример 1.3.2. Пусть сетевой график («вершина – событие») имеет вид рис. 1.3.7.

33

				1		(5; 4)
(6; 3)
0						(4; 1)		3
(8; 5)
								(3; 6)
						2
				Рис. 1.3.7
Величины ai, ki, di и Di		для всех работ приведены в табл. 1.3.1.
									Таблица 1.3.1
			ai		ki		di	Di
	(0, 1)		20		3		2	6
	(0, 2)		45		5		5	8
	(1, 2)		7		1		1	4
	(1, 3)		23		4		1	5
	(2, 3)		20		6		1	3

1 шаг. Полагаем i = Di для всех работ и определяем критический путь в сети. На рис. 1.3.7 в скобках у дуг указаны значения Di (первые числа) и ki (вторые числа) соответствующих работ. Критический путь выделен толстыми дугами. Для критического пути T0 = 13, стоимость проекта S0 = 15. Очевидно, что сокращать следует работу (1, 2). При сокращении работы (1, 2) на две единицы, критическими становятся работы (0, 2) и (1, 3) на рис. 1.3.8, длина критического пути T1 = 11, стоимость проекта S1 = 17.

2 шаг. Чтобы сократить продолжительность проекта теперь следует сократить продолжительность всех критических путей. Для этого необходимо определить множество работ, таких что каждый критический путь содержит хотя бы одну работу из этого множества и сумма коэффициентов ki является минимальной. Это задача эквивалентна задаче определения разреза в сети, имеющего минимальную пропускную способность, которая является двойственной к задаче о потоке максимальной величины (коэффициенты ki определяют пропускные способности дуг). В нашем примере непосредственным перебором можно убедиться, что уменьшение продолжительностей работ (0, 1) и (0, 2) дает минимальное увеличение стоимости проекта (8 единиц на каждую единицу уменьшения продолжительности. Уменьшаем продолжительности работ (0, 1) и (0, 2) на 3 единицы. Больше нельзя, т.к. минимальная продолжительность работы (0, 2) равна 5. Длина критического пути становится равной T2 = 8, стоимость проекта

S2 = 41.

34

		1	(5; 4)
	(6; 3)
0			(2; 1)	3
	(8; 5)

(3; 6)

2

Рис. 1.3.8

3 шаг. Теперь минимальное увеличение стоимости обеспечивается при уменьшении продолжительностей работ (0, 1) и (2, 3). Уменьшаем продолжительности работ (0, 1) и (2, 3) на единицу (при этом продолжительность работы (0, 1) становится минимальной). Длина критического пути T3 = 7, стоимость проекта S3 = 50.

4 шаг. Заметим, что в сети имеются всего 2 критических пути (рис. 1.3.9). Сокращаем продолжительности работ (1, 3) и (2, 3) на 1. Продолжительность проекта становится равной T4 = 6, стоимость проекта S4 = 60.

		1	(5; 4)
	(2; )
0			(2; 1)	3

(5; )

(2; 6)

2

Рис. 1.3.9

1.4. Задачи календарного планирования

Рассмотрим существующие формы представления расписаний работ.

Как известно, существуют три формы представления календарных графиков:

линейная;

циклограммная;

сетевые графики.

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

35

Такая модель имеет простое математическое описание: определить

множество фиксированных значений сроков начала и окончания работ, то есть [58]
P Tн ;Tо n	,
i i i 1

где Р – множество, определяющее расписание работ; Tiн - срок начала i-й работы;

Tiо - срок окончания i -й работы;

i=1,2,…,n – нумерация работ, n – число работ, подлежащих выполнению. При этом на сроки выполнения работ могут быть наложены ограничения

вида:

Tiн ui , Tiо Ui i=1,2,…,n,

это означает, что i-я работа должна быть начата не ранее момента времени u i и завершена не позднее U i .

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

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

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

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

Другой формой представления календарных планов являются циклограммные модели. Эти модели являются обобщением линейных моделей

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

При этом формализованное описание циклограммных моделей может быть представлено в следующем виде [58]:

Trsн Trо 1,s , Trsн Trо,s 1 ,

при этом должно выполняться условие непрерывности деятельности исполнителей

n

Trnо Trн1 t rs , s 1

где r – номер исполнителя; s – номер работы (s=1,2,…,n).

36

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

Относительно просто такая задача решается для частных случаев соотношения производительностей работы различных исполнителей, например, когда объемы работ и состав исполнителей подобран таким образом, что продолжительность выполнения каждой работы будет одинакова, но уже для более общих случаев, когда продолжительности хотя бы нескольких работ будут различны, задача увязки становится гораздо сложнее. Рассмотрим этот алгоритм на простейшем примере [58].

Пусть L – объем работы, подлежащий выполнению, тогда длительность работы смежных исполнителей p и r определяется по следующей формуле:

T	L	, T	L	,
p	k p Ip	r	k r Ir

yp , yr - производительность исполнителей; kp , kr - сменность выполнения работ

исполнителями p и r соответственно.

Необходимо определить минимально возможную величину организационного перерыва между исполнителями p и r r при условии, что

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

За время, равное r , исполнитель p выполнит объем работ, равный r k p Ip , в то время как объем выполненных работ исполнителем r будет равен 0. За

произвольный	промежуток времени t объемы работ соответственно	будут
равны: r kp Ip	t kp Ip и t k r I r . Тогда фронт работ для рассматриваемого
потока будет определяться выражением
	Fr r kp Ip t kp Ip t kr Ir .	(1.4.1)
Причем необходимо соблюдение следующего неравенства:
	Fr tcrp max kp Ip ;kr Ir ,	(1.4.2)

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

При этом возможны два случая:

темп работы рассматриваемого исполнителя ниже темпа работы предыдущего исполнителя, то есть kp Ip kr Ir ;

темп рассматриваемого исполнителя выше темпа предыдущего исполнителя ( kp Ip kr Ir ).

Рассматривая первый случай, запишем соотношение (1.4.2) с учетом (1.4.1) в следующем виде:

37

				k	I
r	t crp	t 1		r		r	.	(1.4.3)
				k p Ip

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

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

r

t crp .

(1.4.4)

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

			t crpk r Ir			k	I	r
				t 1		r			.	(1.4.5)
	r
			k p Ip			k p Ip
В данном случае выражение в скобках будет всегда отрицательным,
поэтому неравенство (1.4.5) будет				выполняться при						t Tp r . После

преобразований получаем

r tcrp Tr Tp .

Для случая синхронизированной работы исполнителей получаем r t crp .

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

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

Математическое описание модели представляет собой набор неравенств вида

Tiо Tiн t i , Tjн Tjо 0,

где t i - продолжительность i-й работы; i, j – номера зависимых работ , i, j= 1,2,…,n.

Всетевых моделях учет директивных сроков строительства

осуществляется путем задания ограничений в форме неравенств

T1н u1 , Tnо Un .

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

38

случае если число частей в силу каких-то причин изменилось, то приходится строить модель заново, так как при этом меняется вся топология сети и весь расчет необходимо осуществлять заново. Таким образом, при построении сетевой модели приходится заранее задаваться числом частей, на которые разбивается работа, то есть необходимо заранее определить степень совмещения выполняемых работ. Но, как известно из практики, степень совмещения работ является величиной нечеткой, то есть значение, которое может изменяться в некоторых пределах, а, как уже было сказано, всякое такое изменение в конечном итоге приводит к необходимости повторного построения модели. В целях устранения этих недостатков традиционные сетевые графики получили дальнейшее развитие в обобщенных сетевых моделях (ОСМ) [99].

Обобщенные сетевые модели представляют собой попытку объединения достоинств линейных моделей при моделировании совмещения работ и достоинств традиционных сетевых моделей в части оперативного управления процессом реализации проекта.

Для процедуры формализованного описания совмещения работ используют метод, который оперирует коэффициентами совмещения работ [9]. Известны два вида коэффициентов совмещения:

коэффициент совмещения по началу (Кн);

коэффициент совмещения по концу (Ко).

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

	Кн = а1 / (а1+а2)
	Ко = в2 / (в1+в2).
Предыдущая работ
а1	а2
Последующая работа
в1	в2
	Рис. 1.4.1

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

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

39

В модели, описанной в [99], календарный план должен удовлетворять следующим требованиям:

timк = timн + tim - где timк - момент окончания i-й работы m-м исполнителем, timн - момент начала i-й работы m-м исполнителем, tim- продолжительность выполнения i-й работы m-м исполнителем;

синхронизация процесса выполнения работ предполагает, что момент окончания i-й работы m-м исполнителем совпадает с моментом начала i-й работы m+1-м исполнителем;

проведение i-й работы m-м исполнителем зависит от выполнения предыдущей и последующей работ, что выражается коэффициентом опережения или запаздывания;

завершение проекта происходит после выполнения всего комплекса

работ.

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

						Таблица 1.4.1
N	Виды взаимной увязки работ				Описание
1	i			Работы i и j выполняются
		j		последовательно
2	i			Работы i и j выполняются
		j		последовательно при			наличии
				технологического перерыва
3	i			Работы i и j начинаются
				одновременно
	j
4	i			Работы i и j заканчиваются
				одновременно
	j
5	i			Работа	j	начинается	после
				выполнения части rij работы I
		j
	rij
6	i			Часть pij	работы j остается после
				выполнения работы I
	j	pij
			40