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

событие, 1-е, 2-е, и так далее, до завершающего события, в тупик зайти не

может, при условии, что рассчитывая ранний срок свершения очередного

события, сразу же определяются ранние окончания всех, исходящих из него

работ.

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

Зададимся нулевым сроком свершения 0-го события, и рассчитаем ранние

окончания всех, исходящих из него работ. Далее. Рассмотрим 1-е событие. В

него могут входить только работы, исходящие из событий с меньшими номерами

– в данном случае только из 0-го события, при этом ранние окончания этих

работ уже известны. Тогда можно рассчитать ранний срок свершения 1-го

события. Рассчитав ранний срок свершения 1-го события, сразу же рассчитаем

ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 2-е

событие. В него могут входить работы, только из 0-го и 1-го события, и

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

свершения 2-го события. Рассчитав ранний срок свершения 2-го события, сразу

же рассчитаем ранние окончания всех, исходящих из него работ. Далее.

Рассмотрим 3-е событие. В него могут входить работы, только из 0-го, 1-го и

2-го события, и ранние окончания которых уже известны. Тогда можем

рассчитать ранний срок свершения 3-го события….

Продолжая данные рассуждения, по индукции, рано или поздно дойдём до

завершающего события сетевого графика, ранний срок которого окажется

возможным рассчитать, так как к этому времени, уже будут известны ранние

окончания всех работ сетевого графика. Теорема доказана.

Из данной теоремы, непосредственно, вырисовывается алгоритм расчёта

параметров сетевого графика на первом этапе. Данный алгоритм представлен в

виде блок-схемы 4.3 , и основан на том, что после выполнения алгоритма 4.2

, в таблице исходных данных и результатов [pic] уже находятся коды работ

сетевого графика и их длительности.

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

графика

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

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

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

из этого события, может быть неудача, так как к этому моменту не все

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

такой порядок расчёта сетевого графика, при котором, переходя от события к

событию, всегда удаётся находить их поздние сроки свершения. Оказывается,

для всех сетевых графиков, с правильно занумерованными событиями этот

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

Теорема 4.2 – Если события сетевого графика занумерованы так, что

любая его работа исходит из события с меньшим номером и входит в событие с

большим номером, то расчёт поздних сроков свершения событий в порядке:

последнее событие, предпоследние событие, предшествующее предпоследнему

событию, и так далее, до начального (0-го) события, в тупик зайти не может,

при условии, что рассчитывая поздний срок свершения очередного события,

сразу же определяются поздние начала всех, входящих в него работ.

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

Зададимся поздним сроком свершения последнего события, равным его

раннему сроку свершения, и рассчитаем поздние начала всех, входящих в него

работ. Далее. Рассмотрим предпоследнее событие. Из него могут исходит

только работы, входящие в события с большими номерами – в данном случае

только в последнее событие, при этом поздние начала этих работ уже

известны. Тогда можно рассчитать поздний срок свершения предпоследнего

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

рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим

событие, предшествующее предпоследнему. Из него могут исходить работы,

только в предпоследнее и в последнее событие, и поздние начала которых уже

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

предшествующего предпоследнему….

Продолжая данные рассуждения, по индукции, рано или поздно дойдём до

начального события сетевого графика, поздний срок которого окажется

возможным рассчитать, так как к этому времени, уже будут известны поздние

начала всех работ сетевого графика. Теорема доказана.

Из данной теоремы, непосредственно, следует алгоритм расчёта

параметров сетевого графика на втором этапе. Данный алгоритм представлен в

виде блок-схемы 4.4 , и основан на том, что после выполнения алгоритма 4.3

, в таблице исходных данных и результатов [pic] уже рассчитаны все ранние

сроки свершения событий.

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

графика

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

Если, сначала выполнить алгоритм расчёта ранних сроков свершения

событий 4.3 , а затем алгоритм расчёта поздних сроков свершения 4.4 , то в

таблице исходных данных и результатов останутся не заполненными только три

последних столбца, с номерами: 11, 12 и 13. Данные столбцы, как видно из

таблицы 4.1 , отведены под расчёт резервов времени сетевого графика. Расчёт

резервов времени сетевого графика можно осуществить в любом порядке строк

таблицы исходных данных и результатов, например, подряд – с 0-й строки по

последнюю. Такой порядок расчёта представлен ниже, в виде блок-схемы 4.5 .

Данный алгоритм является завершающим для процесса расчёта параметров

сетевого графика, после выполнения которого, все ячейки таблицы исходных

данных и результатов 4.1 , будут заполнены значениями соответствующих

параметров.

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

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

Как уже известно, найти особые пути сетевого графика представляется

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

входящих в него работ. Тогда, перед поиском особых путей, необходимо

выполнять, описанные в предыдущем подразделе алгоритмы по расчёту

параметров сетевого графика.

Из раздела 3 ясно, что для поиска, и критического пути и

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

заключается в последовательном выборе, от 0-го события до завершающего, тех

работ, которые имеют нулевые полные резервы времени. В случае, если

параметры сетевого графика рассчитывались для положительных длительностей,

входящих в него работ, то указанная методика даёт критический путь сетевого

графика. Если же параметры рассчитывались при отрицательных длительностях

работ, то методика даст наикратчайший путь сетевого графика.

Алгоритм, реализующий методику поиска особого пути сетевого графика,

представлен в виде блок-схемы 4.6 , и основан на том, что таблица исходных

данных и результатов [pic] уже полностью рассчитана, либо при

положительных, либо при отрицательных длительностях работ.

Имея в арсенале, все рассмотренные в данном разделе алгоритмы, любому

программисту не составит труда объединить их в одну, общую программу

анализа оптимальности сетевого графика по критерию оптимальности, подробно

