Gép, 1994 (46. évfolyam, 1-12. szám)
1994-02-01 / 2. szám
zási modul célja. A feladat leírása a korábban bevezetett fogalmak használatával a következőképpen hangzik. Keressük azt hozzárendelési mátrixot, mely teljesíti a hozzárendelésre vonatkozó M5, M6, M7, M9 megkötöttségeket illetve a megvalósíthatóság (2), (3) kritériumait, úgy hogy az (4), (5), (6)-ban megadott célfüggvényrendszer a kívánt szélsőértékét éri el. A hozzárendelés meghatározását célszerűbb programonként vizsgálni, e célból két új változót vezetünk be. Az első mátrix jelöli, hogy a programban a g. technológiai berendezéshez melyik termék rendelődött hozzá: KIOg=L ‘ *s8n Xm= 1xtmgp (7) A második mátrix, KIOMgm a technológiai berendezések és a műveletek összerendelését tartalmazza: KIOM,gm IQ(8) A KIOMgm értéke 1, ha a g. gép elvégzi a hozzárendelt termék m. műveletét, különben 0 az értéke. Ekkor KIOMgm—X(Kios)mgp (9) is teljesül. A meghatározott megkötések átírhatók a KIO és KIOM mátrixra is, így például az M6 feltétel az M5 figyelembe vételével úgy fogalmazható meg, hogy egy technológiai berendezéshez egy termék egy vagy folytonosan egymást követő műveletei rendelhetők, azaz ha m 1 és m2 műveletet elvégzi a technológiai berendezés, akkor minden köztes m műveletet is el kell végeznie. Ez az állítás mátrixalakban a következőkkel fogalmazható meg: Vgm 1 ,m2\KIOMg(m\g= = 1 л.КIOMg(m2)= 1 лт 1 ‰p?/2 -ra teljesül, hogy —Эт,т\·т‰т2лКЮМ gm= 0 A KIO és KIOM meghatározása a kombinatorikus hozzárendelési feladatokhoz tartozik, melyekhez csak egy-két gépet tartalmazó rendszerekhez létezik konstruktív eljárás, így a nagyobb rendszerekre számításba jöhetnek a — leszámlálásos; — véletlenen alapuló; — heurisztikus módszerek. A KIO mátrix meghatározására egy heurisztikus A keresést alkalmazunk. A keresés egy állapotfa csomópontjain, fentről lefelé történő mozgással valósul meg, ahol a következő lépést a költségfüggvények értékei alapján választják ki. A keresés a fa legfelső gyökeréből indul ki. Jelentsék esetünkben a csomópontok és a mozgások a következőket. A csúcsban egy olyan KIO mátrix áll, melyben még egyetlen gép sem lett termékhez hozzárendelve. Az első szinten állnak azok a KIO mátrixok, melyekben az első gép lett egy termékhez hozzárendelve, a második szinten állnak azok a KIO mátrixok, melyekben már az első két gép hozzá lett rendelve egy-egy termékhez. Ugyanígy értelmezendő a fa további szintjei is, a fa legutolsó szintjén már minden gép le lett kötve termékhez, így a lefelé mozgás a következő gépnek egy termékhez való hozzárendelését jelenti. A csomópontokból kiinduló ágak száma a rendszerben jelenlévő terméktípusok darabszámával egyezik meg. Jelen esetünkben, mivel a felső szintek egyes csomópontjai önmagukban életképtelenek (nem elégítik ki a hozzárendelési szabályokat), ezért ahelyett, hogy a g(x) illetve h(x) függvényeket külön-külön meghatároznánk, közvetlenül az /W(sM+M*) (12) függvényre térünk rá, mely az adott csomóponton áthaladó megoldások célfüggvényeinek alsó korlátját jelenti, így f(x) értéke az átfutási idő minimalizálását kiválasztva célként, azt a minimális áteresztési időt jelenti a t terméknél, melynél minden élő, teljes KIO hozzárendelésben, mely ezen a csomóponton halad át (valódi t termékre vonatkozó áteresztési idő ennél csak nagyobb lehet). Ezen alsó korlátot úgy határozhatjuk meg, hogy feltesszük, hogy a szabad gépek mindezen termékhez lesznek hozzárendelve. Mivel a valóságban a hozzárendelt gépek száma a fában való mozgások során ettől több nem lehet, így a ténylegesen hozzárendelt gépek száma egyenlő vagy kisebb ezen feltételezett értéktől, ami azt is jelenti, hogy az átfutási idő viszont egyenlő vagy nagyobb ezen kiszámított értéktől. A KIOM mátrix optimalizálásánál jelentkező feladat nagyságának meghatározására példaként vehető egy átlagos g6 gép és m = 10 műveletet tartalmazó rendszer, amikor is a KIOM mátrixnak 1018 változata lehetséges, melynek teljes átvizsgálása egy nagyobb teljesítőképességű minigépen a kisebb rendszerekkel vonatkozó mérésekből következtetve mintegy 200000 év futási idő lenne szükséges. A vizsgált megoldási módszerek közül a leghatékonyabb módszert az adta, melyet az alapgenetikus algoritmus módosításával kaphatunk. A genetikus algoritmus minden rendszerváltozót, függetlenül attól, hogy milyen rendszert vizsgálnak, egy karakterlánccal jellemez, amit génnek is neveznek. Minden változathoz különböző paraméterlánc, gén tartozik. Az alapalgoritmusban indulásként felvesznek N darab gént, s minden génhez kiszámolják a hozzá tartozó célfüggvényértéket (a vele reprezentált rendszerváltozat jóságát). A gének a generációk sorozatán keresztül folyamatosan változnak, ahol a változásban mind a véletlen, mind a célirányosság szerepet játszik. Egy új generáció a régiből három genetikus operátor egyidejű alkalmazásával jön létre: — reprodukció: gén átkerülése a következő generációba, ahol az átkerülés valószínűsége a gén jóságával arányos; — keresztezés: két gén ugyanazon helyen kettétörik, s felcserélik egymással a részeket. (10) (11) FEBRUÁR GÉP, XLVI. évfolyam, 1994.