Нахождение критического пути табличным методом

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

4.6. Определяются конечные этапы. Если в таблице исходных данных строка не содержит данные длительности, значит, этим этапом не начинается ни один вид работ, то есть он конечный

.

4.7. Для всех конечных этапов, найденных по исходной таблице заносятся значения позднего завершения работ равные длительности проекта и время позднего начала работ, равное разнице длительности проекта и длительности вида работ. Вычисляется полный резерв равный разнице между поздним и ранним временем окончания (начала) работ.

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

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

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

5. Результаты вычислений выводятся на экран. Пользователь может перевести единицы времени в обратном порядке (п. 3).

5.Пример решения задачи на ЭВМ

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

Пусть задан граф.

На основе данных графа строится таблица

Сначала вводится число этапов работ (в данном примере 10)

Исходя из данных таблицы заполняется электронная таблица исходных данных, где номер строки – этап начала работы, а номер столбца – этап завершения работы.

После нажатия на кнопку «ОК» откроется меню решения

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

 Скачать реферат