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

• ⇐ Назад
• 1
• 234
• 5
• 6
• Далее ⇒

 

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

 

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

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

 

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

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. И т.д.

 

---

• ⇐ Назад
• 1
• 234
• 5
• 6
• Далее ⇒