Hálózati grafikonok számítása, elemzése. Az esemény korai időpontja

A hálózati diagram főbb paraméterei

A hálózati diagram fő paraméterei a következők:

kritikus út

Időtartalék az események befejezésére

Időtartalék a munka elvégzésére

Pálya - jobok sorozata, amelyben az egyik job záróeseménye egybeesik egy másik job kezdési eseményével.

Teljes útvonal - egy út, amelynek kezdete a kezdeti esemény, a vége pedig a végső esemény.

Az időtartam, az út hossza egyenlő a munka időtartamainak összegével. Összetevői.

kritikus út - teljes útvonal. a leghosszabb hálózati diagram útvonalak a kezdeti eseménytől (I) a végső eseményig (C).

A kritikus út hossza határozza meg a teljes munkacsoport teljes időtartamát. A kritikus útvonal lehetővé teszi, hogy megtalálja a végső esemény időpontját.

A teljes utak a kritikuson kívülre eshetnek, vagy részben egybeeshetnek vele. Ezeket a rövidebb utakat ún kipihent. Jellemzőik az. Hogy van időtartalékuk. A kritikus út nem. Minden i-edik eseményre meghatározzák:

tpi– korai kezdetű- az esemény bekövetkezésének minimális lehetséges ideje egy adott munkaidőre.

t p i– késői érkezés dátuma- az esemény bekövetkezésének maximális időtartama, amely alatt az esemény bekövetkezésére megállapított határidő betartása mellett az összes következő munka elvégzése még lehetséges.

R i – laza egy rendezvényre- az az időtartam, ameddig az esemény kezdete elhalasztható a tervezett komplexum egészének fejlesztési idejének megsértése nélkül. A különbség a kései ( t p i) és korai ( t p i) az esemény befejezésének időpontja.

Egy esemény tartalékai a kritikus úton egyenlők nullával, mivel azon t p i =t p i

Minden egyes munkához tij) meghatározása:

korai kezdési dátum (t w.d. ij)- a munka megkezdésének minimális lehetséges ideje.

korai befejezési dátum (t p.o. ij)- a munka elvégzésének minimális lehetséges határideje, adott munkaidőre

késői kezdési dátum (t b.s. ij)- a munka megkezdésének megengedett időpontjainak maximuma

késői befejezési dátum (t p.o. ij)- a jelen munka elvégzésére megengedhető határidők maximuma, amelynél a záróesemény bekövetkeztére megállapított határidő betartásával még lehetséges az alábbi munkák elvégzése.

Nyilvánvaló, hogy a tevékenység korai kezdési dátuma egybeesik a kezdeti esemény kezdetének korai dátumával, és a korai befejezési dátum a tevékenység időtartamával meghaladja azt:

t r.n. ij = t p i

t r.o. ij = t p i + t ij

A tevékenység késői befejezési dátuma megegyezik a befejező esemény késői dátumával, és a tevékenység késői kezdési dátuma a tevékenység időtartamával kevesebb:

t p.o. ij = t p j

t a.s. ij = t p j – t ij

Teljes tartalékidő a munka elvégzésére Rnij– az a maximális időtartam, ameddig a munka megkezdését elhalaszthatja vagy növelheti a munkavégzés időtartamát anélkül, hogy a befejezési esemény bekövetkezésének időpontját megváltoztatná.

Szabadidő a munkára, amely a teljes tartalék része - az a maximális időtartam, ameddig elhalaszthatja a munka megkezdését vagy növelheti a munka időtartamát, miközben nem módosítja a későbbi munkák korai kezdési dátumát.

A kritikus úton lévő munkahelyeknek nincs tartaléka, mivel minden tartalék a kritikus és a figyelembe vett utak időtartamának különbsége miatt jön létre.

A munkavégzés időtartalékát jellemző relatív mutató az feszültségi együtthatójuk, amely egyenlő az azonos események közötti útszakaszok időtartamának arányával, ráadásul az egyik szegmens része a maximális időtartamú útnak ezen a munkán áthaladó összes útból, a másik szakasz pedig a kritikus út része.

3.Hálózati modellek számítása

A hálózati diagramok hálózati paramétereit grafikus és táblázatos módszerrel, az összetetteknél pedig matematikai módszerrel számítjuk ki.

Grafikusan a számítási módszert közvetlenül a diagramon hajtják végre, és olyan esetekben használják, amikor az események száma kicsi. Ehhez minden kört 4 szektorra osztanak.

A felső szektor az esemény bekövetkezéséhez szükséges időtartalék R i

bal oldali szektor – az esemény korai időpontja tpi

jobb szektor - az esemény késői időpontja t p i

alsó - eseményszám

Paraméterszámítási módszer

1) Az események korai időpontja . A kezdeti (első vagy nulla) esemény befejezésének korai dátumát nullának kell tekinteni. Az összes többi esemény befejezésének korai dátumát szigorú sorrendben határozzák meg az események növekvő száma. Bármely j esemény korai befejezési dátumának meghatározásához az ebben az eseményben szereplő összes munkát figyelembe kell venni, minden munkánál a végső esemény korai befejezési dátumát a munka kezdeti eseményének korai befejezési dátumának és a e munka időtartama tij , a kapott értékekből kiválasztjuk a j-edik esemény korai befejezésének maximális idejét

t pj = (t pi +t ij) max, és a diagramon kerül rögzítésre (az esemény bal oldali szektora)

