Глава 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) и не забудь поделиться с друзьями:
Найдите 2 минуты и прочитайте про:
Административные правоотношения — это урегулированные нормами административного права фактические.
Административно-правовые отношения: понятие, особенности, структура и виды Административно-правовые отношения — это регулируемые нормами административного права общественные отношения.
Правила оформления рецептов на спирт этиловый. Нормы отпуска спирта этилового и спиртосодержащих лекарственных препаратов. Учёт в аптеке спирта этилового Строго регламентированные требования предъявляют к оформлению рецептов на этиловый спирт.
МИКРОБИОЛОГИЧЕСКИЕ ЛАБОРАТОРИИ И ИХ ОБОРУДОВАНИЕ Введение Все микробиологические, биохимические и моле-кулярно-биологические исследования микроорганизмов про­.
Понятие «социальная защита населения»: сущность и содержание. Социальная защита населения — это одно из важнейших направлений социальной политики государства.
Расчёт сетевого графика «вершины-события»
Для расчёта такого графика имеется несколько алгоритмов Наиболее распространенные из них это алгоритм расчёта сетевого графика в табличной форме и непосредственно на графике.
Алгоритм расчёта сетевого графика в табличной форме
Для расчёта сетевого графика в таблице необходимо, чтобы события были пронумерованы следующим образом: номер начального события каждой работы должен быть меньше номера её конечного события. Исходному событию присваивается первый номер, а все последующие события получают номера в порядке возрастания от исходного до завершающего. После нумерации каждая работа получает свой код, соответствующий номерам её начального и конечного событий.
Исходные данные из графика для расчёта заносятся в графы 1, 2 и 3 таблицы (см. табл. 6.2). Все эти три графы заполняются одновременно.
В графу 1 заносятся номера начальных событий предшествующих работ. Например, для работы (7,9) (рис. 6.8> предшествующими являются работа (3,7) и зависимость (6,7), следовательно, в гр. 1 заносятся номера начальных событий этих работ 3 и 6.
В гр. 2 заносятся коды работ и зависимостей в порядке возрастания начальных номеров событий, т.е. сначала работы, выходящие из события 1, затем из события 2 и т.д.
В гр. 3 проставляются продолжительности работ.
Расчёт сетевого графика в таблице
Номера начальных событий предшествующих работ
Сравнение сетевых графиков типа «вершины-работы» и «вершины-события»
Сетевые графики типа «вершины-события» имеют более давнюю историю, они появились в 50-х годах. И лишь в конце 60-х годов появились сетевые графики типа «вершины-работы» В настоящее время сетевые графики типа «вершины-работы» приобретают всё более широкое применение по следующим причинам.
1. Отсутствие событий и пунктирных зависимостей позволяет определить взаимосвязи работ до построения сетевого графика по таблице исходных данных. Каждой работе присваивается постоянный номер (код), не зависящий от изменений и дополнений в сетевом графике. Обособленное положение каждой работы позволяет ввести специальные коды для всех исполнителей.
2. Более удобное построение сетевого графика. Все прямоугольники могут быть нарисованы на листе, а затем между ними расставлены организационно-технологические зависимости. Введение новых работ и связей, так же как исключение ранее существующих, производится без изменения топологии сетевого графика. Для сетевых графиков типа «вершины-события» этого сделать нельзя, так как работы находятся между двумя событиями, а это предполагает другую логику.
3. Написание прикладных программ для сетей типа «вершины-работы» является наиболее простым делом, поэтому большинство современных прикладных программ применимо только для таких сетевых графиков
4. Сетевые графики типа «вершины-работы» адаптированы к стандартам управления и используются в специализированных пакетах программ планирования и оперативного управления.
Временные параметры сетевого графика
Каждая работа сетевого графика имеет временную оценку – продолжительность. Продолжительность (t) выполнения работы измеряется в единицах времени: часах, днях, неделях и т.д.
Любая непрерывная последовательность работ в сетевом графике называется путём. Путь от исходной до завершающей работы (события) является полным путём сетевого графика. Если известна продолжительность выполнения каждой работы, то может быть определена продолжительность пути. Продолжительность любого пути равна сумме продолжительностей составляющих его работ. Полный путь, имеющий наибольшую продолжительность, называется критическим.
Продолжительность критического пути (Ткр) определяет общую продолжительность строительства. Следовательно, чтобы сократить продолжительность строительства, необходимо уменьшить продолжительность критических работ, т.е. работ, находящихся на критическом пути. Одной из главных задач руководителей строительства является тщательный контроль за соблюдением установленных продолжительностей выполнения именно этих работ, изыскание путей их сокращения и принятие оперативных мер по предотвращению их срыва
Для определения продолжительности критического пути и сроков выполнения каждой работы определяют следующие временные параметры сетевой модели: раннее начало работы – t p н , раннее окончание работы – t po ; позднее начало работы – t пн , позднее окончание работы – t по ; полный резерв времени – R; свободный резерв времени – r.
Раннее начало работы – самый ранний момент начала работы. Раннее начало исходных работ сетевого графика равно нулю. Раннее начало любой работы равно максимальному раннему окончанию предшествующих работ.
Раннее окончание работы – самый ранний момент окончания данной работы. Он равен сумме раннего начала и продолжительности работы.
Позднее окончание работы – самый поздний момент окончания работы, при котором продолжительность критического пути не изменится. Позднее окончание завершающих работ равно продолжительности критического пути. Позднее окончание любой работы равно минимальному позднему началу последующих работ.
Позднее начало работы – самый поздний момент начала работы, при котором продолжительность критического пути не изменится. Он равен разности между поздним окончанием данной работы и ее продолжительностью.
У работ критического пути ранние и поздние сроки начала и окончания равны между собой, поэтому они не имеют резервов времени. Работы, не лежащие на критическом пути, имеют резервы времени.
Полный резерв времени – максимальное время, на которое можно увеличить продолжительность работы или перенести её начало без увеличения продолжительности критического пути. Он равен разности между поздним и ранним сроком начала или окончания работы.
Свободный резерв времени – время, на которое можно увеличить продолжительность работы или перенести её начало, не изменив при этом раннего начала последующих работ. Он равен разности между ранним началом последующей работы и ранним окончанием данной работы.