Вычисление длины критического пути. Разработка программы для вычисления длины критического пути на сетевом графике

ЛАБОРАТОРНАЯ РАБОТА N 7

Вычисление длины критического  пути

1.Цель и задачи.

Разработка программы для вычисления длины критического пути на сетевом графике.

2.Теоретические сведения.

При разработке программы для вычисления длины  критического пути на сетевом графике главным являетсся вопрос : как представлять  в компьютере сетевой график (граф) ?

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

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

(лабораторные работы 1 и 2 ). Тогда каждая работа может быть задана парой (i,j), где

i – номер вершины, в которой работа начинается, а   j - номер вершины, в которой работа заканчивается. Например,

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

i –я работа,i –й элемент второго массива равен номеру вершины, в которой

i –я работа  заканчивается. Для рассматриваемого примера объявление этих массивов может выглядеть так

int begin[]={0,0,1,2,1,3,3,4};

intend[]={2,1,2,3,4,4,5,5};

Массивы .begin   и    end. полностью задают граф  и с их помощью легко выполнить различные построения на графе. Например, если нужно найти все работы, заканчивающиеся в вершине j, ищем все вхождения   j  в массиве  end..

(См. приводимую далее программу).

.

Программа 7

/* вычисление длины критического пути*/

double cripa(int nv,int nrab,int *begin,int *end,double *t)

{

    int i,j;

    double *lbl,r;

    lbl=malloc(nv*sizeof(double));

    lbl[0]=0;

    for(j=1;j<nv;j++){

        lbl[j]=0;

        for(i=0;i<nrab;i++){

            if(end[i]!=j) continue;

            r=lbl[begin[i]]+t[i];

            if(r>lbl[j]) lbl[j]=r;

        }

    }

    r=lbl[nv-1];

    free(lbl);

    return r;

}

Пояснения к программе 7.

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

2. При обращении к программе ей передаются следующие параметры

nv - число вершин сетевого графика;

nrab – число дуг (работ) сетевого графика;

адрес массивов  .begin   и   end. , задающих структуру сетевого графика адрес массива  .t , в котором указаны продолжительности работ.

3. В программе объявляется массив lbl. , в котором происходит расчет ранних сроков свершения событий. Массив имеет размерность  nv ,  элемент  lbl[nv-1] после окончания цикла равен длине критического пути. Под массив выделяется память (malloc), перед выходом из программы ее надо освободить  (free).

Задание.

Освоить программу расчета длины критического пути и с ее помощью найти длину критического пути

- для сетевого графика из лабораторной работы 2;.

- для сетевого графика  с оптимистическими оценками работ;.

- для сетевого графика  с пессимистическими оценками работ;.

- для сетевого графика  в котором; продолжительность работы считается равной      математическому ожиданию.указанной в задании случайной величины.

Оформление отчета.

Отчет должен содержать:

-  ваш сетевой  график с правильной нумерацией вершин;

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