2) Események késői időpontjai . A záróesemény befejezésének késői dátuma megegyezik a korai dátummal. Az összes többi esemény befejezésének késői időpontjának kiszámítása fordított sorrendben, csökkenő eseményszámok szerint történik. Az előző i esemény befejezésének késői határidejének meghatározásához minden, az i-edik eseményből származó alkotást figyelembe kell venni. Minden munkához kiszámításra kerül a kezdeti esemény befejezésének késedelmes határideje t p i , mint e munka záróeseményének késői befejezési időpontja közötti különbség t p jés e munka időtartama tij.A kapott értékből válassza ki az i-edik esemény késői befejezésének minimális idejét: t p i = (t p j - t ij)minés a megfelelő szektorban van rögzítve.

3) Kritikus úthossz egyenlő a befejező esemény korai dátumával.

4) Rendezvényidőtartalék . Az események időtartalékának meghatározásakor az esemény jobb oldali szektorába írt számból le kell vonni a bal szektorba írt számot, és a felső szektorba kell tenni.

5) A teljes munkaidő-tartalék meghatározásakor le kell vonni a záróesemény jobb oldali szektorában rögzített számot, az induló esemény bal szektorában rögzített számot és magának a munkavégzés időtartamát.

6) A munkavégzés szabad tartalékának meghatározásakor a befejező esemény bal szektorában rögzített számból le kell vonni a kezdeti esemény bal szektorában rögzített számot és magának a munkavégzés időtartamát.

Kiinduló adatok:

Táblázatos módszer

A táblázatban szereplő munkakódok növekvő indexben vannak írva én.

A 2. és 3. oszlop segédadatokkal van kitöltve: korábbi és későbbi munkák kódjai. Ezekre az adatokra szükség lesz a számításokhoz. Ha a művek kezdők, azaz nincsenek korábbi művek, vagy véglegesek, azaz nincsenek későbbi művek, akkor a megfelelő oszlopokba kötőjelek kerülnek. Egy adott eseményben végződő vagy kezdődő vektorok száma szerint több korábbi és következő munka is lehet./

A 4. oszlop a munka időtartamának értékeit tartalmazza.

Az 5. oszlop kezdi a számított adatokat. A számítás két menetben történik a táblázat sorain keresztül. Az első felülről lefelé halad át a sorokon, amelyekben a legkorábbi munkadátumok számítanak, a második pedig alulról felfelé haladva halad át a sorokon, amelyekben a kései munkadátumok számítanak.

A korábbiakkal nem rendelkező tevékenységek korai kezdete (a 2. oszlopban - egy kötőjel) 0-nak vehető, ha nincs más érték megadva. A munka korai befejezését a képlet szerint határozzuk meg t r.o. ij = t pH ij + t ij és a 6. oszlopba írták be.

A többi rész korai kezdése úgy definiálható, hogy ha például a 2.5-ös munkát vesszük figyelembe, amelynek kezdeti eseménye 2, akkor a korai kezdési ideje megegyezik a 12-es munka korai befejezési idejével, mivel van vége 2. esemény. A 6. oszlop értékét átírja az 5. oszlopba. A 2. oszlopban a korábbi munkák kódjait tüntettük fel. A korai befejezést is a képlet határozza meg t r.o. ij = t pH ij + t ij

Ha a 2. oszlopban az szerepel, hogy egy bizonyos művet egynél több mű előz meg (az 5.6-os művet a 2.5-ös és a 3.5-ös munka előzi meg), akkor több értéklehetőség közül kell kiválasztani a korai kezdés értékét (9 - a munkavégzés végére 2 , 5 vagy 13 - a munka végére 3.5). A kiválasztási szabály megfelel a képletnek t p .n. ij = (t pi + t ij) max , azaz a maximális érték van kiválasztva (a példában - 16). A korai befejezések a fentiek szerint vannak meghatározva.

A 6. oszlop korai végének maximális értéke a kritikus út időtartamának (16) értékének felel meg.

A második lépés a táblázat sorai mentén az utolsó sorban rögzített munkától az első sorban rögzített munkáig lehetővé teszi a késői teljesítménymutatók értékeinek meghatározását. Azoknál a munkáknál, amelyeknek nincs következő munkája (a 3. oszlopban - kötőjel, a 46., 5,6. feladat példájában), a kritikus útvonal értéke a késői befejezés oszlopába (8) kerül beírásra. Ezeknél a munkáknál a késői kezdés értékét a képlet számítja ki t a.s. ij t által ij - t ij

A többi rész kései befejezése úgy definiálható, hogy ha például a 3.5-ös munkát vesszük figyelembe, amelynek végeseménye 5, akkor a kései befejezési ideje megegyezik az 5.6-os munka késői kezdési idejével, mivel annak van vége 5. esemény. A 7. oszlop értékét átírjuk a 8. oszlopba. A későbbi munkák kódjai a 3. oszlopban vannak feltüntetve. A késői kezdést is a képlet határozza meg t a.s. ij t által ij - t ij .

