2: Gráftechnikai alapfogalmak VÁLLALKOZÁS. javított háttöltés

Építésikivitelezés-Vállalkozás / 2: Gráftechnikai alapfogalmak

Elõadás:Folia201.doc

VÁLLALKOZÁS ( tervezés - bonyolítás - változásmenedzsment ) ideiglenes földút

monolit vb.támfal

javított háttöltés

új földtöltés

régi töltés

humusz teherbíró talaj

Sz 1 2 3 4 5 6 7

Tevékenység Megnevezés Idõ Humusz leszedés 2 n Töltés lépcsõzés 4 n Tereprendezés 1n Munkagödör 2n Szerelõbeton 3n Zsaluzás 3n Beton vasszerelés 5 n

Munkanap Erõf. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 dózer 10 ém 1 gréder 1 kotró 5 ém 2 ács 4 vassz.

Τ = f ( §, $, λ, µ, π, ... ) § $ λ µ π

: szabályozás : finanszírozás : elhelyezkedés : technológia : idõszak

BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-

Dr. Vattai Zoltán András



GRÁF ( Gráf-technikai alapfogalmak )

A "modell" szempontjából : Jól beazonosított összetevõk és a közöttük páronként feltárt összefüggések. ... összetevõk : − alkotórészek − fázisok / állapotok − folyamatok : összefüggések : − kapcsolódások − ok-okozati viszonyok − sorrendiség :

Matematikailag : Csomópontok és élek rendezett halmaza. Él : összerendelt csomópontpár ...




e


b

a

d

c

f

Ponthalmaz ( N = "node" = csomópont ) N = { a, b, c, d, e, f } Élhalmaz ( E = "edge" = él ) E = [ {a,c},{a,e},{b,c},{b,d}, {b,e},{c,e},{c,f},{d,f} ] Gráf ( G = "graph" = "gráf" ≅ grafika ) G = [ N, E ] BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Irányított él ( A = "arrow" = nyíl ) Az összerendelt { i, j } csomópontok között csak egyik irányban, pl. "i" -bõl "j" -be értelmezünk kapcsolatot. ( A csomópontok sorrendje az irányultságot is mutatja. Pl: ( i, j ), ... ( a, e ), ... )

e

b

a

d

c

f

N = { a, b, c, d, e, f } A = { (a,c),(a,e),(b,c),(b,d), (c,b),(c,f),(e,b),(e,c),(f,d) } G = [ N, A ] BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Irányított Gráf : ( "DiGráf" = "Directed Graph" = irányított gráf ) "Olyan gráf, melynek valamennyi éle irányított" ( Implicite: két csomópont között csak egyetlen - irányított - él van megengedve ) Megjegyzés : Minden "nem irányított gráf" kezelhetõ irányított gráfként, hiszen bármely nem irányított él helyettesíthetõ ugyanazon két összerendelt csomópont között kettõ darab ellentétes irányú irányított éllel { i, j } = { ( i, j ), ( j, i ) } ( Két csomópont között több irányított él létét is megengedhetjük )

i

j

i


j




Súlyozott Gráf A csomópontokon és/vagy az éleken kvantitatív jellemzõket, ú.n. "súlyszámokat" értelmezünk

τae

τbe

e

τce

a

τac

b

τbc

τbd d

τdf c

τcf

f

N = { a, b, c, d, e, f } E = [{a,c,τac},{a,e,τae},{b,c,τbc},{b,d,τbd}, {b,e,τbe},{c,e,τce},{c,f,τcf},{d,f,τdf}]

G = [ N, E, τ ] ( Irányított Gráfnál hasonlóan : G = [ N, A, τ ] ) BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Irányított gráfok alapfogalmai Forrás : Csomópont, mely legalább egy élnek kezdõpontja, de egyetlen élnek sem végpontja

Nyelõ : Csomópont, mely legalább egy élnek végpontja, de egyetlen élnek sem kezdõpontja

Út : ( "P" = "Path" = út/ösvény ) Irányított élek (hurokmentes) nyílfolytonos láncolata Azonosításuk az érintett csomópontok felsorolásával. pl.: P[i,l] = { i, j, k, l } i

j

k

l

Hurok : Út, melynek kezdõ- és végpontja azonos Önmagába záródó út. pl.: P[i,i] = { i, j, k, i } j i BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-

k Dr. Vattai Zoltán András



GRÁF - topológiák ( Csomópontok és élek/utak viszonya )

"teljes"

"fa"

"páros"

"összefüggõ nem összefüggõ"





Struktúra ("adjacencia") mátrix 4

e

b

2

3 3

a

6

d

1

5 c

a

b

4

c

d

e

c

4

+

3

4 + +5

1

b 6

6 a3 b

3

c

4

3 d 4 e5 +

1

d e f

2

f

f

a2 b

a c

f

+

d

f

+ +

+ +

+ +

e

+ +

+ +


+ Dr. Vattai Zoltán András



Hálózat ( "Network" ) 4

e

b

2

3 3

a

6

d

1

5 c

4

f

Hálózat ( mint gráf-technikai fogalom ) : Összefüggõ súlyozott irányított gráf, egyetlen forrással és egyetlen nyelõvel, az éleken nem-negatív súlyszámokkal.

Hálózat ( mint a gráf szinonímája ) : Gráf ... mindennemû elõzetes szûkítõ, avagy általánosító megkötés nélkül. BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Hálózati "problémák" ( leggyakoribb alap-feladatok ) - Útkeresés * - Integritás vizsgálat (összefüggõség) - Hurok keresés - Dominancia - Út(variáns) számlálás - Leghosszabb / legrövidebb út * - Súlypont / Centrum - Maximális folyam / minimális vágás * - Potenciál feladatok : * ú.n. irányított problémák BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Idõ-ütemterv hálók Gráf-technikai analógiák: - Leghosszabb út keresése - Potenciál feladatok ( Valamennyi összetevõre szükség van, keressük a mértékadókat, illetve követjük az esetleges beavatkozások tovagyûrûzõ hatásait )

