A termelésirányítás optimalizálása az IBM adattároló gyárában Jüttner Alpár ELTE TTK Operációkutatási Tsz.
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
1 / 27
IBM-ELTE Center for Applied Mathematics IBM Research Zurich által finanszírozott együttmuködés ˝ Célok Gyakorlati feladatokhoz kapcsolódó matematikai kompetenciák fejlesztése Kutatási együttmuködések ˝ Konkrét ipari feladatokban való részvétel Internship, kutatói ösztöndíjak
Kutatási területek Raktárkészlet optimalizálás Gyártási folyamatok optimalizálása (High performance computing) Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
2 / 27
IBM DS8000 gyártás optimalizálás
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
3 / 27
IBM DS8000 Storage System
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
4 / 27
IBM DS8000 Storage System
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
5 / 27
IBM DS8000 Storage System
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
6 / 27
IBM DS8000 Storage System
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
7 / 27
IBM DS8000 Storage System
Nagy tárkapacitás Gyors, párhuzamos elérés Nagy megbízhatóság Tesztelés
Kis példányszám, nagy ˝ egyedi eroforrásigény Minden részletében konfigurálható ⇒ Sorozatgyártás helyett egyedi ütemezés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
8 / 27
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
9 / 27
Megapack összeszerelés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
10 / 27
Tesztelési folyamat
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
11 / 27
„On-demand business” Rendelések Egyedi rendelési modell Sok visszavont rendelés Az adott negyedévben kell teljesíteni Egyenetlen rendelési ráta a negyedév során Kétfázisú gyártási folyamat Startoff build ˝ Egy elozetes konfiguráció összeszerelése Teljes tesztelés (hosszú)
Rekonfiguráció Egy korábban felépített konfiguráció átszerelése egy megrendelt konfigurációra Újratesztelés (rövid) Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
12 / 27
„On-demand business” Rendelések Egyedi rendelési modell Sok visszavont rendelés Az adott negyedévben kell teljesíteni Egyenetlen rendelési ráta a negyedév során Kétfázisú gyártási folyamat Startoff build ˝ Egy elozetes konfiguráció összeszerelése Teljes tesztelés (hosszú)
Rekonfiguráció Egy korábban felépített konfiguráció átszerelése egy megrendelt konfigurációra Újratesztelés (rövid) Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
12 / 27
Termelésirányítás Startoff build Felépítendo˝ konfigurációk kijelölése ˝ Tervezés két napra elore Rekonfiguráció Aznapi feladat kijelölése minden nap (reggel) Lépések: 1 2 3
Megépítendo˝ rendelések kiválasztása Hasonló konfigurációjú boxok kiválasztása Cserélendo˝ alkatrészek meghatározása
Problémák Emberi döntések óriási táblázatokból Összehangolatlan döntések Nehéz a hosszútávú tervezés Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
13 / 27
Termelésirányítás Startoff build Felépítendo˝ konfigurációk kijelölése ˝ Tervezés két napra elore Rekonfiguráció Aznapi feladat kijelölése minden nap (reggel) Lépések: 1 2 3
Megépítendo˝ rendelések kiválasztása Hasonló konfigurációjú boxok kiválasztása Cserélendo˝ alkatrészek meghatározása
Problémák Emberi döntések óriási táblázatokból Összehangolatlan döntések Nehéz a hosszútávú tervezés Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
13 / 27
Termelésirányítás Startoff build Felépítendo˝ konfigurációk kijelölése ˝ Tervezés két napra elore Rekonfiguráció Aznapi feladat kijelölése minden nap (reggel) Lépések: 1 2 3
Megépítendo˝ rendelések kiválasztása Hasonló konfigurációjú boxok kiválasztása Cserélendo˝ alkatrészek meghatározása
Problémák Emberi döntések óriási táblázatokból Összehangolatlan döntések Nehéz a hosszútávú tervezés Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
13 / 27
Termelésirányítás Startoff build Felépítendo˝ konfigurációk kijelölése ˝ Tervezés két napra elore Rekonfiguráció Aznapi feladat kijelölése minden nap (reggel) Lépések: 1 2 3
Megépítendo˝ rendelések kiválasztása Hasonló konfigurációjú boxok kiválasztása Cserélendo˝ alkatrészek meghatározása
Problémák Emberi döntések óriási táblázatokból Összehangolatlan döntések Nehéz a hosszútávú tervezés Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
13 / 27
Termelésirányítás Startoff build Felépítendo˝ konfigurációk kijelölése ˝ Tervezés két napra elore Rekonfiguráció Aznapi feladat kijelölése minden nap (reggel) Lépések: 1 2 3
Megépítendo˝ rendelések kiválasztása Hasonló konfigurációjú boxok kiválasztása Cserélendo˝ alkatrészek meghatározása
Problémák Emberi döntések óriási táblázatokból Összehangolatlan döntések Nehéz a hosszútávú tervezés Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
13 / 27
Termelésirányítás Startoff build Felépítendo˝ konfigurációk kijelölése ˝ Tervezés két napra elore Rekonfiguráció Aznapi feladat kijelölése minden nap (reggel) Lépések: 1 2 3
Megépítendo˝ rendelések kiválasztása Hasonló konfigurációjú boxok kiválasztása Cserélendo˝ alkatrészek meghatározása
Problémák Emberi döntések óriási táblázatokból Összehangolatlan döntések Nehéz a hosszútávú tervezés Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
13 / 27
Felhasználható adatok Raktárkészlet Beérkezett alkatrészek darabszáma, típusa Összeszereltéségi fokuk, teszteltségi szintek ˝ Mikortól lesznek elérhetok Rendelések Pontos konfigurációk Az elkészítés határideje Költségek ˝ Elemi lépések idejébol ˝ könnyen számítható Szerelési ido: ˝ Bonyolult, sok tényezo˝ befolyásolja Tesztelési ido: Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
14 / 27
Felhasználható adatok Raktárkészlet Beérkezett alkatrészek darabszáma, típusa Összeszereltéségi fokuk, teszteltségi szintek ˝ Mikortól lesznek elérhetok Rendelések Pontos konfigurációk Az elkészítés határideje Költségek ˝ Elemi lépések idejébol ˝ könnyen számítható Szerelési ido: ˝ Bonyolult, sok tényezo˝ befolyásolja Tesztelési ido: Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
14 / 27
Felhasználható adatok Raktárkészlet Beérkezett alkatrészek darabszáma, típusa Összeszereltéségi fokuk, teszteltségi szintek ˝ Mikortól lesznek elérhetok Rendelések (sokat visszavonnak) Pontos konfigurációk (változhat) Az elkészítés határideje (változhat) Költségek ˝ Elemi lépések idejébol ˝ könnyen számítható Szerelési ido: ˝ Bonyolult, sok tényezo˝ befolyásolja Tesztelési ido: Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
14 / 27
Felhasználható adatok Raktárkészlet Beérkezett alkatrészek darabszáma, típusa Összeszereltéségi fokuk, teszteltségi szintek ˝ Mikortól lesznek elérhetok Rendelések (sokat visszavonnak) Pontos konfigurációk (változhat) Az elkészítés határideje (változhat) Költségek ˝ Elemi lépések idejébol ˝ könnyen számítható Szerelési ido: ˝ Bonyolult, sok tényezo˝ befolyásolja Tesztelési ido: Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
14 / 27
˝ Statisztika, elorejelzés feladatok
1 2
Tesztido˝ becslése ˝ Elorejelzések 1 2
Rendelések visszamondásának valószínusége ˝ Paraméterek változásának valószínusége ˝ Határido˝ változása
3
˝ Negyedév során az igények elorejelzése.
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
15 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Best Match Jelenleg Input: Egyetlen megépítendo˝ box konfigurációja Output: Boxok egy rendezett listája Kihívások Tesztido˝ csak teljes stringre számolható Sokféle célfüggvény Változó szempontok Real-time Mi legyen az output?
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
16 / 27
Gráfelméleti modell A Box
A részegységeket egy gráffal reprezentáljuk.
Console Gigapack
HDD
Gigapack
HDD
Gigapack
HDD
HDD
HDD
IO Drawer
Gigapack
HDD
HDD
Power 6+ server
HDD
HDD
HDD
HDD
HDD
A gráf csúcsai tartalmazzák a részegység típusát és teszteltségi fokát Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
17 / 27
Gráfelméleti modell Megengedett operációk
Kiszerelés
Beszerelés
Tesztelés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
18 / 27
Gráfelméleti modell Megengedett operációk
Kiszerelés
Beszerelés
Tesztelés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
18 / 27
Gráfelméleti modell Megengedett operációk
Kiszerelés
Beszerelés
Tesztelés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
18 / 27
Gráfelméleti modell Rekonfigurációs alapfeladat GI Inventory gráf: Az elérheto˝ összes részalkatrész és box gráfja együtt. GR Reconf gráf: Az elkészítendo˝ konfigurációk gráfja.
GI GR
φ Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
19 / 27
Gráfelméleti modell Rekonfigurációs alapfeladat Megengedett ϕ hozzárendelés: Beágyazás Minden alkatrészhez azonos típusút rendel, A szükséges szerelési és tesztelési ˝ beleférnek a határidobe ˝ idok
GI GR
φ
Költségfüggvény kiszámítása: Szükséges operációk meghatározása Egyes operációk költségének meghatározása
A legjobb ilyen ϕ-t keressük.
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
19 / 27
Gráfelméleti modell Rekonfigurációs alapfeladat Megengedett ϕ hozzárendelés: Beágyazás Minden alkatrészhez azonos típusút rendel, A szükséges szerelési és tesztelési ˝ beleférnek a határidobe ˝ idok
GI GR
φ
Költségfüggvény kiszámítása: Szükséges operációk meghatározása Egyes operációk költségének meghatározása
A legjobb ilyen ϕ-t keressük.
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
19 / 27
Gráfelméleti modell Rekonfigurációs alapfeladat Megengedett ϕ hozzárendelés: Beágyazás Minden alkatrészhez azonos típusút rendel, A szükséges szerelési és tesztelési ˝ beleférnek a határidobe ˝ idok
GI GR
φ
Költségfüggvény kiszámítása: Szükséges operációk meghatározása Egyes operációk költségének meghatározása
A legjobb ilyen ϕ-t keressük.
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
19 / 27
Maximális izomorf színezett részfenyo˝ ˝ A rekonfigurációs alapfeladat egy építokockája
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
20 / 27
Maximális izomorf színezett részfenyo˝ ˝ A rekonfigurációs alapfeladat egy építokockája
Algoritmus: Dinamikus programozás Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
20 / 27
Maximális izomorf színezett részfenyo˝ Részfeladat
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
21 / 27
Maximális izomorf színezett részfenyo˝ Részfeladat
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
21 / 27
Maximális izomorf színezett részfenyo˝ ˝ Kezdolépés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
22 / 27
Maximális izomorf színezett részfenyo˝ Általános lépés
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
23 / 27
Maximális izomorf színezett részfenyo˝ Futásido˝ Elméleti felso˝ becslés: O(nCD 3 ) ˝ n: 1. fenyoben csúcsok száma ˝ C: 2. fenyoben egyszínu˝ csúcsok max száma D: egyszínu˝ gyerekek max száma
Alkalmazhatóság ˝ Rögzített gyökér - Tetszoleges gyökér Élszínezés Színezés helyett megengedettségi szabály Rekurzív súlyfüggvény Izomorf részfenyves Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
24 / 27
Maximális izomorf színezett részfenyo˝ Futásido˝ Elméleti felso˝ becslés: O(nCD 3 ) ˝ n: 1. fenyoben csúcsok száma ˝ C: 2. fenyoben egyszínu˝ csúcsok max száma D: egyszínu˝ gyerekek max száma
Alkalmazhatóság ˝ Rögzített gyökér - Tetszoleges gyökér Élszínezés Színezés helyett megengedettségi szabály Rekurzív súlyfüggvény Izomorf részfenyves Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
24 / 27
Maximális izomorf színezett részfenyo˝ Futásido˝ Elméleti felso˝ becslés: O(nCD 3 ) ˝ n: 1. fenyoben csúcsok száma ˝ C: 2. fenyoben egyszínu˝ csúcsok max száma D: egyszínu˝ gyerekek max száma
Alkalmazhatóság ˝ Rögzített gyökér - Tetszoleges gyökér Élszínezés Színezés helyett megengedettségi szabály Rekurzív súlyfüggvény Izomorf részfenyves Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
24 / 27
Maximális izomorf színezett részfenyo˝ Futásido˝ Elméleti felso˝ becslés: O(nCD 3 ) ˝ n: 1. fenyoben csúcsok száma ˝ C: 2. fenyoben egyszínu˝ csúcsok max száma D: egyszínu˝ gyerekek max száma
Alkalmazhatóság ˝ Rögzített gyökér - Tetszoleges gyökér Élszínezés Színezés helyett megengedettségi szabály Rekurzív súlyfüggvény Izomorf részfenyves Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
24 / 27
Maximális izomorf színezett részfenyo˝ Futásido˝ Elméleti felso˝ becslés: O(nCD 3 ) ˝ n: 1. fenyoben csúcsok száma ˝ C: 2. fenyoben egyszínu˝ csúcsok max száma D: egyszínu˝ gyerekek max száma
Alkalmazhatóság ˝ Rögzített gyökér - Tetszoleges gyökér Élszínezés Színezés helyett megengedettségi szabály Rekurzív súlyfüggvény Izomorf részfenyves Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
24 / 27
Maximális izomorf színezett részfenyo˝ Futásido˝ Elméleti felso˝ becslés: O(nCD 3 ) ˝ n: 1. fenyoben csúcsok száma ˝ C: 2. fenyoben egyszínu˝ csúcsok max száma D: egyszínu˝ gyerekek max száma
Alkalmazhatóság ˝ Rögzített gyökér - Tetszoleges gyökér Élszínezés Színezés helyett megengedettségi szabály Rekurzív súlyfüggvény Izomorf részfenyves Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
24 / 27
˝ Statisztika, elorejelzés feladatok
1 2
Tesztido˝ becslése ˝ Elorejelzések 1 2
Rendelések visszamondásának valószínusége ˝ Paraméterek változásának valószínusége ˝ Határido˝ változása
3
˝ Negyedév során az igények elorejelzése.
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
25 / 27
Optimalizációs feladatok
1 2
(Best Match alkalmazás) Rekonfiguráció tervezés adott rendelésekre egy nap több nap
3 4
Teljes rekonfiguráció tervezés Döntéstámogatás: Startoff build vagy Rekonfiguráció
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
26 / 27
Köszönöm a figyelmet!
Jüttner Alpár (ELTE TTK)
Adattárolók gyátásának optimalizálása
27 / 27
