4.3. 4.3. Algortimus az időtervezési feladatra

A számításokat a tervütemháló táblázatán szokás elvégezni. Ezt a táblázatot kiegészítjük egy oszloppal, ide fogjuk számítani az események legkorábbi idejét, továbbá kiegészítjük egy sorral, ahová az események legkésőbbi idejét fogjuk számolni. Ha az események sorszámozása olyan, hogy nagyobb sorszámú pontba vezet az él, akkor ez a táblázat ún. felső háromszög-táblázat lesz. A számolás a tétel bizonyításában adott összefüggések alapján történik.

  1. Az legkorábbi eseményidők számolása:

    Kiindulásként . Ezután a pontok sorrendjében számítjuk az értékeket.

    Az x pont értékét úgy határozzuk meg, hogy az értékek oszlopában (utolsó oszlop) és az x pont oszlopában levő számokat összeadjuk minden sorban és ezen összegek közül a maximumot vesszük.

  2. Az legkésőbbi eseményidők számolása:

    Kiindulásként . Ezután a pontok sorrendjében visszafelé haladva számítjuk az értékeket. Az x pont értékét úgy határozzuk meg, hogy az értékek sorában (utolsó sor) lévő elemből kivonjuk az x pont sorában levő elemet minden oszlopban és ezen különbségek közül a minimumot vesszük.

Megjegyzés :

Az időtervezési feladat megoldási módszerét kritikus út módszernek is szokás nevezni, ebből származik az időtervezési feladat CPM/time elnevezés is (Critical Path Method). Az időtervezési modelleket az 1950-es évek első felében dolgozták ki a RAND Corporation-nál. Ezeket a módszereket azonban titkosan kezelték, kezdetben nem hozták nyilvánoságra, FORD L.R. Jr. [ 4 ] és MINTY G.J. [ 11 ] munkáiban lettek nyivánosságra hozva.