Workflow és Petri hálók
Algoritmusok tervezése és elemezése MSc
Brájer Gábor 2015
Workflow Tekintsünk egy megoldandó feladatot. A feladat komplexitását tekintve lehet egyszerű vagy nagyon bonyolult, de fel lehet bontani jól definiálható részfeladatokra. A feladatok végrehajtása valamilyen cél elérése érdekében történik. A workflow (munkafolyamat) adott feladatok – ezek rendszerint mintaszerű, ismételten előforduló feladatok – logikus szervezése, irányítása. Matematikailag tekintsük a workflow-ot egy G összefüggő, irányított gráfnak, ahol G pontjai lehetnek feladatok, állapotok vagy események (az előbb leírt jól definiált részfeladat); élei pedig ezeket a pontokat kötik össze. Az élekhez rendelhetünk feltételeket. G gráf tartalmazhat köröket. G gráf pontjainak típusai: •
Belépési pont: Legalább egy ilyennek kell lennie a gráfban. Kiváltója valamilyen külső esemény (trigger).
•
Kilépési pont (végállapot): Befoka legalább egy, kifoka nulla. Ezek a pontok reprezentálják a kitűzött célt. A belépési pont(ok)hoz hasonlóan lehet több, de nem jellemző.
•
Belső pont: A gráf egyéb pontjai. Ki- és befoka legalább egy.
A workflow jelöli ki, hogy milyen módon járhatjuk be a gráfot adott feladat elvégzéséhez. Iránymutatást ad arra, hogy adott pontból milyen más pontokba juthatunk el (esetlegesen adott feltételek mellett). A workflow a valódi munkamenet absztrakciója. Egy- vagy több előforrás (például személy) hajtja végre az adott feladatot. Nevezzük flowoknak a gráf olyan részgráfjait, amik legalább egy pontot és legalább egy élt tartalmaznak. Workflow tervezése során 4 fajta útvonaltervezési módszert használhatunk: •
Szekvenciális végrehajtás: A pontok végrehajtása egymás után történik, az ábrán A után B és végül C.
•
Párhuzamos végrehajtás: Több folyamat paralell végrehajtása egymástól függetlenül. Vizsgáljuk meg külön az
elválási- és a találkozási pontokat az ábra szerint: ◦ AND split: B és C végrehajtódhat, ha A végrehajtódott. ◦ AND join: Szinkronizálja a párhuzamos szálakat. D végrehajtódhat, ha B és C is befejeződött.
•
Elágazás: Elágazás, egy pont kifoka nagyobb, mint egy. Ekkor a kivezető élekhez szabályokat rendelünk, amikkel próbáljuk lefedni a teljes eseményteret. Leggyakoribb példa erre, ha a pontban egy kérdés áll, a kivezető élek szabályai pedig az igen és nem. A mellékelt ábrán A után vagy csak B, vagy csak C hajtódik végre, amiből eljutunk D-be. Az előző módszerhez hasonlóan két részre oszthatjuk: ◦ OR-split: A után kiértékeljük, hogy merre kell mennünk; vagy csak B-be, vagy csak C-be. ◦ OR-join: D végrehajtása akkor kezdődhet, ha B vagy C végrehajtódott.
•
Iteráció: Ha egy részfeladatot többször végre kell hajtanunk, akkor iterációt használunk. Leggyakoribb esete ennek ,ha valamilyen hibába ütköztünk és visszább kell lépni a folyamatban.
Workflow előnyei: •
Könnyen algoritmizálható: Használhatjuk a gráfalgoritmusokat, a 4 útvonaltervezési módszer könnyen kezelhető programozástechnikai szempontból. Például egy termék gyártási folyamatát DAG-á alakítjuk (ha lehetséges).
•
Áttekinthetőség: Grafikusan ábrázolva az ember által is könnyen megérthető. Megtehetjük azt is, hogy a workflow egyes részeit "elfedve" csak bizonyos flowokat teszünk publikussá adott erőforrásoknak. Például egy külső rendszer elég, ha egy részét látja a workflownak. Analizálás és monitorozás: Nyomon követhetjük az egyes flow-ok terhelését, a pontok végrehajtási idejét, elágazás esetén azt, hogy melyik ágba milyen arányban mentünk be, stb. Nagyon hasznos, ezt a workflow rendszerek biztosítják nekünk, ezekről később lesz szó.
•
Automatizálás: A flow-ok tervezése során törekszünk a minél nagyobb fokú automatizálásra, a kézi (emberi) bevatkozás szükségességének minimalizálásával.
•
Optimalizálás: Az analizálás és monitorozás eredményeképp létrejövő adatok alapján a flow-ok javítása. A flow-ok javítása automatikusan történhet, ha ezzel más flow hatékonyságát nem rontjuk.
Workflow rendszerek és üzleti folyamatok A workflow egyik legfelkapottabb felhasználási területe az üzleti folyamatok modellezése. A vállalkozások workflow rendszereket (workflow management system, röviden WFMS) használnak a feladataik tervezésére, irányítására, monitorozására és automatizálására. A workflow célja az, hogy adott erőforrásokból (emberi munkaerő, gépi számítási kapacitás, információ, ...) valamilyen folyamattal - amit a workflow gráf ír le – egy végterméket állítsunk elő. Ez sokféle lehet, például valamilyen szolgáltatás nyújtása, fizikai termék, információ, stb. Az előző részben már volt szó a workflow-ok előnyeiről, ezeket mind élvezheti az a cég, amelyik workflow alapú megközelítést használ. Az üzleti életben számtalan komplex folyamat van jelen, legyen szó gyártási folyamatról, adminisztrációról vagy a cégen belüli információáramlásról. Fel kell térképezni az ilyen ismétlődően előforduló, a működéshez elengedhetetlen folyamatokat, ami már önmagában is egy nagy projekt lehet. Az üzleti folyamatok menedzselésével, optimalizálásával a Business
Process Management (BPI) foglalkozik, ennek a része a workflow alapú tervezés és automatizálás. A BPM célja, hogy minimalizálja az emberi hiba lehetőségét és a kommunikációs félreértéseket a résztvevők feladataira koncentrálva. A workflow rendszer egy szoftver, elvárjuk tőle, hogy adaptív legyen, azaz könnyen tudjon alkalmazkodni a folyamatosan változó igényekhez és magas szinten integrálható legyen. Lehetséges a workflow alapú tervezés workflow rendszer nélkül, azonban ez nem jellemző. Minden üzleti folyamatot érdemes workflow folyamatként ábrázolni? Nem. A következőképpen karakterizálhatjuk a workflow folyamatokat: i., eset-vezéreltek (case driven) ii., alapvető fontosságú iii., explicit definiálható. Nem ajánlatos továbbá workflow-t használni ideiglenes, rövidtávú feladatokra vagy extrém teljesitménycentrikus folyamatoknál. Tekintsük át a workflow rendszerek működését egy vállalaton belül. Adott a workflow rendszer magja (workflow engine), ami egy szolgáltatásba (service) van beágyazva. Érdemes megjegyezni, hogy egy szolgáltatásba több workflow motor is beágyazható, így több részre oszható a workflow menedzselése. Ehhez kapcsolódnak interfészen keresztül a különböző komponensek. Ezek lehetnek folyamatleíró eszközök, adminisztratív és monitorozó eszközök, más workflow rendszerek, meghívott külső alkalmazások vagy workflow kliens alkalamzások. A legtöbb workflow rendszer a következő folyamatleíró eszközöket támogatja: 1. workflow-ok grafikus felületen történő definiálása 2. erőforrás osztályok megadása (szervezeti modell) 3. szimulációs eszköz a workflow analizálásához A végfelhasználó a workflow kliens alkalmazás segítségével kommunikál a workflow rendszerrel. Az adminisztratív és monitorozó eszközök segítségével figyelhetjük a workflow-t, ezekkel rögzíthetjük a változásokat, az esetek előrehaladását és kiszűrhetjük a szűk keresztmetszeteket (bottleneck). Lehetőség van külső workflow rendszerrel való kommunikációra is, ez azonban nem kiforrott technológia, hiányoznak a legfektetett sztenderdek. Később lesz szó a Petri hálókról, amik jó alapot szolgáltatnának egy ilyen sztenderd workflow framework-höz.
A szélesebb körben elterjedt üzleti workflow rendszerek: •
IBM BPM
•
jBPM
•
Microsoft WWF
•
SAP Business Workflow
Gyakorlati példa – webáruház rendelési folyamata Valós workflow alapján egy egyszerűsített példája az internetes rendelési folyamatnak egy ismert hazai webáruháznak. Az alapok nagyjából minden webáruház esetén hasonlóak: az ügyfél megrendelést ad fel adott termékekre, a webáruház beszerzi a termékeket. Legyen a kiínduló folyamat az, hogy rendelést lehet feladni a webáruházban feltüntetett – nem feltétlenül raktáron lévő - termékekre, fizetési módként a készpénz választható , a rendelés feladása után véglegesítés szükséges (email-ben vagy telefonon) a megrendelő részéről. A megrendelés feladása után a megrendelést nem lehet módosítani.
A fenti ábrán látszik, hogy egy belépési pontja van a folyamatnak és két végállapota: a megrendelés sikeres (csomagolható, átadható szállításra) vagy pedig törlésre kerül. Van egy külső trigger esemény is, ami a megrendelő kérésére – azonosítás után – töröl egy megrendelést. Egészítsük ki ezt a workflow-ot az online bankkártyás fizetés és az előre utalás lehetőségével. Az előbbi esetben a rendelés feladása után a megrendelőt elirányítjuk egy szerződött bank oldalára, ahol biztonságosan fizethet. Az ilyen fizetési módoknál nem kell explicit véglegesíteni a megrendelést, a pénz beérkezése automatikusan véglegesítést eredményez. Adjunk lehetőséget továbbá a megrendelés módosítására a véglegesítés előtt. A könyebb áttekinthetőség érdekében vezessünk be színezést: a sárga jelenti a megrendelő interakcióját, a zöld pedig a webáruházat üzemeltetők feladatait.
Ez a workflow is részben hiányos még, azonban ad egy ötletet arra vonatkozóan, hogy hogyan építsünk fel egy ilyen gráfot. További rendelési státuszok bevezetésével, külső rendszerek felé beküldött rendelésekkel tovább bonyolódik a gráf. Pedig ez egy viszonylag egyszerű üzleti
folyamat. Tegyük fel, hogy elemeztük a workflow-ban való eddigi eseteket és azt tapasztaljuk, hogy a rendelések kevesebb, mint 5%-a kerül törlésre végül. Ekkor elgondolkodhatunk azon, hogy a rendelés rögzítésével párhuzamosan berendeljük a rendelésben szereplő készleten nem lévő termékeket, legroszabb esetben törlik a rendelést, a termék pedig ott lesz raktáron. Ezzel időt és pénzt spórolhatunk meg, hiszen az ügyfél hamarabb kapja kézhez a termék(ek)et. Viszonylag adaptív módon sikerült megalkotni az első modellt, a második modellben szinte érintetlenül maradtak az előző változat pontjai.
Petri hálók A Petri hálók irányított, páros gráfok, ahol a pontok állapotok (places) vagy átmenetek (trasition) lehetnek. A pontok élekkel vannak összekötve, a pont típusok felváltva követik egymást az élek mentén. A állapotokat körökkel, az átmeneteket téglalappal reprezentáljuk. Formálisan a Petri-háló egy (P, T, F) hármas, ahol •
P: helyek véges halmaza
•
T: átmenetek véges halmaza (P ∩ T = ∅)
•
F ⊆( P × T ) ∪( T × P ) az élek halmaza (flow reláció)
A Petri hálókban minden él súlya 1, másnak nem is lenne értelme, hiszen a helyek megfelelnek a feltételeknek. Az állapot meghatározásához tokeneket használunk. Ezeket kis fekete pontokkal jelöljük a helyekben. Tekintsük egy részbenrendezését a pontoknak (az állapotok összehasonlításához). Ekkor például azt az állapotot, hogy az első pontban egy token van, a második pontban két token van, a harmadik pontban szintén egy token van és a negyedik pontban nincs token a következőképp írjuk le: p1 + 2p2 + p3 + 0p4. A nullás tagokat el is hagyhatjuk a felsorolásból. A tokenek száma változhat a háló végrehajtása során. Az átmenetek képezik a háló aktív részét és a következő szabályokkal változtatják az állapotát: 1. Egy t átmenet engedélyezett, ha minden p input helye t-nek legalább egy token-t tartalmaz 2. Egy engedélyezett átmenet végrehajtható. Ha t átmenet végrehajtódik, akkor minden p
input helyén t-nek elhasznál egy tokent és minden p output helyén t-nek létrehoz egy tokent A Petri hálókban ugyan azok a konstrukciók léteznek, mint a workflow-ok esetén: szekvenciális végrehajtás, párhuzamos végrehajtás, elágazás és iteráció. A Petri hálókat könnyen átírhatjuk workflow gráfra a megfelelő átalakítások használatával: a helyekből feladatok, az átmenetek pedig feltételek lesznek, a műveletek szinte analóg módon átvihetők.
Felhasznált irodalom és források [1] W.M.P. van der Aalst - The Application of Petri Nets [2] http://en.wikipedia.org/wiki/Workflow [3] http://www.workflowrendszer.hu/ [4] http://en.wikipedia.org/wiki/Business_process_management
