Dr. Kulcsár Gyula. Virtuális vállalat félév. Projektütemezés. Virtuális vállalat félév 5. gyakorlat Dr

Dr. Kulcsár Gyula

Virtuális vállalat 2016-2017 1. félév

Projektütemezés Virtuális vállalat 2016-2017 1. félév 5. gyakorlat Dr. Kulcsár Gyula

Dr. Kulcsár Gyula


Projektütemezési feladat megoldása

Dr. Kulcsár Gyula


Projektütemezés • Projekt: – Egy nagy, összetett, általában egyedi igény alapján előállítandó termék vagy nyújtandó szolgáltatás előállítására/teljesítésére irányú törekvés, amely általában nagyszámú komponens feladat/aktivitás végrehajtását igényli.

• Projektütemezés: – Projekt(ek) időbeli végrehajtásának megtervezése úgy, hogy a megfogalmazott célok teljesüljenek figyelembe véve az előírt korlátozásokat.

Dr. Kulcsár Gyula


Projektütemezés jellemzői • Cél: – egy vagy többcélú optimalizálás, – amelyben sokféle szempont szerepelhet (pl. minőség, idő, költség, felhasználói elégedettség stb.).

• Feladatok/aktivitások hálózata alakul ki (pl. megelőzési relációk alapján). • Korlátozottan/korlátlanul rendelkezésre álló erőforrásokat kell figyelembe venni.

Dr. Kulcsár Gyula


Projekt példák • • • • • • • •

Termelés Tervezés Kutatás/fejlesztés Menedzsment Építés Karbantartás, fenntartás Implementálás, telepítés stb.

Dr. Kulcsár Gyula


Projektütemezés alapjai • Projekt/projektek reprezentálása (precedencia gráfok) • Modellek és megoldási módszerek – Kritikus útvonal módszer (egyszerű) (Critical Path Method, CPM) – Erőforrás-korlátos projektütemezés (bonyolult) (Resource-Constrained Project Scheduling, RCPS) • Prioritás/szabályalapú megoldási módszerek • Tudás-intenzív megoldási módszerek

– Kiterjesztett modellek és módszerek (összetett)

Dr. Kulcsár Gyula

Feladat 1 2 3 4 5 6


Projekt ábrázolása

p(j) Előfeltétel 2 3 1 4 1, 2 2 2, 3 1 4

„job on node” reprezentáció: 1

2

4

3

5

6

„job on arc” reprezentáció: 1 2 3

6

4 5

7

Dr. Kulcsár Gyula


Projekt ábrázolása Feladat Végrehajtási idő Megelőző [időegység] feladat(ok) 1 2 2 3 1 3 1 1 4 4 2 5 2 3 6 1 4, 5 7 3 4, 5

„job on arc” reprezentáció:

1

2

4

3

6

7 5 8

Dr. Kulcsár Gyula


Projekt reprezentálása precedencia gráffal Feladat Végrehajtási idő Megelőző [időegység] feladat(ok) „job on node” ábrázolás Csomópont: feladat 1 2 2 3 1 A csomópontok számozottak. 3 1 1 Irányított él: kötelező 4 4 2 sorrendiség 5 2 3 Nincs irányított körút. 6 1 4, 5 Nincs redundáns él. 7 3 4, 5 1

2

4

6

3

5

7

Dr. Kulcsár Gyula


Projektütemezési feladat erőforráskorlátok nélkül • Feltételezzük, hogy: – korlátlan erőforrások állnak rendelkezésre párhuzamosan. – adott n feladat megelőzési relációkkal. – minden egyes feladat pj végrehajtási idejét ismertjük.

• Az ütemezés célja: – a projekt befejezési időpontjának (makespan) 10 minimalizálása.

Dr. Kulcsár Gyula


Projektütemezési feladat erőforráskorlátok nélkül • A j feladat: – végrehajtási ideje: ‫݌‬௝ – legkorábbi lehetséges kezdési időpontja:

ᇱ ܵ௝

– legkorábbi lehetséges befejezési időpontja: ‫ܥ‬௝ᇱ – legkésőbbi megengedett befejezési időpontja: ‫ܥ‬௝ᇱᇱ – időtartaléka: slack j = C ''j − p j − S 'j

• Kritikus feladat: nincs tartaléka slack j = 0 • Kritikus útvonal: kritikus feladatok láncolata.11

Dr. Kulcsár Gyula


Kritikus útvonal módszer (Critical Path Method, CPM) • A CPM módszer két algoritmusból áll: – „Forward procedure” – „Backward procedure”

Dr. Kulcsár Gyula


Kritikus útvonal módszer (Critical Path Method, CPM) • Előre haladó eljárás (Forward procedure): – Kezdeti időpontból indul, a precedencia gráfon végighaladva az irányított élek mentén kiszámítja minden feladat esetében a legkorábbi megengedett indítási és befejezési időpontot. – Az utolsónak elkészülő feladat adja meg a projekt befejezési időpontját.

Dr. Kulcsár Gyula


Előre haladó eljárás (Forward procedure) 1. lépés: Legyen t = ts (pl. ts = 0 az indítás referencia időpontja). A megelőző feladattal nem rendelkező minden egyes j feladat esetében legyen Sj’ = t és Cj’ = t + pj. 2. lépés: A megelőző feladattal rendelkező minden egyes j feladat esetében legyen induktív módon: S 'j = max Ck' és Cj’ = Sj’ + pj. all k → j 3. lépés: A legkorábbi projekt-befejezési időpont:

