Курсовая работа: Сетевое планирование и управление

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

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

Сетевые графики составляются на начальном этапе планирования. Главными элементами сетевой модели являются события и работы.

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

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

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

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

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

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

Если на ребре указано направление связи между вершинами, то оно называется дугой. Ориентация дуги указывается стрелками. Дуга, соединяющая вершину i с вершиной j, обозначается символом (i, j) или pij.

Если все соединения в графе изображаются дугами, то граф называется ориентированным, или орграфом.

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

Путь, у которого начальная вершина совпадает с конечной, называется контуром. Контур с одной вершиной – петля.

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

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

Любой путь в сетевом графике от истока к стоку называется полным.

Если дугам (ребрам) графа сопоставлены какие-то числовые характеристики – весами.

Вершина хi («предок») предшествует в графе вершине хj («потомок»), если существует путь из хi в хj .

Граф является упорядоченным, если в нем порядковый номер «предка» всегда меньше порядкового номера «потомка».

Графический номер упорядочения графа реализуется по алгоритму Фалкерсона:

1-ый шаг – выделяем вершины, не имеющие «предков», и последовательно нумеруем их в произвольном порядке;

2-ый шаг – мысленно вычеркиваем из графа все вершины, имеющие номера и дуги из них выходящие;

3-ый шаг – в получившемся графе повторяем процедуры 1-го и 2-го шагов до тех пор, пока все вершины не будут пронумерованы.

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

Сетевой график – это связанный взвешенный орграф без контуров (петель).

На изображении комплекса работ с помощью сетевого графика основано сетевое планирование и управление (СПУ).

События обозначаются на сетевом графике вершинами.

Подготовка исходных данных для построения сетевого графика включает:

- определение начального и конечного событий;