Автоматизация расчёта параметров сетевого графика

Анализ оптимальности сетевого графика возможно провести, только после расчёта всех, присущих ему параметров. Исходными данными для расчёта явля­ются длительности всех, входящих в сетевой график работ. Результатами расчёта являются значения, описанных в раз­деле 2, параметров. И первое и второе, можно объединить в одной таблице исход­ных данных и результатов 4.1.

Данная таблица – есть двумерная матрица с пронумерованными строками и столбцами. Номера строк изменяются от 0 до  (см. таб. 4.1), где  – число ра­бот в сетевом графике, которое можно найти, подсчитав все единицы в матрице смежностей. Номера столбцов изменяются от 0 до 13, где каждый номер соответ­ствует своему параметру сетевого графика. Нумерация строк и столбцов необхо­дима для представления таблицы исходных данных и результатов в машинной форме.

 Столбцы под номерами 0,1 и 2 определяют часть таблицы 4.1, отведённую под хранение исходных данных, к которым относятся коды работ и длительности работ. Как видно, коды работ задаются ячейками двух столбцов под номерами 0 и 1. Здесь индекс  (столбец 0) определяет номер события, из которого работа исхо­дит, а индекс  (столбец 1) определяет номер события, в которое она входит. Найти все возможные коды работ сетевого графика легко по матрице смежностей , если, просматривая её строки, номера которых соответствуют индексу , выбирать в качестве индекса  номера тех столбцов, для которых будут отыски­ваться единицы.

Алгоритм заполнения таблицы 4.1 исходными данными представлен в виде блок-схемы 4.2, где ячейки самой таблицы обозначены символом . Для дан­ного обозначения:  – номер строки таблицы исходных данных и результатов,  – номер столбца той же таблицы. Алгоритм предполагает, что таблица исходных данных и результатов  уже зарезервирована и имеет размерность ,  – число работ в сетевом графике.

 

    Блок-схема 4.2 – Алгоритм заполнения исходными данными таблицы исходных данных и результатов

      После заполнения таблицы 4.1 исходными данными для расчёта, идёт сле­дующая стадия, – непосредственно, сам расчёт параметров сетевого графика. Данная стадия выполняется в три этапа. На первом этапе осуществляется расчёт сетевого графика в порядке – от начального события до завершающего, и опреде­ляются ранние сроки свершения событий, ранние начала и окончания работ. На втором этапе осуществляется расчёт сетевого графика в обратном порядке – от за­вершающего события до начального, и определяются поздние сроки свершения событий, поздние начала и окончания работ. На третьем этапе осуществляется расчёт резервов времени событий и работ, в произвольном порядке.

Рассмотрим расчёт параметров сетевого графика на первом этапе.

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

Теорема 4.1 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт ранних сроков свершения событий в порядке: 0-е событие, 1-е, 2-е, и так далее, до завершающего события, в тупик зайти не может, при условии, что рассчитывая ранний срок свершения очередного события, сразу же определя­ются ранние окончания всех, исходящих из него работ.

Докажем эту теорему методом математической индукции.

Зададимся нулевым сроком свершения 0-го события, и рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 1-е событие. В него могут входить только работы, исходящие из событий с меньшими номерами – в данном случае только из 0-го события, при этом ранние окончания этих работ уже известны. Тогда можно рассчитать ранний срок свершения 1-го события. Рассчи­тав ранний срок свершения 1-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 2-е событие. В него могут вхо­дить работы, только из 0-го и 1-го события, и ранние окончания которых уже из­вестны. Тогда можем рассчитать ранний срок свершения 2-го события. Рассчитав ранний срок свершения 2-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 3-е событие. В него могут входить работы, только из 0-го, 1-го и 2-го события, и ранние окончания которых уже из­вестны. Тогда можем рассчитать ранний срок свершения 3-го события….

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

Из данной теоремы, непосредственно, вырисовывается алгоритм расчёта па­раметров сетевого графика на первом этапе. Данный алгоритм представлен в виде блок-схемы 4.3, и основан на том, что после выполнения алгоритма 4.2, в таблице исходных данных и результатов   уже находятся коды работ сетевого графика и их длительности.

Блок-схема 4.3 – Алгоритм расчета ранних сроков свершения событий сетевого графика

     Рассмотрим расчёт параметров сетевого графика на втором этапе.

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

Теорема 4.2 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт поздних сроков свершения событий в порядке: последнее со­бытие, предпоследние событие, предшествующее предпоследнему событию, и так далее, до начального (0-го) события, в тупик зайти не может, при условии, что рас­считывая поздний срок свершения очередного события, сразу же определяются поздние начала всех, входящих в него работ.

Докажем эту теорему методом математической индукции.

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

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

Из данной теоремы, непосредственно, следует алгоритм расчёта параметров сетевого графика на втором этапе. Данный алгоритм представлен в виде блок-схемы 4.4, и основан на том, что после выполнения алгоритма 4.3, в таблице ис­ходных данных и результатов   уже рассчитаны все ранние сроки свершения событий.

 

Блок-схема 4.4 – Алгоритм расчёта поздних сроков свершения событий сетевого графика

     Рассмотрим расчёт параметров сетевого графика на третьем этапе.

Если, сначала выполнить алгоритм расчёта ранних сроков свершения собы­тий 4.3, а затем алгоритм расчёта поздних сроков свершения 4.4, то в таблице ис­ходных данных и результатов останутся не заполненными только три последних столбца, с номерами: 11, 12 и 13. Данные столбцы, как видно из таблицы 4.1, отве­дены под расчёт резервов времени сетевого графика. Расчёт резервов времени се­тевого графика можно осуществить в любом порядке строк таблицы исходных данных и результатов, например, подряд – с 0-й строки по последнюю. Такой по­рядок расчёта представлен ниже, в виде блок-схемы 4.5. Данный алгоритм явля­ется завершающим для процесса расчёта параметров сетевого графика, после вы­полнения которого, все ячейки таблицы исходных данных и результатов 4.1, будут заполнены значениями соответствующих параметров.

Блок-схема 4.5 – Алгоритм расчёта резервов времени сетевого графика