Ha a 3. oszlopban az szerepel, hogy egy bizonyos munkát egynél több munka követ (a 0.1-es feladatot az 1.2-es és az 1.3-as munka követi), akkor több lehetőség közül kell kiválasztani a késői befejezés értékét (3 - szerint a munka kezdési ideje 1 , 3 vagy 7 - az 1, 2 kezdési időpontnak megfelelően, a minimális érték kerül kiválasztásra (a példában - 3). A kései kezdést a fenti képlet szerint határozzuk meg t a.s. ij t által ij - t ij .

A teljes lazaság értékét (9. oszlop) a képlet számítja ki

R nij = t by ij - t pH ij - t ij.

A szabad laza értéket (10. oszlop) a képlet segítségével számítjuk ki

R ij-vel = t ро ij - t рр ij - t ij

A hálózati tevékenységek minden olyan sorozata, amelyben az egyes tevékenységek befejező eseménye egybeesik az azt követő tevékenység kezdő eseményével, ún. keresztül.

Olyan hálózati útvonalat hívunk meg, ahol a kezdőpont megegyezik a kezdő eseménnyel, a végpont pedig a végesemény teljes.

Az eredeti eseménytől a megtett útig megelőzte ez az esemény. Az eseményt megelőző és a leghosszabb utat hívják meg maximum előző. Jelölése L 1 (i), időtartama t.

Az adott eseményt a végsővel összekötő útvonalat hívják későbbiút. Ezt a leghosszabb utat hívják lehetőség szerint későbbés L 2 (i)-vel jelöljük, és időtartama t.

A legnagyobb hosszúságú teljes utat nevezzük kritikai. A kritikus úttól eltérő útvonalakat hívják kipihent. Van időtartalékuk.

A kritikus úton végzett tevékenységek vastag vonalakkal vagy dupla vonalakkal vannak kiemelve. A kritikus út időtartamát tekintjük a gráf fő paraméterének.

Tekintsünk egy algoritmust a kritikus útvonal meghatározására egy hálózati diagramon a dinamikus programozási módszer algoritmusával.

Rendezzük a gráf csúcsait rangok szerint, és számozzuk a végétől az elejéig. Ez lehetővé teszi a rangszámok és a visszafelé mozgás szakaszainak egyeztetését, amikor az utolsó, az utolsó kettő és így tovább feltételesen optimális vezérlőket találunk. szakasz. A kritikus út megtalálását az ábrán látható hálózati diagram példájával elemezzük. 10.7.

A Bellman optimalitás elve szerint az optimális szabályozást minden szakaszban a szabályozási cél és a szakasz kezdeti állapota határozza meg. A rendszer állapota a rangokon elhelyezkedő események. Az X 16 záró esemény befejezéséhez szükséges az előző események befejezése. A rendszer lehetséges állapotai az utolsó munkaszakasz elején - X 14 és X 15 események bekövetkezése. Az X 14 és X 15 pontokban lévő körökben a munkavégzés maximális időtartamát az utolsó szakaszba helyezzük: X 14 5 , X 15 7 . Határozzuk meg a munkavégzés maximális időtartamát az utolsó két szakaszban. A rendszer állapota az utolsó előtti szakasz elején az X 13 eseménynek köszönhető. Az X 13-ból X 16-ba vezető út maximális időtartama .

Ezért a 14-es számot az X 13 esemény közelében lévő körbe kell helyezni, és így tovább. A szakaszokat a végétől az elejéig végrehajtva megtudjuk a kritikus út hosszát t cr =96. Magának a kritikus útnak a megtalálásához menjünk végig a számítási folyamaton az X 1 kezdeti eseménytől a végső X 16-ig. A 96-os számot az első szakaszban (a kezdettől fogva) kaptuk, ha a 80-hoz hozzáadtuk a 16-ot. Ezért a kritikus út ebben a szakaszban egyenlő lesz (X 1, X 3). A 80-as szám = 16 + 64. Ezért a kritikus út a második szakaszban áthalad a munkán (X 3 , X 4) stb. A grafikonon félkövér vonallal van jelölve:

X 1 - X 3 - X 4 - X 7 - X 8 - X 10 - X 11 - X 12 - X 13 - X 15 - X 16 .

A rendezvények befejezésének korai és késői időpontja. Esemény lazaság

Minden olyan útnak, amelynek időtartama eltér a kritikus úttól, van időtartalék. A kritikus út és bármely nem kritikus út hossza közötti különbséget az adott nem kritikus út teljes lazának nevezzük, és a következővel jelöljük: .

korai term egy esemény befejezésének azt a legkorábbi időpontot nevezzük, amikorra az eseményt megelőző összes munka befejeződik, azaz. az eseményt megelőző maximális útvonal időtartama határozza meg, azaz:

vagy

A j esemény korai dátumának megtalálásához ismerni kell az irányított részgráf kritikus útját, amely az adott j eseményt megelőző útvonalak halmazából áll. A kezdeti esemény korai tagja nulla: t p (1)=0.

késői határidő esemény a legkésőbbi időpontnak nevezzük, amely után pontosan annyi idő áll rendelkezésre, amennyi az eseményt követő összes munka elvégzéséhez szükséges. Az esemény befejezésének megengedhető határideje közül a legkésőbb az összes későbbi tevékenység végrehajtásának időtartamával együtt nem haladhatja meg a kritikus út hosszát. Az esemény kései határidejét a kritikus út időtartama és az eseményt követő útvonalak maximumának időtartama közötti különbségként számítják ki:

A kritikus úton lévő események esetében ezeknek az eseményeknek a befejezésének korai és késői dátuma megegyezik.

A rendezvény befejezésének késői és korai időpontja közötti különbség a rendezvény tartalék időpontja: . Az intervallumot eseményszabadság-intervallumnak nevezzük. Az esemény lazasága azt mutatja meg, hogy mennyi ideig lehet egy eseményt a kritikus út megnövelése nélkül visszatolni.

Az összeg óta meghatározza az ezen az eseményen áthaladó maximális hosszúságú út időtartamát, akkor , azaz. bármely esemény lazasága megegyezik az eseményen áthaladó maximális útvonal teljes lazaságával.

Az időparaméterek kézi kiszámításakor kényelmes a négyszektoros módszer alkalmazása. Ezzel a módszerrel az eseményt jelölő hálózati diagram körét négy szektorra osztjuk. Az esemény száma a felső szektorba kerül; bal oldalon - az esemény lehető legkorábbi időpontja (); jobb oldalon - az esemény megengedett időpontja közül a legkésőbbi; alsó szektorban - az esemény tartalék ideje: .

Az események legkorábbi esedékességének kiszámításához: , alkalmazza a képletet , az eseményeket növekvő számsorrendben figyelembe véve, a kezdettől a végsőig, az ebben az eseményben szereplő művek szerint.

Az események befejezésének késői dátumát a képlet számítja ki , a záróeseménytől kezdve, amelyre ( - a záróesemény száma), az abból kikerülő munkák szerint.

A kritikus események nullával lazulnak. Meghatározzák a kritikus tevékenységeket és a kritikus utat.

Példa 10.2. ábrán látható hálózati diagramot. 10.8.

Megoldás. Számolja ki az események befejezésének korai dátumait:

Tehát a végső esemény csak a projekt kezdetétől számított 14. napon következhet be. Ez az a maximális idő, amely alatt minden projekttevékenység befejezhető. A leghosszabb út határozza meg. A munka korai befejezésének időpontja 6 =14 egybeesik a kp kritikus idővel - a kritikus úton fekvő munka teljes időtartamával. Most kiemelheti azokat a tevékenységeket, amelyek a kritikus úthoz tartoznak, visszatérve a végeseménytől az eredetihez. A 6 , eseményben szereplő két munka közül a kritikus út hossza határozta meg az (5, 6) munkákat, mivel (5 + 56)=14. Ezért a munka (5, 6) kritikus, és így tovább. Az (1, 3), (3, 4), (4, 5), (5, 6) munkák határozták meg a kritikus utat: cr = (1-3-4-5-6).

Most kiszámítjuk a rendezvények befejezésének késői dátumait. Hadd . Használjuk a dinamikus programozási módszert. Minden számítást a végső eseménytől a kezdeti eseményig végeznek. A rendezvények befejezésének késői időpontjai:

Mivel az 5. esemény után a projekt befejezéséhez az (5, 6) munkát 3 napig kell elvégezni. A 4-es eseményből két munka jön ki, tehát:

A 2. esemény lazasága: . A fennmaradó események tartalékai nullával egyenlőek, mivel ezek az események kritikusak.

Korai és késői kezdési és befejezési dátumok. Munkaidő tartalékok meghatározása. Teljes munkaidő tartalék.

A munkát közvetlenül megelőző esemény elnevezésre kerül elsődlegesés jelölje, és az azt közvetlenül követő eseményt, - végsőés kijelölni. Ekkor bármely munkát a jelöli. Az események befejezésének időzítésének ismeretében meghatározhatja a munka időbeli paramétereit.

Korai kezdési időpont egyenlő az esemény korai időpontjával: .

A munka korai vége egyenlő a kezdeti esemény befejezésének korai dátumának és a munka időtartamának összegével: vagy .

Késő munkavégzés egybeesik záróeseményének késői befejezési dátumával: .

Késői kezdési időpont egyenlő a végső esemény befejezésének késői időpontja és a munka értéke közötti különbséggel:

Mivel a munka elvégzésének határideje a és által meghatározott határokon belül van, eltérő típusú időtartalékkal rendelkezhetnek.

Teljes munkaidő tartalék - ez a maximális idő, amely a kritikus út túllépése nélkül elvégezhető bármely munka elvégzéséhez. Kiszámítása a késői befejezési esemény és a munka befejezésének korai időpontja közötti különbség: . Azóta .

Ily módon teljes futásidejű tartalék az a maximális idő, ameddig az időtartama a kritikus út időtartamának megváltoztatása nélkül megnövelhető. Minden nem kritikus feladat nullától eltérő teljes lazasággal rendelkezik.

Ingyenes munkaidő tartalék- ez a munkavégzés során rendelkezésre álló időhatár, feltéve, hogy a kezdeti és a végső események a legkorábbi időpontban következnek be: .

A hálózati gráf táblázatos számítása a 4. pontban (1-10) korábban megadott képletek szerint történik. A hálózati modellek paramétereinek analitikus módon történő meghatározásakor a számítás táblázat formájában történik. Tekintsük a hálózati modellek ilyen módon történő számításának jellemzőit (1. alkalmazás) a kurzusmunka feladatában (15. lehetőség) bemutatott hálózati diagram paramétereinek kiszámításának példájával.

A kezdeti szakaszban le kell írni a kezdeti hálózati modellt. Ebben az esetben az összes job és függőség titkosítása a táblázat első oszlopába kerül, az első eseményből kilépő jobtól kezdve. A munkakódokat sorban kell szerepeltetni a táblázatban, a feladatok és függőségek táblázatba való tetszőleges sorrendje nem megengedett. A táblázat második oszlopa az összes munka és függőség időtartamát tartalmazza.

A hálózati ütemezés kiszámítása a munka korai paramétereinek értékeinek meghatározásával kezdődik. Az 1-2 munka korai kezdete nulla (1. képlet), korai vége pedig a 2. képlet szerint.

A 2-6. és 2-7. tevékenységek korai kezdete (a 3. képlet szerint) megegyezik az 1-2. tevékenység korai befejezésével.

A munka korai befejezésének 19-21 maximális értéke, amely 36, meghatározza a kritikus út időtartamát, és ezáltal az összes tevékenység végrehajtásának teljes időtartamát az eredeti hálózati modellben. E munka korai befejezésének eredő értéke 19-21 = 36 átkerül a 20-21. zárómunka késői befejezésének oszlopába.

Késői munkakezdés 20-21 az 5 képlet szerint kerül meghatározásra (= 34)

A késői munkakezdés 20-21 az azt megelőző 15-20 (=) munka késői vége.

Ezenkívül a késői paraméterek kiszámítása hasonlóan történik, kivéve azokat az eseteket, amikor a munkának több egymást követő munkája van (például a 6-9. munkának két egymást követő munkája van - 9-10 és 9-14). Ebben az esetben a 4-es képlet szerint a 6-9 munka kései befejezése megegyezik a későbbi 9-10 és 9-14 munka késői kezdésének minimális értékével.

A kritikus út helyzetének meghatározásához minden munkához meg kell határozni a teljes és privát időtartalék értékeit, valamint a hálózati diagram függőségeit, és be kell írni azok értékeit a számítás 7. és 8. oszlopába. táblázat, ill.

A teljes munkaidő-tartalék a 8-9 képlet szerint a kései és korai befejezés különbségeként, vagy a megfelelő munka késői és korai kezdése közötti különbségként kerül meghatározásra. A teljes lazaság értékét mindkét módon célszerű meghatározni, a kapott értékek egybeesése kiegészítő ellenőrzésnek tekinthető. Például a 6-7. munkához:

A 10. képlet szerint a részleges munkaidő-hiány a következő tevékenység korai megkezdése és az adott tevékenység korai befejezésének értéke közötti különbség. Például a 6-7. munkához:

A kritikus utat nulla lazaság jellemzi. Az ágazati és táblázatos módszerekkel kapott hálózati modell paramétereinek összehasonlítása fel kell, hogy fedje azok teljes azonosságát, az eltérések jelenléte a számítások hibásságát jelzi.

Grafikus módszer a hálózati diagramok kiszámítására

A hálózati gráf grafikus számítása a táblázatos módszerhez hasonlóan történik (1-10. képletek), azonban a hálózati gráf paramétereinek grafikus vagy szektorszámítási módszere azt jelenti, hogy azokat közvetlenül a modellre rögzítjük (2. melléklet). Minden esemény (kör) négy szektorra van osztva. A szektorok megnevezése a következő ábrán látható:

A kritikus útvonali tevékenységeknél a teljes és a részleges lazaság értéke nulla, ez a hálózati diagramon dupla vonallal van kiemelve.

Az elvégzett számítások helyességének ellenőrzéséhez meg kell győződnie a következőkről:

• * folyamatos kritikus utat tárt fel;
• * a számított időtartaléknak nem negatív értéke van;
• * az összes munkára vonatkozó privát lazaság értéke kisebb vagy egyenlő, mint az ezekre a munkákra vonatkozó teljes lazaság értéke;
• * az első eseményből kilépő munkák (munkálatok) késői kezdésének legalább egy értéke nulla.

Kettő ismert módszer a hálózati gráf paraméterek kiszámítására". számítás közvetlenül a hálózati grafikonon; elemző (táblázatos).

Számítás a hálózati modell fő mutatói a következő módon lehet megtenni.

• 1. A korai időpontok számítása:
  • ? korai munkakezdés a kiinduló eseménytől a jelen munka végrehajtásának megkezdéséig tartó leghosszabb út időtartama határozza meg,
  • ? korai befejezési dátumok- ez a munka lehető legkorábbi befejezési időpontja. A munka korai befejezési ideje megegyezik a munka korai kezdési időpontjának és magának a munkának az időtartamának összegével.
• 2.A kritikus út kiszámítása. Ennek időtartama a kritikus úton végzett tevékenységek teljes ideje, azaz. a teljes műegyüttes elkészülési ideje az összes mű legnagyobb párhuzamosításával. Ez az idő megegyezik a hálózati grafikonok korai befejezési idejének legnagyobbjával. A kritikus út olyan eseményeken halad keresztül, amelyeknek nincs időtartalékuk (kritikus tevékenységeken keresztül).
• 3.Késői kezdési és befejezési dátumok számítása a munkavégzési határidők numerikus tengelye mentén a jobbra történő határeltolódás lehetőségeiből határozzák meg úgy, hogy a kritikus út időpontja ne változzon. Ezért logikus az utolsó eseménytől az elsőig számításokat végezni, és először meghatározni a munka késői befejezésének időpontját, majd kiszámítani a munka késői kezdésének időpontját:
  • ?késői kezdési dátum (ij) a munka késői befejezése és a munka időtartama közötti különbség,
  • ? késői teljesítési dátum a végeseménytől hozzá vezető minimális időtartamú út értéke határozza meg, és a kritikus út és a munkavégzés maximális időtartamának különbségeként kerül kiszámításra a hálózat záróeseményétől a munka befejezéséig.
• 4. Az időtartalék számítása".

énteljes futásidejű tartalék a kései kezdés és a korai rajt, vagy a késői cél és a korai cél közötti különbség. Meg kell jegyezni, hogy a teljes munkaidő a kritikus úton egyenlő nullával,

• ? magán (szabad) időtartalékok”.
• 1)az első fajta privát lazaság a kései kezdési időpont megváltoztatásának képessége határozza meg ( ij) korábbi időpontokra a közvetlenül megelőző munkák befejezésének késedelmes határidejének megváltoztatása nélkül,
• 2) a második fajta privát lazaság a munka korai végének megváltoztatásának képessége határozza meg (ij) későbbi időpontokban, anélkül, hogy megváltoztatná a közvetlenül ezt követő munkakezdés korai időpontját; a következő tevékenység korai kezdete és e tevékenység korai vége közötti különbség határozza meg.

