12.1. Idő, ütemezés és erőforrások
A STRIPS reprezentáció azt írja le, hogy mit csinálnak a cselekvések, de mivel a reprezentáció a szituációkalkuluson alapul, nem tartalmazza, hogy milyen hosszú egy cselekvés, sem azt, hogy mikor következik be, kivéve azt, hogy egy másik cselekvés előtt vagy után jön. Néhány feladatkörben azt szeretnénk tudni, hogy a cselekvések mikor kezdődnek és végződnek. A teherszállítási problémakörben például, azt szeretnénk tudni, hogy egy adott csomagot hordozó repülőgép mikor érkezik, nem csak azt, hogy megérkezik, amikor a repülésnek vége.
Az alkalmazások egy általános családjának, az ütemezési feladatok (job shop scheduling) családjának a lényege az idő. Az ilyen feladatok munkák elvégzését igénylik, melyek mindegyike cselekvések sorozatából áll, ahol minden cselekvés adott időtartamú és bizonyos erőforrásokat igényelhet. A probléma, hogy egy olyan ütemezést határozzunk meg, ami – az erőforráskorlátok figyelembevétele mellett – minimalizálja az összes feladat elvégzéséhez szükséges összidőt.
A 12.1. ábrán egy ütemezési feladatra láthatunk példát. Ez egy nagyon leegyszerűsített autó-összeszerelési feladat. Két munkánk van, a C1 és a C2 autó összeszerelése. Minden munka három cselekvésből áll: a motor beszerelése, a kerekek felszerelése, valamint az eredmény végső ellenőrzése. Először a motort kell berakni (mivel az első kerekek beszerelése megakadályozná, hogy hozzáférjünk a motortérhez), a vizsgálatot pedig értelemszerűen utoljára kell végrehajtani.
12.1. ábra - A két autó összeszerelését tartalmazó ütemezési feladat. A jelölésben az Időtartam(d) jelentése, hogy egy cselekvés d percet vesz igénybe. A Motor(E1, C1, 60) jelentése az, hogy az E1 egy motor, ami a C1 alvázba illeszthető és 60 perc alatt szerelhető be.
A 12.1. ábrán látható probléma bármely eddig látott tervkészítővel megoldható. A 12.2. ábra (ha a számokkal nem törődünk) a részben rendezett tervkészítő megoldását mutatja. Hogy az inkább egy ütemezési, mintsem egy tervkészítési feladat legyen, minden cselekvéshez meg kell határoznunk, hogy mikor kezdődjön és mikor végződjön. Ez azt jelenti, hogy figyelnünk kell minden cselekvés hosszára, csakúgy, mint a sorrendjére. Az Időtartam(d) jelölés egy cselekvés kapcsán (ahol d csak egy számmal helyettesíthető be) azt jelenti, hogy egy cselekvés elvégzéséhez d percre van szükség.
Ha adott a cselekvések egy részleges rendezése az időtartamokkal, ahogy a 12.2. ábra is mutatja, akkor a kritikus útvonal módszer (critical path method – CPM) felhasználható az egyes cselekvések lehetséges kezdési és befejezési időpontjainak meghatározására. Egy részben rendezett tervben található útvonal, cselekvések egy lineárisan rendezett sorozata, ami az Indít-ból indul és a Befejez-ben fejeződik be (például a 12.2. ábra részben rendezett tervében két út található).
A kritikus útvonal (critical path) az az út, amelynek a teljes ideje a leghosszabb; az útvonal „kritikus”, mert meghatározza a teljes terv hosszát. Más utak rövidítése nem rövidíti a terv egészét, de a kritikus útvonalon lévő bármely cselekvés kezdetének elhalasztása a teljes tervet lassítja. Az ábrán a kritikus útvonal vonalát vastag vonallal jelöljük. Hogy a teljes tervet minimális idő alatt hajtsuk végre, a kritikus útvonal cselekvéseit úgy kell végrehajtani, hogy köztük ne legyen késleltetés. A kritikus útvonalon kívül eső cselekvéseknek van valamennyi mozgásterük — egy időablak, amelyben végrehajthatók. Ezt az időablakot a kezdeti időpont lehető legkorábbi (ES) és a lehető legkésőbbi (LS) értékével definiáljuk. Az LS – ES mérőszámot, a cselekvés mozgásterének (slack) nevezzük. A 12.2. ábrán láthatjuk, hogy a teljes terv 85 percet vesz igénybe, a kritikus útvonal minden cselekvésének a mozgástere 0 (ez mindig igaz), és a C1 összeszerelésének minden cselekvése egy 15 perces ablakban indítható. A cselekvések ES és LS idői a probléma ütemtervét (schedule) adják.
12.2. ábra - A 12.1. ábrán szereplő ütemezési probléma megoldása. Az ábra tetején a részben rendezett terv megoldása látható. Minden cselekvés hozza a téglalap alján látható, a legkorábbi és a legkésőbbi kezdési időkkel [ES, LS] a bal felső sarokban. A két szám között különbség a cselekvés mozgástere, a 0 mozgásterű cselekvések a kritikus útvonalon vannak, melyeket vastag vonallal jelölünk. Az ábra alján ugyanezen megoldás időrendjét láthatjuk. A szürke téglalapok azt az intervallumot jelölik, ami alatt a cselekvés végrehajtható, feltételezve, hogy a sorrendezési megkötéseket betartjuk. A szürke téglalapok nem felhasznált, nem kitöltött területei a mozgásteret jelölik.
![A 12.1. ábrán szereplő ütemezési probléma megoldása. Az ábra tetején a részben rendezett terv megoldása látható. Minden cselekvés hozza a téglalap alján látható, a legkorábbi és a legkésőbbi kezdési időkkel [ES, LS] a bal felső sarokban. A két szám között különbség a cselekvés mozgástere, a 0 mozgásterű cselekvések a kritikus útvonalon vannak, melyeket vastag vonallal jelölünk. Az ábra alján ugyanezen megoldás időrendjét láthatjuk. A szürke téglalapok azt az intervallumot jelölik, ami alatt a cselekvés végrehajtható, feltételezve, hogy a sorrendezési megkötéseket betartjuk. A szürke téglalapok nem felhasznált, nem kitöltött területei a mozgásteret jelölik.](/mi_almanach/sites/default/files/books/35/files/kepek/12-02.png)
A következő kifejezések az ES és LS definícióiként szolgálnak, és egyúttal a kiszámításukra szolgáló dinamikus programozási algoritmust is körvonalazzák:
ES(Indít) = 0
ES(B) = maxA ≺ B ES(A) + Időtartam(A)
LS(Befejez) = ES(Befejez)
LS(A) = minA ≺ B LS(B) – Időtartam(A)
Az ötlet az, hogy az ES(Indít) értékének 0-ra állításával indítunk. Ezután, amint elérünk egy olyan B cselekvést, hogy minden cselekvés, ami közvetlenül B előtt jön, már rendelkezik ES értékekkel, az ES(B) értéket a közvetlenül megelőző cselekvések közül a legkorábbi befejezési idő maximumára állítjuk be, ahol a legkorábbi befejezési időt úgy definiáljuk, mint a cselekvés kezdési időpontja plusz a cselekvés időtartama. A folyamat addig folytatódik, amíg minden cselekvéshez egy ES értéket rendelünk. Az LS értékeket hasonlóképpen számítjuk ki a Befejez cselekvéstől visszafelé haladva. A részleteket egy későbbi feladat tartalmazza.
A kritikus útvonal algoritmus komplexitása csak O(Nb), ahol N a cselekvések száma és b az egy cselekvésbe be-, illetve kimenő maximális elágazások száma. (Ennek megértéséhez vegyük észre, hogy az LS és ES számításokat minden cselekvésre csak egyszer hajtjuk végre, és minden számítás legfeljebb b másik cselekvésen megy végig.) Ezért, ha adott a cselekvések egy részben rendezése, a minimális időtartamú ütemezés megtalálása elég könnyedén elvégezhető.
A valós ütemezési problémákat az erőforrásokra (resources) vonatkozó korlátozások jelenléte megbonyolítja. Például egy motornak az autóba szereléséhez egy motoremelőre van szükség. Ha csak egyetlen emelőnk van, akkor nem tudjuk egyszerre beszerelni az E1 motort, a C1 és az E2 motort a C2 autóba, így a 12.2. ábrán bemutatott ütemezés végrehajthatatlan. A motoremelő példa egy újrahasznosítható erőforrásra (reusable resource). Az erőforrás foglalt, amíg a cselekvés tart, de újra használhatóvá válik annak befejezése után. Vegyük észre, hogy az újrahasznosítható erőforrásokat nem tudjuk a hagyományos előfeltétel és következmény alakú cselekvésleírásokkal kezelni, mert a rendelkezésre álló erőforrás-mennyiség nem változik, miután egy cselekvést lezártunk.[118] Ezért kiterjesztjük a leírásunkat, hogy egy ERŐFORRÁS: R(k)-t is tartalmazzon, amelynek jelentése, hogy k egység R típusú erőforrásra van szükség a cselekvéshez. Az erőforrás-szükséglet mind előfeltétel (a cselekvés nem hajtható végre, ha az erőforrás nem érhető el), mind pedig átmeneti következmény, abban az értelemben, hogy az R erőforrás rendelkezésre állása k-val csökken a cselekvés időtartama alatt. A 12.3. ábra mutatja, hogyan lehet a motorbeszerelés problémáját kiterjeszteni, hogy az három erőforrást is tartalmazzon: egy motoremelőt a motorok beszereléséhez, egy kerékállomást a kerekek felszereléséhez és két vizsgálóbiztost. A 12.4. ábra a legrövidebb szerelési idejű megoldást mutatja, ez 115 percet igényel. Ez hosszabb, mint az erőforrás-megkötések nélküli 85 perces ütemezés. Vegyük észre, hogy nincs olyan időpillanat, amikor mindkét vizsgálóbiztosra szükség van, ezért az egyik vizsgálóbiztost azonnal egy termelékenyebb posztra helyezhetjük.
Az erőforrások numerikus mennyiségekként történő leírása mint a Vizsgálóbiztosok(2), a megnevezett entitások használata helyett, mint a Vizsgálóbiztos(I1) és a Vizsgálóbiztos(I2), jó példa a nagyon általánosan használt aggregációs (aggregation) technikára. Az aggregáció központi ötlete, hogy egyedi objektumokat csoportosítsunk mennyiségekké, amikor maguk az objektumok nem megkülönböztethetők a cél szempontjából. Az összeszerelési problémánkban nem számít, hogy melyik vizsgálóbiztos vizsgálja az autót, ezért nincs szükség különbségtételre. (Ugyanez az ötlet működik a 3.9. feladat misszionáriusok és kannibálok problémájára.) Az aggregáció a komplexitás csökkentéséhez elengedhetetlen. Vizsgáljuk meg, mi történik, ha egy ütemezés 10 konkurrens Vizsgálat cselekvést tartalmaz, de csak 9 vizsgálóbiztos áll rendelkezésre. Ha a vizsgálóbiztosokat mint mennyiségeket reprezentáljuk, a bukást az algoritmus azonnal detektálja, és visszalép, hogy egy másik ütemezéssel próbálkozzon. Ha a vizsgálóbiztosokat önálló személyekként reprezentáljuk, akkor az algoritmus feleslegesen mind a 10! vizsgálóbiztos-kiosztás kipróbálásához visszalép.
12.3. ábra - Két autó összeszerelésének ütemezési feladata erőforrásokkal. Egy összeszerelő állomás, egy kerékszerelő-állomás és két vizsgálóbiztos az összes elérhető erőforrás. Az
ERŐFORRÁS:r jelölés jelentése, hogy az r erőforrást egy cselekvés végrehajtása alatt használjuk, de a cselekvés befejezése után újra szabad.
12.4. ábra - A 12.3. ábra erőforrásokat is tartalmazó ütemezési feladatának megoldása. Az ábra bal széle az erőforrásokat sorolja fel, a cselekvések az általuk használt erőforrásokkal egy sorban jelennek meg. Attól függően, hogy melyik összeszerelés használja a motorszerelő-állomást először, két lehetséges ütemezés létezik. Mi az optimális megoldást ábrázoltuk, ami 115 percet vesz igénybe.
Az előnyök ellenére, az erőforrás-megkötések nagyon megbonyolítják az ütemezési feladatokat azáltal, hogy a cselekvések közé további kölcsönhatásokat vezetnek be. Habár a megkötések nélküli ütemezés a kritikus útvonal módszer felhasználásával könnyű, a legkorábbi befejezési idejű erőforrás-megkötéseket tartalmazó ütemezés megtalálása NP-nehéz. Ez a komplexitás gyakran mind a gyakorlatban, mind az elméletben látható. Az 1963-ban közzétett nagy kihívást jelentő feladat – egy optimális ütemezés megtalálása egy 10 gépet, 10 munkát és 100 cselekvést tartalmazó problémához – 23 évig megoldatlan maradt (Lawler és társai, 1993). Sok megközelítést kipróbáltak, köztük az elágazásos megkötést, a szimulált lehűtést, a tabu keresést, a kényszerkielégítést és számos más, a II. részben szereplő technikát. A legegyszerűbb, de népszerű heurisztika a minimális tartalék (minimum slack) algoritmus. Ez a cselekvéseket mohó jelleggel ütemezi. Minden iterációban megnézi azokat a cselekvéseket, amelyeknek az összes előzményét már ütemeztük, és azt ütemezi, amelyiknek a legkevesebb tartalék ideje van a legkorábbi lehetséges kezdéshez. Ezután frissíti az ES és LS időértékeket minden egyes érintett cselekvésre, és ezt ismétli.
A heurisztika ugyanazon az ötleten alapul, mint a legjobban korlátozott változó heurisztika a kényszerkielégítésnél. Ez a gyakorlatban gyakran jól működik, de a mi összeszerelési problémánkra egy 130 perces megoldást ad, nem pedig a 12.4. ábrán bemutatott 115 perceset.
Az ebben a fejezetben bemutatott megközelítés a „tervezzünk először, ütemezzünk később” megközelítés: azaz a teljes problémát egy tervkészítési fázisra és egy ütemezési fázisra bontjuk. A tervezési fázisban a cselekvéseket részben rendezzük, hogy elérjük a probléma céljait, az ütemezési fázisban pedig az időinformációkat illesztjük a tervhez, ezzel biztosítva, hogy a terv kielégítse az erőforrás- és a határidőkorlátokat. Ez a megközelítés nagyon gyakori a valós idejű gyártási és logisztikai problémákban, ahol a tervkészítési fázist leggyakrabban emberi szakértők végzik. Ellenben, amikor sok erőforrás-megkötés van, adódhat, hogy néhány érvényes terv sokkal jobb ütemezéshez vezet, mint mások. Ebben az esetben, a tervkészítési és ütemezési fázist célszerű integrálni úgy, hogy a részben rendezett tervkészítés során figyelembe vesszük a cselekvések időtartamait és átfedéseit. A 11. fejezetben bemutatott számos tervkészítő algoritmus kiterjeszthető úgy, hogy ezt az információt is kezelje. Például a részben rendezett tervkészítők az okozati kapcsolatok konfliktusainak detektálásához hasonlóan az erőforráskorlát megsértéseit is detektálni tudják. A heurisztikák módosíthatók, hogy a cselekvések teljes költségén túl, a tervek teljes végrehajtási idejét is becsüljék. Ez napjainkban a kutatás egy aktív területe.
[118] Ezzel szemben a fogyóeszköz-erőforrások (consumable resources), mint az autó-összeszereléshez használt csavarok, az eredeti keretrendszeren belül kezelhetők; lásd 12.2. feladat.
