Starkné dr. Werner Ágnes
Dinamikus programozás - Szerelőszalag ütemezése A dinamikus programozás minden egyes részfeladatot és annak minden részfeladatát pontosan egyszer oldja meg, az eredményt egy táblázatban tárolja, és ezáltal elkerüli az ismételt számítást, ha a részfeladat megint felmerül. A dinamikus programozást optimalizálási feladatok megoldására használjuk. Ilyen feladatoknak sok megengedett megoldása lehet. Egy dinamikus programozási algoritmus kifejlesztése 4 lépésre bontható fel: 1. Jellemezzük az optimális megoldás szerkezetét. 2. Rekurzív módon definiáljuk az optimális megoldás értékét. 3. Kiszámítjuk az optimális megoldás értékét alulról felfelé történő módon. 4. A kiszámított információk alapján megszerkesztünk egy optimális megoldást. A 1-3. lépések jelentik az alapját annak, ahogy a dinamikus programozás meg tud oldani egy feladatot. Egy autógyár autókat állít elő az egyik gyárában, amelynek két szerelőszalagja van. Mindkét szerelőszalag elején egy alváz jelenik meg, melyhez adott számú állomáson hozzászerelik az alkatrészeket, majd a szalag végén távozik a kész autó. Mindegyik szalagnak n állomása van, melyek indexei j=1, 2, …, n. Sij jelöli az i-edik (i=1 vagy 2) szalag j-edik állomását. Az első szalag j-edik állomása (S1j) ugyanazt a funkciót látja el, mint a második szalag j-edik állomása (S2j). A szalagokat különböző időpontokban különböző technológiával építették, ezért előfordulhat, hogy a két szalag azonos állomásán a terméknek különböző időt kell eltöltenie. Az Sij állomáson a műveleti időt aij jelöli. S11 állomás
1. szerelőszalag
a11
e1
S12 állomás
S1,n-1 állomás
S1n állomás
a1,n-1
a1n
a12
az alváz belép
x1
t1,n-1
t11 …
a kész autó kilép
t2,n-1
t21
x2
e2
2. szerelőszalag
a21 S21 állomás
a22 S22 állomás
a2,n-1 S2,n-1 állomás
a2n S2n állomás
Ahhoz is kell egy bizonyos idő, hogy az alváz a szalagra kerüljön, és ahhoz is, hogy az elkészült autó elhagyja a szalagot. Ezeket az i-edik szalag esetén ei, illetve xi jelöli. Ha szeretnénk a megrendeléseket minél gyorsabban teljesíteni, a két szalag munkáját össze kell hangolni. Az i-edik szalag Sij állomása után az alváznak a másik szalagra való átrakása tij időbe kerül j=1, 2, …, n-1 (mivel n állomás után a kocsi már kész). A feladat az, hogy meghatározzuk, mely állomásokat érintse az egyik és melyeket a másik szalagon, hogy az átfutási idő minimális legyen. 1 PDF created with pdfFactory trial version www.pdffactory.com
Starkné dr. Werner Ágnes Példa a szerelőszalag feladatára. Feltüntettük a különböző költségeket. A vastagon rajzolt út a legrövidebb. S11 állomás
1. szerelőszalag
S12 állomás
7
2
9 2
az alváz belép
S13 állomás
S14 állomás
S15 állomás
3
8
4
3
3
2
a kész autó kilép
1
2
1
3
4
2
4
2. szerelőszalag
8 S21 állomás
5 S22 állomás
6
4
S23 állomás
S24 állomás
7 S25 állomás
A teljes leszámlálás számítási ideje Ω(2n). Ez nagy n mellett elfogadhatatlan. 1. lépés: a legrövidebb gyártási út szerkezete Tekintsük a lehetséges legrövidebb utat, ahogy egy alváz a kiindulási helyzetből túljut az S1j állomáson. Ha j=1, akkor csak egy lehetőség van, és így könnyű meghatározni a szükséges időt. j=2, 3, …,n esetén két lehetőség van: • az alváz érkezhet közvetlenül az S1,j-1 állomásról, amikor ugyanannak a szalagnak a (j-1)-edik állomásáról a j-edik állomására való átszállítás ideje elhanyagolható. • Az alváz S2,j-1 felől érkezik, az átszállítás ideje t2,j-1. Tegyük fel, hogy az S1j állomáson való túljutás leggyorsabb módja az, hogy oda az S1,j-1 felől érkezünk. Az alváznak a legrövidebb módon kell túljutnia az S1,j-1 állomáson, mert ha volna egy gyorsabb mód, hogy az alváz túljusson a S1,j-1 állomáson, akkor ezt használva magán S1,jn is hamarabb jutna túl, ami ellentmondás. Hasonlóképpen tegyük fel, hogy a leggyorsabb út az, amikor az alváz S2,j-1 felől érkezik. Ekkor a kiindulási ponttól indulva a legrövidebb módon kell túljutnia S2,j-1-en. Ha volna egy gyorsabb mód, hogy az alváz túljusson az állomáson, akkor ezt használva magán S2,j-1-n is hamarabb jutna túl, ami ismét ellentmondás. Általánosabban fogalmazva azt mondhatjuk, hogy a szerelőszalag ütemezésének (hogy megtaláljuk a legrövidebb módot az Sij állomáson való túljutásra) optimális megoldása tartalmazza egy részfeladat (vagy az S1,j-1 vagy az S2,j-1 állomáson való leggyorsabb áthaladás) optimális megoldását. Erre a tulajdonságra optimális részstruktúraként fogunk hivatkozni. Azaz részfeladatok optimális megoldásaiból megszerkeszthető a feladat optimális megoldása. Ha a leggyorsabb módon túljutunk az S1j állomáson, akkor túl kell jutnunk a (j-1)-edik állomáson vagy az első vagy a második szalagon. Ezért a leggyorsabb út az S1j állomáson keresztül vagy
2 PDF created with pdfFactory trial version www.pdffactory.com
Starkné dr. Werner Ágnes • a leggyorsabb út az S1,j-1 állomáson keresztül és onnan közvetlenül megyünk az S1j állomásra, vagy • a leggyorsabb út az S2,j-1 állomáson keresztül, ahonnan az alvázat át kell szállítani az első szalag S1j állomására. Mindkét esetben el kell végezni a munkát az S1j állomáson. Hasonlóképpen a leggyorsabb út az S2j állomáson keresztül vagy • a leggyorsabb út az S2,j-1 állomáson keresztül és onnan közvetlenül megyünk az S2j állomásra, vagy • a leggyorsabb út az S1,j-1 állomáson keresztül, ahonnan az alvázat át kell szállítani a második szalag S2j állomására. Ahhoz, hogy bármelyik szalag j-edik állomásán keresztülvezető legrövidebb utat megtaláljuk, mindkét szalag (j-1)-edik állomásán keresztüli legrövidebb út megkeresésére van szükség.
2. lépés: a rekurzív megoldás Az optimális megoldás értékét a részfeladatok optimális értékeiből rekurzívan fejezzük ki. A részfeladatok legyenek mindkét szalag j-edik állomásán való leggyorsabb áthaladás megkeresésének a feladatai j=1, 2,…, n mellett. Jelölje fi[j] azt a legrövidebb időt, ami alatt az alváz túl tud jutni az Sij állomáson. Célunk annak a legrövidebb időnek a meghatározása, ami alatt az alváz az egész üzemen keresztül tud haladni. Ezt az időt f* jelöli. Az alváznak át kell haladnia az első vagy a második szalag n-edik állomásán, és utána el kell hagynia a gyárat. Mivel a két lehetőség közül a gyorsabbik az egész üzemen átvezető leggyorsabb lehetőség, azt kapjuk, hogy f* = min{ f1[n] +x1, f2[n] +x2} Mindkét szalag esetében az első állomáson való keresztülhaladás azt jelenti, hogy az alváz egyenesen erre az állomásra kerül, azaz f1[1] = e1+a11 f2[1] = e2+a21 Hogyan kell kiszámolni az fi[j]-t j=2, 3,…,n és i=1,2 esetén? f1[j] = min{f1[j-1]+a1j, f2[j-1]+ t2,j-1 +a1j}, ha j=2, 3,…,n. Ehhez hasonlóan f2[j] = min{ f2[j-1]+a2j, f1[j-1]+ t1,j-1 +a2j}, ha j=2, 3,…,n. A következő rekurzív egyenletet kapjuk: f1[j] =
e1+a11, ha j=1, min{ f1[j-1]+a1j, f2[j-1]+ t2,j-1 +a1j}, ha j≥2
3 PDF created with pdfFactory trial version www.pdffactory.com
Starkné dr. Werner Ágnes
f2[j] =
e2+a21, ha j=1, min{ f2[j-1]+a2j, f1[j-1]+ t1,j-1 +a2j}, ha j≥2
1 9 12
2 18 16
Példánkban: j f1[j] f2[j]
3 20 22
4 28 26
5 31 33
f*=34 Az fi[j] mennyiségek a részfeladatok optimális érékei. Annak érdekében, hogy vissza tudjuk keresni a legrövidebb utat, definiáljuk li[j]-t mint azt a szerelőszalagot, amelyiknek a j-1-edik állomását használtuk az Sij-n való leggyorsabb keresztülhaladáskor. Itt i=1,2 és j=2,3,…,n. (Nem definiáljuk li[1]-et, mert Si1-t egyik szalagon sem előzi meg másik állomás.) Az l* szalag definíció szerint az, amelyiknek az utolsó állomását használjuk az egész üzemen való áthaladáskor. Az li[j] értékek segítségével lehet nyomon követni a legrövidebb utat. Példánkban: j l1[j] l2[j]
2 1 1
3 2 2
4 1 1
5 2 2
l* =1 Mivel l* =1, ezért az S15 állomást használjuk. Mivel l1[5]=2, ezért ide az S24 állomásról érkeztünk. Így folytatva az l2[4]=1az S13, l1[3]=2 az S22, l2[2]=1 az S11 állomás használatát jelenti. 3. lépés: a legrövidebb átfutási idő kiszámítása Sokkal jobban járunk, ha az fi[j] értékeket más sorrend szerint számoljuk, mint az a rekurzív módszerből adódik. Vegyük észre, hogy j≥2 esetén fi[j] csak f1[j-1] -től és f2[j-1] -től függ. Ha az fi[j] értékeket az állomások j indexének növekvő sorrendjében számoljuk, akkor a legrövidebb átfutási idő meghatározása Θ(n) ideig tart. Az eljárás bemenő paraméterei az aij, tij, ei és xi értékek, valamint mindkét szalag állomásainak n száma.
4 PDF created with pdfFactory trial version www.pdffactory.com
Starkné dr. Werner Ágnes ALGORITMUS1(a,t,e,x,n) 1. f1[1] := e1+a11 2. f2[1] := e2+a21 3. for j:=2 to n 4. do if f1[j-1]+a1j =< f2[j-1]+ t2,j-1 +a1j 5. then f1[j]:= f1[j-1]+a1j 6. l1[j]:=1 7. else f1[j]:= f2[j-1]+ t2,j-1 +a1j 8. l1[j]:=2 9. if f2[j-1]+a2j =< f1[j-1]+ t1,j-1 +a2j 10. then f2[j]:= f2[j-1]+a2j 11. l2[j]:=2 12. else f2[j]:= f1[j-1]+ t1,j-1 +a2j 13. l2[j]:=1 14. if f1[n] +x1 =< f2[n] +x2 15. then f*=f1[n] +x1 16. l*=1 17. else f*=f2[n] +x2 18. l*=2 fi[j] és li[j] kiszámítását úgy is tekinthetjük, hogy kitöltjük egy táblázat elemeit. Az fi[j]-t és li[j]-t tartalmazó táblát balról jobbra és oszloponként felülről lefelé töltjük ki. fi[j] kiszámításához csak f1[j-1]-re és f2[j-1]-re van szükségünk. Ezeket már kiszámítottuk, az adott pillanatban a meghatározásuk mindössze abból áll, hogy kiolvassuk azokat a táblázatból. 4. lépés: a legrövidebb átfutási idejű út megszerkesztése fi[j], f*, li[j] és l* kiszámítását követően meg kell szerkeszteni az üzemen való legrövidebb áthaladást biztosító utat. Az alábbi eljárás az út állomásait az indexek csökkenő sorrendjében nyomtatja ki. ALGORITMUS2(l,n) 1. i:= l* 2. print i”-edik szalag” n„-edik állomás” 3. for j:= n downto 2 4. do i:= li[j] 5. print i”-edik szalag (” j-1„)-edik állomás”
Eredmény a példánkban: 1. 2. 1. 2. 1.
szalag 5. állomás szalag 4. állomás szalag 3. állomás szalag 2. állomás szalag 1. állomás
5 PDF created with pdfFactory trial version www.pdffactory.com