Hálós idõtervezési technikák ( rárakódó algoritmusok, eltérõ megfeleltetések )

- PERTtime - CPMtime cost - CPM - CPMlétra - MPMtime/PDMtime - MPMcost - GTM ( Általános idõmodell ) BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-


Építésikivitelezés-Vállalkozás / 3: Hálós ütemtervek - I


Idõ-ütemterv hálók - I. 5

t

s

4 2

4

u

v 3

PERTtime/cost : ( Program Evaluation & Review Technique ) ( Program Értékelõ és Áttekintõ Technika ) Esemény-csomópontú, valószínûségi változókkal dolgozó ( sztochasztikus ) projekt-modell

CPMtime/cost : ( Critical Path Method = Kritikus Út Módszere ) Tevékenység-élû, diszkrét adatokkal dolgozó projekt-modell BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




PERT/CPM Gráf-megkötések πt t τst τtv πv πs τut s v τsu "Hálózat" :

u πu

τuv

Összefüggõ, súlyozott, hurok-mentes irányított gráf, egyetlen forrással, egyetlen nyelõvel, nem-negatív súly-számokkal

"Egy-az-egyes" megfeleltetés : Minden rész-összetevõ egyszer, és csakis egyszer szerepelhet a gráf-modellben

"Csomópontpáros él-azonosítás" : Bármely két csomópont között csak egyetlen közvetlen él lehet BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Program Evaluation & Review Technique (PERT) 1958 : US Navy, Polaris Program, Farard Csomópont : esemény, állapot, "mérföldkõ", fejlesztési fázis

Él : közelebbrõl be nem azonosított (mûszaki) tartalmú tevékenység ("részfeladat")

Paraméterek (súlyok) : valószínûségi változók ("idõbeli lefolyás") β eloszlás , becsült érték-hármas alapján

Cél : A projekt várható teljes átfutási idejének és rész-teljesítési idõpontjainak elõrejelzése, a hozzájuk tartozó bizonytalansági mutatókkal ("szórás") együtt. Ütemterv teljesíthetõségének ellenõrzése. BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Valószínûség / β eloszlás /

P Pmax

Te=

Tmin+ 4•Tm+ Tmax 6 2

ν = σ2 =

Tmin

P

Tm Te

(

Tmax - Tmin 6

Tmax

)

T

Valószínûség / Gauss-féle standard eloszlás /

Pmax σ

σ

0.98 A 3σ

Te = Tm


3σ

T Dr. Vattai Zoltán András



PERT feladat :

ID

Mi a valószínûsége annak, hogy az alábbi projekt 12 ie alatt megvalósul ?

(a-m-b) µ e; ν

C A (5-6-7) 6; 1/9

0 0 0 B (3-5-7) 5; 4/9

6 1 6

(0-3-12) 4; 36/9

D

E

(6-7-8) 7; 1/9

(3-3-3) 3; 0/9

5 2 6

G (1-3-5) 3; 4/9

10 H 3 (0-2-4) 11 2; 4/9 13 F 5 (1-5-9) 5; 16/9 13 I 9 4 (2-4-6) 4; 4/9 9

a + 4•m + b µe = 6 b-a 2 2 ν = σ =( 6 ) BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-

µT = 13 νT = 5/9 Dr. Vattai Zoltán András



Centrális határ-eloszlás / Gauss-féle standard eloszlás /

P Pmax

σ

σ

z•σ µS =12 µT =13 3σ

Z=

µS - µT νT

=

12-13 5/9

= -1.3416

Z CP

CP ≈ 9 %

T

3σ

- 2.0 - 1.5 - 1.3 - 1.0 - 0.9 - 0.8

0.02 0.07 0.10 0.16 0.18 0.21


Z CP + 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 0.6

0.54 0.58 0.62 0.66 0.69 0.73




Critical Path Method (CPM

time

)

1957 : USA, E. I. du Pont de Nemours, James E. Kelly, Morgan R. Walker Csomópont : kapcsolat, közvetlen megelõzési reláció

Él : konkrétan beazonosított (mûszaki) tartalmú rész-projekt, avagy tevékenység ("részfeladat"), illetve - szükség szerint megelõzési reláció ("látszat-tevékenység")

Paraméterek (súlyok) : tevékenységidõk, idõtartamok és határidõpontok ( determinisztikus változók )

Cél : a projekt idõbeli lefolyása során kiemelt jelentõségû ( "domináns" / "kritikus" ) tevékenységek beazonosítása, határidõpontok meghatározása, illetve a részprojektek, avagy tevékenységek idõbeli "mozgási szabadságának" feltárása. BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




CPM / PERT gráf-struktúra - operatív információk 2

I

4

C 0

F

D B

1

6

G 5

A C

B

G

I

A,B,I < H C,G < B,I

7

H 3

Közvetlen megelõzési lista

E

A

C F G D

B

H

I

E H

D,H < E F < C,G G < A,B,I I < D,H

G

A I

D B

I H

Operatív információk





CPMtime feladat 2 1 4

idõtartam

B(1) E(4)

6 2 7

A(2) ( lehetséges ) legkorábbi ( megengedett ) legkésõbbi

Tev T A 2 B 1

C(1) 0 0

0

F(6) D(8)

8 3 8

LK LB MK MB TT ST FeT FüT 0 2 2 4 2 0 2 0 2 3 6 7 4 3 2 1