Tekintsük a paraméterek kiszámításának eljárását egy példa segítségével. A hálózati diagram az ábrán látható. 7.5.

Rizs. 7.5.

A paraméterek kiszámításához a táblázatos módszert fogjuk használni, és az érzékelés egyszerűsítése érdekében mindent egy táblázatban foglalunk össze. 7.1.

Az időtartalék felhasználásának szabályai a hálózattervezésben.

• 1. Ahhoz, hogy az (y) munka teljes és részleges tartaléka egyenlő legyen, szükséges és elegendő, hogy a kérdéses munka Y záróeseménye a kritikus úton lévő esemény legyen.
• 2. Ha teljes tartalék (én és]1) néhány munkából nulla, akkor a második típusú magántartalék (g "f) is egyenlő nullával. E tartalékok között mindig van egy arány R(IJ) > r"ijy A teljes és privát időtartalék mindig nagyobb vagy egyenlő nullával.
• 3. Ahhoz, hogy a munkaidő (y) részleges tartaléka nullával egyenlő legyen, szükséges és elegendő, hogy ez a munka az első eseménytől az y eseményig tartó maximális hosszúságú úton haladjon.
• 4. Ha a munkavégzés időtartamát (y) p-vel megnöveljük, azaz. p, akkor a következő munka korai kezdési dátuma p értékével nő - g" ("uu
• 5. Ha a munkavégzés időtartamát (y) megnöveljük az ehhez a munkához szükséges teljes időtartalék összegével, akkor egy új kritikus út alakul ki, amelynek időtartama megegyezik a régi időtartamával.
• 6. A teljes munkaidő-tartalék (y) egyenlő a jelen munka második típusa részidőtartalékának és az összes közvetlenül ezt követő munka teljes tartalékának minimumával.

A hálózati diagram paramétereinek kiszámításának eredményei

7.1. táblázat

	Időtartam	Korai	feltételek, h	Késői időpontok, h		Időtartalékok, h
	működik, h	Kezdetek	befejezések	Kezdetek	befejezések	Teljes	Ingyenes
	Kritikus út, h		(működik 1-3

7. Ha a munka időtartamát (r /) megnöveljük p-vel, akkor egy új kritikus út jelenik meg, amelynek időtartama p-vel meghaladja a régi kritikus út időtartamát -

A hálózati grafikon felépítése és főbb mutatóinak kiszámítása után elkezdik optimalizálni.

• 1. Válassza ki a kritikus utat, és keresse meg a hosszát;
• 2. Határozza meg az egyes események időtartalékát;
• 3. Határozza meg az összes munka időtartalékát és az utolsó előtti munka intenzitási tényezőjét

Megoldás

A probléma megoldásához a következő jelölést alkalmazzuk.

Hálózati elem	Paraméter neve	Paraméter szimbólum
Esemény i	A rendezvény korai befejezésének időpontja
A rendezvény késői befejezési dátuma
Esemény lazaság
Munka (i, j)	Munkaidő
Korai kezdési időpont
A munka korai vége
Késői kezdési időpont
Késő munkavégzés
Teljes futásidejű tartalék
	Utazási idő
Kritikus úthossz
Utazási idő tartalék

A hálózat eseményeinek időtartalékának meghatározásához az események befejezésének legkorábbi t p és legkésőbbi t p dátumát számítják ki. Semmilyen esemény nem következhet be addig, amíg az azt megelőző összes esemény be nem fejeződött, és minden korábbi munka nem fejeződött be. Ezért az i-edik esemény korai (vagy várható) tp(i) idejét az eseményt megelőző maximális útvonal időtartama határozza meg:

t p(i) = max(t(L ni)) (1)

ahol L ni bármely, az i-edik eseményt megelőző út, azaz a hálózat kezdeti eseményétől az i-edik eseményig tartó út.

Ha a j eseménynek több korábbi útvonala van, és ezért több korábbi i eseménye is van, akkor célszerű a j esemény befejezésének korai dátumát a következő képlettel megkeresni:

t p (j) = max (2)

Az i esemény befejezésének a korai időponthoz viszonyított késése nem befolyásolja a záróesemény befejezési idejét (és így a munkaegyüttes befejezési idejét) a jelen esemény befejezési idejének összegéig és az azt követő utak maximumának időtartama (hossza) nem haladja meg a kritikus út hosszát. Ezért az i-edik esemény befejezésének t p (i) kései (vagy határ) tagja egyenlő:

t p (i) = t kp - max(t(L ci)) (3)

ahol Lci bármely, az i-edik eseményt követő út, azaz. az i-ediktől a végső hálózati eseményig vezető út.

Ha az i eseménynek több egymást követő útvonala van, és így több egymást követő j esemény is, akkor az i esemény késői befejezési dátuma kényelmesen megkereshető a következő képlettel:

t p(i) = min

Az i-edik esemény R(i) időtartaléka a befejezés késői és korai időpontjai közötti különbségként definiálható:

R(i) = t p (i) - t p (i)

Egy esemény lazasága megmutatja, hogy az esemény mennyi ideig késleltethető anélkül, hogy a munkacsomag időtartamának növekedését okozná.

A kritikus eseményeknek nincs lazasága, mert a kritikus útvonalon lévő esemény befejezésének bármely késése ugyanazt a késleltetést okozza a végső esemény befejezésében. Így, miután meghatároztuk a hálózat végső eseményének korai időtartamát, meghatározzuk a kritikus út hosszát.

A tp(i) események korai időzítésének meghatározásakor balról jobbra haladunk a hálózati gráfon, és az (1), (2) képleteket használjuk.

Az események időzítésének kiszámítása.

Az i=0 (kezdeti esemény) esetén nyilvánvalóan tp(0)=0.

i=1: t p(1) = t p(0) + t(0,1) = 0 + 0 = 0.

i=2: t p(2) = t p(1) + t(1,2) = 0 + 8 = 8.

i=3: t p(3) = t p(1) + t(1,3) = 0 + 3 = 3.

i=4: max(tp(2)+t(2,4);tp(3)+t(3,4)) = max(8+6;3+3)=14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i=6: max(t p(4) + t(4,6);t p(5) + t(5,6)) = max(14 + 5;14 + 3) = 19.

i=7: tp(7)=tp(6)+t(6,7)=19+9=28.

i=8: max(tp(2)+t(2.8);tp(6)+t(6.8);tp(7)+t(7.8)) = max(8+18;19+5; 28+4 ) = 32.

i=9: max(t p(5) + t(5,9);t p(7) + t(7,9)) = max(14 + 2;28 + 4) = 32.

i=10: max(tp(4)+t(4,10);tp(7)+t(7,10);tp(9)+t(9,10)) = max(14+4;28) + 2; 32 + 0) = 32.

i=11: max(tp(8)+t(8,11);tp(10)+t(10,11)) = max(32+12;32+4)=44.

A kritikus út hossza megegyezik a 11. végső esemény korai befejezési dátumával: t kp =tp(11)=44

A t p (i) események befejezésének késői időpontjainak meghatározásakor az ellenkező irányba haladunk a hálózaton, azaz jobbról balra, és (3), (4) képleteket használunk.

i=11 (a végső esemény) esetén az esemény késői dátumának meg kell egyeznie a korai dátumával (ellenkező esetben a kritikus út hossza megváltozik): t p (11)= t p (11)=44

i=10: tp(10)=tp(11)-t(10,11)=44-4=40.

i=9: tp(9)=tp(10)-t(9,10)=40-0=40.

A 8-as számmal kezdődő összes sort átnézi.

i=8: tp(8)=tp(11)-t(8,11)=44-12=32.

Az összes 7-es számmal kezdődő sort átnézi.

i=7: min(tp(8)-t(7,8);tp(9)-t(7,9);tp(10)-t(7,10)) = min(32-4;40-4;40-2) ) = 28.

