Методы построения и расчета сетевых моделей типа «вершины-события»
Последовательность выполнения задач и логические связи между ними служат основой для разработки расписания проекта. Разработка расписания проекта означает определение дат начала и завершения всех работ проекта
Утвержденное расписание служит базовым планом по расписанию Разработка расписания — существенно итеративный процесс и производится на протяжении всего жизненного цикла проекта.
Основные методы, используемые для разработки расписания: метод критического пути (CRM) и графический метод (график Гантта). Метод критического пути реализуется, как правило, с помощью построения и расчета сетевых моделей.
Важной предпосылкой применения метода CPM является предположение о том, что время выполнения каждой роботы точно известно. В результате использования метода CPM удается получить ответы на следующие вопросы.
1. За какое минимальное время можно выполнить проект?
2. В какое время должны начаться и закончиться отдельные работы?
3. Какие работы являются «критическими» и должны быть выполнены точно в установленное время, чтобы не сорвать срок выполнения проекта?
4. На какое время можно отложить срок выполнения «некритической» работы, чтобы она не повлияла на срок выполнения проекта?
Рассмотрим порядок расчета сетевой модели типа «Вершины-события» и построение сетевого графика
Изображение сетей. В сетях типа «вершины-события» работа представляется стрелкой, а событие — кругом, поделенным на 4 части (рисунок 4.1).
Рисунок 3.6 — Изображение события в сетевой модели
— ранний срок наступления события i. Это время, которое необходимо для выполнения всех работ, предшествующих данному событию i. Оно равно наибольшей из продолжительности путей, предшествующих данному событию.
— поздний срок наступления события i. Это такое время наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети. Поздний срок наступления любого события i равен разности между продолжительностью критического пути и наибольшей из продолжительностей путей, следующих за событием i.
— резерв времени наступления события i. Это такой промежуток времени, на который может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом. Начальные и конечные события критических работ имеют нулевые резервы событий.
Расчет ранних сроков свершения событий ведется от исходного (И) к завершающему (З) событию.
Текущую длительность работы буквой с соответствующим кодом работы, например, , и т.д.
Для всех остальных событий i , где максимум берется по всем работам , входящим в событие i.
Поздние сроки свершения событий рассчитываются от завершающего к исходному событию.
Для завершающего события З .
Для всех остальных событий , где минимум берется по всем работам , выходящим из события i.
Даты раннего наступления события определяются при прямом проходе — от начального к конечному событию. Даты позднего наступления события — при обратном проходе от конечного к начальному событию.
Рассчитаем сетевую модель для таблицы 3.1
Таблица 3.3 — Исходные данные для расчета сетевой модели
Глава 6. Основы сетевого планирования и управления
Одним из важнейших приложений теории графов является сетевое планирование и управление (СПУ) сложными комплексами взаимосвязанных работ. Графической моделью комплекса работ или производственного процесса является сетевой график (сетевая модель, сеть). С математической точки зрения сетевой график – это связанный орграф без петель и контуров.
Сетевые модели состоят из следующих элементов: работа (или задача); событие.
Работа – это процесс, который необходимо выполнить для получения, определенного (заданного) результата, как правило, позволяющего приступить к последующим действиям. Различают три вида работ.
| Вид работы (обозначение) | Определение | Пример |
| действительная (сплошная стрелка) | процесс, требующий затрат времени и ресурсов | разработка проекта, подвоз материалов, выполнение монтажных работ |
| ожидание (штрихпунктирная стрелка) | процесс, требующий времени, но не потребляющий ресурсы | процессы затвердения бетона, сушки пиломатериалов |
| фиктивная работа (пунктирная стрелка) | работа, не требующая времени и ресурсов, но указывающая, что возможность начала одной работы непосредственно зависит от результатов другой (продолжительность равна нулю) |
Событие – момент изменения состояния системы, в частности, момент начала или окончания любой работы по своей сути является событием. Предполагается, что события не имеют продолжительности и наступают мгновенно. В сетевом графике различают три вида событий.
| Вид события | Определение |
| исходное | это такое событие, с которого начинается выполнение комплекса операций |
| завершающее | соответствует достижению конечной цели, то есть завершению комплекса работ |
| промежуточные | все прочие события |
Виды сетевых моделей
По способу представления информации существуют два принципиально различных вида сетевых моделей (графиков).
1. Сеть вида «вершина – событие, дуги — работы»: вершины соответствуют событиям, а соединяющие их дуги – работам. При графическом представлении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i, j), где i — номер события, из которого работа выходит, а j — номер события, в которое она входит. События изображаются кружками. Этот вид сетевой модели представлен на рис. 6.1.
Каждая работа имеет определенную продолжительность t (i, j). Например, запись t (2,5) = 4 на рис. 6.1. означает, что работа (2,5) имеет продолжительность 4 единицы.
Рис. 6.1. Сетевая модель «вершина – событие»
2. Сеть вида «вершина – работа»: вершины соответствуют работам, а дуги – связям. События при необходимости отображаются какими-либо фигурами, например – треугольниками.
Замечание. Мы будем использовать сетевые графики в терминах «вершина – событие, дуги – работы».
Требования, предъявляемые к сетевым моделям
1. События правильно пронумерованы, т. е. для каждой работы (i, j) выполняется условие i
2. Отсутствуют тупиковые события (кроме завершающего), т.е. такие, за которыми не следует хотя бы одна работа.
3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа.
4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим.
Однако иногда в исходном сетевом графике события имеют неупорядоченную нумерацию. Поэтому после построения графика в случае необходимости рекомендуется перенумеровать его события (номер начального события любой работы должен быть меньше номера её конечного события).
Алгоритм нахождения
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Расчёт сетевого графика «вершины-события»
Для расчёта такого графика имеется несколько алгоритмов Наиболее распространенные из них это алгоритм расчёта сетевого графика в табличной форме и непосредственно на графике.
Алгоритм расчёта сетевого графика в табличной форме
Для расчёта сетевого графика в таблице необходимо, чтобы события были пронумерованы следующим образом: номер начального события каждой работы должен быть меньше номера её конечного события. Исходному событию присваивается первый номер, а все последующие события получают номера в порядке возрастания от исходного до завершающего. После нумерации каждая работа получает свой код, соответствующий номерам её начального и конечного событий.
Исходные данные из графика для расчёта заносятся в графы 1, 2 и 3 таблицы (см. табл. 6.2). Все эти три графы заполняются одновременно.
В графу 1 заносятся номера начальных событий предшествующих работ. Например, для работы (7,9) (рис. 6.8> предшествующими являются работа (3,7) и зависимость (6,7), следовательно, в гр. 1 заносятся номера начальных событий этих работ 3 и 6.
В гр. 2 заносятся коды работ и зависимостей в порядке возрастания начальных номеров событий, т.е. сначала работы, выходящие из события 1, затем из события 2 и т.д.
В гр. 3 проставляются продолжительности работ.
Расчёт сетевого графика в таблице
Номера начальных событий предшествующих работ