"Kritikus út" : Azon csomópontok - és a közöttük lévõ domináns élek - halmazából alkotott részgráf , melyeknél a lehetséges legkorábbi- és a megengedett legkésõbbi idõ megegyezik. ( "... idõ-tartalékkal nem rendelkezik ..." ) A forrás és a nyelõ közötti leghosszabb utak alkotta részgráf BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




"Teljes" tartalékidõ : Adott tevékenység idõtartamának lehetséges növekménye ( avagy kezdésének késleltetése ) anélkül, hogy az a háló teljes átfutási idejét növelné, feltéve, hogy valamennyi megelõzõ tevékenységét legkorábbi ütemezése szerint tudjuk befejezni.

"Szabad" tartalékidõ : Adott tevékenység idõtartamának lehetséges növekménye ( avagy kezdésének késleltetése ) anélkül, hogy az bármely az adott tevékenységet követõ tevékenység legkorábbi kezdését késleltetné, feltéve, hogy valamennyi megelõzõ tevékenységét legkorábbi ütemezése szerint tudjuk befejezni.

"Feltételes" tartalékidõ : Adott tevékenység idõtartamának lehetséges növekménye anélkül, hogy az a háló teljes átfutási idejét növelné, feltéve, hogy valamennyi megelõzõ tevékenységét legkésõbbi ütemezése szerint tudjuk csak befejezni.

"Független" tartalékidõ : Adott tevékenység idõtartamának lehetséges növekménye anélkül, hogy az bármely az adott tevékenységet követõ tevékenység legkorábbi kezdését késleltetné, feltéve, hogy valamennyi megelõzõ tevékenységét legkésõbbi ütemezése szerint tudjuk csak befejezni. ( Csak nem-negatív értékét értelmezzük ! ) BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-



CPM

cost


( CPM költség modell ) Projekt költségek

C

közvetett

közvetlen

ΣT C

Tevékenység / rész-projekt közvetlen költségek

CTmin

CTmax költség-intenzitás Tmin BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-

Tmax

T



CPM

cost


feladat :

Milyen minimális ("közvetlen") költség mellett valósítható meg az alábbi projekt 10 ie -nél nem hosszabb idõ alatt ? Normal Roham ksg idõ ksg CS

Tev idõ A 2 B 3 C 4 D 3 E 1 F 5 G 6

120 80 100 150 250 130 80

1 1 2 3 1 2 5

200 200 350 150 250 460 110

3 C(4)

A(2) 2 0 3 d1 0 0 3 B(3)2 3

80 60 125 110 30

A

2

12

5 4

1 E(1) 4

12 G(6)

F

5

B

G

1

4

E

2 C(4)

3 F(5)

D(3)

3 D

d1

0

7 7

C

A(2) 2 0 2 0 B(2)

6

6 d1

0

6 11

5

D(3)

2 2

3 F(5)4

3

1 E(1) 4

11 G(6)

5

C11 = C12 + CSB = 910 + 60 = 970 C10 = C11 + CSF = 970 + 110 = 1080 BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-



C


Projekt közvetlen költségek / CPMcost /

max CTmin min CTmin

max

max CTmax

min

min CTmax

Tmin

C

Tmax

ΣT

Optimális projekt futamidõ és minimális költség összesített

Cmin

közvetett ∆

közvetlen Topt


ΣT Dr. Vattai Zoltán András

Építésikivitelezés-Vállalkozás / 4: Hálós ütemtervek - II

CPM

létra


konvenció :

Gond: CPM - baj van az átlapolt idõhelyzetekkel. Válasz: Paraméterek a „látszat-tevékenységeken” A ( tA ) ( τ2 )

( τ1 ) B ( tB )

( τ4 ) ( τ3 ) C ( tC )

Negatív paraméterek továbbra is tiltottak. Gond a nyitott háló és a meg-nem-szakítható tevékenység BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-



CPM

cost


feladat :

Milyen minimális ("közvetlen") költség mellett valósítható meg az alábbi projekt 4 ie -nél nem hosszabb idõ alatt ? Normal

Roham

Tev idõ ksg idõ ksg CS 3 A 2 1 1 2 5 B 3 1 1 2 2 C 2 1 1 1 5 D 3 1 1 2 3 E 2 1 1 2

0

0

D

C

2

3

E

0

2

A(2)1

1

0

C(2)1 D(3) 4

2

B(3)2 3

3 6

D(3)

C(1)

6

E(2)

1

0

2

B(3)

4

B

1

0

2

0

2

A(2)

A

2 3

5

E(2)

3 5

C5 = C6 + CSC = 5 + 1 = 6 C4 = C5 + CSA+B = 6 + 4 = 10 ? BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-



CPM

cost


feladat :

Milyen minimális ("közvetlen") költség mellett valósítható meg az alábbi projekt 4 ie -nél nem hosszabb idõ alatt ? Normal

Roham

Tev idõ ksg idõ ksg CS 3 A 2 1 1 2 5 B 3 1 1 2 2 C 2 1 1 1 5 D 3 1 1 2 3 E 2 1 1 2

0

0

2

3

E

1

A(1)

1

0

4

1

B(3)

C(2)

6

E(2)

D

0

D(3)

C(2)

1 C

0

2

B(3)

4

B

1

0

2

0

2

A(2)1

A

D(3)

3

3

2

6

3

5

E(2)1 5

3

C5 = C6 + CSA = 5 + 2 = 7 ( > 6 ) C4 = C5 + CSE = 7 + 2 = 9 ( < 10 ) ! BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Idõ-ütemterv hálók - II.

