4. fejezet - Időtervezési feladat (CPM/time)

4.1. 4.1. A feladat megfogalmazása

A termelési folyamat vagy egy gépsor leállítása, szétszedése, javítása, összeszerelése stb. egymás után és egymással párhuzamosan végezhető tevékenységekből áll. A tevékenységek logikai kapcsolatát egy digráffal lehet szemléltetni. A digráf élei a tevékenységeket, a csúcspontok pedig az eseményeket jelölik. Ezek az események bizonyos tevékenységek befejezését ill. belépő tevékenységek kezdését jelölik.

Például tekintsük egy csarnoképület szerelésének tevékenységlistáját és tevékenységidejét:

A következő ábra a tevékenységek kapcsolatának digráffal történő ábrázolását mutatja:

A szaggatott vonallal jelölt tevékenységet azért kellett beiktatni, hogy a helykitűzés (A) megelőzze az elemek helyszínre szállítását (E). Az ilyen tevékenységet, amely csupán a végrehajtás sorrendjét hivatott jelezni, látszattevékenységnek nevezzük és tevékenységidejét zérusnak vesszük. Mint a példából is kitűnik, egy munkafolyamat logikai ábrázolásaként egy speciális digráfot ún. tervütemhálót kapunk. A tervütemháló olyan digráf, amelynek

  1. létezik kezdőpontja és végpontja úgy, hogy bármely esetén vezet út s-ből x-be és x-ből t-be,

  2. körútmentes, azaz nincs önmagába visszatérő út.

Az eseményeket (csomópontokat) , amelyek a tevékenységeket fűzik össze, sorszámmal szoktuk ellátni és így a tevékenységeket a kezdő eseménye és a befejező eseménye sorszámával jelöljük: (x,y), a tevékenységidőt pedig egész szám jelöli. Mivel a tervütemháló speciális digráf, így az események sorszámozását mindig el lehet úgy végezni, hogy minden tevékenységre igaz legyen, hogy a kezdő eseményének sorszáma kisebb, mint a befejező eseményének sorszáma. A példa is ezt a sorszámozást követi és ezt a tárgyalásunkban is mindig feltesszük.

Nyilvánvaló, hogy egy ilyen munkafolyamat megtervezésénél egyik felmerülő kérdésünk, hogy mennyi az átfutási idő. Ezt a leghosszabb út hossza adja. Másik kérdésként felmerül az a probléma, hogyan kell ütemezni az egyes tevékenységek elvégzését. E szempontból fontos mozzanat az események bekövetkezése, mert ez a feltétele annak, hogy az eseményből kiinduló tevékenységek elkezdődhessenek. Ebből a szempontból tehát az események bekövetkezése a fontos, amelyet az eseményidővel jellemzünk. Ezekután fogalmazzuk meg a feladatokat matematikai formában.

Primál feladat:

Meghatározandó az tervütemhálóban az s-ből a t-be vezető

utak közül az, amelynél a

érték maximális.

Ezt a maximális utat kritikus útnak, a hozzátartozó maximális célfüggvényértéket átfutási időnek nevezzük.

Duál feladat:

Meghatározandó minden ponthoz egy eseményidő, amelyre az

feltételek fennállnak és az

érték minimális.

Az eseményidők együttesét ütemezésnek vagy időpolitikának nevezzük. Az értéket az ütemezés értékének nevezzük.