i=6: min(tp(7)-t(6.7);tp(8)-t(6.8))=min(28-9; 32-5)=19.

Minden 5-ös számmal kezdődő sort átnézünk.

i=5: min(tp(6)-t(5,6);tp(9)-t(5,9)) = min(19-3;40-2) = 16.

i=4: min(tp(5)-t(4,5);tp(6)-t(4,6);tp(10)-t(4,10)) = min(16-0;19-5;40-4) ) = 14.

A 3-as számmal kezdődő összes sort átnézi.

i=3: tp(3)=tp(4)-t(3,4)=14-3=11.

i=2: min(tp(4)-t(2.4);tp(8)-t(2.8))=min(14-6; 32-18)=8.

i=1: min(tp(2)-t(1,2);tp(3)-t(1,3))=min(8-8;11-3)=0.

(0,1): 0 - 0 = 0;

1. táblázat - Rendezvénytartalék számítása

Rendezvényszám	Esemény időpontja: korai tp(i)	Az esemény időpontja: késő tp(i)	Időtartalék, R(i)

2. táblázat kitöltése.

A művek listája és időtartama átkerül a második és harmadik oszlopba. Ebben az esetben a munkát a 2. oszlopban sorban kell rögzíteni: először a 0-tól kezdve, majd az 1-es számtól kezdve stb.