CPM - CPMlétra : Továbbra is gond az átlapolás, a nyitott háló és a meg-nem-szakítható tevékenység ( termelésközeli ütemtervek ) time

MPM

: ( METRA Potential's Method ) ( METRA Potenciálok módszere )

Tevékenység-csomópontú, többszörös és többféle kapcsolatot kezelni tudó, diszkrét változókkal dolgozó (determinisztikus) projekt-modell

GTM : ( General Time Model ) ( Általános idõmodell ) Homogén korlátozó feltételeket kezelõ, határ-idõpont orientált projekt-modell BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




METRA Potential's Method time (MPM ) 1960 : B. Roy, Franciaország, Atomerõmû ( eredetileg csak kezdési idõpotenciálok ... ) Csomópont : meg-nem szakítható tevékenység ( 0 idejû tev. = esemény, mérföldkõ )

Él : mûszaki-, technológiai, avagy erõforrás indíttatású paraméteres kapcsolat

Paraméterek (súlyok) : késleltetési idõk, idõtartamok, idõpontok ( determinisztikus változók )

Cél : termelés közeli technológiai idõtervek, termelésirányítás, termelés követés, változás menedzsment ... ... tetszõlegesen átlapolt (relatív) idõbeli helyzetek, erõforrás-allokációs feltételek, térbeliség, technológiai elõírások, stb. (idõvetületeinek) kezelése BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




"Tevékenység csomópont" Tevékenység azonosító ( opcionális ) Legkorábbi kezdés

Tevékenységidõ

[A]

Legkorábbi befejezés

Legkésõbbi kezdés

Legkésõbbi befejezés Teljes tartalékidõ

"Kapcsolati reláció" (min) „Megelõzõ” (viszonyítási alap) tevékenység határidõpontja ( jelen esetben „Befejezése” )

„Követõ” (viszonyított) tevékenység határidõpontja ( jelen esetben „Kezdése” )

Kapcsolati paraméter

BKp

A kapcsolat „típusa” („Befejezés-Kezdés minimum”)

A nyíl a viszonyítás irányát, a folyamatos vonal a kapcsolati paraméter alulról korlátozó jellegét mutatja





"Kapcsolati reláció" (max) „Megelõzõ” (viszonyítási alap) tevékenység határidõpontja ( jelen esetben „Befejezése” )

"negatív" elõjel

„Követõ” (viszonyított) tevékenység határidõpontja ( jelen esetben „Kezdése” )

Kapcsolati paraméter

- BK p

A nyíl a fordított viszonyítási irányt, a szaggatott vonal és a "negatív" elõjel a kapcsolat felülrõl korlátozó jellegét mutatja

A kapcsolat „típusa” („Befejezés-Kezdés maximum”)

"Befüggesztett tevékenység"

[kezdés]

[befejezés] BK0





MPM Kapcsolati alap-típusok progresszió ( készültségi fok ) [%]

Tm

BBp3

100

m

k

0

idõ

B K p1 K K p2

Tk

KBp4

Kapcsolat típusok átváltása BBq BBp

BKq

KBq

KKq

q = p - Tk

q = p + Tm

q = p + Tm - Tk

q = p +Tm + T k

q = p + Tm

BKp

q = p + Tk

KBp

q = p - Tm

q = p - Tm - Tk

KKp

q = p + T k - Tm

q = p - Tm

q = p - Tk q = p + Tk





Egyszerû kapcsolati típusok BKp „befejezéskezdés min p”

-BKp „befejezéskezdés max p”

KKp „kezdés-kezdés min p”

-KKp „kezdés-kezdés max p”

BBp „befejezés-befejezés min p”

-BBp „befejezés-befejezés max p”

KBp „kezdés-befejezés min p”

-KBp „kezdés-befejezés max p”

A követõ (viszonyított) tevékenység legalább "p" idõegységgel a megelõzõ (viszonyítási alap) tevékenység befejezése után kezdõdjék

Erõsen erõforrás-korlátos esetek tipikus kapcsolata ( általában „0” paraméterrel, soros folyamatkapcsolások létrehozására )

A követõ (viszonyított) tevékenység legfeljebb "p" idõegységgel a megelõzõ (viszonyítási alap) tevékenység befejezése után kezdõdjék

Általában a BKp kapcsolattal együtt, állagmegóvási, illetve erõforrás-kihasználási követelmények tipikus kapcsolata

A követõ (viszonyított) tevékenység legalább "p" idõegységgel a megelõzõ (viszonyítási alap) tevékenység kezdése után kezdõdjék

Jól szinkronizált, illetve párhuzamos folyamatok tipikus kapcsolata, pl. nagyobb léptékû ütemtervek, projektek esetén

A követõ (viszonyított) tevékenység legfeljebb "p" idõegységgel a megelõzõ (viszonyítási alap) tevékenység kezdése után kezdõdjék

Nem tipikus kapcsolat; magában, illetve KKp kapcsolattal együtt allokációs segédeszközként nyújthat hasznos segítséget

A megelõzõ (viszonyítási alap) tevékenység befejezése és a követõ (viszonyított) tevékenység befejezése között legalább "p" idõegység legyen

Többnyire „adminisztrációs”, pl. átadási, ellenõrzési tevékenység „visszaszámlálás” jellegû idõzítésére szolgáló kapcsolat

A megelõzõ (viszonyítási alap) tevékenység befejezése és a követõ (viszonyított) tevékenység befejezése között legfeljebb "p" idõegység legyen

Nem tipikus kapcsolat; magában, illetve BBp kapcsolattal együtt allokációs segédeszközként nyújthat hasznos segítséget

A megelõzõ (viszonyítási alap) tevékenység kezdése és a követõ (viszonyított) tevékenység befejezése között legalább "p" idõegység teljen el

Teoretikus kapcsolat; tipikusan a -BKp kapcsolat kiváltására ( idõtervezési eszközként ) szolgálhat, ... negatív paraméterrel

A megelõzõ (viszonyítási alap) tevékenység kezdése és a követõ (viszonyított) tevékenység befejezése között legfeljebb "p" idõegység teljen el

Teoretikus kapcsolat, a teljesség kedvéért kerül megemlítésre. Bonyolult allokációs feltételek esetén nyújthat segítséget.





Leggyakrabban használt összetett kapcsolati típusok KKp } CRp BBp „(min) kritikus megközelítés”

