Анализ и оптимизация сетевого графика

ВВЕДЕНИЕ

 

Методы СПУ используются при планировании сложных комплексных проектов. Характерной особенностью таких проектов является то, что они состоят из ряда отдельных, элементарных работ. Они обуславливают друг друга так, что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие. Например, укладка фундамента не может быть начата раньше, чем будут доставлены необходимые материалы; эти материалы не могут быть доставлены раньше, чем будут построены подъездные пути; любой этап строительства не может быть начат без составления соответствующей технической документации и т.д.

СПУ состоит из трех основных этапов.

1. Структурное планирование начинается с разбиения проекта на четко определенные операции, для которых определяется продолжительность. Затем строится сетевой график, который представляет взаимосвязи работ проекта. Это позволяет детально анализировать все работы и вносить улучшения в структуру проекта еще до начала его реализации.

2. Календарное планирование предусматривает построение календарного графика, определяющего моменты начала и окончания каждой работы и другие временные характеристики сетевого графика. Это позволяет, в частности, выявлять критические операции, которым необходимо уделять особое внимание, чтобы закончить проект в директивных срок. Во время календарного планирования определяются временные характеристики всех работ с целью проведения оптимизации сетевой модели, которая улучшает эффективность использования какого-либо ресурса.

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

 

СТРУКТУРНОЕ ПЛАНИРОВАНИЕ

 

Основными понятиями сетевых моделей являются понятия события и работы.

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

По своей физической природе работы можно рассматривать как:

· действие: заливка фундамента бетоном, составление заявки на материалы, изучение конъюнктуры рынка;

· процесс: старение отливок, выдерживание вина, травление плат;

· ожидание: ожидание поставки комплектующих, пролеживание детали в очереди к станку.

По количеству затрачиваемого времени работа, может быть:

· действительной, т.е. требующей затрат времени;

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

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

Таким образом, начало, и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для идентификации конкретной работы используют код работы (i,j), состоящий из номеров начального (i-го) и конечного (j-го) событий, например (2,4).

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

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

При построении сетевого графа необходимо следовать следующим правилам:

n длина стрелки не зависит от времени выполнения работы;

n стрелка не обязательно должна представлять прямолинейный отрезок;

n для действительных работ используются сплошные, а для фиктивных - пунктирные стрелки;

n каждая операция должна быть представлена только одной стрелкой;

n не должно быть параллельных работ между одними и теми же событиями, для избежания такой ситуации используют фиктивные работы;

n следует избегать пересечения стрелок;

n не должно быть стрелок, направленных справа налево;

n номер начального события должен быть меньше номера конечного события;

n не должно быть висячих событий, кроме исходного;

n не должно быть тупиковых событий, кроме завершающего;

n не должно быть циклов.

Поскольку работы, входящие в проект могут быть логически связаны друг с другом, то необходимо всегда перед построением сетевого графика дать ответы на следующие вопросы

Þ Какие работы необходимо завершить непосредственно перед началом рассматриваемой работы?

Þ Какие работы должны непосредственно следовать после завершения данной работы?

Þ Какие операции могут выполняться одновременно с рассматриваемой работой?

 

Основное назначение календарного плана - определить:

а) общую продолжительность работы и сроки ввода в действие отдельных участков;

б) сроки поставки основных материалов, а также сроки поставки и монтажа основного технологического оборудования предприятий;

в) сроки выдачи технической документации на проведение работ;

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

и транспортных средств.

Календарный план проекта производства работ составляют на основе данных научных изысканий и рабочих чертежей объекта, его увязывают с директивными сроками сдачи объекта и сроками поставки материалов. Такой календарный план служит основным документом для решения вопросов оперативного руководства и планирования работ.

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

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

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

Наиболее удобным в этих условиях являются системы сетевого планирования и управления (СПУ), основанные на применении сетевых моделей планируемых процессов, допускающих использование современной вычислительной техники, позволяющих быстро определить последствия различных вариантов управляющих воздействий и находить наилучшие из них. Они дают возможность руководителям своевременно получать достоверную информацию о состоянии дел, о возникших задержках и возможностях ускорения хода работ, концентрируют внимание руководителей на "критических" работах, определяющих продолжительность проведения разработки в целом, заставляют совершенствовать технологию и организацию работ, непосредственно влияющих на сроки проведения разработки, помогают составлять рациональные планы работ, обеспечивают согласованность действий исполнителей.

Применение методов СПУ в конечном счете должно обеспечить получение календарного плана, определяющего сроки начала и окончания каждой операции. Построение сети является первым шагом на пути к достижению этой цели. Вторым шагом является расчет сетевой модели, который выполняют прямо на сетевом графике, пользуясь простыми правилами.