Cmax = max {C1' ,C2' ,...,Cn' }

14

Dr. Kulcsár Gyula


Kritikus útvonal módszer (Critical Path Method, CPM) • Visszafelé haladó eljárás (Backward procedure): – A projekt befejezési időpontjából indul, a precedencia gráfon az irányított élek mentén visszafelé haladva kiszámítja minden feladat esetében a legkésőbbi megengedett befejezési és indítási időpontot tekintettel arra, hogy a projektbefejezési határidő még tartható legyen.

Dr. Kulcsár Gyula


Visszafelé haladó eljárás (Backward procedure) 1. lépés: Legyen t = Cmax A rákövetkező feladattal nem rendelkező minden ܵ௡ᇱᇱ legyen egyes j feladat esetében Cj’’= Cmax és Sj’’ = Cmax - pj. 2. lépés: A rákövetkező feladattal rendelkező minden egyes j feladat esetében legyen C ''j = min S k'' és Sj’’ = Cj’’ - pj. j → all k 3. lépés: Ellenőrizzük, hogy t s = min{ S1'' ,...,S n'' }. 16

Dr. Kulcsár Gyula


Magyarázat • A forward procedure megadja az Sj’ megengedett legkorábbi indítási időpontját minden feladatnak. • A backward procedure megadja az Sj’’ megengedett legkésőbbi indítási időpontját minden feladatnak. • Ha ezek azonosak akkor a feladat kritikus. • Ha ezek különbözőek akkor a feladatnak van tartaléka (slack). • Kritikus útvonal (critical path): kritikus feladatok láncolata, amely a ts kezdési időponttól a Cmax befejezési időpontig vezet. • Kritikus útvonalból egyszerre több is lehet, ezek akár részben fedhetik is egymást.

Dr. Kulcsár Gyula


CPM példa 1 j

1

2

3

4

pj

5

6

9

12 7

2

5

4

6

7

8

12 10 6

9

10 11 12 13 14

10 9

7

8

7

5

7

10 1 6

9

3

12 11

5

8

13

14

Dr. Kulcsár Gyula


Előre haladó eljárás j pj

1 5

2 6

3 9

4 12

5+6=11

5 7

6 12

11+12=23

2

4

7 10

8 6

9 10

10 9

11 7

12 8

13 7

14 5

23+10=33 7 33+9=42

5 1

Cmax = 56

14+12=26

26+10=36 6

5+9=14

10

9

3

12 11

5 14+7=21

8

43+8=51

36+7=43

51+5=56

14

13 43+7=50

26+6=32 Cmax =

A feladatok legkorábbi befejezési időpontjainak számítása

Dr. Kulcsár Gyula


Visszafelé haladó eljárás j pj

1 5

2 6

3 9

4 12

12-6=6 2

5 7

6 12

24-12=12 4

7 10

8 6

9 10

10 9

11 7

12 8

13 7

14 5

34-10=24 7 43-9=34

5-5=0 26-12=14

1

6

10 36-10=26 9

3 14-9=5

5 26-7=19

51-8=43 56-5=51 43-7=36

12

11

13

8 36-6=30

A feladatok legkésőbbi indítási időpontjainak számítása

51-7=44

14

56

Dr. Kulcsár Gyula


Kritikus útvonal

2

4

7

10 1 6

9

3

12 11

5

8

13

14

Dr. Kulcsár Gyula


CPM példa 2 Feladat Műveleti idő Megelőző feladat(ok)

Job p(j) Predecessors 1 2 2 3 3 1 4 4 1,2 5 2 2,3 6 1 4

Projekt indítás (Source)

Projekt befejezés (Sink)

2 1

0

3

4

1

0

S

2

4

6

T

1

2

3

5

Dr. Kulcsár Gyula


CPM példa 2 (folyt.)

Job p(j) Predecessors S' C'' 1 2 0 3 2 3 0 3 3 1 0 6 4 4 1,2 3 7 5 2 2,3 3 8 6 1 4 7 8

Kritikus feladat (Critical job): S’+ p = C’ = C’’ = S’’+ p 2 1

0 Jelölés: p

0

0

3

4

1

0

S

2

4

6

T

0

0 3

j S’

3

C’’ 0

7

3

1

2

3

5 6

3

8

7

8

8 8

Dr. Kulcsár Gyula


Erőforrás korlátozott projektütemezés (RCPS)

• A munkák erőforrást igényelnek: Job p(j) Predecessors S' C'' R(1,j) 1 2 0 3 3 2 3 0 3 1 3 1 0 6 2 4 4 1,2 3 7 2 5 2 2,3 3 8 3 6 1 4 7 8 3

6 5

3

4 2

3

5

2

Erőforrás-igény

1

1

6 4

1

2

3

4

5

6

7

8 24

Dr. Kulcsár Gyula


Erőforrás korlátozott projektütemezés (RCPS) • Tételezzük fel, hogy

R1 = 4

, ekkor:

6 5 4 2

3 2 1

1

5 3

1

2

6

4 3

4

5

6

7

8

9

10

Cmax nő 2 időegységgel!

25

Dr. Kulcsár Gyula


RCPSP Példa

Job p(j) P(j) S' C'' R(1,j) R(2,j) 1 2 - 0 3 3 2 2 3 - 0 3 1 1 3 1 - 0 6 2 1 4 4 1,2 3 7 2 1 5 2 2,3 3 8 3 2 6 1 4 7 8 3 1 4

R1 = 4

2

2 1

0

3

0

4

6

8

2 2

4 4

6

6 8

5

10

3

1

R2 = 2

4

2

2

6

10

12

5 26

12

Dr. Kulcsár Gyula


Köszönöm a figyelmet! Dr. Kulcsár Gyula Miskolci Egyetem Alkalmazott Informatikai Tanszék [email protected] http://ait.iit.uni-miskolc.hu/~kulcsar

Dr. Kulcsár Gyula. Virtuális vállalat félév. Projektütemezés. Virtuális vállalat félév 5. gyakorlat Dr

Recommend Documents