VYSOKE UCENI TECHNICKE V BRNEBRNO UNIVERSITY OF TECHNOLOGY
FAKULTA INFORMACNICH TECHNOLOGIIUSTAV INTELIGENTNICH SYSTEMU
FACULTY OF INFORMATION TECHNOLOGYDEPARTMENT OF INTELLIGENT SYSTEMS
OPTIMALIZACE ULOZENI MATERIALU PRO PREPRAVU
BAKALARSKA PRACEBACHELOR’S THESIS
AUTOR PRACE MICHAL VACEKAUTHOR
BRNO 2007
VYSOKE UCENI TECHNICKE V BRNEBRNO UNIVERSITY OF TECHNOLOGY
FAKULTA INFORMACNICH TECHNOLOGIIUSTAV INTELIGENTNICH SYSTEMU
FACULTY OF INFORMATION TECHNOLOGYDEPARTMENT OF INTELLIGENT SYSTEMS
OPTIMALIZACE ULOZENI MATERIALU PRO PREPRAVUSTUFF PLACING OPTIMIZATION FOR TRANSPORT
BAKALARSKA PRACEBACHELOR’S THESIS
AUTOR PRACE MICHAL VACEKAUTHOR
VEDOUCI PRACE Ing. BOHUSLAV KRENA, Ph.D.SUPERVISOR
BRNO 2007
AbstraktPrace se zabyva aplikacı pro optimalizaci ulozenı materialu pro prepravu. Aplikace jevyvıjena ve spolupraci se spolecnostı Skoda Auto a.s., ktera resı problem prepravy ma-terialu v kontejnerech z vyrobnıch hal v Ceske republice do montaznıch zavodu v zahranicı.Zde je popsana jejı analyza, navrh i implementace. Aplikace se sklada ze dvou castı. Prvnıvypocıta optimalizaci – vybere z mnoziny modulu (krabic) vhodnou kombinaci a umıstı jikontejneru. Druha cast aplikace toto rozlozenı zobrazuje. Cast teto prace je take venovanaprıbuznym optimalizacnım metodam, zejmena pak Knapsack a Bin-packing problemu.
Klıcova slovaOptimalizace, ulozenı materialu, Knapsack, Bin-packing problem
AbstractThis bachelor thesis treats of application of stuff placing optimization for transport.Application is developed in cooperation with Skoda Auto a.s., which solves the problemof transport materials in containers from their factories to assembly halls abroad. It de-scribes an application analysis, a plan and an implementation. Application consist of twoparts. The first computes the optimalization – it selects subset from set of moduls (boxes)and it locates this boxes to a container. The second part of application display the stuffplacing. The part of this bachelor thesis is also set of agnated optimalization methods,mainly Knapsack and Bin-packing problem.
KeywordsOptimalization, stuff placing, Knapsack, Bin-packing problem
CitaceMichal Vacek: Optimalizace ulozenı materialu pro prepravu, bakalarska prace, Brno, FITVUT v Brne, 2007
Optimalizace ulozenı materialu pro prepravu
ProhlasenıProhlasuji, ze jsem tuto bakalarskou praci vypracoval samostatne pod vedenım panaBohuslava Kreny. Dalsı informace mi poskytli zamestnanci spolecnosti Skoda Auto a. s.Uvedl jsem vsechny literarnı prameny a publikace, ze kterych jsem cerpal.
. . . . . . . . . . . . . . . . . . . . . . .Michal Vacek
10. kvetna 2007
PodekovanıRad bych podekoval Ing. Bohuslavu Krenovi, Ph.D., za pomoc s prıpravou bakalarske pracea take vsem zamestnancum spolecnosti Skoda Auto a. s., kterı se mnou na vyvoji aplikacespolupracovali.
c© Michal Vacek, 2007.Tato prace vznikla jako skolnı dılo na Vysokem ucenı technickem v Brne, Fakulte in-formacnıch technologiı. Prace je chranena autorskym zakonem a jejı uzitı bez udelenı opravnenıautorem je nezakonne, s vyjimkou zakonem definovanych prıpadu.
Obsah
1 Uvod 31.1 Optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Struktura bakalarske prace . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Specifikace zadanı 52.1 Vstupnı parametry pro optimalizaci . . . . . . . . . . . . . . . . . . . . . . 52.2 Omezenı a kriteria pri vypoctu optimalizace . . . . . . . . . . . . . . . . . . 6
2.2.1 Stohovatelnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.2 Vkladanı malych modulu do velkych . . . . . . . . . . . . . . . . . . 62.2.3 Ostatnı omezenı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Pozadavky na zobrazenı vysledku . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Prıbuzne optimalizacnı metody 73.1 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 Formalnı definice 0/1 knapsack problemu . . . . . . . . . . . . . . . 73.2 Bin-packing problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Navrh aplikace pro optimalizaci vcetne graficke reprezentace 94.1 Struktura souboru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1.1 Vstupnı soubory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.1.2 Vystupnı soubory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114.1.3 Konfiguracnı soubory . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Graficke uzivatelske rozhranı pro zıskanı pozadavku pro optimalizaci . . . . 114.2.1 Prehled jednotlivych castı . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Optimalizacnı program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.3.1 Vstupnı parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.3.2 Nactenı a uchovavanı dat behem vypoctu . . . . . . . . . . . . . . . 144.3.3 Princip vypoctu ulozenı materialu . . . . . . . . . . . . . . . . . . . 154.3.4 Ulozenı vysledku a ukoncenı programu . . . . . . . . . . . . . . . . . 16
4.4 Program pro zobrazenı kontejneru a jejich nalozenı . . . . . . . . . . . . . . 164.4.1 Prehled jednotlivych castı . . . . . . . . . . . . . . . . . . . . . . . . 184.4.2 3D zobrazenı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5 Implementace a testovanı 215.1 Adresarova struktura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2 Graficke uzivatelske rozhranı pro zıskanı pozadavku pro optimalizaci . . . . 225.3 Optimalizacnı program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.4 Program pro zobrazenı kontejneru a jejich nalozenı . . . . . . . . . . . . . . 23
1
5.4.1 Program pro 3D zobrazenı . . . . . . . . . . . . . . . . . . . . . . . . 245.5 Testovanı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.5.1 Vlastnosti optimalizacnıho algoritmu . . . . . . . . . . . . . . . . . . 25
6 Vysledky a moznosti dalsıho vyvoje 276.1 Splnenı pozadavku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276.2 Moznosti dalsıho vyvoje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276.3 Zaver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Literatura 28
A Tabulky 30
B Uzivatelsky manual 35
2
Kapitola 1
Uvod
Cılem prace je popsat aplikaci, kterou jsem vytvoril ve spolupraci se spolecnostı Skoda Autoa.s. (dale pouze Skoda). V teto spolecnosti vykonavam externı staz a dostal jsem moznostpropojit vyvoj optimalizacnı aplikace s mojı bakalarskou pracı. V tomto dokumentu jetedy popsan navrh a implementace vsech castı programu vcetne ovladanı a komunikaces vnitrnımi systemy Skody.
Spolecnost resı problem prepravy materialu z vyrobnıch hal v Ceske republice do montaz-nıch zavodu v zahranicı. Z ekonomickych duvodu, predevsım kvuli vysokym clum na hotovevyrobky v nekterych zemıch, se nevyplatı do danych statu vyvazet cela auta. V ruznemstupni rozlozenı se tak jednotlive soucastky balı do krabic nebo palet (oznacovanych dalejako moduly) a pote se posılajı do zahranicı v kontejnerech ci vagonech.
Preprava materialu je dosti nakladna a promıta se znacne v cene vsech vyrobku, problemvhodne vyuzıt nakladovy prostor proto trapı nejen expedicnı firmy po celem svete.
Ukolem tak bylo optimalizovat nalozenı kontejneru (resp. vagonu), neboli vypocıtatzpusob, jak jednotlive moduly v kontejneru nejlepe usporadat. A vysledek pote vhodnezobrazit. Detaily zadanı jsem shrnul v kapitole 2.
1.1 Optimalizace
Nejdrıve se podıvejme, co optimalizace vubec znamena. Jde vlastne o matematickou dis-ciplınu, ktera hleda minimum (resp. maximum) dane funkce f(x) na mnozine prıpustnychresenı M . Nekdy, stejne jako v nasem prıpade, pomahajı optimalizacnı ulohu resit tzv.podmınky optimality. Jde o podmınky, ktere musı platit pro optimalnı resenı, a slouzıpredevsım k redukci mnoziny prıpustnych resenı. [4] Takoveto podmınky nası optimalizacejsou popsany v podkapitole 2.2. Podmınky lze rozdelit na:
• nutne (musı splnovat kazde optimalnı resenı ulohy)
• postacujıcı (pokud je nejaky bod splnuje, automaticky jde o optimalnı resenı)
Optimalizaci a predevsım optimalizacnım metodam prıbuznym nasemu problemu se venujekapitola 3.
1.2 Struktura bakalarske prace
V nasledujıcıch kapitolach jsem popsal vyvoj aplikace (od navrhu az po implementacia testovanı), ktera ma zefektivnit cyklus balenı a nakladky materialu a predevsım snızit
3
naklady na jeho prepravu. Jelikoz aplikace jeste nedostala sve “jmeno”, pouzıvam docasnepracovnı oznacenı b2c, coz jsou pocatecnı pısmena anglickeho spojenı boxes to containers.Jednotlive kapitoly obsahem vıcemene kopırujı body zadanı bakalarske prace.
V prvnı kapitole 2 detailne specifikuji zadanı. Popısu zde problemy, ktere musı aplikaceresit, a pozadavky, ktere jsou na program kladeny ze strany Skody. Ve druhe kapitole trochuodbocım. Projdu prıbuzne metody, ktere se rovnez zabyvajı problemem kombinacnı opti-malizace, zejmena Knapsack a bin-packing problem. Tım vytvorım dostatecnou teoretickoupudu pro vytvorenı vlastnıho optimalizacnıho algoritmu.
Dalsı dve kapitoly se zabyvajı navrhem (viz. kapitola 4), resp. implementacı (viz. kapi-tola 5) aplikace. Tvorı hlavnı cast bakalarske prace a jsou v nich popsany vsechny castiaplikace, zpusob, jakym byly vytvoreny, a funkce, ktere zastavajı. Popısu zde take princip,jakym je optimalizace vypocıtavana a zahrnuta bude take podkapitola venujıcı se testovanıa merenı vlastnostı aplikace.
V poslednı kapitole shrnu dosazene vysledky. Upresnım, do jake mıry se podarilo splnitpozadavky na aplikaci a jakym zpusobem je mozne program dale rozsirovat a vyvıjet.
Doplnujıcı tabulky a grafy s vyrazne popisnym charakterem jsem umıstil do prıloh.Nalezneme zde i uzivatelsky manual, ktery jsem k aplikaci vytvoril.
4
Kapitola 2
Specifikace zadanı
V teto kapitole budou analyzovany vsechny detaily zadanı, naroky, ktere musı aplikacesplnovat, a nastınena bude i struktura cele aplikace. Specifika zadanı jsem prubezne konzul-toval s odpovednymi lidmi ve Skode tak, aby program byl nasledne pouzitelny v praxi, a tokonkretne v expedicnıch halach V8 v Mlade Boleslavi.
Hlavnım pozadavkem Skody bylo rozdelit aplikaci na dve nezavisle casti. Jeden pro-gram ma optimalnı rozlozenı modulu v kontejneru vypocıtat a druhy ho vhodne zobrazit.Duvodem je moznost samostatne obsluhy obou castı. Prvnı (optimalizacnı) program budouobsluhovat lide, kterı vytvarı balıcı plan pro expedici. Zatımco druhy (zobrazovacı) programbudou pouzıvat zejmena lide, kterı material balı ci ho prımo nakladajı do kontejneru.
Z tohoto rozdelenı vyplyva i prvnı otazka: jak spolu oba dva programy majı komuniko-vat?! Zvolen byl ten nejjednodussı zpusob. Optimalizacnı program vysledky ulozı do souborua zobrazovacı program jej odtud bude cıst. Tato varianta byla vybrana i s ohledem nahlavnı pozadavek Skody, aby cela aplikace jakymkoliv zpusobem nezasahovala do vnitrnıchsystemu spolecnosti, a veskera komunikace tak probıhala pouze na urovni ctenı/zapisu z/dosouboru.
2.1 Vstupnı parametry pro optimalizaci
Seznam materialu, ktery ma byt expedovan, je znam priblizne na 5 dnı dopredu. Kekazdemu materialu prıslusı modul, do ktereho se material balı. Seznam nejpouzıvanejsıchmodulu i s jejich rozmery je uveden v tabulce A.3. Dulezite je rozdelit material podle dne,kdy ma byt expedovan, a hlavne zavodu, kam ma byt poslan. Vsechna data jsou pak ulozenave vstupnıch souborech, strukturou souboru se zabyva sekce 4.1.1.
Dulezite je take zjistit, do jak velkeho kontejneru (resp. vagonu) ma byt materialnalozen, tedy pro jak velky prostor se ma optimalizace vypocıtat. Rozmery standartnıchkontejneru ci vagonu jsou znamy, ale pro ruzne necekane situace ci pro testovanı a dalsıvyvoj by mela byt moznost tyto rozmery zadat i rucne.
Dale mezi pozadavky byla doplnena moznost zadat mıru zaplnenı. V praxi nenı temermozne dosahnout 100 % zaplnenı kontejneru, tato mıra zaplnenı proto udava, jake zaplnenıje dostatecne pro ukoncenı optimalizacnıho vypoctu (touto aproximacı algoritmu se zabyvapodkapitola 4.3).
5
2.2 Omezenı a kriteria pri vypoctu optimalizace
Pri skladanı jednotlivych modulu do kontejneru narazıme na radu problemu. V teto pod-kapitole je uveden jejich strucny prehled, ktery do znacne mıry ovlivnuje samotny algorit-mus vypoctu.
2.2.1 Stohovatelnost
Zrejme nejvıce omezujıcım faktorem je hmotnost materialu ulozeneho v modulu a takekonstrukce onoho modulu. Nesmı totiz dojıt k pretızenı ci narusenı modulu umıstenychvespod kontejneru, aby nedoslo ke znehodnocenı materialu.
Pri skladanı jednotlivych modulu na sebe existuje jednoduche pravidlo. Na mensı bednunesmı prijıt vetsı z duvodu jejich nosnosti. I zde existujı vyjımky – system modulu GLT.Jedna se o vysokonosne bedny, ktere svymi rozmery do sebe “zapadajı”. Tyto moduly tvorıkostru celeho kontejneru, a jako jedine je lze stavet na sebe zpusobem, kdy pod velkoubednu prijdou 2 az 4 male. Prehled pravidel, jak lze takto moduly GLT stohovat je uvedenv tabulce A.1.
2.2.2 Vkladanı malych modulu do velkych
Jednım z resenı male nosnosti ostatnıch modulu je jejich vkladanı do GLT. V praxi sevkladajı nektere mensı moduly KLT a MOD primarne do GLT5754. Pouze pokud nenı dotohoto modulu dostatecny pocet kusu materialu, vkladajı se do GLT5755. Po kolika kusechse tyto moduly do GLT modulu vkladajı je uvedeno v tabulce A.2. Zbyle moduly, kterychnenı dostatecny pocet, se pouzıvajı k vyplnenı vrchnıch mıst v kontejneru.
2.2.3 Ostatnı omezenı
Dalsım zajımavym problemem byla moznost rotace modulu, ty se totiz mohou otacet pouzepodle y osy, tedy nikoliv prevracet. Duvod je zrejmy, nesmı dojıt k poskozenı materialuuvnitr.
Mezi poslednı pozadavek Skody patrı moznost bezproblemoveho nalozenı danych moduludo kontejneru. Dvere kontejneru nesahajı pres jeho celou celnı stranu, ale odzhora chybıpriblizne 20 cm. Tudız nelze v poslednıch dvou metrech kontejneru skladat moduly az kestropu, vysokozdvizny vozık by se tam nedostal. Tento problem odpada u vagonu, ktere senakladajı ze strany.
2.3 Pozadavky na zobrazenı vysledku
Pri zobrazenı vysledku, tedy rozlozenı modulu v kontejneru, je kladen duraz predevsım naprehlednost. Program by mel jednoduse zobrazit jednotlive moduly a postupne znazornitjejich umıstenı do kontejneru. Take musı zobrazit veskere dostupne informace o danemmodulu a materialu v nem, aby byla mozna jejich snadna identifikace. Program by si melpamatovat vsechny dosud nevyexpedovane kontejnery, ktere se identifikujı pomocı ID cısla(prideleno behem optimalizacnıho vypoctu).
6
Kapitola 3
Prıbuzne optimalizacnı metody
Nynı trochu odbocıme od naseho tematu. Podıvame se detailneji na ruzne problemy, kteremajı urcite podobne vlastnosti jako nase optimalizace. Algoritmy resıcı problem kombinacnıoptimalizace jsou charakteristicke tım, ze hledajı maximalnı ze vsech nabızenych moznostılimitovane nejakym omezenım. Mezi nejznamejsı patrı Knapsack nebo Bin-packing prob-lem. Pro mnohe optimalizacnı problemy je vsak obtızne navrhnout algoritmy, ktere je vyresıoptimalne a zaroven rychle (napr. pro NP-uplne problemy). V takovem prıpade studujemetzv. aproximacnı algoritmy, ktere pracujı rychle, a najdou resenı vıce ci mene blızke op-timalnımu resenı. Takoveto aproximace vyuzıva i algoritmus, ktery jsem pro vypocet pouzil(viz. podkapitola 4.3)
3.1 Knapsack
Mezi nejzajımavejsı prıklady kombinacnıch algoritmu patrı Knapsack problem, v cestinetez oznacovan jako problem batohu. Jedna se o libovolne presne aproximovatelny problem.Zjednodusene receno vybırame z kolekce polozek, z nichz kazde ma svoji vahu a hodnotu,jejich nejlepsı kombinaci, ktera se vejde do vymezeneho prostoru (jiz zminovane omezenı),a pritom hodnota slozek bude co mozna nejvetsı.
Mezi zakladnı verze patrı tzv. 0/1 knapsack problem. Zde pocet jednotlivych polozekmuze nabyvat pouze hodnot nula nebo jedna, tedy bud’ je v resenı polozka zahrnuta nebonenı. Pokud omezıme pocet polozek nejakym cıslem, mluvıme o bounded knapsack problem.
3.1.1 Formalnı definice 0/1 knapsack problemu
Mejme n polozek a m uloznych prostoru,
• pi,j hodnota polozky j v prostoru i
• wi,j vaha polozky j v prostoru i
• ci kapacita prostoru i.
7
Hledame vektor
x = x1, x2, . . . , xn ∈ {0, 1}n, kde xj = 1, pokud je prvek zvolen, (3.1)f(x) = (f1(x), f2(x), . . . , fm(x)) je maximum, kde (3.2)
fi(x) =n∑
j=1
pi,j ∗ xj , a kde (3.3)
∨i ∈ 1, 2, . . . , m :n∑
j=1
wi,j ∗ xj ≤ ci. (3.4)
Slozitost resenı knapsack problemu pote zalezı na kapacite jednotlivych uloznych pros-toru. Pro testovanı a porovnavanı rychlostı jednotlivych algoritmu se pouzıva obecne hod-nota ci = 0.5
∑nj=1 wi,j . [2]
Resenı muze probıhat mnoha metodami. Od “hrube sıly”, kdy se neustale zjist’ujelepsı vyber polozek. Po resenı heuristikou podle pomeru hodnota/vaha. Ta je dıky mensıasymptoticke slozitosti pouzitelna i pro instance s vetsım poctem prvku. Danou heuristikumuzeme jeste rozsırit o tzv. testovanı nejcennejsı veci.
3.2 Bin-packing problem
Pomocı bin-packing problemu zkousıme minimalizovat pocet uloznych prostoru (tzv. bins)potrebnych k nalozenı urciteho poctu polozek. Otazku lze take ovsem pojmout z opacnehopohledu, pokusit se do jednoho ulozneho prostoru naskladat co nejvıce polozek, resp. conejlepe vyplnit dany prostor.
Prave tato varianta ma mnoho spolecneho s nası optimalizacı a tudız si ji detailnejirozebereme. Mejme bin a mnozinu krabic, jejichz celkovy objem je vetsı nez objem uloznehoprostoru. Ukol je vybrat podmozinu danych krabic a rozmıstit ji do prostoru tak, aby zabralaco nejvıce mısta. Pokud V je objem prostoru a Vb je celkovy objem vsech krabic, vyuzitıkazde krabice je potom Vb/V . V zavislosti na poctu rozmeru krabic a prostoru pote hovorımeo 2D bin-packing (pokud majı pouze sırku a vysku) nebo o 3D bin-packing problemu (pokudmajı i hloubku). V prvnım prıpade se jedna v podstate o mnozinu obdelnıku, ve druhempak o mnozinu kvadru. Zde umyslne vynechavam moznosti, kdy se nejedna o symetricketvary, jelikoz zde je vypocet jeste daleko narocnejsı. [1]
Algoritmus vypoctu je zalozen na neustalem pridavanı a odebıranı krabic do uloznehoprostoru, casto k tomu vyuzıva rekurzi. Pokud bychom nechali probehnout algoritmus cely,tzn. nasel by vsechny moznosti, jak polozky do prostoru umıstit, jednoduse bychom z nichvybrali tu nejlepsı. V nasem prıpade tu, ktera zabrala nejvıce mısta. Ovsem jsou zde dvaproblemy. Kam umıstit prvnı polozku, od ktere se cely vypocet provadı?! Pokud bychomzkouseli umıstit do daneho prostoru vsechny polozky (coz bychom museli, pokud chcemezjistit vsechny moznosti rozlozenı), a pritom je zkouseli postupne umıstit do vsech castıprostoru, jiz pri pomerne malem poctu polozek by byl vypocet neunosne casove narocny.Zde prichazı na radu jiz zminovana aproximace. Nejefektivnejsı mısto, kde vypocet zacıt,je jeden z rohu ulozneho prostoru. Tım snızıme narocnost vypoctu.
Druhy problem ovsem muze byt, ze pokud mame nekolik tisıc polozek (jako naprıkladv nasem prıpade), vypocet bude trvat i tak prılis dlouho. Druhou aproximacı muze bytstanovenı urcite urovne, kdy lze povazovat resenı za dostatecne. Ovsem to uz nemusı bytnejlepsı mozne.
8
Kapitola 4
Navrh aplikace pro optimalizacivcetne graficke reprezentace
V teto kapitole budou detailne popsany jednotlive casti aplikace, jejich funkce a vzajemnakomunikace, zejmena z pohledu uzivatele. Popsano bude chovanı i ovladanı aplikace. Jakjiz bylo naznaceno v popisu pozadavku, aplikace je rozdelena do dvou na sobe nezavislychcastı.
S ohledem na obecnost aplikace a moznost jejıho pozdejsıho sirsıho vyzitı byla jesteoptimalizacnı cast rozdelena na dalsı dva celky. Kostru aplikace tak tvorı samotny opti-malizacnı program b2c.exe, ktery provadı vlastnı vypocet ulozenı materialu v kontejneru.K tomu vyuzıva vsechny vstupnı soubory, ktere jsou popsany v sekci 4.1.1 a vysledek ukladado souboru res.dat. Nadstavbou tohoto programu je graficke uzivatelske rozhranı, ktereslouzı k jednoduchemu zıskanı parametru od uzivatele. Vypoctenou optimalizaci nasledneprogram b2cII.jar zobrazı. Cely optimalizacnı cyklus vcetne zobrazenı je znazornen naobrazku 4.1.
4.1 Struktura souboru
Veskera komunikace jak mezi jednotlivymi castmi, tak mezi samotnou aplikacı a vnitrnımisystemy Skody, probıha pomocı souboru. V teto podkapitole budou detailne popsany struk-tury jednotlivych souboru, ktere jsou pro cinnost aplikace nezbytne. Rozdelit bychom jemohli do trı kategoriı. Prvnı tvorı vstupnı soubory, ktere obsahujı vstupnı data pro op-timalizaci. Druhou pote vystupnı soubory, kde jsou ulozeny vysledky, a poslednı kategoriitvorı konfiguracnı soubory, ktere obsahujı potrebne informace pro cinnost jednotlivych castıaplikace.
4.1.1 Vstupnı soubory
Nejdulezitejsı vstupnı soubor je EXP_H_TETRIS.txt. Obsahuje jiz zminovany seznam ma-terialu, ktery je v danou chvıli mozne zahrnout do vypoctu rozlozenı. Prıklad obsahu tohotosouboru je v tabulce A.4. Soubor obsahuje:
• kod zavodu, kam je material expedovan
• den, kdy ma byt material expedovan, a kod smeny
• kod materialu
9
EXP_H_TETRIS.TXT
EXP_THI_MODUL.txt
MODULS.DAT
CONFIG.XML
GRAFICKÉ ROZHRANÍ
OPTIMALIZAČNÍ APLIKACE
ZOBRAZENÍ
RES.DAT
USED.DAT
UNUSED.DAT BCONFIG.DAT
VÝSTUPNÍ SOUBORY:
VSTUPNÍ SOUBORY:
Obrazek 4.1: Struktura optimalizacnı cyklu
• pocet kusu
• zavesku (tj. cıslo krabice slouzıcı k identifikaci)
• hmotnost jednoho kusu materialu
Po zpracovanı techto informacı, vybranı odpovıdajıcıch materialu, je nutne jednotlivekody “rozlustit”, abychom vedeli, do jakych modulu je material balen – tedy naprıkladkolik zabıra mısta. K tomu slouzı dalsı dva soubory EXP_H_MODUL.txt a moduls.dat.V prvnım jmenovanem souboru je cıslovany popis postupu balenı jednotlivych materialurazeny vzestupne, znazorneno v tabulce A.5. Tento “oficialnı” (nesnadno pochopitelny)popis zjednodusene znamena, ze v souboru lze nalest postup, jak s jednotlivymi materialyzachazet, do ceho je postupne ukladat a naprıklad jake bezpecnostnı folie pouzıt. Na koncitohoto cyklu je pochopitelne uveden i modul, ve kterem je material prevazen (a prave tenje dulezity). Jelikoz je tento seznam razen vzestupne (opacne nez se balı), pro nasi optima-lizacnı aplikaci je potrebna pouze prvnı polozka. Rozmery a nosnost jednotlivych moduluje popsana v druhem souboru moduls.dat (viz. tabulka A.3).
Po zpracovanı souboru EXP_H_TETRIS.txt, a dohledanı vsech potrebnych informacıv dalsıch dvou souborech, zıskame uplny seznam modulu a materialu v nich, ze kterych
10
posleze pocıtame optimalnı rozlozenı v nakladovem prostoru. Jakym zpusobem se z jed-notlivych souboru ctou udaje a v jakem poradı se zabyva podkapitola 4.3.
4.1.2 Vystupnı soubory
V techto souborech jsou uvadeny vysledky optimalizacnıho vypoctu. Hlavnım souborem jeres.dat. Jde o soubor, do ktereho optimalizacnı program ulozı vypocıtane rozlozenı moduluv kontejneru. Soubor pote vyuzıva zobrazovacı cast aplikace. Struktura tohoto souboru jepopsana v tabulce A.6.
Mimo tento soubor se pri vypoctu ulozenı materialu vytvorı jeste dalsı tri soubory, dokterych je rozdelen material ze vstupnıho souboru EXP_H_TETRIS.txt. Jedna se o souboryused.dat, unused.dat a error.dat. Jak nazev napovıda, soubor used.dat slouzı k ulozenıinformacı o materialu, ktery byl pouzit pri vypoctu optimalizace, a je jiz ulozen v nejakemkontejneru. Soubor slouzı predevsım pro kontrolu. S tımto materialem se jiz nesmı v dalsımcyklu optimalizace pocıtat.
Druhy soubor unused.dat obsahuje naopak material, ktery nebyl vhodnym zpusobemnalozen do kontejneru, a musı tedy byt zahrnut do vypoctu v dalsım cyklu. Data se tamprakticky ukladajı prubezne a na konci vypoctu aktualnıho cyklu optimalizace jsou veskerematerialy z tohoto souboru nakopırovany zpet do vstupnıho souboru EXP_H_TETRIS.txt.
Poslednı soubor z teto skupiny error.dat obsahuje material, pro ktery nebyly prinacıtanı dohledany vsechny potrebne informace, a neslo ho tedy zaradit do vypoctu. Vet-sinou se jedna o doplnkovy material. Tento problem si budou pracovnıci resit sami. Dodalsıho cyklu vypoctu se tak tento material jiz nezarazuje.
4.1.3 Konfiguracnı soubory
Aplikace obsahuje dva konfiguracnı soubory. Prvnı, config.xml, slouzı prımo optimalizac-nımu programu. Obsahuje pouze poradove cıslo kontejneru, pro ktery probehne dalsı cyklusvypoctu. Po domluve bylo zvoleno 7-mi mıstne cıslo, tedy zacatek na 1 000 000.
Druhy konfiguracnı soubor bconfig.dat slouzı k ulozenı vsech dosud nevyexpedovanychkontejneru. Struktura tohoto souboru je shodna se souborem res.dat. Rozdelenı do dvousouboru je predevsım z duvodu bezpecnosti. Zatımco res.dat pouzıvajı dva programy, kdejeden do neho zapisuje a druhy z neho cte, bconfig.dat slouzı pouze zobrazovacı castiaplikace.
4.2 Graficke uzivatelske rozhranı pro zıskanı pozadavku prooptimalizaci
Tento program slouzı ke snadnemu zıskanı kriteriı pro vypocet optimalizace. Hlavnı jehofunkcı je spustit se spravnymi parametry probram b2c.exe, ktery prımo provadı vypocet.Ukazka rozhranı je uvedena na obrazku 4.2. a popis jednotlivych castı je v nasledujıcı sekci4.2.1 Po spustenı, ktere lze jednoduse provest pres zastupce b2c.lnk, je otevreno oknoo velikosti 350 × 350 pixelu s nazvem Optimalizacnı aplikace.
4.2.1 Prehled jednotlivych castı
V hornı casti okna je umısteno menu, ktere obsahuje ovsem pouze tlacıtko pro uzavrenı.Jine moznosti nejsou potrebne. Menu jsem se rozhodl ponechat kvuli uzivatelum, kterı jsou
11
Obrazek 4.2: Screenshot rozhranı pro zıskanı pozadavku pro optimalizaci
na tuto moznost ukoncenı programu zvyklı. Dale samotne okno obsahuje tri rolovacı listy.Prvnı skryva vsechny dny v tydnu (Pondelı az Nedele). Zvolena kolonka oznacuje den, proktery se ma optimalizace vypocıtat. Lze vypocıtat optimalizaci dopredu, maximalne vsako tyden, jelikoz program nerozlisuje datum, ale pouze den. Rozlisenı data je v tomto prıpadezbytecne, protoze balıcı plan je vytvaren maximalne nekolik dnı dopredu, tudız vıce nez natyden dopredu by stejne nebyl znam potrebny material.
Druhy rolovacı seznam obsahuje vsechny (dosud zname) montaznı zavody, do kterychse muze dany kontejner posılat. Pokud je vybran zavod z nabıdky, v polıcku pod listboxemse zobrazı kod zavodu (napr. “74” pro Ukrajinu). Pokud je treba zadat jiny zavod, lzev seznamu zvolit moznost “. . . jiny zavod”. Jiz zminovane polıcko pod rolovacı listou sezaktivnı a lze do neho napsat kod zavodu rucne.
Poslednı seznam obsahuje nekolik beznych typu kontejneru a vagonu, ktere se pouzıvajıpro prepravu materialu. Tato rolovacı lista je propojena se tremi polıcky pod nı, takze pozvolenı nejake moznosti se zobrazı i velikost daneho nakladoveho prostoru. Pokud v sez-namu nenı potrebny kontejner, lze zadat opet moznost “. . . jiny rozmer” a do polıcek podseznamem vyplnit pozadovanou velikost rucne. Velikost nakladoveho prostoru je v centime-trech, to platı i pro zadavanı velikosti rucne! Byla take stanovena hornı hranice velikostinakladoveho prostoru a to na 100 m ve vsech trech rozmerech, coz je vıce nez postacujıcı.Pokud nenı zadana hodnota jakehokoliv rozmeru v intervalu 0 – 10 000 cm nebo cıslo ob-sahuje chybny znak, naprıklad pısmeno, program upozornı uzivatele varovnou hlaskou 4.4.V takovem prıpade nelze pokracovat ve vypoctu, dokud nenı chyba odstranena.
Po vyplnenı vsech polıcek lze stisknout tlacıtko “Spustit”, ktere spustı samotny opti-malizacnı program se zadanymi parametry 4.3.1. Behem vypoctu nelze jakkoliv programovladat. Na uspesne ukoncenı vypoctu upozornı hlaska 4.3, ktera obsahuje cıslo kontejneru
12
Obrazek 4.3: Hlaska pri ukoncenı vypoctu
Obrazek 4.4: Varovna hlaska
a jeho procentualnı zaplnenı. Dana optimalizace je jiz ulozena v souboru res.dat a lze jizobrazit.
Pokud vsechny zadane parametry jsou syntakticky spravne, avsak z nejakeho duvodunelze rozlozenı vypocıtat, zobrazı se informacnı hlaska 4.5. K tomuto muze dojıt naprıklad,pokud nenı dostatecne mnozstvı materialu, ci pokud nelze material vhodnym zpusobemusporadat.
4.3 Optimalizacnı program
Tato podkapitola se zabyva jadrem celeho projektu, a to programem, ktery vypocıtavarozlozenı modulu ve zvolenem nakladovem prostoru. Mimo zpusobu, jakym ma byt programspusten, zde naleznete zakladnı principy, jak program pracuje.
Obrazek 4.5: Informacnı hlaska pri neprovedenı optimalizace
13
4.3.1 Vstupnı parametry
Optimalizacnı program b2c.exe je spousten s mnoha parametry. Vetsina z nich jsou poza-davky uzivatelu na provedenı vypoctu. Jine jsou nastaveny grafickym rozhranım na stalestejnou hodnotu. Takove parametry na prvnı pohled nejsou vubec potrebne, dodany tamvsak byly z duvodu moznosti dalsıho vyuzitı a rozvoje samotneho optimalizacnıho programu(viz. kapitola 6.2).
Po spustenı jsou vsechny parametry precteny funkcı getParams() a jsou ulozeny dostruktury params tak, aby k nim byl behem celeho procesu vypoctu mozny prıstup. Pokudpro spustenı nepouzijeme graficke uzivatelske rozhranı, lze program spustit take s para-metrem -h, tzn. ./b2c.exe -h. Tım se vypıse obrazovka s napovedou, jak lze jednotliveparametry zadat a co znamenajı (viz. tabulka 4.1).
Prıklad pouzitı: b2c.exe -pocet_dnu (PO-NE) mira_uspesnosti -kontrola_vysledkucislo_zavodu cislo_kontejneru velikost_x velikost_y velikost_z-pocet_kontejneru.
Parametr Popis–pocet dnu pocet dnu, ktere se majı vypocıtat(PO-NE) seznam pozadovanych dnumira uspesnosti urcuje, kdy lze ukoncit vypocet–kontrola vysledku pozadavek, zda se ma pred ukoncenım odsouhlasit vysledek zaplnenıcislo zavodu cıslo zavodu, kam se material posılacislo kontejneru poradove cıslo kontejneruvelikost x sırka nakladoveho prostoru v cmvelikost y vyska nakladoveho prostoru v cmvelikost z hloubka nakladoveho prostoru v cm–pocet kontejneru pocet kontejneru, ktere se majı vypocıtat
Tabulka 4.1: Popis vstupnıch parametru
Jak je patrne z pozadavku Skody, vypocıtava se v danou chvıli pouze jeden kontejnera vysledek se nekontroluje. Prave v techto oblastech je predpoklad dalsıho vyvoje aplikace.Program s temito moznostmi vsak jiz pracuje a je mozne jej plne vyuzıvat napr. pri testovanıci vyzkumu.
4.3.2 Nactenı a uchovavanı dat behem vypoctu
Po zpracovanı parametru dojde k nactenı informacı o materialu funkcı readData(). Behemvypoctu musı byt vsechny informace neustale k dispozici. Byly proto vytvoreny dva sez-namy, jejichz struktury vcetne jednotlivych slozek jsou ulozeny v hlavickovem souborub2c.h.
Prvnı seznam obsahuje vsechny moduly, se kterymi lze pri vypoctu pocıtat. Kazdymodul je zde reprezentovan strukturou, ktera je znazornena v tabulce 4.2 vcetne popisujednotlivych polozek. Uchovavany tak jsou veskere potrebne informace o materialu. Prozrychlenı vypoctu jsou polozky v seznamu razeny podle velikosti od nejvetsıch po nejmensı.Bylo take nutne rozhodnout, jake datove typy budou postacujıcı pro dane polozky. U vetsinycıselnych hodnot byl pouzit unsigned int, ktery svym rozsahem je vıce nez dostacujıcı,napr. pro zavesku ci vahu modulu.
14
Polozka struktury Popisunsigned int zaveska zaveska slouzı k identifikaci moduluchar matnb[19] kod materialu v modulutsize size velikost modulu, vnorena struktura obsahuje tri rozmeryunsigned int weight vaha modulu vcetne materialuunsigned int max load nosnost moduluint rotation prıznak otocenı modulutsize point umıstenı v kontejneruunsigned int capacity objem moduluint used prıznak pouzitı modulu pri vypoctuchar modul[10] oznacenı moduluint counting prıznak zapocıtanı do vysledkuchar fullstring[64] cely retezec s parametry pro snadne vypisovanıint pocetbal pocet balenı materialutwrap wrap obsahuje pocet a nazev vlozenych modulu
Tabulka 4.2: Struktura box
Druhy seznam obsahuje ukazatele na polozky prvnıho seznamu, ktere jsou v danou chvılipouzity v kontejneru (viz. sekce 4.3.3). Cely vypocet je provaden rekurzı, tudız je nutneznat poradı, v jakem se moduly vkladajı do kontejneru, aby v prıpade neuspesneho vypoctumohly byt zase jednotlive odebırany.
4.3.3 Princip vypoctu ulozenı materialu
V teto sekci bude popsan zakladnı princip vypoctu optimalizace. Po zpracovanı parametrua vytvorenı seznamu s informacemi o jednotlivych modulech, zavola hlavnı funkce main()funkci optimalization(). Teto funkci je jako parametr predan mimojine ukazatel na da-tovy typ tspace, ve kterem jsou ulozeny informace o nakladovem prostoru, do ktereho seoptimalizace vypocıtava.
Funkce v hlavnım cyklu “bere” jednotlive polozky ze seznamu (4.2) a “vklada” je dodaneho prostoru (do leveho spodnıho rohu). Zda lze opravdu modul do prostoru vlozit, kon-troluje funkce checkbox(). Pokud muze dojıt k vlozenı modulu do prostoru, vytvorı se dalsıtri imaginarnı nakladove prostory, alokujı se tri datove typy tspace, a vyplnı se hodnotami.Jeden nad danym modulem, druhy vedle a tretı pred nım (obrazek 4.6).Jak jiz bylo receno,algoritmus funguje na principu rekurze, tudız v tomto mıste funkce optimalization() volasama sebe. V podstate se vola prave trikrat, jako parametr ji je totiz predan pokazde jedenz nove vytvorenych prostoru. Takto dojde k rozdelenı kontejneru na male casti, do kterychjsou vkladany jednotlive moduly.
Pokud ve vrchnıch patrech takto vytvorene pyramidy dojde k dostatecnemu zaplnenıkontejneru, vracı funkce do vrstvy pod sebou objem zaplneneho prostoru. Pokud k tomutonedojde, postupne se odebırajı z prostoru moduly, a funkce zkousı do daneho prostoru vlozitjiny modul a vypocet opakovat. Takto algoritmus probıha ve smycce dokud se nedosahnev celem kontejneru dostatecneho zaplnenı (zadaneho uzivatelem).
Jiz zminovana funkce checkbox() navıc behem testovanı, zda je modul mozne vlozitdo daneho prostoru, take zkouma, zda se nejedna o GLT modul. Tedy o modul, kterylze stohovat podle specifickych pravidel (viz. tabulka A.1). Pokud ano, vyzkousı moznosti
15
Obrazek 4.6: Rozlozenı prostoru v kontejneru
“podlozenı” modulu.Jak jsou jednotlive moduly ukladany do kontejneru, vytvarı se na ne ukazatele a vkladajı
se do druheho seznamu. Takto lze pote jednoduse moduly zase odebırat a mame neustaleprehled, ktere moduly jsou jiz do optimalizace zahrnuty a ktere ne.
4.3.4 Ulozenı vysledku a ukoncenı programu
Pokud vypocet probehne uspesne, tzn. mıra zaplnenı presahla pozadovanou hranici, je nutnevsechna data vhodne ulozit. To ma na starosti funkce saveResult(). Nejdrıve je nutne vsakprepocıtat pouzity material. Prochazı se oba seznamy a do souboru used.dat a unused.datjsou rozdelovany jednotlive moduly s materialem. K tomu slouzı funkce countingBoxes().
Drıve popsany zpusob ukladanı polozek do druheho seznamu s ukazateli naznacil, zetakoveto poradı modulu je vhodne pro vypocet. Ovsem pri zobrazenı by vznikl znacny chaos.Je proto nutne moduly preskladat.Nasledovat po sobe musı tak, jak by se optimalne skladalido kontejneru, tedy odzadu dopredu a odzdola nahoru. To zarizuje funkce rangeResults(),ktera vytvorı pomocny seznam a moduly prerovna. Nynı jiz muzeme vypocıtane rozmıstenımodulu v kontejneru ulozit do souboru res.dat. Nejdrıve jsou ulozeny vsechny informaceo nakladovem prostoru, pote seznam vsech modulu a jejich umıstenı. Prubezne funkceuvolnuje pamet’ alokovonanou slozkami seznamu. Na konci se uvolnı veskere alokovane sez-namy. Program jeste na standartnı vystup vytiskne mıru zaplnenı, kterou zobrazı grafickeuzivatelske rozhranı, a bezpecne se ukoncı.
4.4 Program pro zobrazenı kontejneru a jejich nalozenı
Tato podkapitola se zabyva zobrazenım vypocıtaneho rozlozenı modulu v kontejneru. Durazbyl kladen predevsım na prehlednost, aby pomocı programu bylo mozne prımo provadetnakladku kontejneru. Pro jednoduche spustenı byl vytvoren odkaz b2cII.lnk v hlavnımadresari. Po spustenı programu se otevre hlavnı okno, ktere je znazorneno na obrazku 4.7.Velikost okna je nastavena na 1024 × 735 pixelu, tedy na takovou velikost, aby se namonitorech s nejpouzıvanejsım rozlisenım 1024 × 768 px zobrazilo pres celou obrazovku.Z duvodu velikosti jednotlivych vnorenych castı, ktere jsou popsany v casti 4.4.1, nelzevelikost hlavnıho okna upravovat.
16
Obrazek 4.7: Screenshot programu pro zobrazovanı nalozenı kontejneru
17
4.4.1 Prehled jednotlivych castı
Okno s nazvem “Zobrazenı kontejneru” je rozdeleno do ctyr hlavnıch castı. Vlevo je umıstenstromovy seznam s aktualnımi kontejnery, ktere jeste nebyly vyexpedovany. Vsechny jsouoznacene svymi identifikacnımi cısly. Po kliknutı na cıslo kontejneru se polozka rozvine a ob-jevı se seznam vsech modulu, ktere po vypoctu optimalizace kontejner obsahuje. Toto je nej-jednodussı zpusob ovladanı. Aktivnı prvek, kontejner nebo modul, jsou oznaceny modrympodkladem.
Dalsı cast tvorı panel s nadpisem “Souhrne informace”. V nem se zobrazujı vsechnydulezite informace o prave aktivnım prvku v jiz zminovanem seznamu. Rozdelen je do dvoucastı, v hornı se zobrazujı informace o kontejneru a ve spodnı casti o aktualnım modulu.Pokud je aktivnı prvek v seznamu prımo kontejner, ve spodnı casti se samozrejme nicnezobrazuje. U kontejneru jsou zde informace o ID cısle, dnu, kdy ma byt odeslan, koduzavodu, kam je posılan, a jeho velikosti v centimetrech. Spodnı cast, zobrazujıcı informaceo aktivnım modulu, naopak zobrazuje zavesku, oznacenı modulu, velikost modulu, poceta druh vlozenych modulu, pokud nejake obsahuje.
Jednou z nejdulezitejsıch castı celeho programu jsou okna, kde se nalozenı kontejneruprımo zobrazuje. Jsou tri a jsou na sobe plne zavisla. Kazde vsak zobrazuje kontejnerz jineho pohledu. Prvnı mensı okno je umısteno uprostred v hornı casti a zobrazuje kontejnerzepredu, tzn. ze strany, kde jsou dvere. Dalsı dve vetsı okna jsou rozmıstena v dolnı castihlavnıho okna a ukazujı kontejner zprava, resp. zleva. Kde jsou dvere kontejneru znazornujesipka na strane. Vsechna okna navıc ve svych okrajovych castech obsahujı informace o smerupohledu, zvetsenı a velikosti kontejneru samotneho.
Kontejnery jsou zde znazorneny modre, nalozene moduly v nich zlute a poslednı(aktivnı) modul cervene. Pokud bychom najednou zobrazili vsechny moduly v kontejneru,ktere jsou jiz nalozene, nebylo by z obrazku mozne temer cokoliv vycıst. Zobrazujı setudız pouze moduly, ktere jsou bezprostredne nejblıze aktivnımu modulu. Pokud je modulnaprıklad ve vyssı vrstve, zobrazı se s nım pouze moduly pod nım.
Pro jeste lepsı znazornenı presneho umıstenı modulu v kontejneru, obsahuje programdalsı dve funkce. Jedna z nich je moznost zvetsenı pohledu. Velikost prvku v oknech sepote zvetsı, tudız zobrazı vetsı detail. Implicitne je pohled po zvetsenı zarovnan na aktivnımodul, tudız druhou dulezitou funkcı je moznost “pohybu” v zobrazovacıch oknech. Lzese pohybovat jednak po ose x, tzn. doprava a doleva, a take ve smeru osy y, tudız nahorua dolu. K pouzitı techto funkcı slouzı bud’ tlacıtka v ovladacım panelu (viz. dale) nebonabıdka menu v zalozce Zobrazenı. Jedine okno nepodlehajıcı temto upravam je hornı,ktere zobrazuje celnı pohled.
Poslednı castı je jiz zminovany ovladacı panel. Obsahuje tlacıtka pro posun v seznamus kontejnery (a to jak na dalsı modul, tak na dalsı kontejner a zpet). Zda se jedna o moznosttykajıcı se kontejneru nebo modulu, je zrejme z maleho c (z anglickeho container),resp. b (z anglickeho box ). Dale je zde tlacıtko pro aktualizaci seznamu, tzv. “Refresh”.Po stisknutı program zkontroluje soubor res.dat, zda od doby spustenı nedoslo k vypoctudalsıho kontejneru. Pokud ano, zaradı novy kontejner na konec aktualnıho seznamu kon-tejneru a lze ho zobrazit. Tlacıtko s oznacenım “Uzavrenı (vymazanı) kontejneru” slouzık ukoncenı balıcıho cyklu daneho kontejneru. Program kontejner vyradı ze seznamu a jiz hodale neuklada. Tudız dany kontejner jiz nelze zobrazit ani se k nemu nijak vracet. Ve spodnıcasti panelu jsou tlacıtka umoznujıcı jiz zminovany pohyb a zvetsovanı. K jednoduchemunavratu slouzı tlacıtko “Vychozı”, po jehoz stisknutı jsou kontejnery opet vykresleny v pu-vodnı velikosti a pozici.
18
Vsechny tyto moznosti, ktere obsahuje ovladacı panel, lze rovnez nalezt v menu. Toje tradicne umısteno v hornı casti okna a je rozdeleno do trı zakladnıch polozek: Soubor,Navigace a Zobrazenı.
4.4.2 3D zobrazenı
Velkym specifikem celeho programu je moznost zobrazenı ve 3D sıt’oveho modelu kontejneru.Jde o samostatny program spustitelny pomocı tlacıtka v ovladacım panelu “3D zobrazenı”.Skoda puvodne planovala zaradit tento program jako soucast svych aplikacı a vlastnı zobra-zovacı program, jak je popsan vyse, vubec nevytvaret. Zmena je ale zivot, navrh pozdejsıhozobrazovacıho programu jiz s moznostı 3D zobrazenı nepocıtal, predevsım pro jejı obtıznostorientace pri beznem pouzıvanı. Avsak zrejme bych aplikaci ochudil, kdybych moznost 3Dzobrazenı nezahrnul vubec.
Program je napsan v OpenGL. Pri zobrazenı vyuzıva soubor bconfig.dat, do kterehozobrazovacı program uklada seznam kontejneru. Pri spustenı zobrazı pouze jedno oknos danym kontejnerem. Ovladanı se provadı pomocı klavesnice, jak je popsano v tabulce 4.3.Pouze otacenı kolem zadnıho dolnıho bodu kontejneru se provadı pomocı stisknutı a pohybumysi.
Jako parametr pri spustenı program ocekava cıslo kontejneru, ktere se ma nacıst a in-dex aktivnıho modulu. Zobrazı tak kontejner shodne, jako vsechna tri okna zobrazovacıhoprogramu. Ukazka programu je znazornena na obrazku 4.8. Pri jakekoliv cinnosti v hlavnımokne zobrazovacıho programu, je okno 3D zobrazenı uzavreno.
Klavesa Popisf fullscreeng velikost okna 500 × 500 pxu vlozenı dalsıho modului odebranı poslednıho modulup vlozenı vsech moduluo vyprazdnenı kontejnerud pohyb dopravaa pohyb dolevaw pohyb nahorus pohyb doluq uzavrenı okna
Tabulka 4.3: Ovladanı programu pro 3D zobrazenı
19
Obrazek 4.8: Zobrazovanı pomocı 3D sıt’oveho modelu
20
Kapitola 5
Implementace a testovanı
Tato kapitola se zabyva popisem implementace cele aplikace, pouzitych nastroju a problemunavrhu, ktere bylo nutne vyresit ci ktere na vyresenı jeste cekajı. Prubezne bude zmınenpostup pri testovanı jednotlivych castı, ktery bude na zaver shrnut.
Graficke rozhranı pro zıskanı pozadavku i zobrazovacı program jsou napsany v jazyceJava. To prinası i urcita opatrenı, ktera jsou potrebna pro jejich bezproblemove spustenı,jako je napr. nutnost instalace Java Virtual Machine. To je v podstate software, kteryvystupuje jako hardwarove zarızenı a ktere prevadı bytovy kod (ktery vytvarı prekladacjazyku Java) do nativnıch instrukcı pro dany hostitelsky pocıtac. Zmıneny bytovy kod(nebo take pseudokod) je zjednodusene optimalizovana sada instrukcı. Velkou vyhodouje prenositelnost techto bytovych kodu [3]. Oba programy psane v Jave byly testovanyv prostredı Java 2, Standart Edition SKD (JDK 1.4).
Optimalizacnı program je pote napsan pomocı standartnıch knihoven v jazyku C a pro-gram umoznujıcı 3D zobrazenı nalozenı kontejneru pote jeste vyuzıva knihovny OpenGL.Oba tedy vyuzıvajı prekladac, ktery je zavisly na typu procesoru a nezrıdka i na operacnımsystemu. Prekladac ale vytvorı spustitelny kod, ktery je sobestacny. Nevyhodou je, ze taktovytvorene programy nelze prenaset do jinych prostredı. Na snade je tedy otazka, proc nejsouvsechny casti aplikace psane stejnym programovacım jazykem. Duvod je prosty, puvodnenemel mıt optimalizacnı program zadne graficke rozhranı, pres ktere by se zadavaly parame-try. Tedy bylo jedno, v jakem jazyce bude optimalizacnı program napsan a jazyk C se zdalpostacujıcı.
5.1 Adresarova struktura
Cela aplikace je vlozena do jedineho adresare. Ve Skode byl pro aplikaci urcen prostorv adresari \\skdambveot\eota$\eot6$\hala_U33. Prımo zde jsou dva zastupci b2c.lnka b2cII.lnk. Prvnı spustı graficke rozhranı pro zadavanı pozadavku, jak je popsano v pod-kapitole 4.2. Druhe pak zobrazovacı program popsany v podkapitole 4.4.
Ve slozce data jsou pote umısteny vsechny programy vcetne souboru potrebnych k jejichspustenı. Zatımco ve druhe slozce sources se nachazejı zdrojove kody.
21
5.2 Graficke uzivatelske rozhranı pro zıskanı pozadavku prooptimalizaci
Program byl implementovan podle navrhu popsanem v podkapitole 4.2. V teto podkapitolese detailneji podıvame na zpusob, jakym byl program vytvoren predevsım z pohledu pro-gramatora. Jak jiz bylo receno, je cely napsan v Jave. Graficke komponenty byly vytvorenypredevsım pomocı knihovny Swing definovane v balıcku javax.swing. Program tvorı tritrıdy. Trıda Main obsahuje pouze funkci main() a slouzı k zobrazenı hlavnıho okna pomocıfunkce run(). Hlavnı trıdou je tak BFrame, ktera se pak stara o vytvorenı a beh tohotookna.
Na zacatku vytvorı hlavnı ramec (frame), do ktereho umıstı vsechny komponenty jakjsou popsane v sekci 4.2.1. Rolovacı seznamy jsou vytvareny komponentou JComboBox,zatımco polıcka pro zadavanı naprıklad cıloveho montaznıho zavodu jsou vytvareny kompo-nentou JTextField. Po vytvorenı tototo okna je nejdulezitejsı spravne zachytavat vznikleudalosti. K tomu slouzı metoda actionPerformed(ActionEvent e), ktera naprıklad pristisknutı tlacıtka “Spustit” vola funkce, ktere vedou ke spustenı optimalizacnı aplikace. Jdepredevsım o funkci checkExe(), ktera nejprve kontroluje zadane parametry. Pokud nas-tane nejaka chyba, vypıse chybovou hlasku. Pote spustı optimalizacnı program a ceka naodpoved’.
Poslednı trıdou je BConfig. Konstruktor trıdy na zacatku nacte konfiguraci, tedy pre-devsım cıslo kontejneru, jehoz nalozenı bude optimalizovano. Dale se take stara o ulozenıaktualnı konfigurace naprıklad pri ukoncenı programu.
5.3 Optimalizacnı program
Optimalizacnı program byl implementovan podle navrhnu popsanem v podkapitole 4.3vcetne vsech zakladnıch principu. Jsou zde nastıneny i funkce a ovladanı programu. V tetopodkapitole bych se proto vıce venoval “bolavym mıstum”, ktere pri implementaci vznikly.
Nejvetsı z nich zrejme je, ze ackoliv kontrola pretızenı jednotlivych modulu v algoritmuje implementovana, lide ze Skody jeste nezjistili vahu vsech materialu. Nemohou je tedyuvadet u vsech polozek v souboru EXP_H_TETRIS.txt, a tudız je tato funkce z programuzatım vyclenena. Program tak vypocıtava rozlozenı pouze s ohledem na velikost modulua moznost jejich stohovanı. Tato skutecnost se samozrejme odrazila predevsım na dobevypoctu. Lze predpokladat, ze po zaclenenı teto funkce zpet vzroste cas, ktery je k vypoctupotreba. Nejde ani tak o samotnou funkci, ktera pretızenı kontroluje, ale predevsım o to,ze bude vyhovovat pro dane umıstenı mensı procento modulu, cili se vhodny modul budehledat dele.
Tım narazıme na dalsı problem. Jak stanovit dobu, po kterou je mozne na vysledekjeste cekat? Omezit program casove by bylo zrejme kratkozrake, jelikoz by pote na kazdemtypu procesoru provedl jiny pocet rekurzı. Omezen je tedy pocet rekurzı, ktery algoritmusprovede. V globalnı promenne timer je inkrementovana hodnota pokazdem volanı funkceoptimalization(), zaroven je v tuto chvıli i dana promenna porovnavana s promennouTIMER, ve ktere je ulozena hodnota udavajıcı maximalnı pocet rekurzı. V nasem prıpadestanovena na 20 000 000 a v prıpade prekrocenı teto hodnoty provede program nezbytnekroky a ukoncı se. Jak je videt pri testovanı z tabulky A.8, kde je prehled vysledku testovanı,je to vıce nez postacujıcı hodnota. Po zaclenenı kontroly pretızenı modulu bude nutnehodnotu opet uvazit, ale myslım si, ze i pote bude 20 mil. postacovat.
22
5.4 Program pro zobrazenı kontejneru a jejich nalozenı
Tato cast aplikace je zrejme nejvetsı, co se tyce radku kodu. Napsana je v jazyce Java.Obsahuje celkem 16 trıd, ktere se starajı o bezproblemovy beh programu, a jsou vsechnyumısteny v balıku b2cii, coz odpovıda i organizaci adresare se zdrojovymi kody. Vstupnıbod do programu je trıda Main, ktera obsahuje metodu main(). Jak bylo popsano v podkapi-tole 4.4, hlavnı okno aplikace obsahuje nekolik prvku. Kazda komponenta je pote ovladanasamostatnou trıdou, ktera obsahuje vsechny potrebne metody.
Nez si vsak ukazeme trıdy, ktere jsou v programu “videt”, je dulezite popsat dve trıdy,se kterymi ostatnı neustale pracujı. Jedna se o trıdy BContainer a BBox. Instance techtotrıd tvorı uzly stromoveho seznamu s kontejnery a obsahujı vsechny potrebne informaceo kontejneru ci modulu.
Hlavnı trıdou programu pak je BMainWindow. Jejı konstruktor vytvorı nejprve hlavnıokno a upravı jeho nastavenı. Deklaruje promenne objektovych typu, pomocı operatorunew vytvorı a prida postupne vsechny objekty, ktere si dale jednotlive rozebereme. Jednouz nejdulezitejsıch funkcı teto trıdy je prave propojenı onech objektu. Pokud v seznamukontejneru dojde k zachycenı udalosti, naprıklad posunu aktivnıho prvku, tato trıda zajistı,aby se dana zmena projevila i v zobrazovacıch oknech. K tomu obsahuje trıda metodysetCont() na nastavenı aktivnıho kontejneru a setBox() na vykreslenı modulu. Trıda sedale take metodou saveConfig() stara o ukladanı aktualnıho stavu seznamu kontejneru cimetodou Refresh() o zjistenı nove vypocıtanych kontejneru.
A nynı si projdeme jednotlive objekty. Trıda BMenuBar vytvarı listu menu. Z deklaracetrıdy je patrne, ze “rozsiruje” trıdu JPanel z knihovny Swing. Konstruktor vytvorı novouinstanci trıdy JMenuBar a postupne do nı vlozı vsechny zalozky. Pomocı rozhranıActionListener jsou zde zachytavany udalosti, tedy v nasem prıpade kliknutı tlacıtka mysina nejakou nabıdku v menu. O “obslouzenı” takoveto udalosti se stara metodaactionPerformed().
Dalsı komponentou v programu je stromovy seznam kontejneru obsahujıcı i dane mo-duly. O vytvorenı tohoto objektu se stara konstruktor trıdy BTreeStruct. Na zacatku do-jde k nactenı dat ze souboru bconfig.dat a res.dat pomocı stejne metody readData(),protoze oba soubory majı shodnou strukturu. Jednotlive radky souboru se musı rozdelitna jednotliva slova reprezentujıcı ruzne informace. K tomu je vyuzıvana instance trıdyStringTokenizer a jejı metoda hasMoreTokens(). Postupne jsou data ukladana do da-tovych typu BContainer ci BBox a ty jsou pouzity k vytvorenı uzlu stromu (datovy typDefaultMutableTreeNode), ktere jsou nakonci ukladany do instance trıdy JTree. Uzly repre-zentujıcı kontejnery obsahujı tak pote jeste tzv. “listy”, ktere reprezentujı jednotlive modulyv kontejneru. Tento “strom” je pote vlozen prımo do objektu BTreeStruct, cımz se zobrazıdany stromovy seznam. Trıda BTreeStruct dale jeste obsahuje metodu changeValue(),ktera obsluhuje vznikle udalosti, a take radu metod, ktere se starajı o posouvanı aktivnıhoprvku ci smazanı uzlu ve stromove strukture.
Dany aktivnı prvek je pote dulezity pro cely program, jelikoz se jedna o aktualnı modul,ktery se ma nalozit do kontejneru (nebo prımo o samotny kontejner). Informace o takovemtoprvku jsou zobrazovany v informacnım panelu, ktery je tvoren dvema castmi. Prvnı, kterazobrazuje informace o kontejneru, je objekt trıdy BContPanel. Druha, zobrazujıcı modul,je pote instance trıdy BBoxPanel. V podstate majı stejnou ulohu. V konstruktorech jsoudo instance trıdy JPanel, ktera je umıstena v hlavnım ramci, vlozeny vsechny komponentya nastaveny vlastnosti zobrazenı, jak je uvedeno v sekci 4.4.1. Dulezitou roli zde ale hrajımetody setCont, resp. setBox, ktere do polıcek v panelu vkladajı prıslusny text, ktery se
23
tyka aktualnıho prvku (uzlu) v seznamu kontejneru. Volany jsou z hlavnı trıdy programuBMainWindow vzdy, kdyz dojde k nejake zmene.
Nejdulezitejsı cast programu jsou okna, ve kterych se znazornuje nalozenı kontejneru.Kazde okno je popsano v jedne trıde. Hornı, ktere znazornuje nalozenı kontejneru z celnıhopohledu, je instancı trıdy BCenterView. Spodnı okna s bocnımi pohledy pak trıdyBRightView, resp. BLeftView. Nejdrıve si popıseme hornı okno, ktere je z nich nejjednodussı,zobrazuje totiz nalozenı pouze ve 2D prostoru. Konstruktor trıdy pouze nastavı pozadı oknana bılou barvu. Vykreslovacı metody jsou metody trıdy Canvas, kterou trıda BCenterViewrozsiruje. Jedna se predevsım o metodu paint(Graphics g), ktera nejprve zjistı, jaky kon-tejner se ma vykreslit. Do promenne pomer ulozı pomer sırky kontejneru k sırce okna (nebovysky kontejneru k vysce okna v zavislosti na tvaru kontejneru), toto dulezite cıslo se potepouzıva k urcenı velikosti vsech modulu uvnitr. Dale prochazı pozpatku stromovy sez-nam kontejneru a od aktivnıho modulu vykresluje vsechny moduly nalozene prednım. Tımdocılıme lepsı nazornosti, kam ma dany modul prijıt. Moduly se vykreslujı pomocı metodydraw2DBox. Metoda draw2DCont pote slouzı k vykreslenı kontejneru, metodyvykreslitUdaje() a vykreslitVelikost() k zobrazenı udaju o vlastnostech do okrajuokna.
Dalsı dve jiz zminovane trıdy BLeftView a BRightView jsou v mnohem hodne podobnetrıde BCenterView. Princip zobrazovanı je shodny, pouze pomocı 2D primitiv (vetsinoujednoduchych car) je zobrazovana 3D perspektiva. Kontejner je navıc vykreslovan nadva-krat, zadnı strana se zobrazuje pred vykreslovanım modulu, prednı az po nem. Aby nedoslok nezadoucım prekryvum. Trıdy navıc obsahujı metody pro posun zobrazovanych objektuvsemi smery a metody zmensit() a zvetsit() pro upravu velikostı. Oproti normalnımustavu lze zmensit objekt na 50 %. Vetsı zmensenı nema z pohledu prehlednosti smysl. Mırazvetsenı omezena nenı, presto nejake velke zvetsenı rovnez nema vyznam. Po kazde upravea prepocıtanı rozmeru se znovuvykreslenı provadı metodou repaint().
Poslednı viditelnou castı programu je ovladacı panel v prave hornı casti hlavnıho okna.Jde o instanci trıdy BControlPanel. Konstruktor teto trıdy se stara o vlozenı vsech kompo-nent, viz. sekce 4.4.1. Dulezitou roli zde hraje metoda actionPerformed(), ktera rozlisujejednotlive udalosti a vola prıslusne metody jinych trıd. Tım je zajisteno, ze pomocı techtotlacıtek lze ovladat celou aplikaci. Trıda mimojine take zajist’uje spoustenı jiz zminovanehoprogramu pro zobrazenı sıt’oveho 3D modelu nalozenı kontejneru s moznostı pohybu v tomtoprostoru, viz. sekce 4.4.2. Vedlejsı moznostı je take zobrazenı dne a datumu, ktere jev pravem dolnım rohu panelu.
5.4.1 Program pro 3D zobrazenı
Jak jiz bylo receno, program je psan v jazyce C s vyuzitım knihovny OpenGL. OpenGL(Open Graphics Library) je nızkourovnova knihovna pro praci s trojrozmernou grafikou.OpenGL predstavuje jednotne API (Application Programming Interface) mezi programema grafickym hardware. Standard API popisuje mnozinu funkcı a procedur s presne speci-fikovanym chovanım.
Zdrojovy kod tohoto programu je v souboru b2c_ogl.c. Nejdrıve jsou nacteny vsechnyhlavickove soubory, predevsım GL/glut.h a GL/glext.h, coz jsou prave knihovny OpenGL.Program podobne jako optimalizacnı program vyuzıva seznam, jehoz prvky reprezentujıjednotlive moduly v kontejneru. Ktery kontejner se ma nacıst ze souboru bconfig.dat,udava prvnı parametr, se kterym je program spusten. Nejdrıve jsou nastaveny vlastnostiokna a jsou registrovany vsechny funkce, ktere zajıst’ujı obsluhu udalostı, jako naprıklad
24
tazenı mysi. Frekvence vykreslovanı je nastavena na 40-krat za sekundu. Pote je spustenanekonecna smycka, ktera vykreslovanı zajist’uje. Ve funkci onDisplay() dojde k vykreslenıkontejneru a vsech modulu, ktere byly jiz “nalozeny”. Pocet nalozenych modulu udavadruhy parametr, se kterym byl program spusten. Vykreslovanı vsech hran modulu ci kon-tejneru je provadeno funkcı glVertex3f().Ovladanı celeho programu stejne jako popis jsouuvedeny v sekci 4.4.2.
5.5 Testovanı
Testovanı probıhalo v prubehu celeho cyklu implementace po jednotlivych castech tak, abybyly odstraneny vsechny dılcı chyby. Po sestavenı aplikace do jednoho celku probehla druhafaze testovanı, ktera mela potvrdit bezchybovost a spravnost vypoctu.
Aplikace byla vyvıjena i testovana na procesoru Intel Celeron, 2,4GHz. Behem testovanıbyla provadena ruzna merenı udaju, ktere klasifikujı vlastnosti optimalizacnıho algoritmu.Nektere namerene vysledky jsou samozrejme ovlineny frekvencı procesoru a velikostı pameti,jako naprıklad doba vypoctu. Ostatnı, jako je pocet rekurzı ci pocet modulu umıstenychv kontejneru, vlastnostmi procesoru ovlivneny nejsou. Vlastnosti algoritmu byly zkoumanyna trech kategoriıch testu.
Prvnı testovanı probıhalo na ruznych vstupnıch datech, tzn. s ruznymi vstupnımi parame-try ci s ruznymi vstupnımi soubory. Pocet materialu v aktualnı den je vzdy priblizne stejny,ovsem menı se jejich druh, tedy i druh modulu, ktere se majı nalozit. Prehled vysledku jeuveden v tabulce A.7. Z tabulky lze vycıst, ze nalozenı jednoho kontejneru z priblizne3500 kusu modulu trva priblizne stejnou dobu. Duvod je prosty, pomer mnozstvı skutecnenalozenych modulu od poctu modulu, ze kterych se vybıra, je velky. Tudız je snadnejsıvybrat ty vhodne.
Zajımavejsı vysledky prineslo opakovane merenı se stejnymi vstupnımi parametry a stej-nym vstupnım souborem. Pri nalozenı kontejneru se samozrejme pouzite moduly ze seznamuodebrali a vypocet se opakoval s nizsım poctem vstupnıch modulu. Pocet rekurzı algoritmuv zavislosti na poctu krabic je uveden v tabulce A.8. Doba vypoctu (tedy i pocet rekurzı) seexponencialne zvysuje s klesajıcım poctem modulu. V jiste urovni jiz nelze nalozenı s danouprocentualnı mırou zaplnenı vypocıtat a vypocet je po 20mil. rekurzı ukoncen (viz. sekce4.3.3).
V poslednı kategorii testu jsem vyuzil moznost optimalizacnıho programu potvrzovatvypocıtany vysledek. Tato vlastnost skyta jednu z moznostı dalsıho rozsırenı aplikace (viz.kapitola 6.2). Optimalizacnı algoritmus provede vypocet, ale pred ulozenım vysledku jeuzivatel dotazan, zda s vysledkem souhlası. Pokud nesouhlası, vypocet pokracuje dokud ne-dosahne vyssıho procenta zaplnenı. Z takto provadeneho testu zjistıme, jak je mıra zaplnenızavisla na dobe vypoctu (poctu rekurzı). Jak lze vycıst z tabulky A.9, zvysenı zaplnenı lzedosahnout, jedna se vsak radove o desetiny, maximalne jednotky procent, ktere nehrajıve vyslednem nalozenı vyznamnou roli. Algoritmus se sice snazı po odmıtnutı vkladat dokontejneru jine moduly, ovsem pocet stejnych modulu je znacny, tudız casto dojde jen kekosmetickym upravam v nalozenı. To je duvod tak maleho zlepsenı. Jako vstupnı data jsempouzil ruzne dny ve stejnem souboru, znazorneno tez v tabulce.
5.5.1 Vlastnosti optimalizacnıho algoritmu
Testovanı do znacne mıry splnilo ocekavanı. Namerene vysledky potvrdili teoreticky predpo-klad, ze optimalizacnı algoritmus ma exponencialnı slozitost v zavislosti na poctu modulu.
25
Kriticka hodnota, kdy se exponencialnı krivka “lame”, je nekde mezi 1 000 a 1 500 modulyv zavislosti na skladbe modulu. Dale je take patrne, ze pri vhodne skladbe modulu probıhavypocet velmi rychle.
26
Kapitola 6
Vysledky a moznosti dalsıhovyvoje
V teto poslednı kapitole shrnu dosazene vysledky pri vyvoji, splnenı pozadavku a moznostidalsıho vyvoje aplikace. Jelikoz jsem aplikace jeste nemohl plne otestovat prımo v provozujedna se o dılcı udaje a subjektivnı nazory odpovednych lidı, kterı majı zavadenı aplikacena starosti.
6.1 Splnenı pozadavku
Po zaclenenı jiz zminovaneho problemu s pretezovanım modulu bude aplikace plne vy-hovovat narokum a splnı vsechny pozadavky, ktere Skoda mela. Mam prislıbeno, ze tentoproblem bude doresen v nejblizsıch tydnech tak, aby cela aplikace byla po otestovanıspustitelna k 1. cervenci 2007. Puvodnı termın spustenı byl jaro 2007 s blıze nespecifiko-vanym datem. Toto se nepodarilo dodrzet z duvodu jinych priorit v oddelenı EOT (Aplikacepracovnıch procesu) spolecnosti Skoda, zejmena pak zavadenı systemu v novych montaznıchhalach v Indii, coz jsem nemohl ovlivnit.
Graficka rozhranı aplikace obsahujı dokonce nektere komponenty, ktere v puvodnı speci-fikaci nebyly. Nejsou sice prımo nezbytne, ale usnadnı praci zamestnancu ci zpresnı vypocetoptimalizace. Po dohode jsem proto doplnil moznost zadavat postacujıcı mıru zaplnenı cizobrazenı 3D sıt’oveho modelu nalozenı kontejneru.
Rychlost i zpusob vypoctu jsou postacujıcı k urcenemu pouzitı. Vezmeme-li v uvahu, zese behem jednoho dne balı a nakladajı soucastky do trech az ctyrech kontejneru, nehraje parsekund vypoctu nalozenı zadnou roli. Problem muze nastat, pokud dojde k nejake necekanesituaci. Naprıklad se do kontejneru na poslednı chvıli musı vlozit jiny material, nez kterybyl v planu. Tento problem ovsem musı a bude resit vnitrnı system Skody, ktery nahrazenymaterial zaradı zpet do cyklu vypoctu. Aplikace ze vstupnıch dat pouze vypocıta rozlozenımodulu v kontejneru a jiz se nestara, zda k nalozenı a vyexpedovanı skutecne doslo . . .
6.2 Moznosti dalsıho vyvoje
I kdyz je aplikace jiz nynı plne vyuzitelna, obsahuje velky potencial rozsırenı a vyuzitı.Jako vstupnı data vyuzıva informace ze souboru (viz. sekce 4.1.1). Pokud balıcı plan zacnevyuzıvat jiny druh modulu pro balenı soucastek, nemusı se preprogramovavat aplikace, alestacı pouze zmenit dane soubory. Proto lze vyuzıt aplikaci nejen ve skladech V8, kam byla
27
puvodne urcena, ale i v jinych castech vyroby, kde resı podobny problem s nakladanımsoucastek.
Stezejnı cast aplikace je samotny optimalizacnı program a na nej se chci take soustreditpri dalsım vyvoji. V casti 4.3.1 jiz byly naznaceny take moznosti jeho rozsırenı. Programpouzıva parametry, ktere nejsou pro aplikaci potrebne, avsak lze je dale vyuzıt. Prvnı dvaparametry udavajı pocet dnu, ktere se majı vypocıtat. Lze tedy vytvorit pole, kde pro kazdyprvek je vypocıtano samostatne nalozenı. Cıslo kontejneru (sesty parametr) pak udava cısloprvnıho vypocıtaneho kontejneru, dalsı majı cıslo vzdy o jedno vyssı. Dale lze vyuzıt ctvrtyparametr, ktery umoznuje dotazovat se uzivatele, zda s vypocıtanym vysledkem souhlası.Teto vlastnosti bylo vyuzito i pri testovanı optimalizacnıho algoritmu, viz. podkapitola 5.5.Mimo tyto moznosti je zde urcity prostor k zefektivnenı vypoctu. A to naprıklad pokudbychom upravili pruchod seznamem modulu ci zpusob skladanı modulu do kontejneru.
Graficka rozhranı, at’ jiz pro zadavanı parametru nebo pro zobrazovanı vypocıtanychrozmıstenı modulu, sice lze take dale vyvıjet, upravovat rozmıstenı komponent ci zlepsitzobrazovanı modulu v kontejneru. Nicmene jsem oba programy vytvoril tak, aby plne vy-hovovali a plne postacovali zpusobu jejich pouzitı.
6.3 Zaver
Problem efektivnı nakladky jakehokoliv materialu tızı vetsinu nejen expedicnıch firem. Apli-kaci jsem proto vyvıjel predevsım s ohledem na obecnost. Po mensıch upravach, ktere setykajı hlavne druhu materialu a stohovatelnosti modulu, verım, ze aplikace najde sirokeuplatnenı v mnoha oblastech.
28
Literatura
[1] J. Boyar. The maximum resource bin packing problem. Springer-Verlag, 2005.
[2] N. Samphaiboon. Heuristic and exact algorithms for the precedence-constrainedknapsack problem. Journal of Optimization Theory and Applications, (3), 2000.
[3] B. Spell. Java - Programujeme profesionalne. Computer Press, 2002.
[4] Otevrena encyklopedie Wikipedia. Optimalizace. [online]. Dostupne na:http://cs.wikipedia.org/wiki/Optimalizace.
29
Dodatek A
Tabulky
Modul Pod modulGLT5755/63 pod GLT5754/56/62/65GLT54/56 pod GLT5762/65GLT5764 pro stohovanı pouze jeden typ paletGLT5740/41 pro stohovanı pouze tyto typ paletGLT5744 pro stohovanı pouze jeden typ palet
Tabulka A.1: Stohovanı GLT modulu
Modul Pocet kusu do GLT5754 Pocet kusu do GLT5755KLT001 8 4KLT002 16 8KLT003 18 8KLT004 36 16KLT005 84 40MOD009 4 1MOD010 8 2MOD011 8 4MOD012 8 3MOD013 24 9MOD014 16 6MOD015 18 6MOD016 36 12MOD017 36 12MOD018 36 12MOD019 18 4MOD020 36 9
Tabulka A.2: Seznam vkladanı modulu KLT a MOD do modulu GLT5754 a GLT5755
30
Modul Sırka (rozmer x) Hloubka (rozmer z) Vyska (rozmer y) Nosnost (kg)GLT000 1450 1120 585 300GLT001 1450 1120 695 300GLT002 2240 720 695 300GLT003 1096 688 695 300GLT004 1675 1500 715 300GLT5740 2000 1200 730 300GLT5741 1200 800 930 300GLT5744 1685 1285 1100 300GLT5754 1450 1130 730 300GLT5755 1130 825 730 300GLT5756 1450 1130 830 300GLT5762 2260 1450 730 300GLT5763 1130 725 370 300GLT5764 2260 1550 730 300GLT5765 2260 1450 1100 300KLT001 595 395 260 78KLT002 595 395 130 78KLT003 395 295 260 65KLT004 395 295 130 40KLT005 295 195 130 34MOD003 1040 688 550 122MOD004 1040 688 275 122MOD005 1040 688 183 122MOD006 1040 458 550 113MOD007 1040 458 275 113MOD008 1040 458 183 113MOD009 688 520 550 102MOD010 688 520 275 102MOD011 688 520 183 102MOD012 520 344 550 86MOD013 520 344 183 45MOD014 520 275 275 43MOD015 458 346 275 43MOD016 458 346 183 43MOD017 458 260 183 41MOD018 458 173 275 38MOD019 344 346 275 40MOD020 344 346 183 40MOD021 344 346 92 0MOD022 137 130 183 0MOD023 114 115 92 0
Tabulka A.3: Prehled nejpouzıvanejsıch modulu
31
Zavod Smena a den Kod materialu Pocet kusu Zaveska Poznamky74 1NPO 01M300032G 7 1000003161 1 K74 1RPO 02J300047M 173 1000003177 1 K74 1OPO 02J300048B 15 1000003178 1 K74 1NPO 038100037H 29 1000003182 1 K74 1RUT 038100054E 1 1000003183 1 K74 1OUT 038105264H 173 1000003193 1 K74 1OUT 06A100020MD 3 1000003260 1 K74 1OST 06A103724BD 1 1000003261 1 K74 1NPA 06A119518G 1 1000003263 1 K74 1NPA 06A133354G 1 1000003265 1 K74 1RPA 191611715 1 1000003291 1 K74 1OPA 191823395 1 1000003292 1 K74 1RPA 191971790A 2 1000003296 1 K74 1OPA 1C0906109A 1 1000003299 1 K74 1RPA 1C0909601 9 1000003300 1 K74 1NPA 1H0611797 1 1000003307 1 K74 1RPA 1H0819465E 7 1000003308 1 K74 1OUT 1H0867981 2 1000003312 1 K74 1RPA 1H0877236 1 1000003313 1 K74 1OPA 1H0919238 1 1000003316 1 K
Tabulka A.4: Prıklad obsahu souboru EXP H TETRIS.txt
Zavod Material Den Balenı Popis74 1 020110024A (21.11.05) 1 GLT5763 GLT 5763 (1130*725*370)74 1 020110024A (21.11.05) 2 BSE040 VCI–SACEK Z HADICE (400)74 1 020110024A (21.11.05) 3 ZLG003 PROLOZKA GLT00374 1 020110024A (21.11.05) 4 GQG302 HREBEN 4 PRICNY74 1 020110024A (21.11.05) 5 GLG201 HREBEN 2 PODELNY74 1 02011024A (8.2.2005) 1 GLT003 GLT 3 (1096*688*695)74 1 02011024A (8.2.2005) 2 DGL003 VIKO PRO GLT00374 1 02011024A (8.2.2005) 3 PGL003 PALETA GLT374 1 02011024A (8.2.2005) 4 WSR100 VLNITY ROLOVANY PAPIR (1000)74 1 02011024A (8.2.2005) 5 BSE040 VCI–SACEK Z HADICE (400)74 1 021117061B (12.05.05) 1 KLT003 KLT 3 (395*295*260)74 1 021117061B (12.05.05) 2 BSN060 PE–SACEK Z HADICE (600)74 1 02A911023L (8.2.2005) 1 GLT003 GLT 3 (1096*688*695)74 1 02A911023L (8.2.2005) 2 DGL003 VIKO PRO GLT00374 1 02A911023L (8.2.2005) 3 PGL003 PALETA GLT374 1 02A911023L (8.2.2005) 4 WSR100 VLNITY ROLOVANY PAPIR (1000)74 1 02A911023L (8.2.2005) 5 BSE040 VCI-SACEK Z HADICE (400)
Tabulka A.5: Prıklad obsahu souboru EXP THI MODUL.txt
32
Zaveska Umıstenı Rotace Velikost Modul Pocet Vlozene1000004965 0 0 0 0 72 37 113 GLT5763 1 GLT57631000004907 72 0 0 0 72 37 113 GLT5763 1 GLT57631000006540 0 37 0 0 145 73 113 GLT5754 18 KLT0031000004907 145 146 0 0 72 37 113 GLT5763 1 GLT57631000006104 145 0 0 0 82 73 113 GLT5755 1 GLT57551000004410 145 73 0 0 82 73 113 GLT5755 1 GLT57551000006540 0 147 0 0 145 73 113 GLT5754 18 KLT0031000004907 145 183 0 0 72 37 113 GLT5763 1 GLT57631000004397 0 220 0 0 104 18 68 MOD005 1 MOD0051000004395 145 220 0 0 68 18 104 MOD005 1 MOD0051000004907 72 110 0 0 72 37 113 GLT5763 1 GLT57631000006210 104 220 0 0 39 13 59 KLT002 1 KLT0021000006106 104 220 59 0 34 18 52 MOD013 1 MOD0131000006019 0 220 68 0 104 18 45 MOD008 1 MOD0081000006540 0 0 113 0 145 73 113 GLT5754 18 KLT0031000006540 0 73 113 0 145 73 113 GLT5754 18 KLT0031000006540 0 146 113 0 145 73 113 GLT5754 18 KLT0031000006018 0 219 113 0 104 18 45 MOD008 1 MOD0081000004119 104 219 113 0 39 13 59 KLT002 1 KLT002
Tabulka A.6: Prıklad obsahu souboru res.dat
Pocet modulu na vstupu Zaplnenı [ % ] Pocet pouzitych modulu Pocet rekurzı3673 86,173 1153 3 7362634 87,378 633 2 6491122 86,400 166 4992892 85,293 821 2 1203112 87,482 1021 5 8322923 86,932 931 3 121
Tabulka A.7: Test c. 1: Merenı s ruznymi vstupnımi daty
Cıslo vypoctu Modulu na vstupu Zaplnenı [ % ] Pouzitych modulu Pocer rekurzı1 3 673 86,173 1153 3 7362 2 520 87,759 1439 3 0863 1 081 85,021 539 219 4834 5421 1 122 86,400 166 4992 956 88,327 230 56183 7261 2 634 87,378 633 2 6492 2 001 85,239 854 1 2463 1 141 86,127 732 42 3164 409
Tabulka A.8: Test c. 2: Opakovane merenı se stejnymi vstupnımi daty
33
Cıslo merenı Zaplnenı [ % ] Pocet rekurzı1 86,173 3 7362 86,173 4 8943 86,183 7 6724 86,180 11 7575 86,284 63 5996 86,341 172 7167 86,887 1 525 085
- pondelı, 3673 modulu1 86,277 6492 86,298 9143 86,355 1 1554 86,350 1 5415 86,360 1 9416 86,512 478 9247 87,718 1 415 200
- utery, 1321 modulu1 86,400 4992 86,421 5513 86,441 5654 86,441 7475 86,437 239 4596 86,341 172 7167 87,537 4 108 760
- streda, 1122 modulu1 87,121 1 7262 87,317 2 4953 87,507 14 3664 87,532 15 1435 87,886 308 8756 87,899 5 227 108
- ctvrtek, 1021 modulu
Tabulka A.9: Test c. 3: Vypocty optimalizace pri odmıtanı vysledku
34
Dodatek B
Uzivatelsky manual
Dale bude nasledovat uzivatelsky manual, ktery je napsan v MS Wordu, aby byl snadnoaktualizovatelny dalsımi pracovnıky Skody. Ma proto samostane cıslovanı a mırne odlisnystyl sazby. . .
35
