Линейный график и способы его построения
Сетевой график дает общее представление о структуре комплекса работ и технологической последовательности их выполнения.
Недостатком сетевого графика является то, что он не дает четкого преставления о взаимном расположении работ во времени, что затрудняет нахождение критического пути и оптимизации сетевого графика.
Это недостаток отсутствует у линейного графика, или диаграммы Ганта. Элементами линейного графика являются работы, которые изображаются в системе координат (номер работы – время выполнения).
Линейный график строится по следующему правилу:
· работы изображаются на графике линиями (прямоугольниками), длина которых пропорциональна их длительности;
· работы изображаются на графике, если построены все работы, непосредственно ей предшествующие;
· момент начала выполнения данной работы определяется моментом окончания выполнения всех непосредственно предшествующих ей работ.
Пример 7.4.Построить линейный график по данным табл. 7.1
Решение. По изложенным выше правилам построим линейный график.
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 29
| 1.1 |
| 2.1 |
| 2.2 |
| 2.3 |
| 1.2 |
Номер работы
После построения линейного графика технического обслуживания автомобиля перенумеруем работы. Теперь в отличие от нумерации работ в табл. 7.1., например, работа 5 имеет код 1.2.
Для всех работ (i, j) на основе ранних и поздних сроков свершения событий можно определить показатели, которые являются также основными параметрами линейного технологического графика:
· ранний срок начала события
(7.4)
· ранний срок окончания события показывает, через какое время после начала выполнения комплекса работ будет завершена рассматриваемая j-я работа, если все работы будут выполняться в соответствии с графиком,
(7.5)
При описанном выше порядке построения линейного графика ранние сроки завершения работ легко определяются из графика: они соответствуют моментам времени окончания работ (определяются путем проектирования работ на временную ось);
· поздний срок начала события
(7.6)
· поздний срок окончания события
(7.7)
− максимально (предельно допустимый) срок завершения рассматриваемой работы, не приводящий к увеличению критического пути.
Он показывает, через какое время после начала выполнения комплекса работ должна быть завершена данная работа, чтобы общая продолжительность работ не увеличилась.
Заметим, что значения 
и 
завершающего события равны и соответствуют величине критического пути 
;
· длина критического пути – продолжительность выполнения всего комплекса работ – соответствует наибольшему значению из всех 
где N – общее число работ в комплексе;
· полный резерв времени выполнения работы 
показывает, насколько может быть сдвинут срок завершения рассматриваемой работы в сторону его увеличения (увеличена ее продолжительность), не вызывая увеличения критического пути,
. (7.8)
Пример 7.5.Рассчитать параметры линейного графика, представленного в примере 7.4.
Решение. В соответствии с рисунком определим ранний и поздний сроки окончания работы. Ранний срок окончания работы характеризует правый срез прямоугольника (работы).
Если работа выполняется не параллельно с другими работами, то поздний срок окончания работы равен раннему сроку.
Поздний срок окончания работы, не равный раннему сроку, можно указать только для тех работ, которые на линейном графике выполняются параллельно, например работы 2 и 3.
В этом случае без ущерба для величины критического пути можно увеличить продолжительность работы 2. То есть поздний срок окончания работы 2 соответствует времени 15 y.e.
Резерв времени легко определяется как разность последнего и раннего сроков окончания работы.
Результаты расчета сведем в таблицу 7.3.
Таблица 7.3.
| Номер работы | Код работы | Продолжительность работы t(i), y.e. | Ранний срок окончания работы  , y.e.
| Поздний срок окончания работы  ,y.e.
| Резерв времени  , y.e.
|
| 1.1 | |||||
| 2.1 | |||||
| 2.2 | |||||
| 2.3 | max{21,16} =21 | ||||
| 1.2 |
Как очевидно из таблицы, длина критического пути равна раннему сроку выполнения работы 1.2 и составляет 
y.e.; при этом работа 2.1 имеет резерв в 5 y.e. времени.
После определения параметров линейного графика строится критический путь. Признаком принадлежности i-й работы критическому пути является равенство 
. Непрерывность критического пути свидетельствует о правильности его построения.
Таким образом, более наглядное представление работ во времени делает процесс оптимизации линейного графика более легким по сравнению с сетевым графиком.
В рассматриваемом примере критический путь проходит через работы 1.1, 2.2, 2.3, 1.2.
Так как работа 2.1 имеет резерв 5 y.e. времени, то можно попытаться привлечь на это время освободившегося специалиста для выполнения работы 2.2, что, скорее всего, сократит время ее выполнения. В этом случае можно ожидать сокращения критического времени выполнения работ при декларировании и выпуске товаров.
Пример 7.6.Необходимо осуществить таможенный контроль представленных деклараций и принять решение о выпуске товаров.
Перечень событий, а также данные о продолжительности работ (в мин.) приведены в таблицах 7.4 и 7.5.
Таблица 7.4.
| Шифр события | Описание события | Предшествующие события |
| Начало (прием и регистрация ДТ) | ||
| Документальный контроль, представленный декларантом документов и сведений | ||
| Проверка зарегистрированной ДТ на риски | ||
| Представление отметок о результатах документального контроля в ДТ и других документах | 2,3 | |
| Применение мер по минимизации рисков | 2,3 | |
| Заполнение отчета о результатах применения мер по минимизации рисков | ||
| Проверка соблюдения условий выпуска | 4,6 | |
| Конец (выпуск товаров) |
Таблица 7.5.
| Номер работы | Продолжительность работы, мин. |
| 1,2 | |
| 1,3 | |
| 2,4 | |
| 2,5 | |
| 3,4 | |
| 3,5 | |
| 4,7 | |
| 5,6 | |
| 6,7 | |
| 7,8 |
Определить основные параметры сетевого графика.
Решение. По данным таблиц составим сетевой график.
Рис. 7.6
Для сетевого графика полными путями будут:
путь 1 → 2 → 4 → 7 → 8 продолжительностью 10 + 30 + 0 + 20 = 60 мин;
путь 1 → 2 → 5 → 6 → 7 → 8 продолжительностью 10 + 0 + 40 + 0 + 20 = 70 мин;
путь 1 → 3 → 4 → 7 → 8 продолжительностью 20 + 0 + 0 + 20 = 40 мин;
путь 1 → 3 → 5 → 6 → 7 → 8 продолжительностью 20 + 20 + 40 + 0 + 20 = 100 мин.
Последний путь имеет наибольшую продолжительность и является критическим. Продолжительность критического пути составляет 100 мин. Быстрее работу выполнить нельзя, так как для достижения завершающего события критический путь надо пройти обязательно.
Расчет параметров сетевого графика:
При определении ранних сроков свершения событий 
двигаемся по сетевому графику слева направо и используем формулу (7.1).
Для начального события j = 1, очевидно, 
.
Для j = 2: 
мин, так как для события 2 существует только один предшествующий путь 1 → 2.
Для j = 3: 
мин, так как для события 3 существует один предшествующий путь 1 → 3.
Для j = 4: 
, так как для события 4 существует два предшествующих пути 1 → 2 → 4 и 1 → 3 → 4 и два предшествующих события: 2 и 3.
Аналогично определяем ранние сроки для остальных событий сети:
;
;
;
Длина критического пути равна раннему сроку свершения завершающего события 8
Найденные параметры сведем в таблицу 7.6.
Таблица 7.6.
| Номер работы | Сроки свершения события, мин. | Резерв времени
 ,мин.