A második oszlopba egy számot teszünk, amely a közvetlenül megelőző művek (KPR) számát jellemzi ahhoz az eseményhez, amelytől a szóban forgó munka kezdődik.

Tehát az (1,2) munkához az 1. oszlopban az 1-es számot írjuk, mert az 1-es szám 1 munkával végződik: (0,1).

A 4. oszlop az 1. táblázatból származik (t p (i)). A 7. oszlop az 1. táblázatból származik (t p (i)).

Az 5. oszlopban szereplő értékeket a 3. és 4. oszlop összegzésével kapjuk.

A 6. oszlopban a késedelmes munkakezdés a munkák késedelmes befejezése és időtartama közötti különbség (a 3. oszlopban szereplő adatokat levonjuk a 7. oszlop értékéből);

A 8. oszlop tartalma (teljes lazaság R(ij)) egyenlő a 6. és 4. vagy a 7. és 5. oszlop különbségével. Ha R(ij) nulla, akkor a munka kritikus

2. táblázat – A hálózati modell időbeli elemzése

Munka (i,j)	Korábbi munkák száma	Időtartam tij	Korai időpontok: kezdete tijR.N.	Korai időpontok: vége tijР.О.	Késői időpontok: kezdete tijP.N.	Késői időpontok: vége tijP.O.	Időtartalék: teljes RijP	Független időtartalék Rij	1. típusú magánrezervátum, Rij1	II. típusú magánrezervátum, RijC