-KKp }-CRp -BBp „(max) kritikus megközelítés”

BKp } -BKp „szoros követés”

BK0 } -BK0 „azonnali követés”

BBf(Tk) } KKf(Tm) „(min) általános kettõs kapcsolat”

-BBf(Tk) } -KKf(Tm) „(max) általános kettõs kapcsolat”

A megelõzõ (viszonyítási alap) tevékenység számára a követõ (viszonyított) tevékenységgel szemben minden készültségi foknál legalább „p” egységnyi idõelõny biztosítandó

Technológiai ( kötési, száradási, szilárdulási stb.) feltételek tipikus kapcsolata átlapolt, vagy nem ismert idejû tevékenységek között

A megelõzõ (viszonyítási alap) tevékenység és a követõ (viszonyított) tevékenység között minden készültségi foknál legfeljebb „p” egységnyi követési idõ biztosítandó

Kellõ körültekintéssel állagmegóvási feltételek kapcsolata lehet. Alkalmazása azonban sok veszélyt rejt magában, ezért ha nem szükséges, ne használjuk !

A követõ (viszonyított) tevékenység a megelõzõ (viszonyítási alap) tevékenység befejezését követõen pontosan „p” idõegység elteltével kell hogy kezdõdjék

Tipikusan az egymást követõ tevékenységek relatív idõhelyzetének direkt megadására ( pl. allokációs célú rögzítésére ) szolgáló kapcsolat

A követõ (viszonyított) tevékenység a megelõzõ (viszonyítási alap) tevékenység befejezését követõen azonnal, késedelem nélkül el kell hogy kezdõdjék

Fõleg nagyértékû erõforrások allokációjára ( adott erõforrás folyamatos munkavégzésének elõírására ) szolgáló kapcsolat

A követõ (viszonyított) és a megelõzõ (viszonyítási alap) tevékenység kezdése között legalább f(Tm) egységnyi, befejezéseik között pedig legalább f(Tk) egységnyi követési idõ biztosítandó ! ( a tevékenységidõk függvényében megadott idõparaméterekkel )

Pl. a minimális térköz biztosításának tipikus eszköze. A kapcsolat idõparaméterei az érintett tevékenységek elõrehaladási ütemének (idõtartamának) függvényében kerülnek meghatározásra

A követõ (viszonyított) és a megelõzõ (viszonyítási alap) tevékenység kezdése között legfeljebb f(Tm) egységnyi, befejezéseik között pedig legfeljebb f(Tk) egységnyi követési idõ biztosítandó ! ( a tevékenységidõk függvényében megadott idõparaméterekkel )

Kellõ körültekintéssel állagmegóvási, illetve munkaterület korlátozási feltételek kapcsolata lehet. Alkalmazása azonban sok veszélyt rejt magában, ezért ha nem szükséges, ne használjuk !





Technológiai szünet biztosítása progresszió [%] Tm

BBp

100

CRp

m

0

KKp

k

Tk

idõ

progresszió [%] Tm

BBp

100

m

0

KKp

CRp

k

Tk


idõ Dr. Vattai Zoltán András



Térköz biztosítása progresszió [m]

BB

Tm

l ⋅ Tk L

l

L

m

k 0 Tk l KK

idõ

l ⋅ Tm L

progr.[m] Tm

BB

l ⋅ Tk L

l

L

m

k 0 Tk l KK

idõ

l ⋅ Tm L





Állagmegóvás progresszió [%]

progresszió [%]

Tm

-BBp

Tm

100

-BBp

100 -CRp

m 0

-CRp

k

k

m 0

-KKp Tk

Tk

-KKp

idõ

idõ

Munkaterület korlátozás progresszió [m] Tm

l ⋅ Tk

-BB L

progr.[m] l ⋅ T k -BB L Tm

l

L

L

m

k

m

0 l

l

k

0 l T -KK ⋅ m L

idõ

l

Tk


Tk

idõ

l ⋅ Tm

-KK L




Tevékenységidõ korlátozás progresszió [%] -Tmax j

100

0

j’

i Tmin

idõ

Virtuális lassítás / paradoxon / progresszió [munkaszakasz] ∆ T n .. ∆=

3

T-t n

2 1 ∆

t


idõ




MPM hálós feladat:

Bal hídfõ

Bal mederpillér

Jobb mederpillér

0 0

Terület elõkészítés KK0

2 0

2 2

KK0

0 0

Cölöp alapozás

Jobb hídfõ

KK0

KK0

BK0 10 10 10 10 20 0 10 -BK0 10 0 20

BK0

BK0

BK0 BK0

Síkalapozás

0 3

6 3

6 9

12 15

5 3

17 BK0 20 20 20

BK5

BK5

5 0

25 25

6 9

6 3

BK5

BK0

12 15 BK5

BK0

Felmenõ szerkezet

11 18

5 7

16 23

22 28

BK20

Áthidaló szerkezet

50 50

BK20 2 0

2 6

24 BK0 30 30 30 BK20

52 BK0 52 52 52 -BK0

BK0

