4.7. Какой содержательный смысл свободного резерва времени работ на сетевом графике?

Свободным резервом времени работы называется величина

.

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

4.8. В каких целях в сетевом планировании используют линейные диаграммы?

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

4.9. Как на линейной диаграмме найти основные временные параметры сетевого графика?

Минимальный момент совершения каждого события будет соответствовать самой правой проекции концов работ, вида .

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

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

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

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

4.10. В чем суть задачи оптимального распределения ограниченного ресурса в сетевом планировании?

Пусть для какого-то проекта построен СГ, на дугах-работах которого указаны продолжительности работ . Кроме того, для каждой работы известно число - интенсивность потребления ресурса одного вида, т.е. количество того или иного ресурса, необходимого для выполнения работы в единицу времени. Будем предполагать, что в течение всей работы эта интенсивность постоянна. Для всего проекта известны значения , означающие объем наличных ресурсов в каждый момент времени . В целях упрощения изложения предположим, что постоянная величина, то есть .

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

4.11. Как строится график использования ресурса во времени на основе линейной диаграммы?

Построим ЛД, на отрезках которого будут указаны потребности ресурса для соответствующей работы.

Пользуясь ЛД, можно посчитать, сколько единиц ресурса требуется в каждый момент. Например, при требуется 6+3+5=14 единиц ресурса. Такие данные позволяют построить график использования ресурса в каждый момент времени. Он имеет вид:

Пример алгоритма распределения ограниченного ресурса.

Общий шаг. Строятся (по возможности) ЛД и график использования ограниченного ресурса. Определяются временные параметры СГ (в том числе и полный резерв времени каждой работы).

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

Условие А: работа не допускает перерыва.

Условие В: работа допускает перерыв.

При варианте А начало помеченной работы передвигается до момента и продолжаются после него.

При варианте В участок работы от момента считается самостоятельной работой и именно его передвигаем до момента-начала .

Замечание. Вариант А можно учесть уже при нумерации работ. В первую очередь номера присваиваются тем работам, которые были начаты до момента . Для каждой из таких работ вычисляется разность между ее полным резервом и отрезком этой работы от ее начала до . Такие работы нумеруются в порядке возрастания этих разностей.

При любом из вариантов сдвига получается новая ЛД и общий шаг повторяется.