1 Постановка задачи

2 Теоретические основы сетевого планирования

3 Обоснование рациональных методик поиска особых путей сетевых график

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

4 Автоматизация анализа оптимальности сетевых графиков на ЭВМ

4.1 Представление сетевого графика в машинной форме

Любая ЭВМ нуждается в преобразовании различных абстрактных понятий, ясных для человека, в удобную для неё форму. Сетевой график, как графическое изображение упорядоченных кружков и стрелок само по себе для ЭВМ нечего не значить. Для того, чтобы ЭВМ могла понимать структуру сетевого графика и, главное, обрабатывать её, необходимо представить эту структуру в эквивалентной машинной форме.

Наиболее удобный способ представления структуры сетевого графика в ма­шинной форме, основан на понятии матрицы смежностей . Пример данной матрицы для структуры сетевого графика на рисунке 2.1 представлен на рисунке 4.1 .

Матрица смежностей квадратная и имеет размерность , где – число событий сетевого графика. Номера строк матрицы задаются номерами событий , из которых работы сетевого графика исходят, номера столбцов матрицы зада­ются номерами событий , в которые работы сетевого графика входят. На пере­сечении строки и столбца , в матрице смежностей, может быть только одно из двух значений: 0 или 1. Если , то это означает, что на сетевом гра­фике существует работа, исходящая из события с номером и входящая в со­бытие с номером . Если , то такой работы на сетевом графике нет.

Матрица смежностей будет верно отражать структуру сетевого графика, если сетевой график построен по всем, узаконенным стандартом правилам. Здесь, наиболее важны следующие:

−

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

− Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события, разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. 4.2 ). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответст­вии с первым правилом.

Верно построенная матрица смежностей обладает радом полезных свойств:

−

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

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

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

Любопытно заметить, что если последнее из перечисленных свойств не вы­полняется, то в сетевом графике есть петли, то есть, работы, концы которых явля­ются началами других работ, предшествующих первым по времени, при условии, что все события занумерованы, верно. Из этого следует возможность легкой авто­матизации на ЭВМ процесса проверки правильности построения сетевого гра­фика. Данный процесс проверки, алгоритмически, представляется в виде блок-схемы 4.1 .

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

Блок-схема 4.1 – Алгоритм тестирования матрицы смежностей

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

Анализ оптимальности сетевого графика возможно провести, только после расчёта всех, присущих ему параметров. Исходными данными для расчёта явля­ются длительности всех, входящих в сетевой график работ. Результатами расчёта являются значения, описанных в раз­деле 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 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт ранних сроков свершения событий в порядке: 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 – Алгоритм расчёта резервов времени сетевого графика

4.3 Автоматизация процесса поиска особых путей сетевого графика

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

Из раздела 3 ясно, что для поиска, и критического пути и наикратчайшего, возможно использовать одну и туже методику. Данная методика заключается в по­следовательном выборе, от 0-го события до завершающего, тех работ, которые имеют нулевые полные резервы времени. В случае, если параметры сетевого гра­фика рассчитывались для положительных длительностей, входящих в него работ, то указанная методика даёт критический путь сетевого графика. Если же пара­метры рассчитывались при отрицательных длительностях работ, то методика даст наикратчайший путь сетевого графика.

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

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

Блок-схема 4.6 – Алгоритм поиска особого пути сетевого графика

Заключение

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

Кроме того, в курсовом проекте были рассмотрены вопросы автоматизации на ЭВМ рациональных методик поиска особых путей сетевого графика. В резуль­тате – разработаны блок схемы алгоритмов расчёта параметров сетевых графиков и поиска их особых путей, которые предполагается использовать при создании конкретной программы анализа оптимальности сетевых графиков на любом из из­вестных языках программирования.

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

Список использованных источников

Технико-экономическое обоснование дипломных проектов проектов: Учеб. Пособие для втузов / Л. А. Астреина, В. В. Балдесов, В. К. Беклешов и др.; Под ред. В. К. Беклешова. – М.: Высш. Шк., 1991. – 176 c.: ил.