Коэффициент напряженности работы. Анализ и оптимизация сетевого графика.
После нахождения критического пути и резервов времени работ, и оценки вероятности выполнения проекта в заданный срок должен быть проведен всесторонний анализ сетевого графика и приняты меры по его оптимизации. Этот весьма важный этап в разработке сетевых графиков раскрывает основную идею СПУ. Он заключается в приведении сетевого графика в соответствие с заданными сроками и возможностями организации, разрабатывающей проект.
Вначале рассмотрим анализ и оптимизацию календарных сетей, в которых заданы только оценки продолжительности работ.
Анализ сетевого графика начинается с анализа топологии сети, включающего контроль построения сетевого графика, установление целесообразности выбора работ, степени их расчленения.
Затем проводятся классификация и группировка работ по величинам резервов. Следует отметить, что величина полного резерва времени далеко не всегда может достаточно точно характеризовать, насколько напряженным является выполнение той или иной работы некритического пути. Все зависит от того, на какую последовательность работ распространяется вычисленный резерв, какова продолжительность этой последовательности.
Определить степень трудности выполнения в срок каждой группы работ некритического пути можно с помощью коэффициента напряженности работ.
Коэффициентом напряженности 
работы 
называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим — критический путь:
|
|
|
, (29)
где 
— продолжительность максимального пути, проходящего через работу 
;
— продолжительность (длина) критического пути;
— продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.
Формулу (29) можно легко привести к виду
, (30)
где 
— полный резерв времени работы 
.
Коэффициент напряженности 
может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути).
Пример 4. Найти коэффициент напряженности работы (1, 4) для сетевого графика (рис 6).
Решение. В разд. 5 мы установили, что длина критического пути =61 (сутки), а максимальный путь, проходящий через работу (1,4) — путь 
— имеет продолжительность 
49 (суток). Максимальный путь 
совпадает с критическим (см. рис. 6) на отрезке 
продолжительностью 
(сутки). Используя формулу (29), найдем
|
|
|
.
Или иначе: зная полный резерв работы 
(см. рис. 3), по формуле (30) находим
.
Чем ближе к 1 коэффициент напряженности 
, тем сложнее выполнить данную работу в установленные сроки. Чем ближе к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.
Работы могут обладать полными одинаковыми резервами, но степень напряженности сроков их выполнения, выражаемая коэффициентом напряженности , может быть различна. И наоборот, полным различным резервам могут соответствовать одинаковые коэффициенты напряженности.
Так, полные резервы работ (3,6) и (6,7) для сетевого графика равны: 
(суток) — см. табл. 14.3, а их коэффициенты напряженности различны:
, 
.
Обратим внимание на то, что больший полный резерв одной работы (по сравнению с другой) не обязательно свидетельствует о меньшей степени напряженности ее выполнения. Так, в рассматриваемой сети (см. рис. 6), хотя работа (2, 7) обладает большим полным резервом по сравнению с работой (6, 10): 
, но имеет вдвое больший коэффициент напряженности: 
против 
.
Это объясняется разным удельным весом полных резервов работ в продолжительности отрезков максимальных путей, не совпадающих с критическим путем.
|
|
|
Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины выделяют три зоны: критическую ( 
>0,8); подкритическую (0,6< <0,8); резервную ( <0,6).
Оптимизация сетевого графика представляет процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения. Оптимизация проводится с целью сокращения длины критического пути, выравнивания коэффициентов напряженности работ, рационального использования ресурсов.
В первую очередь принимаются меры по сокращению продолжительности работ, находящихся на критическом пути. Это достигается:
• перераспределением всех видов ресурсов, как временных (использование резервов времени некритических путей), так и трудовых, материальных, энергетических (например, перевод части исполнителей, оборудования с некритических путей на работы критического пути); при этом перераспределение ресурсов должно идти, как правило, из зон, менее напряженных, в зоны, объединяющие наиболее напряженные работы;
• сокращением трудоемкости критических работ за счет передачи части работ на другие пути, имеющие резервы времени;
|
|
|
• параллельным выполнением работ критического пути;
• пересмотром топологии сети, изменением состава работ и структуры сети.
В процессе сокращения продолжительности работ критический путь может измениться, и в дальнейшем процесс оптимизации будет направлен на сокращение продолжительности работ нового критического пути и так будет продолжаться до получения удовлетворительного результата. В идеале длина любого из полных путей может стать равной длине критического пути или по крайней мере Пути критической зоны. Тогда все работы будут вестись с равным напряжением, а срок завершения проекта существенно сократится.
Весьма эффективным является использование метода статистического моделирования, основанного на многократных последовательных изменениях продолжительности работ (в заданных пределах) и "проигрывании" на компьютере различных вариантов сетевого графика с расчетами всех его временных параметров и коэффициентов напряженности работ. Процесс "проигрывания" продолжается до тех пор, пока не будет получен приемлемый вариант плана или пока не будет установлено, что все имеющиеся возможности улучшения плана исчерпаны и поставленные перед разработчиком проекта условия невыполнимы.
До сих пор мы говорили лишь о соблюдении директивных сроков выполнения комплекса работ и не затрагивали непосредственно вопросов стоимости разработки проектов. Однако на практике при попытках эффективного улучшения составленного плана неизбежно введение дополнительно к оценкам сроков фактора стоимости работ.
7. Оптимизация сетевого графика методом "время — стоимость".
Оптимизация сетевого графика в зависимости от полноты решаемых задач может быть условно разделена на частную и комплексную. Видами частной оптимизации сетевого графика являются: минимизация времени выполнения комплекса работ при заданной его стоимости; минимизация стоимости комплекса работ при заданном времени выполнения проекта.
Комплексная оптимизация представляет собой нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации.
При использовании метода "время — стоимость" предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа 
характеризуется продолжительностью 
, которая может находиться в пределах
, (31)
где 
— минимально возможная (экстренная) продолжительность работы 
, которую только можно осуществить в условиях разработки;
— нормальная продолжительность выполнения работы .
При этом стоимость 
работы 
заключена в границах от 
(при нормальной продолжительности работы) до 
(при экстренной продолжительности работы).
Используя аппроксимацию по прямой (см. рис. 12), можно легко найти изменение стоимости работы 
при сокращении ее продолжительности на величину
(32)
Величина 
, равная тангенсу угла 
наклона аппроксимирующей прямой (см. рис. 12), показывает затраты на ускорение работы 
(по сравнению с нормальной продолжительностью) на единицу времени:
(33)
Рис. 12
Самый очевидный вариант частной оптимизации сетевого графика с учетом стоимости предполагает использование резервов времени работ. Продолжительность каждой работы, имеющей резерв времени, увеличивают до тех пор, пока не будет исчерпан этот резерв или пока не будет достигнуто верхнее значение продолжительности 
. При этом стоимость выполнения проекта, равная до оптимизации
(34)
уменьшится на величину
(35)
Для проведения частной оптимизации сетевого графика кроме продолжительности работ 
, необходимо знать их граничные значения 
и 
, а также показатели затрат на ускорение работ 
, вычисляемые по формуле (33). Продолжительность каждой работы 
целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного резерва времени 
.
Пример 5. Провести частную оптимизацию сетевого графика (рис. 6). Граничные значения продолжительностей работ и , их стоимости 
, коэффициенты затрат на ускорение работ 
приведены в табл.3.
Решение. Свободные резервы времени работ 
были вычислены нами ранее (см. табл. 2). Их ненулевые значения даны в табл. 3. Там же представлены результаты частной оптимизации рассматриваемой сети.
Стоимость первоначального варианта сетевого графика или плана по формуле (33) равна сумме стоимостей всех работ (включая работы, не имеющие резервов и не включенные в табл. 4):
С = 694+50+45+...+35+10=1216 (усл. руб.).
Стоимость нового плана равна 
=1216—293=923 (усл. руб.), т.е. уменьшилась почти на 25%. Новый оптимизированный сетевой график представлен на рис. 13. Нетрудно убедиться в том, что появились новые критические пути длиной = 61 (сутки), например: 
; 
; 
; 
и т. д.
Таблица 4
| № п/п
| Работа
| Продолжительность работы, в сутки
| Свободный резерв времени работы, в сутки
| Стоимость работы
| Коэффициент затрат на ускорение работы, руб./сутки
| Уменьшение стоимости проекта, усл. руб.
| ||
|
|
| ||||||
| 1 | (0,5) | 5 | 9 | 14 | 11 | 60 | 8 | 5*8=40 |
| 2 | (1,4) | 4 | 6 | 10 | 9 | 28 | 4 | 4*4=16 |
| 3 | (1,3) | 3 | 4 | 6 | 1 | 37 | 12 | 1*12=12 |
| 4 | (2,7) | 2 | 3 | 7 | 13 | 86 | 6 | 4*6=2 |
| 5 | (3,6) | 4 | 6 | 9 | 10 | 92 | 10 | 3*10=30 |
| 6 | (4,7) | 3. | 8 | 14 | 2 | 48 | 5 | 2*5=10 |
| 7 | (4,6) | 1 | 3 | 6 | 3 | 64 | 12 | 3*12=36 |
| 8 | (5,8) | 5 | 10 | 18 | 7 | 15 | 1 | 7*1=7 |
| 9 | (5,9) | 3 | 6 | 12 | 16 | 86 | 7 | 6*7=42 |
| 10 | (6,10) | 2 | 5 | 10 | 14 | 44 | 5 | 5*5=25 |
| 11 | (7,10) | 1 | 5 | 15 | 10 | 74 | 4 | 10*4=40 |
| 12 | (8,9) | 2 | 4 | 8 | 1 | 20 | 3 | 1*3=3 |
| 13 | (9,11) | 11 | 17 | 23 | 2 | 40 | 4 | 2*4=8 |
| Итого | 694 | - | 293 | |||||
Примечания: 1. В таблице представлены параметры лишь тех работ, которые имеют свободный резерв времени.
2. Стоимости 
остальных работ: с(0,1)=50; с(0,3)=45; с(1,2)=&2; с(3,4)=55; с(3,5)=72; с(5,б)=30; с(6,7)=26; с(6,9)=75; с (6,8)=42; с(9,10)=35; с(10,11)=10 (усл. руб.).
3. Подчеркнуты те работы, свободные резервы времени которых полностью использованы на увеличение их продолжительности.
Рис 13.
Можно показать, что в этом варианте сетевого графика из 64 полных путей 28 — критические. Если бы верхние границы продолжительностей работ дали возможность полностью использовать резерв времени всех работ, представленных в табл. 4, то в новом плане все полные пути были бы критические.
Итак, в результате оптимизации сети мы пришли к плану, позволяющему выполнить комплекс работ в срок 
= 61 (сутки) при минимальной его стоимости С = 923 (усл. руб.).
Рис. 14
В реальных условиях выполнения проекта может потребоваться ускорение его выполнения, что, естественно, отразится на стоимости проекта: она увеличится. Поэтому необходимо определить оптимальное соотношение между стоимостью проекта С и продолжительностью его выполнения 
, представленное, например, в виде функции С = С(t).
Для оптимизации сетей и, в частности, для нахождения функции С(t) могут быть использованы эвристические методы, т.е. методы, учитывающие индивидуальные особенности сетевых графиков.
Пример 6. Оптимизировать сетевой график, изображенный на рис. 14, в котором указаны максимально возможные продолжительности работ (в сутках). Необходимые для оптимизации исходные данные представлены в табл. 5.
Таблица 5.
| № п/п
| Работа
| Продолжительность работы, сутки
| Коэффициент затрат на ускорение работы.
| Стоимость работы, усл. руб.
| |
минимальная
| максимальная
| ||||
| 1 | (0,1) | 10 | 20 | 6 | 35 |
| 2 | (0,2) | 12 | 32 | 3 | 50 |
| 3 | (1,2) | 2 | 12 | 3 | 15 |
| 4 | (1,3) | 2 | 7 | 8 | 10 |
| 5 | (2,7) | 2 | 7 | 3 | 10 |
| 6 | (3,4) | 16 | 26 | 2 | 50 |
| 7 | (3,5) | 8 | 13 | 6 | 15 |
| 8 | (4,6) | 12 | 22 | 4 | 40 |
| 9 | (5,6) | 20 | 25 | 4 | 30 |
| 10 | (6,7) | 8 | 13 | 5 | 25 |
| 11 | (7,8) | 6 | 11 | 9 | 20 |
| Итого: | 300 | ||||
Решение. Исходный для оптимизации план (см. рис. 14) имеет максимальную продолжительность работ 
и соответственно минимальную стоимость С = 300 (усл. руб.). Найдем все полные пути сетевого графика.
Их четыре:
продолжительностью 
=89 (суток);
продолжительностью 
=99 (суток);
продолжительностью 
=50 (суток.);
продолжительностью 
=50 (суток).
Для удобства дальнейших расчетов представим эти пути графически в виде цепочек работ (рис. 15), в которых цифры над стрелками показывают коэффициенты затрат на ускорение работ 
, а под стрелками — максимально возможные величины уменьшения продолжительности работ 
.
Рис. 15.
I шаг. Уменьшить продолжительность выполнения комплекса можно, как известно, только за счет сокращения продолжительности работ критического пути 
. Из работ критического пути 
наименьший коэффициент затрат на ускорение 
имеет работа (3,4): 
, т.е. 
. Продолжительность работы (3,4) можно сокращать не более чем на 10 суток. При этом изменится длина только критического пути (с 99 до 89 суток) — единственного из четырех путей, проходящего через работу (3,4). А стоимость проекта за счет ускорения работы (3,4) с учетом формул (33) и (34) возрастет до 300+2*10=320 (усл. руб.). Итак, на I шаге:
;
новые длины путей равны 
.
II шаг. Теперь мы имеем два критических пути 
и 
и сократить срок выполнения проекта можно за счет одновременного сокращения их продолжительности. Сократить одновременно 
и 
можно, уменьшив продолжительность работ, лежащих на этих путях (см. рис. 15): либо 
, либо 
, либо 
. Останавливаемся на 
, поскольку при этом обеспечивается минимум затрат на ускорение работы: 
, т. е. 
.
Продолжительность работы 
, можно уменьшить не более чем на 5 суток. На эту величину уменьшатся длины критических путей и 
, а следовательно, и срок выполнения проекта 
. При этом стоимость проекта увеличится с 320 до 320+5*5=345 (усл. руб.). Итак, на II шаге:
;
Продолжая аналогичным образом сокращать продолжительность работ, получим
III шаг. 
, т.е. 
. Сокращая продолжительность работы 
до 10 суток, найдем
;
IV шаг. 
, т.е. 
. Сокращая продолжительность работы 
до 5 суток, найдем
;
V шаг. Сокращая продолжительность работы 
до 5 су-
ток, найдем (учитывая, что 
=9)
;
.
VI шаг. Теперь несокращенными остались продолжительности трех критических работ: 
и 
критического пути 
, каждую из которых можно сократить до 5 суток, и 
критического пути , которую можно сократить до 10 суток. Сокращение какой-либо одной из названных величин не приведет к сокращению продолжительности выполнения проекта, ибо при этом сократится лишь один из двух путей, а длина несокращенного пути, который станет единственным критическим путем, не изменится. Поэтому последовательно сокращая 
и 
до 5 суток (с учетом времени сокращения продолжительности работ), найдем (теперь коэффициент затрат на ускорение работ равен 
= 4+4 = 8):
;
VII шаг. Продолжительность работы 
можно сократить еще до 5 суток и на тот же срок можно сократить 
(иначе срок выполнения проекта не изменится). Полагая, что 
= 4+6=10, найдем
.
График оптимальной зависимости стоимости проекта 
от продолжительности его выполнения показан на рис. 16. С помощью этого графика можно, с одной стороны, оценить минимальную стоимость проекта при любом возможном сроке его выполнения, а с другой стороны — найти предельную продолжительность выполнения проекта при заданной его стоимости. Например, при продолжительности проекта t = 79 (суток) минимальная стоимость выполнения рассматриваемого комплекса составит 375 (усл. руб.), а при стоимости выполнения комплекса, например, 540 (усл. руб.) предельная продолжительность проекта составит 55 (суток). С помощью функции 
можно оценить дополнительные затраты, связанные с сокращением сроков завершения комплекса. Так, сокращение продолжительности проекта с 79 до 55 суток потребует дополнительных затрат 540—375=165 (усл. руб.).
Рис. 16.
Итак, мы рассмотрели один из возможных эвристических алгоритмов оптимизации сетевого графика (см. рис. 14). Можно было использовать и другие алгоритмы. Например, взять в качестве первоначального план, имеющий не максимальные, а минимальные значения продолжительности работ 
и соответственно максимальную стоимость проекта. А затем последовательно увеличивать продолжительность выполнения комплекса работ путем увеличения продолжительности работ, расположенных на некритических, а затем и на критическом (ских) пути в порядке убывания коэффициентов затрат .
Следует заметить, что при линейной зависимости стоимости работ от их продолжительности задача построения оптимального сетевого графика может быть сформулирована как задача линейного программирования, в которой необходимо минимизировать стоимость выполнения проекта при двух группах ограничений. Первая группа ограничений показывает, что продолжительность каждой работы должна находиться в пределах, установленных неравенством (31). Вторая группа ограничений требует, чтобы продолжительность любого полного пути сетевого графика не превышала установленного директивного срока выполнения проекта. Однако решать такие задачи классическими методами линейного программирования, как правило, неэффективно, в связи с чем используются специально разработанные методы.
Решение задач.
- Для сетевого графика (рис 17) найти все полные пути, критический путь; рассчитать ранние и поздние сроки свершения событий, начала и окончания работ; определить резервы времени полных путей и событий, резервы времени (полные, частные резервы первого вида, свободные и независимые) работ и коэффициент напряженности работ.
Решение:
Сетевой график:
Полные пути:
Длины полных путей соответственно равны: 92, 52, 92, 122, 111, 97, 71 (сут.).
Наиболее продолжительным является путь 
. Таким образом, он и является критическим.
Найдем теперь ранние и поздние сроки свершения событий, используя формулы (1), (2), (4):
1. 
2. 
Ранние сроки начала и окончания работ:
- Используя формулу (6) получим, что ранний срок начала работ совпадает с ранним сроком наступления начального события, которое подсчитано выше.
- Вычислим теперь ранний срок окончания работ, используя формулу (7):
Поздние сроки начала и окончания работ:
- Используя формулу (8) получим, что поздний срок окончания работ совпадает с поздним сроком свершения события, которое подсчитано выше.
- Вычислим теперь поздний срок начала работ, используя формулу (9):
Резервы времени путей:
Вычислим полный резерв времени, используя формулу (11):
Вычислим частный резерв времени, используя формулу (12):
Вычислим свободный резерв времени, используя формулу (14):
Вычислим независимый резерв времени, используя формулу (16):
Вычислим коэффициент напряженности работы, используя формулу (29):
подкритическая зона;
подкритическая зона;
резервная зона;
резервная зона;
резервная зона;
подкритическая зона.
Занесем полученные данные в таблицу:
| № п/п
| Работа
| Продолжительность работы
| Сроки начала и окончания работы
| Резервы времени работы
| |||||||
| 
| 
| 
| 
| 
| 
| 
| ||||
| 1 | (0,1) | 18 30 | 0 | 18 | 30 | 48 | 30 | 28 | 0 | -2 | |
| 2 | (0,2) | 30 | 0 | 30 | 2 | 32 | 2 | 0 | 0 | -2 | |
| 3 | (0,3) | 15 | 0 | 15 | 13 | 28 | 13 | 11 | 0 | -2 | |
| 4 | (1,4) | 22 | 18 | 40 | 48 | 70 | 30 | 0 | 0 | -30 | |
| 5 | (1,9) | 12 | 18 | 30 | 88 | 100 | 70 | 40 | 40 | 10 | |
| 6 | (2,7) | 25 | 30 | 55 | 32 | 57 | 2 | 0 | 0 | -2 | |
| 7 | (2,10) | 30 | 30 | 60 | 60 | 90 | 30 | 30 | 30 | 28 | |
| 8 | (3,6) | 9 | 15 | 24 | 28 | 37 | 13 | 0 | 0 | -13 | |
| 9 | (3,5) | 25 | 15 | 40 | 40 | 65 | 25 | 12 | 0 | -13 | |
| 10 | (4,9) | 30 | 40 | 70 | 70 | 100 | 52 | 0 | 0 | -30 | |
| 11 | (5,8) | 15 | 40 | 55 | 65 | 80 | 25 | 0 | 0 | -25 | |
| 12 | (6,7) | 20 | 24 | 44 | 37 | 57 | 13 | 0 | 11 | -2 | |
| 13 | (6,8) | 5 | 24 | 29 | 75 | 80 | 51 | 38 | 26 | 13 | |
| 14 | (7,10) | 35 | 55 | 90 | 55 | 90 | 0 | 0 | 0 | -2 | |
| 15 | (8,11) | 42 | 55 | 97 | 80 | 122 | 25 | 0 | 25 | 0 | |
| 16 | (9,11) | 22 | 70 | 92 | 100 | 122 | 30 | 0 | 30 | 0 | |
| 17 | (10,11) | 32 | 90 | 122 | 90 | 122 | 0 | 0 | 0 | 0 | |
2. В таблице указаны оценки времени выполнения работ сетевого графика, данные ответственными исполнителями и экспертами.
| № п/п
| Работа
| Оценки времени выполнения работы, сутки
| ||
оптимистическая
| пессимистическая 
| наиболее вероятная
| ||
| 1 | (1,2) | 5 | 9 | 6 |
| 2 | (1,3) | 2 | 7 | 5 |
| 3 | (1,4) | 4 | 10 | 8 |
| 4 | (3,4) | 9 | 14 | 11 |
| 5 | (2,5) | 7 | 13 | 10 |
| 6 | (4,5) | 1 | 4 | 3 |
Необходимо: а) построить сетевой график; б) определить средние (ожидаемые) значения продолжительности работ; в) определить критический путь и его длину. Полагая, что продолжительность критического пути распределена по нормальному закону, найти: а) вероятность того, что срок выполнения комплекса работ не превысит 17 суток; б) максимальное значение продолжительности выполнения проекта, которое можно гарантировать с надежностью 0,95.
Решение:
1. Сетевой график:
2. Найдем средние (ожидаемые) значения продолжительности работ. Для этого воспользуемся формулой (21):
3. Определим критический путь и его длину:
Полные пути: 
Наиболее продолжительным является путь 
. Таким образом, он и является критическим. Его длина составляет 
4. Найдем вероятность того, что срок выполнения комплекса работ не превысит 17 суток. Для этого воспользуемся формулой (26):
Но сначала вычислим 
по формуле (22) для критического пути:
Найдем 
Тогда 
Вероятность близка к 1, то есть с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.
5. Вычислим теперь максимальное значение продолжительности выполнения проекта, которое можно гарантировать с надежностью 0,95.
Воспользуемся формулой (28):
, где 
.
Таким образом, срок выполнения проекта не превысит 21 суток.
Заключение.
В данной курсовой работе представлены основные типы задач по курсу сетевого планирования и управления, расширены представления в этой сфере, а также в различных направлениями и методах сетевого планирования и управления.
Литература:
1. Н. Ш. Кремер. Исследование операций в экономике. М., Юнити, 2004.
Дата добавления: 2018-09-22; просмотров: 3174; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!