Megjegyzendő, hogy a teljes üzemidő-tartalékon kívül még három tartaléktípus létezik. Az első típusú R 1 magánmunkaidő - a teljes munkaidő egy része, amellyel a munkavégzés időtartama a kezdeti esemény késői időpontjának megváltoztatása nélkül növelhető. R1 a következő képlettel kereshető:

R(i,j)= R p(i,j) - R(i)

A második típusú részleges lazaság, vagy a munka Rc szabad lazasága (i, j) a teljes lazaság része, amellyel a munkavégzés időtartama növelhető anélkül, hogy a befejezési esemény korai időpontja megváltozna. Rc-t a következő képlettel találjuk meg:

R(i,j)= R n (i,j) - R(j)

A szabad futásidejű slack értéke az optimalizáláshoz szükséges lazaság helyét jelzi.

Önálló munkaidő-tartalék Rn (i, j) a teljes tartalék része, amelyet arra az esetre kapunk, ha minden korábbi munka későn ér véget, és minden későbbi munka korán kezdődik. Az Rн a következő képlettel található:

R(i,j)= Rp(i,j) - R(i) - R(j)

kritikus út: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Kritikus útvonal időtartama: 44

Határozzuk meg az utolsó előtti munka munkaintenzitási együtthatóját. Mivel a kritikus út hossza 44, a maximális munkaút (1,10) 32, akkor

