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

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

ü Изменять структуру (топологию) сетевой модели, доводя ее до срока Тдир. Но это сложный и длительный процесс.

ü Изменять метрику (продолжительности работ) уже сформированной сетевой модели. Этот способ проще и рациональнее.

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

t(ij) = t(ij) * K_н(ij)

Kн(ij)=

Tдир

Ткр – R^п(ij) , где (1.12)

t(ij) – новая, измененная продолжительность работы;

t(ij) – старая, заданная продолжительность работы (в соответствии с которой получено значение Ткр);

Тдир – директивный желаемый срок выполнения всего комплекса работ;

R^п(ij) – полный резерв работы при первоначальном расчете.

По формуле (1.12) производится пересчет всех продолжительностей работ. При этом некоторые работы будут уменьшаться по значению; другие увеличиваться; какие-то останутся без изменения. А именно:

1.Если ij Є Lкр => R^п(ij) = 0, т.е. если работы принадлежат критическому пути, то К_н=Тдир/Ткр ; и следовательно данные работы будут уменьшаться пропорционально величине Тдир/Ткр.

<1

2.Если К_н(ij) < 1, то Тдир

Ткр – R^п(ij)

Тдир < Ткр – R^п(ij)

R^п(ij) < Ткр – Тдир (при условии Ткр > Тдир)

Следовательно, все работы сетевой модели , у которых полный резерв меньше разницы (Ткр – Тдир), будут уменьшены пропорционально коэффициенту К_н(ij).

3.Если К_н(ij) > 1, то R^п(ij) > Ткр –Тдир.

Следовательно, те работы, у которых полный резерв больше разницы (Ткр–Тдир), будут даже увеличены пропорционально К_н(ij)

4.Если К_н(ij) = 1, то R^п(ij) =Ткр – Тдир.

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

Рассмотренный алгоритм позволяет автоматически на основе расчета сетевой модели (табл.1.3), рассчитанного Ткр и заданного Тдир, получить измененные продолжительности работ; при этом можно утверждать, что если взять за основу измененные продолжительности работ, то проект будет выполнен за Тдир, т.е. Ткр^изм=Тдир

Рассмотрим пример, основываясь на сетевой модели (рис.1.11) и результатов расчета (табл.1.4). Пусть Тдир = 22 дня. То есть заказчика данного продукта не устраивает срок в 25 дней, который получился у исполнителя как Ткр = 25.

В соответствии с выше приведенными рассуждениями можно сказать, что

1.Работы критического пути должны быть уменьшены пропорционально

=

Кн(ij)=

Тдир22 .

Ткр 25

Это работы (1-5); (5-7); (7-6); (6-8)

t(1-5) = 5*22/25 = 22/5 = 4,4 дня.

и т.д.

Кн(ij)=

2.Работы, у которых R^п(ij) < (25-22) = 3, должны быть также уменьшены, но пропорционально коэффициенту Тдир

Ткр - R^п(ij)

В данной модели таких работ нет.

3.Работы, у которых R^п(ij) > 3, могут быть увеличены. Это работы: (1-2); (1-4); (2-3); (3-6); (3-8); (7-8).

22

= 3*

≈3,7

t(1-2) = 3*

22

25-7 18

и т.д.

4.Работы, у которых R^п(ij) = 3, остаются без изменения.

= 8

T(5-4) =8*

22

25-3

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

1.6. Задача «время-стоимость»

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

Зависимость между длительностью работы и ее стоимостью с некоторой долей условности можно представить в виде аппроксимирующей прямой, имеющей линейную зависимость (рис.1.16)

C(ij)

C_max

C_изм

∆С

С_min

t_min t_изм t_max t(ij)

Рис.1.16. График «время-стоимость» работы (ij)

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

S(ij) =

C_max(ij) – C_min(ij)

t_max(ij) – t_min(ij)

В курсе рассматривается алгоритм оптимизации сетевой модели по критерию «стоимость».

Дано: Сетевая модель. По каждой работе (ij) дается возможный диапазон длительности работы t_min(ij), t_max(ij), минимальная стоимость работы C_min(ij),коэффициент S(ij). Необходимо найти зависимость Ткр между и суммарными затратами, ставя задачу обеспечить минимум возрастания затрат при уменьшении Ткр.

Алгоритм заключается в следующем:

1. Найти критический путь, его длину Ткр.

С = ∑С(ij)

Lкр = (i₀, i₁,…,i_n) из предположения t(ij) = t_max(ij)

2. На этом пути найти работу (kℓ) Є Lкр, у которой S(kℓ) будет иметь наименьшее значение.

3. Для выбранной работы найти величину ∆t(kℓ) = t_max(kℓ) - t_min(kℓ)

4. Определить ∆С(kℓ) = S(kℓ)*∆t(kℓ)

5. Следовательно, при уменьшении Ткр на величину ∆t(kℓ) стоимость всех работ увеличивается на величину ∆С(kℓ)

С^* = С_пред. + ∆С(kℓ)

6. Рассчитать сетевую модель с учетом измененной продолжительности работы (kℓ).

7. Возвратиться к п.1. В результате реализации данного алгоритма получается график зависимости С от Ткр. По этому графику легко координировать отношения между инвестором и производителем.

ПРИМЕР

Дано: Сетевая модель (рис.1.17)

Рис.1.17

Информация о сетевой модели задана в табл.1.5.

Таблица 1.5.

ij	tmin дни	tmax дни	Cmin руб	S(ij) руб/день
1-3
3-4
1-2
2-4
1-6
6-7
4-5
7-5
			∑90

Необходимо: сократить Ткр так, чтобы дополнительные затраты были минимальными.

Рассчитаем сетевую модель из предположения t(ij) = t_max, получим Ткр^max = 30; из предположения t(ij) = t_min – получим Ткр^min = 15.

Таким образом:

Ткр^min ≤ Ткр ≤ Ткр^max

15 ≤ Ткр ≤ 30

Будем сокращать Ткр.=30 так, чтобы дополнительные затраты росли оптимально, т.е. были минимальными. Решение сведем в таблицу 1.6.

Таблица 1.6.

Пути	ij / S(ij)	Ткр (шаги)
1-3	3-4	1-2	2-4	1-6	6-7	4-5	7-5
1)1-3-4-5
2)1-2-4-5
3)1-6-7-5
Tmax – tmin									∑ стоимость
шаги

График зависимости стоимости от времени будет иметь вид (рис.1.18)

∑С

∑С_опт^max 235

∑C^min 90

15 21 22 24 30 Ткр

Рис.1.18. График зависимости стоимости от времени выполнения проекта

Последовательность расчета:

На первом шаге рассматриваем 2-ой путь, так как он является критическим Ткр=30. На этом пути выбираем работу (1-2), так как у нее S(1-2) наименьшая среди других работ: S(1-2) = 2.

∆t(1-2) = t_max(1-2) – t_min(1-2) = 6

∆C(1-2) = S(1-2)* ∆t(1-2) = 2*6 =12

∑С^изм = ∑С^{первоначальн.} + ∆C = 90+12 = 102

Ткр_{(измененное)} = Ткр_{(старое)} - ∆t(1-2) = 30-6 = 24

На втором шаге появились два одинаковых по длине критических пути. Выбираем любой из них, например, путь номер два. На этом пути выбираем работу (4-5), так как = работа (1-2) уже исчерпана с точки зрения уменьшения, а из оставшихся работ S(4-5) имеет меньшее значение, т.е. S(4-5) = 5.

∆t(4-5) = 3.

Работа (4-5) принадлежит и первому и второму пути, следовательно, длина и первого и второго пути должна быть уменьшена на 3 ед. Длина второго пути станет равна (24-3) = 21. Длина первого пути станет равна (20-3) = 17. Длина третьего пути осталась без изменения

∆C(4-5) = 5*3 = 15

∑С^изм = ∑С^{предыд.} + ∆C(4-5) = 102+15 = 117. И т.д.