К временным параметрам событий относятся:

· ранний срок наступления события i – Tp(i);

· поздний срок наступления события i - Tп(i);

· резерв времени наступления события i – R(i).

Tp(i) - это время, необходимое для выполнения всех работ, предшествующих данному событию i.

Tп(i) - это такое время наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети.

R(i) - это такой промежуток времен, на который может быть отсрочено наступление этого события без на рушения сроков завершения разработки в целом.

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

 

Пример построения сетевого графика

Пусть необходимо спроектировать, изготовить и сдать в эксплуатацию электронный программный продукт согласно полученному техническому заданию (ТЗ). Срок выполнения проекта равен 30 дней. Известно, что для этого необходимо выполнить следующие работы (табл.1). Продолжительность каждой работы (чел-дни), определяется экспертами.

 

Таблица 1 - Исходные данные для расчета

 

№ работы	Перечень событий и работ	Продолжительность работы, чел-дни	Примечание
(0, 1)	Составление и анализ ТЗ.
(0, 2)	Определение общего перечня выпускаемых документов
(0, 5)	Составление плана-графика разработки
(1, 3)	Разработка концепции электронного курса продукта
(1, 4)	Согласование концепций электронного курса продукта с соисполнителями
(2, 4)	Определение перечня документов предъявляемых на предварительные испытания
(2, 5)	Концепции электронного курса разработаны
(3, 6)	Проведение предварительных испытаний
(4, 6)	Доработка и выпуск программного продукта
(4, 7)	Окончательное согласование программного продукта с соисполнителями
(5, 7)	Комплексная отладка программного продукта
(5, 8)	Разработка функциональной структуры проведения эксперимента
(6, 9)	Составление программы и выбор методики испытания электронного программного продукта
(6, 10)	Система электронного программного продукта предъявлена на испытание
(7, 10)	Испытание работы электронного программного продукта
(8, 11)	Разработка и согласование электронного программного продукта, составление акта испытаний
(8, 12)	Доработка рабочей документации по результатам испытаний
(9, 12)	Доработка электронного курса по результатам ГИ
(10, 12)	Доработка рабочей документации программного продукта
(11, 12)	Сдача электронного программного продукта ГК
Итого

 

Планирование НИР с применением сетевого метода ведется в следующем порядке:

1) составляется перечень событий и работ;

2) устанавливается топология сети;

3) строится сетевой график по теме;

4) определяется продолжительность работ;

5) рассчитываются параметры сетевого графика;

6) определяется продолжительность критического пути;

7) проводится анализ и оптимизация сетевого графика, если это необходимо.

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

Исходные данные для расчета получают методом экспертных оценок (табл.1).

На основании данных, представленных в таблице 1, необходимо построить сетевой график (рис.1). Требуется:

а) ввести обозначения вершин и рёбер;

б) построить дерево путей сетевого графика и найти по нему критический путь;

в) найти критический путь и резервы времени.

 

Пунктирными линиями на графике изображены фиктивные работы. Здесь они нужны для синхронизации работ (затраты времени и ресурсов на них равны 0). В других случаях фиктивные работы могут отражать отсрочки времени и ожидания (тогда при нулевых затратах ресурсов затраты времени ненулевые). Вершинами данного орграфа являются события; рёбрам соответствуют работы.

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

Для правильной нумерации событий нумерацию начинают с исходного события, которому даётся номер 0. Из исходного события 0 вычёркивают все следующие за ним работы, на оставшейся сети находят событие, которому не предшествует ни одна работа. Это событие получает номер 1. Затем вычёркивают события, следующие за событием 1, и на оставшейся части сети, вновь находят событие, которому не предшествует ни одна работа, ему присваивают номер 2, и так продолжается до завершающего события.

Фиктивные работы участвуют в процессе равноправно.

 

Рис.1 – Сетевой график выполнения работ

 

Обозначения вершин:

1-й слой содержит вершину 0;

2-й слой содержит вершины 1, 2;

3-й слой содержит вершины 3, 4, 5;

4-й слой содержит вершины 6, 7, 8;

5-й слой содержит вершины 9, 10, 11;

6-й слой содержит вершину 12.

 

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

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

 

► 1-й способ вычисления критического пути ("графический")

Совокупность возможных путей сетевого графика (всего их 14) соответствует дереву путей сетевого графика (рис.2).

- общее время выполнения работ равно, соответственно: 29, 28, 26, 25, 27, 19, 18, 20, 22, 22, 16, 24, 24, 18 дней.