Pályaszerkezet + befejezõ m.

BK20 2 0

4 0


32 32

17 23

BK20

BK20

54 BK0 54 54 54 -BK0

BK0 56 56

2 0

2 0

5 6

22 28

56 56

BK0

60 60




Kritikusság / Dominancia típusok A 0

A1

A 0

7

7 -7

7

B BK4 11

7

A2

4

B1

B KK4 4

7

C 4 15 19 3 14 BK4 18 5

3

4

-3 -4

B2

A1

A 0

-7

7

A2

7

C1

C 4 8 3 7 KK4 8

4 7

4

5 -5

5

24

23

C2

13

4 3

B1

4

-3 -4

B2

C1

5 -5

B C 7 4 11 BB4 8 3 11 KK4 12 5

C2

16

17

4

A1

7 -7

A2

B1

3

4

-3 -4

B2

C1

5 -5

C2

4





General Time Model (GTM) 1997 : Magyarország, Z. A. Vattai, Multi-projekt menedzsment (MÁV) Csomópont : határ-idõpont, "esemény" ( kezdés, befejezés, mérföldkõ )

Él : összerendelés, összevetés, reláció kijelölés ( tevékenység, technológiai szünet, követés, késleltetés, várakozás, stb.)

Paraméterek (sú lyok) : reláció-paraméterek, alsó korlát-értékek, idõ-potenciálok, ( determinisztikus változók )

Cél : a projekt idõbeli lefolyásának modellezése az ismert gráf-technikai idõtervezési eljárások (PERT,CPM,MPM) korlátainak feloldásával, rugalmas típus-technológiák, állékony logikai struktúrák létrehozása BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Relá ciók "homogenizá lá sa" πi

τij

πj

i

j

τij ≤ πj − πi πi

− τij

πj

i

j

πj − πi ≤ τij − τij ≤ πi − πj πi

τij

i

πj j

πj − πi = τij τij ≤ πj − πi ≤ τij BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-



MPM

time


→ GTM feladat :

A

C

B KK9

2 7 9 2 0 9

KK4

11 5 16 11 0 16 BK0

BB6

D

15 2 17 16 1 18 BB2

-BK2

E BK0

0 3 3 0 0 3

F

2

0 D1 0

7

9 A2 9

11 B1 11

6

0

-7

3 -3

19 1 20 19 0 20

4

9 2 A1

BK10

5 4 9 5 0 9

3 D2 3

0

5

15 C1

16 B2

-5

16

16

2 -2

17 C2 18

2

-2

5 E1

4

5

-4

9

19 F1

E2

A1 A2 B1 B2 C1 C2 D1 D2 E1 A1 2 7 9 A2 -7 9 B1 11 5 4 B2 -5 16 C1 2 C2 -2 D1 0 3 D2 6 -3 3 0 E1 5 0 -4 E2 F1 F2

9

10

E2 F1 F2

-2

2

4 9 10 19 1 -1 20

19

1 -1

20 F2 20

πmax 2 9 11 16 16 18 0 3 5 9 19 20

πmin 2 9 11 16 15 17 0 3 5 9 19 20





NÉGY "BÛVÖS KÉRDÉS" a hálós idõtervezés témakörébõl 1., Tevékenység-él típusú hálós ütemterven tartalékidõvel nem rendelkezõ tevékenység idõtartama δ értékkel megnõ. Mi lesz a háló teljes átfutási idejével ? 2., Tevékenység-él típusú hálós ütemterven tartalékidõvel nem rendelkezõ tevékenység idõtartama δ értékkel csökken. Mi lesz a háló teljes átfutási idejével ? 3., Tevékenység-csomó típusú hálós ütemterven tartalékidõvel nem rendelkezõ tevékenység idõtartama δ értékkel megnõ. Mi lesz a háló teljes átfutási idejével ? 4., Tud-e olyan esetet említeni, amikor egy tartalékidõvel nem rendelkezõ tevékenység egyaránt "pozitív-", "negatív-", "kezdés-", és "befejezés-kritikus" ?



Építésikivitelezés-Vállalkozás / 6: GrafGlobal-GTM


GRÁFOK GLOBÁLIS ( valamennyi viszonylatra történõ )

VIZSGÁLATA Viszonylat:

irányított csomópont pár [i,j] 1 j

k

n

1 i

aij

k

akj

aik

n

Trivialitás: Egy gráfon ha létezik P[i,k] út, és létezik P[k,j] út is, akkor létezik P[i,j] út is. Ezen összefüggésben k pontot az [i,j] viszonylat közvetítõ pontjának-, míg valamennyi P[i,j] utat – együttesen – ( [i,j] viszonylatbeli ) elérési lehetõségnek (aij) nevezzük. BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




A ϕ(A) transzformáció család ϕ 0 (A) = A ϕ κ (A) = ϕ ( ϕ κ−1(A))

|

κ = 1, 2, ... n

Kiinduló mátrix ( „közvetlen elérési tábla” ): Alaphelyzet ( „üres” mátrix ):

aij = M

Nem súlyozott gráfnál:

aij = 1

aij = τij

Súlyozott gráfnál:

∀ i,j De!: Ha [i,j] él létezik

∀ i,j

Ha [i,j] él létezik

∀ i,j

Mátrix transzformációk: aij0 = aij

∀ i,j

 ϕ ( aijk-1, aikk-1, akjk-1 ) | aijk =   aijk-1

aikk-1 ≠ M; akjk-1 ≠ M; i ≠ k; j ≠ k   ∀i,j ∀ egyébként  k = 1, 2, ... n

Alap feladatok: Integritás vizsgálatok:

Μ = 0;

ϕ ( aijk-1, aikk-1, akjk-1 ) = 1;

