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. Ke­ressük azt hozzárendelési mátrixot, mely teljesíti a hoz­zá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ényrend­szer a kívánt szélsőértékét éri el. A hozzárendelés meghatározását célszerűbb progra­monké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 berende­zé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áren­delt termék m. műveletét, különben 0 az értéke. Ekkor KIOMgm—X(Kio­s)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 berende­zés, akkor minden köztes m műveletet is el kell végez­nie. Ez az állítás mátrixalakban a következőkkel fogal­mazható meg: Vgm­ 1 ,m2\KIOMg(m\g= = 1 л.КI­OMg(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 konst­ruktí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 heu­risztikus A keresést alkalmazunk. A keresés egy­ álla­potfa 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ópon­tok é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 ter­mékhez hozzárendelve. Az első szinten állnak azok a KIO mátrixok, melyekben az első gép lett egy termék­hez hozzárendelve, a második szinten állnak azok a KIO mátrixok, melyekben már az első két gép hozzá lett ren­delve 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övet­kező 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 át­haladó megoldások célfüggvényeinek alsó korlátját je­lenti, í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árende­lésben, mely ezen a csomóponton halad át (valódi t ter­mékre vonatkozó áteresztési idő ennél csak nagyobb le­het). Ezen alsó korlátot úgy határozhatjuk meg, hogy feltesszük, hogy a szabad gépek mind­ezen termékhez lesznek hozzárendelve. Mivel a valóságban a hozzáren­delt 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 át­lagos g­6 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épes­ségű minigépen a kisebb rendszerekkel vonatkozó méré­sekből következtetve mintegy 200000 év futási idő len­ne szükséges. A vizsgált megoldási módszerek közül a leghatéko­nyabb módszert az adta, melyet az alapgenetikus algorit­mus 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ő pa­raméterlánc, gén tartozik. Az alapalgoritmusban indulás­ként felvesznek N darab gént, s minden génhez kiszá­molják a hozzá tartozó célfüggvényértéket (a vele rep­rezentált rendszerváltozat jóságát). A gének a generációk sorozatán keresztül folyamatosan változnak, ahol a vál­tozá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 ope­rá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.

Next