Критическим (наибольшим) является путь, длительность которого равна 29 дням, содержащий работы (0,1), (1,3), (3,6), (6,9), (9,12).

 

► 2-й способ вычисления критического пути ("табличный")

 

Вычислим и сведём в таблицу 2 временные параметры сетевого графика.

 

Таблица 2 - Временные параметры сетевого графика.

 

Номер события	Сроки совершения события	Резерв времени, С3 – с2
ранний	поздний

 

Рис.2 - Дерево путей сетевого графика

 

Ранние сроки для событий:

0) 0,

1) 6,

2) 3,

3) 6+4=10,

4) max{3+0;6+4}=max{3;10}=10,

5) max{8;3+3}= max{8;6}=8,

6) max{10+13; 10+10}=max{23; 20}=23,

7) max{10+5; 8+4}=max{15; 12}=15,

8) 8+5=13,

9) 23+5 = 28,

10) max{23+0; 15+7}=max{23; 22}=23,

11) 13+7 = 20,

12) max{13+5; 28+1; 23+5; 20+4}=max{18; 29; 28; 24}=29.

 

Поздние сроки для событий:

12) 29 (этот срок равен раннему сроку завершающего события),

11) 29−4 = 25,

10) 29−5 = 24

9) 29−1 = 28,

8) min{25−7; 29−5}=min{18; 24}=18,

7) 24−7 =17

6) min{28−5; 24−0}=min{23; 24}=23,

5) min{17−4; 17−5}=min{13; 12}=12,

4) min{23−10; 17−5}=min{13; 12}=12

3) 23−13=10,

2) min{12−0; 12−3}=min{12; 9}=9,

1) min{10−4; 14−4}=min{6; 8}=6,

0) min{6−6; 12−8; 9-3}=min{0; 4; 6}=0.

 

Резерв времени, например, для события 2 равный 9 – 3 = 6 означает, что время свершения события 2 может быть задержано на 6 единиц времени без увеличения общего срока выполнения проекта.

События, не имеющие резерва времени, образуют критический путь, содержащий работы (0,1), (1,3), (3,6), (6,9), (9,12). Его длительность равна 29.

 

в) Вычисление резерва времени для работ.

Различают четыре резерва времени:

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

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

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

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

 

Обычно ограничиваются расчётом полного и свободного резервов. Последовательность расчета полного и свободного резерва времени приведена в таблице 3.

 

 

Таблица 3 - Расчёт полного и свободного резервов времени

 

Работа	Продолжительность, дни	Сроки совершения события, дни	Полный резерв,     с5 – с3	Свободный резерв,   с2 (табл.2) – с3 – с2
раннее начало	раннее окончание,   с3 + с2	позднее начало,   с6 – с2	позднее окончание
(0, 1)			0+6=6	6‐6=0		0‐0=0 (к)	6‐0‐6=0
(0, 2)			0+3=3	9‐3=6		6‐0=6	3‐0‐3=0
(0, 5)			0+8=8	12‐8=4		4‐0=4	8‐0‐8=0
(1, 3)			6+4=10	10‐4=6		6‐6=0 (к)	10‐6‐4=0
(1, 4)			6+4=10	12‐4=8		8‐6=2	10‐6‐4=0
(2, 4)			3+0=3	12‐0=12		12‐3=9	10‐3‐0=7
(2, 5)			3+3=6	12‐3=9		9‐3=6	8‐3‐3=2
(3, 6)			10+13=23	23‐13=10		10‐10=0 (к)	23‐10‐13=0
(4, 6)			10+10=20	23‐10=13		13‐10=3	23‐10‐10=3
(4, 7)			10+5=15	17‐5=12		12‐10=2	15‐10‐5=0
(5, 7)			8+4=12	17‐4=13		13‐8=5	15‐8‐4=3
(5, 8)			8+5=13	17‐5=12		12‐8=4	13‐8‐5=0
(6, 9)			23+5=28	28‐5=23		23‐23=0 (к)	28‐23‐5=0
(6, 10)			23+0=23	24‐0=24		24‐23=1	23‐23‐0=0
(7, 10)			15+7=22	24‐7=17		17‐15=2	23‐15‐7=1
(8, 11)			13+7=20	24‐7=17		17‐13=4	20‐13‐7=0
(8, 12)			13+5=18	29‐5=24		24‐13=11	29‐13‐5=11
(9, 12)			28+1=29	29‐1=28		28‐28=0 (к)	29‐28‐1=0
(10, 12)			23+5=28	29‐5=24		24‐23=1	29‐23‐5=1
(11, 12)			20+4=24	29‐4=25		25‐20=5	29‐20‐4=5

 

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

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

