Тема 4. Потоки с непрерывным использованием ресурсов

(НИР)

Потоки с непрерывным использованием ресурсов были предложены советскими учеными в 70-х годах в виде ритмичных потоков.

Время на каждом частном фронте при выполнении каждого вида работ называется ритмом.

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

Период развертывания - это время начала работ последующего вида, отсчитывая от начала работ предыдущего вида.

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

Расписание работ - это начало и окончание работ каждого вида на каждом частном фронте.

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

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

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

Критерием оптимальности является минимальная продолжительность.

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

Данный метод характеризуется развитием перспективных ветвей, т.е. в отличие от полного перебора (m!) получение оптимального варианта достигается быстрее.

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

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

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

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

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

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

Цель формирования матриц по Джонсону - добиться уменьшения значений периодов развертывания. В худшем случае это значение равно периоду развертывания (Тр) исходной матрицы.

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

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

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

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

Для иллюстрации вышеизложенного далее приведен соответствующий пример.

Исходная матрица

ОФР	А	Б	В	Г
I	1	2	8	9
II	2	3	9	6
III	3	5	7	7
IV	1	4	7	8

А	Б		В		Г
1	2		8		9
1	4		9	7	8
2		4	7	7	7
3	5	5	7	9	6

II

А	Б		В		Г
2	3		9		6
1	4	2	8	7	8
3	5	4	7	8	9
1	2	5	7	7	7

ПВМП = 1+2+8+30= 41

ПВМП - 2+3+10+30 = 45

III

А	Б		В		Г
3	5		7		7
1	4	2	8	7	8
2	3	3	9	8	9
1	2	4	7	9	6

IV

А	Б		В		Г
1	4		7		8
2	3	2	8	8	9
3	5	3	9	7	7
1	2	5	7	9	6

ПВМП = 3+5+7+30 = 45

ПВМП = 1+4+7+30 = 42

I II

А	Б		В		Г
1	2		8		9
2	3		9		6
1	4	4	7	7	8
3	5	5	7	7	7

I III

А	Б		В		Г
1	2		8		9
3	5		7		7
I	4	3	9	7	8
2	3	4	7	9	6

ПВМП = 1+2+9+30 - 42

ПВМП - 2+2+8+30 = 42

I

IV

А	Б		В		Г
1	2		8		9
1	4		7		8
2	3	3	9	7	7
3	5	5	7	9	6

ПВМП = 1+2+8+30 = 41

ОФР	A	Б	В	Г		ОФР	A	Б	В	Г
I	011	123	3811 о	11920		I	1	2	8	9
IV	112 4	347	11718	20828		IV	1	4	7	8
II	224	7310	18927	28634		III	3	5	7	7
III	437	10515	27734	34741		II	2	3	9	6

Т = 1+2+8+30 = 41 Т = 1+2+8+30 = 41

А ~ 10 чел., Б ~ 10 чел., В ~ 20 чел., Г ~ 15 чел.

Исходная матрица

ОФР	А	Б	В	Г
I	1	2	8	9
II	2	3	9	6
III	3	5	7	7
IV	1	4	7	8

Матрицы по Джонсону

Л'	5'
1	4
2	3
3	5
1	2

Б'	В'
2	8
3	9
4	7
5	7

	Г'
7	8
8	9
7	7
9	6

П

T_{I, II, III, IV} = 42

орфириан

I IV II III

41

I IV III II

41

min

min

Optim.

Циклограмма Календарные дни

I

IV

III

III

7

15

34

41

График движения рабочих

N, чел

50

40

30

20

10

0 5 10 15 20 25 30 35 40 Т, дн