| |
ранний  , мин
| поздний  , мин.
| ||
В этой таблице при определении поздних сроков свершения событий 
двигаемся по дугам в обратном направлении, т.е. справа налево и используя формулу (7.2).
Для i = 8 (завершающего события) поздний срок свершения события должен равняться его раннему сроку (иначе изменится длина критического пути):
Для i = 7: 
, так как для события 7 существует только один последующий путь 7 → 8.
Для i = 6: 
, так как для события 6 существует только один последующий путь 6 → 7 → 8.
Для i = 5: 
, так как для события 5 существует только один последующий путь 5 → 6 → 7 → 8.
Для i = 4: 
, так как для события 4 существует только один последующий путь 4 → 7 → 8.
Для i = 3: 
, так как для события 3 существуют два последующих пути: 3 → 4 → 7 → 8 и 3 → 5 → 6 → 7 → 8.
Для i = 2: 
, так как для события 2 существуют два последующих пути: 2 → 4 → 7 → 8 и 2 → 5 → 6 → 7 → 8.
Для i = 1: 
.
По формуле (7.3) определяем резервы времени i-го события:
и т.д.
Резерв времени события 2 составляет 
. Это означает, что время свершения события 2 может быть задержано на 30 мин. без увеличения общего срока выполнения работы.
Анализируя последнюю таблицу, видим, что не имеют резервов времени события 1, 3, 5, 6, 7, 8. Эти события и образуют критический путь.
Расчет параметров линейного технологического графика:
Вычисление временных параметров работы (i, j) покажем на примере работы (2,4).
Ранний срок начала работы вычисляется по формуле (7.4): 
.
Ранний срок окончания работы вычисляется по формуле (7.5): 
.
Поздний срок начала работы вычисляется по формуле (7.6): 
.
Поздний срок окончания работы: 
.
Таким образом, работа 2,4 должна начаться в интервале (10, 50) и окончиться в интервале (40, 80) от начала выполнения работы.
Полный резерв времени работы (2, 4) вычисляется по формуле (7.8): 
, т.е. срок выполнения данной работы можно увеличить на 40 мин., при этом срок выполнения комплекса работ не изменится.
Результаты вычислений сведем в таблицу.
Таблица 7.7.
| Работа (i, j) | Продолжительность работы (i, j), мин. | Сроки начала и окончания работы, мин. | Полный резерв времени  мин.
| |||
| 
|
| 
| |||
| (1, 2) | ||||||
| (1, 3) | ||||||
| (2, 4) | ||||||
| (2, 5) | ||||||
| (3, 4) | ||||||
| (3, 5) | ||||||
| (4, 7) | ||||||
| (5, 6) | ||||||
| (6, 7) | ||||||
| (7, 8) |
Покажем на примере работы (2, 4), что полный резерв времени работы равен резерву времени максимального из путей, проходящих через эту работу.
Этим резервом можно располагать при выполнении данной работы, если ее начальное событие свершится в самый ранний срок, и можно допустить свершение ее конечного события в самый поздний срок.
Важным свойством полного резерва времени работы является то, что он принадлежит не только этой работе, но и всем полным путям, проходящим через нее.
Через работу (2, 4) проходит 1 полный путь: 1 → 2 → 4 → 7 → 8 продолжительностью t = 60 мин. Его резерв 
.
Как видим, полный резерв времени работы (2, 4) равен резерву времени максимального (и единственного) полного пути, проходящего через эту работу.
Если увеличить продолжительность работы (2, 4) на 40 мин., то полностью будет исчерпан резерв времени этого пути, т.е. этот путь станет также критическим.
Контрольные вопросы и задания
1. Дайте определение и приведите пример графа.
2. Какой граф называется орграфом, неориентированным графом?
3. Каковы способы задания графов?
4. Что называют маршрутом в графе?
5. Что называют цепью графа?
6. Какой граф называется эйлеровым?
7. Какой цикл называется гамильтоновым?
8. Каково назначение системы сетевого планирования и управления?
9. Что называется событием, работой, путем и как они обозначаются на схеме.
10. Назовите основные правила построения сетевых графиков.
11. Перечислите основные параметры сетевого графика.
12. Назовите критерии оптимальности сетевого графика.
13. Укажите способы построения линейного графика.
14. Перечислите основные параметры линейного графика.