Полный резерв времени работы вычисляем как разность сроков позднего начала работ и раннего срока события, с которого она начинается. Например, полный резерв времени для работы (0, 2) равен 6 единицам времени, т.е. срок выполнения данной работы можно увеличить на 6, при этом срок выполнения комплекса работ не изменится.

Свободный резерв времени работы вычисляем как разность раннего срока события, которым она завершается, раннего срока события, с которого она начинается, и продолжительности работы. Например, свободный резерв времени для работы (5, 7) равен 3 единицам времени, т.е. начало данной работы можно отсрочить на 3 или можно увеличить продолжительность данной работы на 3, при сохранении общего срока выполнения проекта; но без затрат резерва времени предшествующих ей работ.

Работы, лежащие на критическом пути, имеют следующую особенность: начальные и конечные события критических работ имеют нулевые резервы событий. Однако, как показывает практика, что только требование нулевых резервов событий является необходимым, но не достаточным условием критического пути.

Разность между продолжительность критического пути Ткр и продолжительностью любого другого пути T_L называется полным резервом времени пути L, т.е. R_L= Ткр - T_L. Этот резерв показывает, на сколько в сумме может быть увеличена продолжительность всех работ данного пути L, чтобы при этом не изменился общий срок окончания всех работ, т.е. Ткр.

Rп(i,j) показывает максимальное время, на которое может быть увеличена продолжительность работы (i,j) или отсрочено ее начало, чтобы продолжительность проходящего через нее максимального пути не превысила продолжительности критического пути. Важнейшее свойство полного резерва работы (i,j) заключается в том, что если его использовать частично или полностью, то уменьшится полный резерв у работ, лежащих с работой (i,j) на одних путях. Таким образом полный резерв времени принадлежит не одной данной работе (i,j), а всем работам, лежащим на путях, проходящим через эту работу.

Rс(i,j) показывает максимальное время, на которое можно увеличить продолжительность отдельной работы или отсрочить ее начало, не меняя ранних сроков начала последующих работ, при условии, что непосредственно предшествующее событие наступило в свой ранний срок. Использование свободного времени на одной из работ не меняет величины свободных резервов времени остальных работ сети.

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

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

График привязки можно построить без предварительного расчета ранних сроков начала и окончания всех работе, используя только данные о продолжительности работ. При этом необходимо помнить, что работа (i,j) может начать выполняться только после того как будут выполнены все предшествующие ей работы (k,j).

Построим график привязки для следующих исходных данных (табл.4), имея в виду, что число исполнителей должно быть не менее 99/29 = 3.4, то есть 4 человека. Для выполнения данных работ руководитель проекта планируется привлечь дополнительно несколько программистов.

 

 

Таблица 4 - Исходные данные для построения графика привязки

 

№ работы	Перечень событий и работ	Продолжительность работы, чел-дни	Кол-во исполнителей
(0, 1)	Составление и анализ ТЗ.		программист 1
(0, 2)	Определение общего перечня выпускаемых документов		руководитель проекта
(0, 5)	Составление плана-графика разработки		программист 2
(1, 3)	Разработка концепции электронного курса продукта		программист 1
(1, 4)	Согласование концепций электронного курса продукта с соисполнителями		программист 4
(2, 4)	Определение перечня документов предъявляемых на предварительные испытания
(2, 5)	Концепции электронного курса разработаны		руководитель проекта
(3, 6)	Проведение предварительных испытаний		руководитель проекта
(4, 6)	Доработка и выпуск программного продукта		программист 1
(4, 7)	Окончательное согласование программного продукта с соисполнителями		программист 2
(5, 7)	Комплексная отладка программного продукта		руководитель проекта
(5, 8)	Разработка функциональной структуры проведения эксперимента		программист 3
(6, 9)	Составление программы и выбор методики испытания электронного программного продукта		руководитель проекта
(6, 10)	Система электронного программного продукта предъявлена на испытание
(7, 10)	Испытание работы электронного программного продукта		программист 2
(8, 11)	Разработка и согласование электронного программного продукта, составление акта испытаний		программист 3
(8, 12)	Доработка рабочей документации по результатам испытаний		программист 4
(9, 12)	Доработка электронного курса по результатам ГИ		руководитель проекта
(10, 12)	Доработка рабочей документации программного продукта		программист 1
(11, 12)	Сдача электронного программного продукта ГК		программист 3
Итого