( irányítatlan élek ! )

Dominancia vizsgálatok:

Μ = 0;

ϕ ( aijk-1, aikk-1, akjk-1 ) = 1;

( irányított élek ! )

Hurok keresés:

Μ = 0;

ϕ ( aijk-1, aikk-1, akjk-1 ) = max { aijk-1, 2 - aijk-1}

Útvariánsok leszámlálása: Μ = 0;

ϕ ( aijk-1, aikk-1, akjk-1 ) = aijk-1 + ( aikk-1 ⋅ akjk-1 )

Súlypont/Centrum/Átló:

Μ = +∞; +∞ ϕ ( aijk-1, aikk-1, akjk-1 ) = min { aijk-1, aikk-1 + akjk-1 }

A leghosszabb spúr:

Μ = −∞; −∞ ϕ ( aijk-1, aikk-1, akjk-1 ) = max { aijk-1, aikk-1 + akjk-1 }





INTEGRITÁS VIZSGÁLATOK ( Μ = 0; ϕ ( aijk-1, aikk-1, akjk-1 ) = 1 ) j i

F

G

A

D

E C

B

A

1

B

2

C

3

D

4

E

5

F

6

G

7

A 1

B 2

C 3

D 4

E 5

F 6

G 7

1 1 1

1

1

1 1 1

1

1 1

1

Kiegészített struktúra tábla j i

A

1

B

2

C

3

D

4

E

5

F

6

G

7

A 1

B 2

C 3

D 4

E 5

F 6

G 7

1 1 1 1

1

1 1

1

1

1

1

1

1

j i

A

1

B

2

C

3

D

4

E

5

F

6

G

7

A 1

B 2

i

A 1

B 2

C 3

D 4

A

1

B

2

C

3

D

4

1

1

E

5

1

1

F

6

G

7

E 5

F 6

F 6

G 7

1 1

1

1

1

1

1

1

1

1

1

1 1

G 7

1

j i

A 1

C 3

F 6

G B 7 2

D 4

E 5

A

1

1

1

1

1

C

3

1

1

1

1

F

6

1

1

1

1

1

G

7

1

1

1

1

1

B

2

1

1

1

1 1

1

E 5

K=2

1 1

D 4

1

K=1 j

C 3

1

1

1

1

D

4

1

1

1

1

1

1

E

5

1

1

1

…K=4…

Az átrendezett teljes elérési tábla





DOMINANCIA VIZSGÁLATOK ( Μ = 0; ϕ ( aijk-1, aikk-1, akjk-1 ) = 1 )

C

F

A

D

G

E

B

Domináns pont(halmaz): A gráf azon i pontja (-inak halmaza), melybõl a gráf valamennyi pontjához út vezet. ( P[i,j] minden j ≠ i -re létezik. ) Dominált pont(halmaz): A gráf azon i pontja (-inak halmaza), melyhez a gráf valamennyi pontjából út vezet. ( P[j,i] minden j ≠ i -re létezik. )

j i

A

1

B

2

C

3

D

4

E

5

F

6

G

7

A 1

B 2

C 3

1 1

E 5

F 6

1

1

G 7

j i

A 1

B 2

C 3

D 4

F 6

1

1

1

1

1

1

1

1

1

1

B

2

1

1

C

3

1

1

D

4

1

1

E

5

1

1

1

1

1

F

6

1

1

1

1

1

G

7

1

1

1

1

1

1

1

1

1

E 5

A

1

1

D 4

1

1

1

1 1

1

1

1

1

1

G 7

1

1

1

A közvetlen- és a teljes elérési tábla a domináns- és a dominált ponthalmaz jelölésével BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




HUROK KERESÉS ( Μ = 0; ϕ ( aijk-1, aikk-1, akjk-1 ) = max { aijk-1, 2 – aijk-1 } )

2

D 1

1

1

F

A

1

B

2

C

3

D

4

A

B

C

D

E

F

G

1

2

3

4

5

6

7

2 1

2 1

2

2 2

2

2

1

F

6

2 1

1

2

5

7

A

4

E

G

C

1

E

i

2

B 3

j

G

2

3

2 1

1 1

2 1

2

4

2 1

2

1

2

2

2

1

2

2

1

1

2

2

1

2

2

2

1

2

A teljes elérési tábla a hurokélek becsült befoglaló hurok-variáns számaival BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




ÚTVARIÁNSOK LESZÁMLÁLÁSA ( Μ = 0; ϕ ( aijk-1, aikk-1, akjk-1 ) = aijk-1 + ( aikk-1 · akjk-1 ) )

3

B 1

1

1

1

F

4

A

2

C

3

D E F G

4 5 6 7

C 2

E

2

A

B

C

D

E

F

G

1

2

3

4

5

6

7

1

B

2 2

G

i

6

D

7

j

A

1 1

3 1 6 5

3

1

6

1 1

1

2

4 2

3 2

1 1

8 7

1

2

2

1 1

2 4

2

1

7

2

A teljes elérési tábla az élek FC viszonylatbeli befoglaló út-variáns számaival BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




Súlypont / Centrum / Átló keresés ( Μ = +∞; ϕ ( aijk-1, aikk-1, akjk-1 ) = min { aijk-1, aikk-1 + akjk-1 } )

5

G

F

7 1 3

B

8

4 5

D 5

C

3 1

5

E

A

2

Súlypont: A gráf azon pontja, melybõl (melyhez) a gráf valamennyi más pontjához (pontjából) vezetõ legrövidebb utak hosszának összege a lehetõ legkisebb. Centrum: A gráf azon pontja, melybõl (melyhez) a gráf valamennyi más pontjához (pontjából) vezetõ legrövidebb utak közül a leghosszabb is a lehetõ legrövidebb. Átló: j i

