"Nem tudhatod, hogy mazursky-nak
nem pont egy olyan problémája van-e, amire jó a HRS? "
Mondj olyan módszert, amellyel eldönthető, hogy mely problémákra alkalmazható a HRS. Sajnos az, hogy ki kell próbálni, hogy működik-e , nem járható út mondjuk abban az esetben, ahol a mérések elvégzése nagyon költséges.
Az a helyzet, hogy nem lehet tudni, hogy a HRS által adott érték valóban globális optimum-e.
"Szerintem azokban a feladatokban, amelyekben a genetikus
algoritmusnak létjogosultsága van, ott mindenképpen használható
a HRS."
No, ezt mi alapján mondod?
"Eddig a szimulációkon kívül jellemzően 3 területen tudok arról,
hogy kipróbálták a HRS-t. Mindegyik esetben a leggyorsabb és
leghatékonyabb módszernek bizonyult, a kimeneteket az mérési
hibán belül az elméleti határra tette le."
Ez rendben is van, nagyon szép eredmény. Viszont következik a fenti mondatodból az is, hogy abban az esetben, amikor nincs ilyen, hogy elméleti határ (pont ezt a határt keresed), akkor a módszer hasznosságáról nem lehet beszélni, mivel nem tudható, hogy amit kimenetként kiadott, az valóban a globális optimum-e, vagy nem. Valamint kérdés még, hogy abban az esetben, amikor több globális optimum van (a te fogalomrendszereddel élve több olyan határozott egyed van, amelynek magassága az optimális), akkor nem adja meg az összes ilyen elemet. Azonban ez fontos lehet, hiszen az egyes megoldások megvalósítási költsége más, így lehet olyen megoldás, amelyet alkalmazni olcsóbb, mint egy másik, viszont az optimalitzálási szempontból megegyeznek. A valóságban sokszor nem tudod, mi a probléma elméleti határa. Mondok egy tipikus példát, amivel nálunk a PE-n foglalkozunk. Adott egy gyártó üzem, amelynek működése szakaszos. A működést gráffal reprezentáljuk. Feladat megadni azt az optimális ütemezést, amelynek segítségével az adott termékmennyiség a lehető legrövidebb idő alatt legyártható. Ez egy tipikusan egészoptimalizálási probléma. Itt a problémák esetében nem ismert, hogy mi az elméleti határ a legrövidebb időre, hiszen az összes előforduló lehetőség közül sok olyan van, amely az adott feltételek mellett nem megvalósítható megoldást jelent. Legfeljebb becsléseket lehet adni, azonban a legtöbb esetben ezek a becslések a feladat szerkezete miatt nem elég élesek. Ebben az esetben tehát nem alkalmazható a HRS, hiszen nem tudom, hogy amit kimenetként kiad, mennyire jó megoldás. Így azt sem tudom, hogy meg kell-e állnom az algoritmussal, vagy nem.
"Sőt, a helyedben én benyomtam volna ide egy függvényt azzal,
hogy "na, ennek az optimumát találd meg öcsi, aztán hadoválj"
vagy valami ilyesmit léptem volna."
Nos, akkor legyen! Adott a következő probléma: Legyen T és E,P három véges halmaz, T taszkokat, E műveleti egységeket, P termékeket jelöl. Legyen adott a p: T->P(E) függvény, amely megadja, hogy mely taszk mely műveleti egységekkel hajtható végre. (P(E) itt az E halmaz hatványhalmazát jelenti). Természetesen minden x eleme T esetén p(x) nemüres halmaz.
Legyen adott a w:TxE->R függvény, amely megadja, hogy az adott taszk elvégzése az adott műveleti egységgel mennyi ideig tart.
Legyen adott az n:T->P(T u P) függvény, amely megadja, hogy a végrehajtás során mely taszkot mely taszkok követnek közvetlenül. (ez a leírás egy irányított körmentes gráffal is megadható).
Természetesen minden x eleme P esetén p(x) üres halmaz ( a termékeket már nem kell végrehajtani semmivel).
A leírás megkönnyítése céljából legyen p:(T u P)->P(T) ennek fordítottja (nem inverze n-nek), amely megadja, hogy a végrehajtás során egy taszkot vagy terméket mely taszkok előznek meg közvetlenül.
Nevezzük allokációs függvényeknek azokat a T->E típusú függvényeket (jelülje összességüket A), amelyekre igaz az, hogy minden a eleme A és minden x eleme T esetén a(x) eleme p(x)-nek (azaz gyakorlatilag egy taszkhoz csak olyan műveleti egységet rendelek hozzá, amellyel végre is hajtható).
Legyen a eleme A esetén az allokációs függvényhez tartozó végrehajtási idő függvény t (t típusa Ax(T u P)->R+0). t megadja, hogy az adott allokáció esetén 1-1 taszk mikor kezdődik el.
t-re teljesülnie kell annak, hogy minden x eleme T u P esetén t(x) >= max(t(y) + w(y,a(y):{y eleme p(x)}), azaz egy taszk nem kezdődhet el, illetve termék nem készülhet el hamarabb, mint ahogyan az őt megelőző taszkok befejeződtek. Amennyiben ilyen t nem létezik, akkor a-t nem megengedett allokációnak nevezzük (tipikusan ilyenek a 22-es csapdája: egy taszk arra várna, hogy egy rá következő taszk befejeződjön). Természetesen egy-egy allokációhoz végtelen sok lehetséges t függvény létezik, azonban ezek között van olyan, amely a legrövidebb végrehajtást valósítja meg, azaz egy taszk azonnal elkezdődik, amint lehetséges.
Feladatunk olyan megengedett allokációt és végrehajtási idő függvényt adni, amely esetén a max(t(y):y eleme P) minimális, azaz gyakorlati értelemben olyan ütemezést és az ütemezéshez tartozó műveleti egység-taszk hozzárendelést adni, amely a megadott termékeket a lehető legrövidebb idő alatt legyártja.
Ilyen biztosan létezik, hiszen véges sok allokáció lehet csak, mert T és E mérete (ezért P(E), tehát végsősoron A mérete is) véges.
Adok is rögtön egy feladatot, próbáld meg megoldani HRS-sel:
T = {T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11}
E = {E1,E2,E3,E4,E5)
P = {A,B,C,D}
A p függvény:
p(T1) = {E1,E2}
p(T2) = {E3}
p(T3) = {E2,E5}
p(T4) = {E4}
p(T5) = {E3,E4}
p(T6) = {E1,E2,E3}
p(T7) = {E2,E3}
p(T8) = {E4,E5}
p(T9) = {E3}
p(T10) = {E1,E3}
p(T11) = {E4,E5}
A w függvény:
w(T1,E1) = 6
w(T1,E2) = 8
w(T2,E3) = 9
w(T3,E2) = 7
w(T3,E5) = 7
w(T4,E4) = 10
w(T5,E3) = 15
w(T5,E4) = 12
w(T6,E1) = 10
w(T6,E2) = 17
w(T6,E3) = 13
w(T7,E2) = 6
w(T7,E3) = 10
w(T8,E4) = 12
w(T8,E5) = 16
w(T9,E3) = 8
w(T10,E1) = 9
w(T10,E3) = 8
w(T11,E4) = 18
w(T11,E5) = 16
Az n függvény:
n(T1) = {T2}
n(T2) = {T3}
n(T3) = {A}
n(T4) = {T5}
n(T5) = {T6}
n(T6) = {B}
n(T7) = {T8}
n(T8) = {C}
n(T9) = {T10}
n(T10) = {T11}
n(T11) = {D}
Ebből p kiszámolható, nem írom le.
Jó munkát!