07. Задача сетевого планирования
Задача сетевого планирования является одной из важнейших задач, решаемых в условиях производства. Графический метод планирования применяется для визуализации организационно-управленческих процессов. С помощью сетевых графиков моделируются процессы реализации проектов. Сетевой график представляет собой множество вершин, соединённых между собой дугами. Каждая вершина представляет собой факт наступления определённого события, дуга символизирует выполнение работы. Каждой работе приписывают количественные характеристики (например время), необходимые для выполнения работы.
Один из главных элементов сетевой модели, означающий протяженный во времени процесс, требующий затрат ресурсов, или ожидание, или зависимость (фиктивная работа)
Протяженный во времени процесс не требующий затрат труда.
Логическая связь между двумя или несколькими работами (событиями), не требующими затрат труда, материальных ресурсов или времени
Любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работой.
Момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.
Любой путь, начало которого совпадает с исходным событием сети, а конец – с завершающим.
Путь от начала события до данного события сети.
Путь, совершающий данное событие с завершающим событием сети.
Наиболее продолжительный путь в сетевом графике.
Рассмотрим пример: необходимо построить сетевой график реализации проекта строительства здания и определить сроки реализации проекта. Перечень работ приведём в таблице.
Перечень работ по строительству здания
Продолжительность выполнения, мес.
Оформление заказа на строительные материалы и их получение
Подготовка строительной техники и оборудования к работе
Подготовка строительной площадки
Рытьё траншей под фундамент
Планировка и оформление придворовой территории
Внутренняя отделка помещений
Для построения сетевого графика определим перечень событий:
2 – оформлен заказ и получены строительные материалы;
3 – строительная техника подготовлена к работе;
4 – подготовлена строительная площадка и вырыты траншеи под фундамент;
6 – проведена планировка и оформлена придворовая территория;
7 – проведены коммуникации;
8 – здание готово к эксплуатации.
На основе перечня событий и работ построим сетевой график.
Числа над работами указывают их продолжительность.
Используя метод Форда вычисляем длиннейший путь графа, который определяет самую длительную технологическую цепочку, а следовательно кратчайший срок выполнения задания.
На рисунке отмечены конечные метки для каждой вершины (работы) и критический путь, продолжительность которого равна 11 мес. Таким образом, ранний срок завершающего события равен 11 мес.
Работы в сетевом графике должны быть упорядочены по циклам (слоям). Существуют разные способы разбиения на слои. Например, можно выделить слои в графе исключением «потоков».
Пример. Дан граф. Требуется перенумеровать вершины графа.
1) Выделяем вершины, не имеющие предков (нет входящих дуг), определяем вершины из 1-го слоя (цикла). Это вершина . Вычеркиваем выходящие из вершины дуги. Получим подграф (граф без вершины ).
2) Выделяем в подграфе вершины, не имеющие предков (входящих дуг). Это вершины и . Они образуют 2-ой слой. Вычеркнем дуги, выходящие из вершин и и рассматриваем подграф (граф без вершин , и ).
3) Вновь выделяем вершины, не имеющие входящих дуг. Это , , , (образуют третий слой). Вычеркиваем дуги выходящие из этих вершин.
4) Далее находим вершины четвёртого слоя , , и в последний слой попадает вершина .
Построим граф и перенумеруем вершины. Внутри слоя безразличен порядок нумерации. Вершины внутри каждого слоя не связаны.
Выделение слоёв можно начать с последнего слоя. Для этого находим вершины не имеющие потомков (нет выходящих дуг). Это вершина . Вычеркиваем все дуги входящие в вершину .
Чтобы найти вершины предпоследнего слоя, выбираем вершины не имеющие потомков. Это вершины ,, , . И т. д.
Разбиение двумя способами может дать различные результаты.
Существует другой способ разбиения графа на циклы (слои).
Пусть граф задан в виде матрицы, элементы которой равны длинам дуг (продолжительности работ).
Составим матрицу смежности вершин, поставив в клетках единички, если существует дуга, идущая из вершины в вершину .
Сложим «1» по столбцам матрицы. Там где такая сумма равна нулю предков нет (нет входящих дуг). Это первый столбец. Вершина образует первый слой.
Вычеркиваем строку с номером «1» из матрицы и в новой матрице (имеющей теперь на одну строку меньше) вновь складываем «1» по столбцам. Второй и третий столбцы с нулевой суммой. Вершины и образуют второй слой. Вычеркиваем вторую и третью строки. Вершина Входит в третий слой. Аналогично находим четвёртый слой из вершин и . Вершина входит в последний слой.
Разбиение на слои можно начать с суммирования «1» по строкам, с последующим вычеркиванием соответствующих столбцов. При этом на первом шаге определяем последний слой, затем предпоследний и т. д.
Задача, предлагаемая в задании 4 состоит из четырёх этапов:
1. Упорядочивание планируемых работ по производственным циклам.
2. Построение математической модели задачи в виде размеченного графа.
3. Поиск длиннейшего пути графа, которому отвечает самая длительная технологическая цепочка выполняемых работ, которая в свою очередь, определяет кратчайший срок выполнения всего производственного задания.
4. Анализ полученных результатов и определение возможных резервов для сокращения срока выполнения задания.
Поясним это на конкретном примере.
Задача. Составить сетевой график и определить минимальное время (в днях) выполнения производственного задания. Продолжительности (сроки) выполнения работ и последовательность их выполнения заданы в таблице (для каждой работы указано, после выполнения каких работ Может быть начато её выполнение). Вместо названий работы задаются условно их номерами. Считается, что каждая работа начинается немедленно, как только появилась возможность.
Задачи сетевого планирования
На этой странице вы найдете решенные типовые задания из контрольных по сетевому планированию — разделу экономико-математических методов и моделей.
В рамках изучения сетевого анализа студенты обычно учатся: строить график сети по табличному или словесному описанию проекта (и наоборот), находить ранние и поздние сроки начала и окончания работ, резервы, критический путь и минимальное времеия завершения проекта. Более сложные задания подразумевают различные варианты корректировки и оптимизации сетевого графика (с увеличением времени и уменьшением затрат, или наоборот, с уменьшением времени и увеличением расходов), задачи распределения ресурсов. Изучаются различные графические способы отображения как сетевого графика (см. задачи ниже), так и других диаграмм для проекта (диаграмма Ганта, линейный график).
Примеры решений задач по сетевому планированию онлайн
Задача 1. Для заданной сетевой модели некоторого комплекса работ определить время и критический путь.
Задача 2. Издатель имеет контракт с автором на издание его книги. Ниже представлена последовательность (упрощенная) процессов, приводящая к реализации проекта издания книги. Необходимо разработать сеть для этого проекта.
Задача 3. 1. По заданному перечню работ, построить сетевой график.
2. Определить продолжительности полных путей графика.
3. Определить и выделить критический путь.
4. Определить резерв времени каждого пути.
5. Определить коэффициенты напряженности пути.
6. Определить ранние и поздние сроки начала и окончания работы.
7. Определить полный резерв времени каждой работы.
Задача 4. Рассчитать параметры сетевого графика (см. таблицу работ в файле).
Задача 5. На сетевом графике найти ранние и поздние сроки наступления событий, определить критический путь и резервы времени каждого события.
Задача 6. Построить сетевой график. Решить задачу оптимального распределения ресурсов по работам при постоянных интенсивностях. Наличие ресурса R=10. Работы не допускают перерыва в их выполнении.
Задача 7. По данным варианта требуется:
1) построить сетевую модель;
2) определить критические пути модели;
3) провести максимально возможное уменьшение сроков выполнения проекта при минимально возможных дополнительных затратах