описанному в разделе 1. Проверка данного критерия, с целью выявления

оптимальности сетевого графика, на столько проста в алгоритмической

реализации, что специального рассмотрения не требует.

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

Заключение

В данном курсовом проекте были предложены и обоснованы рациональные

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

методик заключается в том, что они позволяют найти критический и

наикротчайший пути сетевого графика без перебора всех возможных вариантов.

Последнее, позволяет в короткие сроки осуществить решение двух основных

задач сетевого планирования: задачу анализа оптимальности уже готового

сетевого графика и задачу его оптимизации по длительности, в случае, если

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

Кроме того, в курсовом проекте были рассмотрены вопросы автоматизации

на ЭВМ рациональных методик поиска особых путей сетевого графика. В

результате – разработаны блок схемы алгоритмов расчёта параметров сетевых

графиков и поиска их особых путей, которые предполагается использовать при

создании конкретной программы анализа оптимальности сетевых графиков на

любом из известных языках программирования.

Значимость проделанной работы заключается в том, что применение

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

сетевых графиков любой сложности, а во-вторых – сокращает затраты на

сетевое планирование в целом, прежде всего, за счёт сокращения длительности

разработки оптимальных сетевых графиков.

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

Технико-экономическое обоснование дипломных проектов проектов: Учеб.

Пособие для втузов / Л. А. Астреина, В. В. Балдесов, В. К. Беклешов и др.;

Под ред. В. К. Беклешова. – М.: Высш. Шк., 1991. – 176 c.: ил.

-----------------------

[pic]

. 2.1 – Пример сетевого графика

. 3.1 – Поясняющий рисунок к Теореме 3.2

[pic]

-3

-4

-6

-9

-7

-5

-6

-1

-3

[pic]

. 3.2 – Пример сетевого графика при отрицательных

длительностях работ

С0

С1

С2

С3

С4

С5

С6

С7

С0

С1

С2

С3

С4

С5

С6

С7

. 4.1 – Матрица смежностей сетевого графика

Фиктивная работа

. 4.2 – Пример разрыва параллельных работ

Верно

Неверно

Начало

Матрица смежностей уже задана

i:=0

j:=0

Mi j<> 0

Ошибка в структуре графика

Err:=1

Err=1 – Ошибка в

структуре;

Err=0 –Ошибок нет.

Да

Нет

j:=j+1

j > i

Да

Нет

j:=0

i:=i+1

i < p

Нет

Err:=0

p – Число событий на графике

В структуре ошибок нет

Конец

Да

Таблица 4.1 – Таблица исходных данных и результатов

| |Код |Параметры работ и событий |

| |работ| |

| |ы | |

| |i |j |[pi|[pic|[pi|[pic|[pic|[pic|[pic|[pic|[pic|[pi|[pi|[p|

| | | |c] |] |c] |] |] |] |] |] |] |c] |c] |ic|

| | | | | | | | | | | | | | |] |

| |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |12 |13|

|0 | | | | | | | | | | | | | | |

|1 | | | | | | | | | | | | | | |

|k-1 | | | | | | | | | | | | | | |

строки

N Столбца

Начало

i := 0

j := 1

s := 0

Mi j = 1

Нет

Да

As 0 := i

As 1 := j

As 2 := ti j

ti j

Ввод оператором

длительности

работы с кодом i-j

s := s+1

j:= j+1

j ? p

Нет

Да

i:= i+1

j:=i+1

i < p-1

Нет

Да

Конец

p – Число событий на графике

Да

Нет

c > 0

c:= c-1

s:= 0

max:= As 9

Да

Нет

max < As 9

Цикл поиска максимального из ранних окончаний работ, входящих в i-е событие

Да

Нет

As 1= i

-? – Минимально возможное машинное число

c – Счётчик двух циклов для заполнения ячеек A s 5 табл. исходных данных и

результатов

max:= -?

c:= 2

p –Число событий

Да

Нет

i < p

i:= i+1

k – Число строк в таблице исходных данных и результатов

Да

Нет

s < k

s := s+1

As 3:= max

As 7:= max

As 9:= max+As 2

Цикл расчёта ранних окончаний работ, исходящих из i-го события

Да

Нет

As 0 = i

s:=0

max – Хранит ранний срок свершения текущего события

max:= 0

i:= 0

Начало

Да

Нет

s < k

s := s+1

As 5:= max

Конец

Цикл поиска минимального из поздних начал работ, исходящих из j-го события

min:= As 8

Да

Нет

min > As 8

Да

Нет

As 0 = j

s:= s-1

s:= k

+? – Максимально возможное машинное число

c – Счётчик двух циклов для заполнения ячеек As 4 табл. исходных данных и

результатов

min:= +?

c:= 2

Конец

Да

Нет

j < 0

j:= j-1

Да

Нет

s > 0

As 6:= min

As 10:= min

As 8:= min-As 2

Да

Цикл расчёта поздних начал работ, входящих в j-е событие

Нет

As 1 = j

s:= s -1

s:=k

min – Хранит поздний срок свершения текущего события

min:= Ak-1, 5

j:= p-1

Начало

k – Число строк в таблице исходных данных и результатов

As 4:= min

Да

Нет

s > 0

Да

Нет

c > 0

c:= c-1

s:=0

Начало

As 11:= As 10 – As 9

As 12:= As 5 – As 9

As 13:= As 4 – As 3

s:= s +1

Да

Нет

s < k

Конец

i:= 0

Начало

s:= 0

Да

Нет

i < p – 1

Да

Нет

As 0 = i

Да

Нет

As 11 = 0

Вывод кода работы особого пути:

< i, As 1 >

i:= As 1

s:= s+1

Конец

Страницы: 1, 2, 3

МЕНЮ

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