( M*)

A gráf viszonylatain a legrövidebb utak közül a leghosszabb A 1

A

1

B

2

C

3

D

4

E

5

2

F

6

5

G

7

B 2

C 3

D 4

E 5

F 6

1

3

2

5

i

A 1

B 2

C 3

D 4

E 5

F 6

G 7

FS FC

A

1

2

7

1

3

2

5

4

22

7

B

2

7

10 8

8

5

12

7

47

12

C

3

1

8

2

4

3

6

5

27

8

D

4

6

8

7

2

4

4

1

30

8

5

E

5

2

5

3

5

4

7

6

28

7

4

F

6

5

12 6

4

7

8

5

39

12

G

7

5

7

1

3

5

2

27

7

5 1

G 7

7 8 4

5

7

1

3

1

5

A közvetlen- és a teljes elérési tábla a Forrás- és Nyelõ oldali Súlypont és Centrum, valamint az átló jelölésével

j

6

NS

26 47 31 25 24 39 28

NC

7

12


8

8

7

12

7




A LEGHOSSZABB SPÚR ( Μ = −∞; ϕ ( aijk-1, aikk-1, akjk-1 ) = max { aijk-1, aikk-1 + akjk-1 } )

4

B 6

3 1

F 5

j i

A 1

2 5

D 3

C

4

G

6

E

2

A

B

C

D

E

F

G

1

2

3

4

5

6

7

A

1

2

B

2

C

3

D

4

1

E

5

6

F

6

G

7

4

4

4

6

1

3

5

8 6

2

3

3

6

1 6

5

3

4

3


6

1

7 5

2

2

5




GTM ( Általános idõmodell ) Relációk homogenizálása πi

τij ≤ πj − πi τij

i

πj j

πj − πi ≤ τij /⋅(−1) − τij ≤ πi − πj πi

− τij

i

πj j

πj − πi = τij τij ≤ πj − πi ≤ τij πi

τij

i

πj j

− τij BME Építéskivitelezési Tanszék / Építõmérnök Kari Oktatás / 2000-




MPM/PDM

GTM

MPM/PDM hálós idõmodell heterogén feltételekkel A 2 7 9 2 0 9

B 11 5 16 11 0 16

SS9

FS0

FF6

D 0 3 3 0 0 3

SS4

-FS2

E 5 4 9 5 0 9

FS0

C 15 2 17 16 1 18 FF2

FS10

F 19 1 20 19 0 20

MPM/PDM modell GTM átirata homogén feltételrendszerrel 9 A1

7

4 A2

B1 6

D1

-3

B2

C1

-5

-7

3

5

D2

0 0

2

C2

-2 -2

E1

4

E2

-4


2 10

F1

1

F2

-1




Módosított/új fogalmak Pozitív forrás : Csomópont mely legalább egy nem-negatív élparaméterû élnek kezdõpontja, de egyetlen nem-negatív élparaméterû élnek sem végpontja

Pozitív nyelõ : Csomópont mely legalább egy nem-negatív élparaméterû élnek végpontja, de egyetlen nemnegatív élparaméterû élnek sem kezdõpontja

Pozitív/Negatív/Null hurok : Adott hurok élparamétereinek összege alapján

Felismerés : A leghosszabb út elsõ- és utolsó éle nem lehet negatív élparaméterû !

Kritikus út : Pozitív források és pozitív nyelõk közötti leghosszabb utak alkotta rész-gráf

Gráf megkötés :

- ( Pozitív hurok ! )





Idõpotenciálok meghatározása 9 2 A1 2

7 -7

4 9 A2 9

11 5 16 B1 B2 11 -5 16

6 0 D1 0 π

3 -3 πn

f

0

3 D2 3 20

4 -4

9

2

19 1 20 E2 F1 F2 10 20 9 19 -1

20

20

A1 A2 B1 B2 C1 C2 D1 D2 E1 E2 F1 F2

0 A1 0

7

17 C2 18

-2

5 E1 5

0

15 2 C1 16 -2

7 17 18

πmax

9 14 13 15

3

2

A2 -7 0

2

7

6

8

-4 0 10 11

20 9

B1

0

5

4

6

-6 -2 8

9

11

B2

-5 0 -1 1

-11 -7 3

4

20 16

C1

0

2

3

4

16

C2

-2 0

1

2

18

9 19 20

0

D2 -1 6

8 13 12 14 -3 0 02 6 16 17

3

E1

4

9

8 10

0

4 14 15

5

E2

0

5

4

-4 0 10 11

9

0 D1 2

9 11 16 15 17 0

3

6

5

F1

0

1

19

F2

-1 0

20

πmin 0 2

9 11 16 15 17 0

3

5


9 19 20 Dr. Vattai Zoltán András



j

B

E

A

D

G

C j i

1

2

i

3

4

5

F 6

7

j i

1

2

3

4

5

6

7

A

1

B

2

C

3

D

4

E

5

F

6

G

7 j i

1

1

1

2

2

2

3

3

3

4

4

4

5

5

5

6

6

6

7

7

7

j i

1

2

3

4

5

6

7

j i

1

2

3

4

5

6

7

j i

1

1

1

2

2

2

3

3

3

4

4

4

5

5

5

6

6

6

7

7

7

j i

1

2

3

4

5

6

7

j i

1

1

2

2

3

3

4

4

5

5

6

6

7

7

1

2

3

4

5

6


A 1

B 2

C 3

D 4

E 5

F 6

G 7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

7


2: Gráftechnikai alapfogalmak VÁLLALKOZÁS. javított háttöltés

Recommend Documents