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

Обозначим ti = wi/ui - минимальную продолжительность i-ой операции.

tn=mn (n -т«)

Зная поздние моменты свершения всех событий, легко определить поздний момент начала всех операций:

©

Рис. 6.6.

[10]

[0

Р]ГЛ (5) [8]

Пример 6.5. Рассмотрим сеть рис.6.6. Длительности операций указаны в скобках у соответствующих дуг. Длина критического пути T = 10. Поздние моменты свершения событий указаны в скобках у соответствующих вершин.

На рис. 6.7. а приведен календарный график реализации комплекса, при условии, что все операции начинаются в поздние моменты.

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

Задача минимизации времени реализации мультипроекта решается достаточно просто. Пусть Si(t,T) - интегральный график использования

n

ресурсов i-го проекта при его завершении в момент Т, S(t,T) = ^Si(t,T) -

i=1

интегральный график использования ресурса для мультипроекта, M(t) -

интегральный график имеющегося количества ресурса (рис. 6.8).

Для определения минимального времени T0 окончания мультипроекта необходимо сдвигать график S(t, T) влево (см. рис. 6.8) до тех пор, пока он не коснется графика M(t). Получив таким образом интегральный допустимый график распределения ресурса по мультипроекту, мы можем декомпозировать его на графики распределения ресурса для каждого проекта. Задача минимизации упущенной выгоды не имеет такого простого метода решения. При небольшом числе проектов проще всего ее решать методом перебора всевозможных упорядочений проектов. Заметим, что если приоритетность реализации проектов выбрана, то распределение ресурсов получается сдвигом интегральных графиков Si(t, T) максимально влево до касания с графиком M(t) в заданной очередности. При большом числе проектов можно воспользоваться эвристическим правилом, обоснование которого дано в параграфе 4.