K(1,10)=(32-28)/(44-28)=0,296.

4. Egy kisváros internetszolgáltatója 5 dedikált szolgáltatási csatornával rendelkezik. Átlagosan 25 percet vesz igénybe egy ügyfél kiszolgálása. A rendszer óránként átlagosan 6 aczát kap. Ha nincsenek szabad csatornák, visszautasítás következik. Határozza meg a szolgáltatás jellemzőit: a meghibásodás valószínűségét, a szolgáltatás által elfoglalt kommunikációs vonalak átlagos számát, az abszolút és relatív áteresztőképességet, a szolgáltatás valószínűségét. Keresse meg azoknak a dedikált csatornáknak a számát, amelyeknél a rendszer relatív átviteli sebessége legalább 0,95 lesz. Tegyük fel, hogy a kérések és szolgáltatások folyamata a legegyszerűbb

Szolgáltatási áramlás intenzitása:

Terhelési intenzitás:

c \u003d l * t obs \u003d 6 * 25/60 \u003d 2,5

A c=2,5 terhelési intenzitás a szolgáltatási csatorna kérések bemeneti és kimeneti folyamai közötti konzisztencia mértékét mutatja, és meghatározza a sorba állító rendszer stabilitását.

Annak a valószínűsége, hogy a szolgáltatás:

1. csatorna foglalt:

p 1 = 1/1-gyel! p 0 = 2,5 1/1! * 0,0857 = 0,214

2 csatorna foglalt:

p 2 \u003d c 2/2! p 0 = 2,5 2 /2! * 0,0857 = 0,268

3 csatorna foglalt:

p 3 \u003d c 3/3! p 0 = 2,5 3 /3! * 0,0857 = 0,223

4 csatorna foglalt:

p 4 = 4/4-el! p 0 = 2,5 4 /4! * 0,0857 = 0,139

5 csatorna foglalt:

p 5 = 5/5-tel! p 0 = 2,5 5 /5! * 0,0857 = 0,0697

A meghibásodás valószínűsége töredék elutasított pályázatok:

Ez azt jelenti, hogy a beérkezett kérelmek 7%-át nem fogadják el.

A bejövő kérések kiszolgálásának valószínűsége- az ügyfél kiszolgálásának valószínűsége:

A meghibásodott rendszerekben a meghibásodási és karbantartási események az események teljes csoportját alkotják, így:

p nyitott + p obs = 1

Relatív áteresztőképesség Q = p obs .

p obs \u003d 1 - p otk \u003d 1 - 0,0697 \u003d 0,93

Ennek megfelelően a beérkezett kérelmek 93%-át kézbesítik. A szolgáltatás által elfoglalt csatornák átlagos száma

n s \u003d s * p obs \u003d 2,5 * 0,93 \u003d 2,326 csatorna.

Átlagos üresjárati csatornák.

n pr \u003d n - n z \u003d 5 - 2,326 \u003d 2,7 csatorna.

A szolgáltatási csatorna kihasználtsága.

Ezért a rendszer 50%-ban karbantartással van lefoglalva.

Abszolút sávszélesség

A \u003d pobs * l \u003d 0,93 * 6 \u003d 5,581 alkalmazás / óra.

A QS átlagos üresjárati ideje.

t pr \u003d p otk * t obs \u003d 0,0697 * 0,417 \u003d 0,029 óra.

A kiszolgált kérések átlagos száma.

L obs \u003d s * Q \u003d 2,5 * 0,93 \u003d 2,326 egység.

Egy kérelem átlagos tartózkodási ideje a KPSZ-ben(Little képlete).

Egy órán belül elutasított kérelmek száma: l * p 1 = 0,418 kérés óránként.

Névleges QS teljesítmény: 5 / 0,417 = 12 002 alkalmazás óránként.

A KGST tényleges teljesítménye: 5.581 / 12.002 = a névleges teljesítmény 47%-a.

Határozzuk meg a rendszer működőképességének biztosításához szükséges csatornák számát P valószínűséggel? 0,95

Ehhez a feltételből n-t találunk:

Határozzuk meg annak valószínűségét, hogy ha 6 csatorna van a rendszerben és mindegyik foglalt: