Меню

Решение задач сетевого планирования



Табличный метод расчета параметров сетевого графика

Пример . Определить временные параметры сетевого графика на рисунке, пользуясь табличным методом.
Решение проводим через калькулятор: все вычисления будем заносить в таблицу 3.
Перечень работ и их продолжительность перенесем во вторую и третью графы. При этом работы следует записывать в графу 2 последовательно: сначала начиная с номера 1, затем с номера 2 и т.д.
В первой графе поставим число, характеризующее количество непосредственно предшествующих работ (КПР) тому событию, с которого начинается рассматриваемая работа. Так, для работы (5,10) в графу 1 поставим число 2, т.к. на номер 5 оканчиваются 2 работы: (1,5) и (3,5).
Таблица 3 – Табличный метод расчета сетевого графика

КПР Код Работы Продолжительность работы Ранние сроки Поздние сроки Резервы времени
(i,j) t(i,j) tрн(i,j) tро(i,j) tпн(i,j) tпо(i,j) Rп Rс
1 2 3 4 5 6 7 8 9
1 2 3 4 5=3+4 6=7-3 7 8 9
(1,2) 5 5 2 7 2
(1,3) 7 7 7
(1,5) 4 4 11 15 11 3
1 (2,4) 5 5 7 7 2 2
1 (2,6) 8 5 13 12 20 7
1 (3,4) 7 7 7 7
1 (3,5) 7 7 15 15 8
1 (3,8) 7 7 14 13 20 6
1 (3,9) 11 7 18 12 23 5 1
2 (4,7) 12 7 19 7 19
2 (5,10) 5 7 12 15 20 8 2
1 (6,11) 7 13 20 20 27 7 7
1 (7,9) 19 19 23 23 4
1 (7,11) 8 19 27 19 27
1 (8,9) 14 14 23 23 9 5
1 (8,10) 14 14 20 20 6
1 (8,11) 4 14 18 23 27 9 9
3 (9,11) 4 19 23 23 27 4 4
2 (10,11) 7 14 21 20 27 6 6

Работа (i,j)Количество предшествующих работПродолжительность tijСроки выполнения работРезервы времени
ранниепоздниеработсобытий Rj
начало tij Р.Н. окончание tij Р.О. начало tij П.Н. окончание tij П.О. полный tij П свободный tij С.В.
1 2 3 4 5 6 7 8 9 10
(0,1) 15 15 15
(1,2) 1 16 15 31 15 31
(1,3) 1 6 15 21 22 28 7 7
(2,4) 1 6 31 37 31 37
(3,5) 1 5 21 26 28 33 7 7
(4,6) 1 8 37 45 37 45
(5,6) 1 6 26 32 39 45 13 13
(5,7) 1 8 26 34 35 43 9 9
(5,8) 1 14 26 40 33 47 7 7
(6,8) 2 2 45 47 45 47
(7,8) 1 4 34 38 43 47 9 9
(8,9) 3 3 47 50 47 50

а) графы 1 и 3 заполняются на основе исходных данных.
б) в графе 2 записывается количество предшествующих работ по сетевому графику или определяется из графы 1 по числу работ, имеющих второй цифрой в коде ту, с которой начинается данная работа.
г) в графе 4 раннее начало работ, выходящих из исходного события, а раннее окончание этих работ равно их продолжительности (гр. 5). Раннее начало последующих работ определяется путем выбора максимального из сроков раннего окончания предшествующих работ. Количество сравниваемых сроков равно количеству предшествующих работ графы 2. Раннее начало последующих работ можно определить после того, как найдено раннее окончание предшествующих. В свою очередь раннее окончание каждой работы находится как сумма величин раннего начала и продолжительности данной работы;
г) продолжительность критического пути определяется после заполнения граф 4 и 5 как максимальная величина из сроков раннего окончания работ, которые ведут к завершающему событию 9;
д) найденная величина критического пути ТKP дням заносится в графу 7 для всех работ, ведущих к завершающему событию. Затем заполнение ведется снизу вверх. Находятся все работы, следующие за рассматриваемой, и определяются разности между поздним окончанием этих работ и их продолжительностями. Минимальная из величин заносится в графу 7;
е) в графе 6 позднее начало работы определяется как разность позднего окончания этих работ и их продолжительности (из значений графы 7 вычитаются данные графы 3);
ж) в графе 8 полный резерв времени работы определяется разностью между значениями граф 7 и 5. Если он равен нулю, то работа является критической;
з) в графе 10 резерв времени событий j определяется как разность позднего окончания работы, заканчивающегося событием j графы 7, и ранним началом работы, начинающимся событием j;
и) значение свободного резерва времени работы определяется как разность значений графы 10 и данных графы 8 и указывает на расположение резервов, необходимых для оптимизации.

Источник

Построение сетевых моделей

ПОСТРОЕНИЕ СЕТЕВЫХ МОДЕЛЕЙ

1 Теоретическое введение

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

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

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

Фиктивная работа может реально существовать, например, «передача документов от одного отдела к другому». Если продолжительность такой работы несоизмеримо мала по сравнению с продолжительностью других работ проекта, то формально ее принимают равной 0. Существуют фиктивные работы, которым в реальности не соответствуют никакие действия. Такие фиктивные работы только представляют связь между другими работами сетевой модели.

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

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

Рис.1. Кодирование работы

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

2 Методические рекомендации по построению сетевых моделей

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

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

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

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

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

· между одними и теми же событиями не должно быть параллельных работ, т. е. работ с одинаковыми кодами;

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

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

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

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

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

· не должно быть циклов (рис.2).

Рис.2. Недопустимость циклов

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

· описанием предполагаемого проекта. В этом случае необходимо самостоятельно разбить его на отдельные работы и установить их взаимные связи;

· списком работ проекта. В этом случае необходимо проанализировать содержание работ и установить существующие между ними связи;

· списком работ проекта с указанием их упорядочения. В этом случае необходимо только отобразить работы на сетевом графике.

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

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

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

Рис.3. Устранение параллельности двух работ

Задача №1

Постройте сетевую модель программы опроса общественного мнения, которая включает разработку (A; 1 день) и распечатку анкет (B; 0,5 дня), прием на работу (C; 2 дня) и обучение (D; 2 дня) персонала, выбор опрашиваемых лиц (E; 2 дня), рассылку им анкет (F; 1 день) и анализ полученных данных (G; 5 дней).

Решение

Из условия задачи нам известно содержание работ, но явно не указаны взаимосвязи между работами. Поэтому для их установления необходимо проанализировать смысл каждой конкретной работы и выяснить, какие из остальных работ должны ей непосредственно предшествовать. Исходной работой, начинающей сетевой график, в данном случае является «прием на работу» (С), поскольку все остальные работы должны выполняться уже принятыми на работу сотрудниками (рис.7.4). Перед выполнением всех работ по опросу общественного мнения сотрудников необходимо обучить персонал (D). Перед тем как разослать анкеты (F), их надо разработать (A), распечатать (B) и выбрать опрашиваемых лиц (E), причем работу с анкетами и выбор лиц можно выполнять одновременно. Завершающей работой проекта является анализ полученных данных (G), который нельзя выполнить без предварительной рассылки анкет (F). В результате этих рассуждений построим сетевую модель и пронумеруем события модели (см. рис. 4).

Рис.4. Сетевая модель программы опроса общественного мнения

Задача №2

Постройте сетевую модель, включающую работы A, B, C, . L, которая отображает следующее упорядочение работ:

1) A, B и C – исходные операции проекта;

2) A и B предшествуют D;

3) B предшествует E, F и H;

4) F и C предшествует G;

5) E и H предшествуют I и J;

6) C, D, F и J предшествуют K;

7) K предшествует L.

Решение

В пункте 1) условия явно указано, что A, B и C являются исходными работами, поэтому изобразим их тремя стрелками, выходящими из исходного события 1. Пункт 2) условия означает, что стрелки работ A и B должны окончиться в одном событии, из которого выйдет стрелка работы D. Но поскольку стрелки работ A и B также и начинаются в одном событии, то имеет место параллельность работ, которая недопустима правилами построения сетевых моделей (см. рис. 5).

Рис. 5. Устранение параллельности работ A и B

Для ее устранения введем дополнительное событие 2, в которое войдет работа B, после чего соединим события 2 и 3, в которые входят работы A и B пунктирной стрелкой фиктивной работы. В данном случае фиктивная работа (2,3) не соответствует никакой реальной работе, а лишь отображает логическую связь между работами B и D. Дальнейшее построение рассмотрим с помощью рис. 6

Рис. 6. Сетевая модель задачи №2

Согласно пункту 3) условия задачи из события 2, выходят три стрелки работ E, F и H. Согласно пункту 4) условия задачи стрелки работ C и F должны войти в общее событие, из которого выйдет стрелка работы G. Проблема с параллельностью работ E и H [пункт 5) условия задачи] решается путем введения дополнительного события 5 и фиктивной работы (5,6). Для отображения в сетевой модели пункта 6) условия задачи введем стрелки работ D и J в событие 7, а связь работ F и C с работой K отобразим с помощью фиктивной работы (4,7). Стрелки работ F и C нельзя было напрямую вводить в событие 7, потому что после них должна следовать работа G, которая с работами D и J никак не связана. Стрелка работы L выходит из события 8, т. е. после окончания работы K в соответствии с пунктом 7) условия задачи.

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

