Файл: Соловейчик, Р. Э. Программирование на АЛГОЛ-60 учеб. пособие.pdf

i

\

1

2

3

4

в

в

7

I

О

М

м

М

м

м

м

2

М

О

м

м

м

м

м

3

М

2

о

м

м

м

м

4

3

М

м

о

м

м

м

в

Ш Ш

М

м

в

о

м

м

в

Ш ш

м

м

2

м

о

м

7

жв

3

¥ Ш а

м

в

о

' Ш р

path

, имеющей следующие

параметры:

п

- общее число работ, входящих в сеть;

1 {k] , j [к]

- вектор-пара, представляющая k -р работу, которая

понимается как стрелка, связывающая событие

i Г k J (начало работы) с событием j [ к ] (конец

работы), при этом должно выполняться условие

1 0 1 ^ 3 И

для к= 1 ,2 ,... , п ;

did

.[к]

- продолжительность к-й работы.

—

87

Предполагается,

что имеют место соотношения:

1 Ь ]

- 1

*

1 [к] £ i [к 4 1] ,

i [к] < J

[к + ij

'(общее начало работ),

выражающие условие рациональной нумерации

событий. В результа­

те выполнения процедуры для к »

1 ,2 ,...,п определяются:

а1

Гк] ~

самый ранний

срок начала k -й работы;

s2

[к] -

"

поздний

"

" к

-й

"

;

f1

£к] -

"

ранний

" окончания k -й

"

;

f2

[k]_

"

поздний

"

"

k -й

"

;

[к]- полный резерв времени k -й работы;

f t

[к]- свободный резерв времени k -й работы.

если

i

[к] У/ j £к]

, т.е. при неправильной нумера­

ции событий,с

помощью метки

out 1 ;

если

i

[к]

лежит вне

последовательности,

с помощью

метки out

2

;

.

если

1

[*]

пропущено, т.е. нет такого

события, с

помощью метки

out 3

Все эти метки не локализованы в данной процедуре.

Кроме

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

procedure critical

path

(n,i,j,dij) reeults

(S1 , 32, f1,

£2,

tf,

£f),

value n

;

in teg er n j

in t e g e r

a r ra y

i, j ,dij ,Si ,32,£i.,f2,

tf,

ff

t

begin inte ge r к, index, max,min; integer

a rra y

t i , t e

[ 1in j

i

index

: ■

1»

fo r к

t

>

1 step 1 n n tll

n

do

begin

it

i

[ k] ^ 3 [ k ]

then go to

out i

»

i f

i

[ k ]

<Tindex

then go to oat 2 »

it

i

j\J > index

t 1

then

g<4

to

out3

*

i f

i

£kJ

aindex

♦ 1

then

index»

ai [

k ]

;

t i [к ].' •-

0 » t* [ к ] * - M

end

j

fo r kr

»

1

otep

1

n n tll

n

do

begin

maxi

t i j i f k ] ]

i f

t i

[j

[k ] J

<

* x

Jjhen

t i |

j [

k j j

end

t i

»

te [ J

H ]

»

-

t i

[j

[n]j

;

for к »

=

n step

-

1

until

1 do

begin

min: a

te

[j [k]j

-

dij

[k]

;

i f

te [ i

[k]|

>

min

then te

[ i

[k jJ

I

т

min

end te :

к: э

1

step

1

u n til

n

do

begin 31

[kj

»

*

t i

i

[kj

e2

[к ]

:

a

te

■j

M

~ dij

[h]

f1

[k ]

t

=

t i

4

[k j

> d ij

[k ]

f 2

[k ]

»

=

te

[*

M]

[\])

t f

[ k ]

»

a

te

P

[k j]

“ t i

[i f k j ] - d ij

WJ

k

C1* » ^k

)

1

(1Д)

2

2

(ГД)

1

3

(1,4)

В

4

(2.4)

2

В

(2,в)

6

в

' (2,7)

В

7

(8,4)

2

8

(ад)

7

8

(4Д)

6

10

(4Д)

2

11

(ВД)

4

12

(6,7)

2

IS

(6Д)

7

14

(7Д)

4

и присваиваются начальные значения

массиву

ti [к]

« - о

для всех

к

,

массиву

Чв [к]

| - V

для всех

к

,

где М - некоторое очень большое число

(нацример.М =

10^ дней).

событий

,

max:-ti[l]

+

0

t

2

»

2

t l [2 ]= 0< 2

t l [ 2] i - 2

aaxi-ti[t]

4

aijjVj» 0

♦

1

з

1

ы[з]=" 0 < Г

[з] « =• 1