3 Варианты задач для самостоятельного решения

Задача №1

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

Источник

Решение задач сетевого планирования

Решение задач сетевого планирования

Срок выполнения от 1 дня
Цена от 100 руб./задача
Предоплата 50 %
Кто будет выполнять? преподаватель или аспирант

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

Суть задачи

Задачи сетевого планирования сводятся к двум целям:

  1. Найти оптимальный маршрут;
  2. Определить, как максимально быстро выполнить проект.

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

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

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

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

Первый случай

первого типа граф

Выше вы видите граф. Цифры в кружках – это дома, к которым телевизионная компания планирует подвести кабеля. Как мы видим, к одному кружку могут вести два или три пути. Пути называются рёбрами графа. У каждого пути есть свой вес. Это наше расстояние. Нам нужно выбрать из всего этого обилия путей самый короткий, который объединит каждый кружок – вершину графа.

Для этой цели существует специальный алгоритм «Прима». Его суть заключается в следующем:

Мы начинаем идти из первой вершины и присоединяем к ней ребро, имеющее самый маленький вес. В нашем случае – это ребро 1;2. Его вес равен 1.

Теперь мы присоединяем самое короткое ребро, из всех выходящих из вершин 1 и 2. Это ребро 2;5. Его вес – 3.

У нас уже три вершины – 1,2,5. Присоединяем самое короткое ребро, выходящее из них. И это – 2;4. Его вес – 4.

Самое короткое ребро, выходящее из вершин 1,2,4,5 – 4;6. Оно равно 3.

Последнее ребро – 4;3. Мы объединили все вершины. Наш путь в сумме составляет: 1 + 3 + 4 + 3 + 5 = 16.

объединили все вершины

Второй случай

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

таблица

На основании данной таблицы мы рисуем следующий граф.

граф

Правила при составлении графа простые:

Каждая следующая работа всегда находится правее предшествующей.

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

Тупиков быть не должно. Из каждой вершины выходит как минимум, одно ребро.

Далее мы находим так называемый «критический путь». Это самое длинное расстояние от 0 до 6. Мы начинаем двигаться из нуля и присоединяем каждую вершину самым длинным путём. Например, 3 мы можем присоединить, пройдя ребро 0;3, вес которого – 8 или два ребра – 0;1 и 1;3, а так же 0;2 и 2;3. Из этого мы выбираем второй вариант, потому что так мы пройдём самое большое расстояние.

Подпишем расстояния, до каждой вершины сверху.

Подпишем расстояния графа

Теперь нам нужно пройти этот же граф, но уже в обратную сторону, от вершины 6. Только обратно мы следуем, присоединяя каждую вершину самым КОРОТКИМ путём. Обратите внимание, что ребро 3;5 имеет нулевой вес, поэтому и кратчайший путь к вершине 3 будет равен 12. Подпишем самые короткие пути снизу вершин.

обратная сторона вершины

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

кратчайшее расстояние граф

Это крайний срок выполнения проекта. Он равен 3 + 9 + 7 = 19. Раньше этого успеть нельзя. По остальным работам есть резерв времени. Чтобы его посчитать, отнимите верхнее число от нижнего над каждой вершиной.

Источник

Анализ сетевого графика

Размеры графического полотна

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

Инструкция к сервису

Основные определения

На сетевой модели событиям соответствуют вершины графа.

Правила построения сетевой модели

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

Правило 3 . При включении каждой операции в сетевую модель для обеспечения правильного упорядочения необходимо дать ответы на следующие вопросы:
а) Какие операции необходимо завершить непосредственно перед началом рассматриваемой операции?
б) Какие операции должны непосредственно следовать после завершения данной операции?
в) Какие операции могут выполняться одновременно с рассматриваемой?

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

  • в сети не должно быть «тупиков», т.е., событий, от которых не начинается ни одна работа, исключая завершающее событие графика;
  • В сетевом графике не должно быть «хвостовых» событий, то есть событий, которым не предшествует хотя бы одна работа, за исключением исходного.
  • в сети не должно быть замкнутых контуров (рис.1);
  • Любые два события должны быть непосредственно связаны не более чем одной работой.
  • В сети рекомендуется иметь одно исходное и одно завершающее событие.
  • Сетевой график должен быть упорядочен. То есть события и работы должны располагаться так, чтобы для любой работы предшествующее ей событие было расположено левее и имело меньший номер по сравнению с завершающим эту работу событием.

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

Источник

Читайте также:  Оформление таблицы терминов и определений