ˇ ´I TECHNICKE´ V BRNEˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ´ ´ U ˚ USTAV INTELIGENTN´ICH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS
ˇ ´I MATERIALU ´ ˇ OPTIMALIZACE ULOZEN PRO PREPRAVU
´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS
´ AUTOR PRACE AUTHOR
BRNO 2007
MICHAL VACEK
ˇ ´I TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ´ ´ U ˚ USTAV INTELIGENTN´ICH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS
ˇ ´I MATERIALU ´ ˇ OPTIMALIZACE ULOZEN PRO PREPRAVU STUFF PLACING OPTIMIZATION FOR TRANSPORT
´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS
´ AUTOR PRACE
MICHAL VACEK
AUTHOR
´ VEDOUC´I PRACE SUPERVISOR
BRNO 2007
ˇ Ing. BOHUSLAV KRENA, Ph.D.
Abstrakt Pr´ace se zab´ yv´a aplikac´ı pro optimalizaci uloˇzen´ı materi´alu pro pˇrepravu. Aplikace je ˇ vyv´ıjena ve spolupr´aci se spoleˇcnost´ı Skoda Auto a.s., kter´a ˇreˇs´ı probl´em pˇrepravy maˇ teri´alu v kontejnerech z v´ yrobn´ıch hal v Cesk´e republice do mont´aˇzn´ıch z´avod˚ u v zahraniˇc´ı. Zde je pops´ana jej´ı anal´ yza, n´avrh i implementace. Aplikace se skl´ad´a ze dvou ˇc´ast´ı. Prvn´ı vypoˇc´ıt´a optimalizaci – vybere z mnoˇziny modul˚ u (krabic) vhodnou kombinaci a um´ıst´ı ji ˇ ast t´eto pr´ace je tak´e vˇenov´ana kontejneru. Druh´a ˇc´ast aplikace toto rozloˇzen´ı zobrazuje. C´ pˇr´ıbuzn´ ym optimalizaˇcn´ım metod´am, zejm´ena pak Knapsack a Bin-packing probl´emu.
Kl´ıˇcov´a slova Optimalizace, uloˇzen´ı materi´alu, Knapsack, Bin-packing problem
Abstract This bachelor thesis treats of application of stuff placing optimization for transport. ˇ Application is developed in cooperation with Skoda Auto a.s., which solves the problem of transport materials in containers from their factories to assembly halls abroad. It describes an application analysis, a plan and an implementation. Application consist of two parts. 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 stuff placing. The part of this bachelor thesis is also set of agnated optimalization methods, mainly Knapsack and Bin-packing problem.
Keywords Optimalization, stuff placing, Knapsack, Bin-packing problem
Citace Michal Vacek: Optimalizace uloˇzen´ı materi´alu pro pˇrepravu, bakal´aˇrsk´a pr´ace, Brno, FIT VUT v Brnˇe, 2007
Optimalizace uloˇzen´ı materi´alu pro pˇrepravu Prohl´aˇsen´ı Prohlaˇsuji, ˇze jsem tuto bakal´aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım pana ˇ Bohuslava Kˇreny. Dalˇs´ı informace mi poskytli zamˇestnanci spoleˇcnosti Skoda Auto a. s. Uvedl jsem vˇsechny liter´arn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal. ....................... Michal Vacek 10. kvˇetna 2007
Podˇekov´an´ı R´ad bych podˇekoval Ing. Bohuslavu Kˇrenovi, Ph.D., za pomoc s pˇr´ıpravou bakal´aˇrsk´e pr´ ace ˇ a tak´e vˇsem zamˇestnanc˚ um spoleˇcnosti Skoda Auto a. s., kteˇr´ı se mnou na v´ yvoji aplikace spolupracovali.
c Michal Vacek, 2007.
Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysok´em uˇcen´ı technick´em v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorsk´ym z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonn´e, s v´yjimkou z´ akonem definovan´ych pˇr´ıpad˚ u.
Obsah ´ 1 Uvod 1.1 Optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Struktura bakal´aˇrsk´e pr´ace . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3
2 Specifikace zad´ an´ı 2.1 Vstupn´ı parametry pro optimalizaci . . . . 2.2 Omezen´ı a krit´eria pˇri v´ ypoˇctu optimalizace 2.2.1 Stohovatelnost . . . . . . . . . . . . 2.2.2 Vkl´ad´an´ı mal´ ych modul˚ u do velk´ ych 2.2.3 Ostatn´ı omezen´ı . . . . . . . . . . . 2.3 Poˇzadavky na zobrazen´ı v´ ysledku . . . . . .
. . . . . .
5 5 6 6 6 6 6
3 Pˇ r´ıbuzn´ e optimalizaˇ cn´ı metody 3.1 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Form´aln´ı definice 0/1 knapsack probl´emu . . . . . . . . . . . . . . . 3.2 Bin-packing problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 7 7 8
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
4 N´ avrh aplikace pro optimalizaci vˇ cetnˇ e grafick´ e reprezentace 4.1 Struktura soubor˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Vstupn´ı soubory . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 V´ ystupn´ı soubory . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Konfiguraˇcn´ı soubory . . . . . . . . . . . . . . . . . . . . . . 4.2 Grafick´e uˇzivatelsk´e rozhran´ı pro z´ısk´an´ı poˇzadavk˚ u pro optimalizaci 4.2.1 Pˇrehled jednotliv´ ych ˇc´ast´ı . . . . . . . . . . . . . . . . . . . . 4.3 Optimalizaˇcn´ı program . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Vstupn´ı parametry . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Naˇcten´ı a uchov´av´an´ı dat bˇehem v´ ypoˇctu . . . . . . . . . . . 4.3.3 Princip v´ ypoˇctu uloˇzen´ı materi´alu . . . . . . . . . . . . . . . 4.3.4 Uloˇzen´ı v´ ysledku a ukonˇcen´ı programu . . . . . . . . . . . . . 4.4 Program pro zobrazen´ı kontejner˚ u a jejich naloˇzen´ı . . . . . . . . . . 4.4.1 Pˇrehled jednotliv´ ych ˇc´ast´ı . . . . . . . . . . . . . . . . . . . . 4.4.2 3D zobrazen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Implementace a testov´ an´ı 5.1 Adres´aˇrov´a struktura . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Grafick´e uˇzivatelsk´e rozhran´ı pro z´ısk´an´ı poˇzadavk˚ u pro optimalizaci 5.3 Optimalizaˇcn´ı program . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Program pro zobrazen´ı kontejner˚ u a jejich naloˇzen´ı . . . . . . . . . . 1
. . . . . .
. . . . . . . . . . . . . .
. . . .
. . . . . .
. . . . . . . . . . . . . .
. . . .
. . . . . .
. . . . . . . . . . . . . .
. . . .
. . . . . . . . . . . . . .
9 9 9 11 11 11 11 13 14 14 15 16 16 18 19
. . . .
21 21 22 22 23
5.4.1 Program pro 3D zobrazen´ı . . . . . . . . . . . . . . . . . . . . . . . . Testov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.1 Vlastnosti optimalizaˇcn´ıho algoritmu . . . . . . . . . . . . . . . . . .
24 25 25
6 V´ ysledky a moˇ znosti dalˇ s´ıho v´ yvoje 6.1 Splnˇen´ı poˇzadavk˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Moˇznosti dalˇs´ıho v´ yvoje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Z´avˇer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27 27 27 28
Literatura
28
A Tabulky
30
B Uˇ zivatelsk´ y manu´ al
35
5.5
2
Kapitola 1
´ Uvod ˇ C´ılem pr´ace je popsat aplikaci, kterou jsem vytvoˇril ve spolupr´aci se spoleˇcnost´ı Skoda Auto ˇ a.s. (d´ale pouze Skoda). V t´eto spoleˇcnosti vykon´av´am extern´ı st´aˇz a dostal jsem moˇznost propojit v´ yvoj optimalizaˇcn´ı aplikace s moj´ı bakal´aˇrskou prac´ı. V tomto dokumentu je tedy pops´an n´avrh a implementace vˇsech ˇc´ast´ı programu vˇcetnˇe ovl´ad´an´ı a komunikace ˇ s vnitˇrn´ımi syst´emy Skody. ˇ e republice do mont´ Spoleˇcnost ˇreˇs´ı probl´em pˇrepravy materi´alu z v´ yrobn´ıch hal v Cesk´ aˇzn´ıch z´avod˚ u v zahraniˇc´ı. Z ekonomick´ ych d˚ uvod˚ u, pˇredevˇs´ım kv˚ uli vysok´ ym cl˚ um na hotov´e v´ yrobky v nˇekter´ ych zem´ıch, se nevyplat´ı do dan´ ych st´at˚ u vyv´aˇzet cel´a auta. V r˚ uzn´em stupni rozloˇzen´ı se tak jednotliv´e souˇc´astky bal´ı do krabic nebo palet (oznaˇcovan´ ych d´ ale jako moduly) a pot´e se pos´ılaj´ı do zahraniˇc´ı v kontejnerech ˇci vag´onech. Pˇreprava materi´alu je dosti n´akladn´a a prom´ıt´a se znaˇcnˇe v cenˇe vˇsech v´ yrobk˚ u, probl´em vhodnˇe vyuˇz´ıt n´akladov´ y prostor proto tr´ap´ı nejen expediˇcn´ı firmy po cel´em svˇetˇe. ´ Ukolem tak bylo optimalizovat naloˇzen´ı kontejneru (resp. vag´onu), neboli vypoˇc´ıtat zp˚ usob, jak jednotliv´e moduly v kontejneru nejl´epe uspoˇr´adat. A v´ ysledek pot´e vhodnˇe zobrazit. Detaily zad´an´ı jsem shrnul v kapitole 2.
1.1
Optimalizace
Nejdˇr´ıve se pod´ıvejme, co optimalizace v˚ ubec znamen´a. Jde vlastnˇe o matematickou discipl´ınu, kter´a hled´a minimum (resp. maximum) dan´e funkce f (x) na mnoˇzinˇe pˇr´ıpustn´ ych ˇreˇsen´ı M . Nˇekdy, stejnˇe jako v naˇsem pˇr´ıpadˇe, pom´ahaj´ı optimalizaˇcn´ı u ´lohu ˇreˇsit tzv. podm´ınky optimality. Jde o podm´ınky, kter´e mus´ı platit pro optim´aln´ı ˇreˇsen´ı, a slouˇz´ı pˇredevˇs´ım k redukci mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı. [4] Takov´eto podm´ınky naˇs´ı optimalizace jsou pops´any v podkapitole 2.2. Podm´ınky lze rozdˇelit na: • nutn´e (mus´ı splˇ novat kaˇzd´e optim´aln´ı ˇreˇsen´ı u ´lohy) • postaˇcuj´ıc´ı (pokud je nˇejak´ y bod splˇ nuje, automaticky jde o optim´aln´ı ˇreˇsen´ı) Optimalizaci a pˇredevˇs´ım optimalizaˇcn´ım metod´am pˇr´ıbuzn´ ym naˇsemu probl´emu se vˇenuje kapitola 3.
1.2
Struktura bakal´ aˇ rsk´ e pr´ ace
V n´asleduj´ıc´ıch kapitol´ach jsem popsal v´ yvoj aplikace (od n´avrhu aˇz po implementaci a testov´an´ı), kter´a m´a zefektivnit cyklus balen´ı a nakl´adky materi´alu a pˇredevˇs´ım sn´ıˇzit 3
n´aklady na jeho pˇrepravu. Jelikoˇz aplikace jeˇstˇe nedostala sv´e “jm´eno”, pouˇz´ıv´am doˇcasnˇe pracovn´ı oznaˇcen´ı b2c, coˇz jsou poˇc´ateˇcn´ı p´ısmena anglick´eho spojen´ı boxes to containers. Jednotliv´e kapitoly obsahem v´ıcem´enˇe kop´ıruj´ı body zad´an´ı bakal´aˇrsk´e pr´ace. V prvn´ı kapitole 2 detailnˇe specifikuji zad´an´ı. Pop´ıˇsu zde probl´emy, kter´e mus´ı aplikace ˇ ˇreˇsit, a poˇzadavky, kter´e jsou na program kladeny ze strany Skody. Ve druh´e kapitole trochu odboˇc´ım. Projdu pˇr´ıbuzn´e metody, kter´e se rovnˇeˇz zab´ yvaj´ı probl´emem kombinaˇcn´ı optimalizace, zejm´ena Knapsack a bin-packing problem. T´ım vytvoˇr´ım dostateˇcnou teoretickou p˚ udu pro vytvoˇren´ı vlastn´ıho optimalizaˇcn´ıho algoritmu. Dalˇs´ı dvˇe kapitoly se zab´ yvaj´ı n´avrhem (viz. kapitola 4), resp. implementac´ı (viz. kapitola 5) aplikace. Tvoˇr´ı hlavn´ı ˇc´ast bakal´aˇrsk´e pr´ace a jsou v nich pops´any vˇsechny ˇc´asti aplikace, zp˚ usob, jak´ ym byly vytvoˇreny, a funkce, kter´e zast´avaj´ı. Pop´ıˇsu zde tak´e princip, jak´ ym je optimalizace vypoˇc´ıt´av´ana a zahrnuta bude tak´e podkapitola vˇenuj´ıc´ı se testov´ an´ı a mˇeˇren´ı vlastnost´ı aplikace. V posledn´ı kapitole shrnu dosaˇzen´e v´ ysledky. Upˇresn´ım, do jak´e m´ıry se podaˇrilo splnit poˇzadavky na aplikaci a jak´ ym zp˚ usobem je moˇzn´e program d´ale rozˇsiˇrovat a vyv´ıjet. Doplˇ nuj´ıc´ı tabulky a grafy s v´ yraznˇe popisn´ ym charakterem jsem um´ıstil do pˇr´ıloh. Nalezneme zde i uˇzivatelsk´ y manu´al, kter´ y jsem k aplikaci vytvoˇril.
4
Kapitola 2
Specifikace zad´ an´ı V t´eto kapitole budou analyzov´any vˇsechny detaily zad´an´ı, n´aroky, kter´e mus´ı aplikace splˇ novat, a nast´ınˇena bude i struktura cel´e aplikace. Specifika zad´an´ı jsem pr˚ ubˇeˇznˇe konzulˇ toval s odpovˇedn´ ymi lidmi ve Skodˇe tak, aby program byl n´aslednˇe pouˇziteln´ y v praxi, a to konkr´etnˇe v expediˇcn´ıch hal´ach V8 v Mlad´e Boleslavi. ˇ Hlavn´ım poˇzadavkem Skody bylo rozdˇelit aplikaci na dvˇe nez´avisl´e ˇc´asti. Jeden program m´a optim´aln´ı rozloˇzen´ı modul˚ u v kontejneru vypoˇc´ıtat a druh´ y ho vhodnˇe zobrazit. D˚ uvodem je moˇznost samostatn´e obsluhy obou ˇc´ast´ı. Prvn´ı (optimalizaˇcn´ı) program budou obsluhovat lid´e, kteˇr´ı vytv´aˇr´ı bal´ıc´ı pl´an pro expedici. Zat´ımco druh´ y (zobrazovac´ı) program budou pouˇz´ıvat zejm´ena lid´e, kteˇr´ı materi´al bal´ı ˇci ho pˇr´ımo nakl´adaj´ı do kontejner˚ u. Z tohoto rozdˇelen´ı vypl´ yv´a i prvn´ı ot´azka: jak spolu oba dva programy maj´ı komunikovat?! Zvolen byl ten nejjednoduˇsˇs´ı zp˚ usob. Optimalizaˇcn´ı program v´ ysledky uloˇz´ı do souboru a zobrazovac´ı program jej odtud bude ˇc´ıst. Tato varianta byla vybr´ana i s ohledem na ˇ hlavn´ı poˇzadavek Skody, aby cel´a aplikace jak´ ymkoliv zp˚ usobem nezasahovala do vnitˇrn´ıch syst´em˚ u spoleˇcnosti, a veˇsker´a komunikace tak prob´ıhala pouze na u ´rovni ˇcten´ı/z´ apisu z/do soubor˚ u.
2.1
Vstupn´ı parametry pro optimalizaci
Seznam materi´alu, kter´ y m´a b´ yt expedov´an, je zn´am pˇribliˇznˇe na 5 dn´ı dopˇredu. Ke kaˇzd´emu materi´alu pˇr´ısluˇs´ı modul, do kter´eho se materi´al bal´ı. Seznam nejpouˇz´ıvanˇejˇs´ıch modul˚ u i s jejich rozmˇery je uveden v tabulce A.3. D˚ uleˇzit´e je rozdˇelit materi´al podle dne, kdy m´a b´ yt expedov´an, a hlavnˇe z´avodu, kam m´a b´ yt posl´an. Vˇsechna data jsou pak uloˇzena ve vstupn´ıch souborech, strukturou soubor˚ u se zab´ yv´a sekce 4.1.1. D˚ uleˇzit´e je tak´e zjistit, do jak velk´eho kontejneru (resp. vag´onu) m´a b´ yt materi´ al naloˇzen, tedy pro jak velk´ y prostor se m´a optimalizace vypoˇc´ıtat. Rozmˇery standartn´ıch kontejner˚ u ˇci vag´on˚ u jsou zn´amy, ale pro r˚ uzn´e neˇcekan´e situace ˇci pro testov´an´ı a dalˇs´ı v´ yvoj by mˇela b´ yt moˇznost tyto rozmˇery zadat i ruˇcnˇe. D´ale mezi poˇzadavky byla doplnˇena moˇznost zadat m´ıru zaplnˇen´ı. V praxi nen´ı t´emˇeˇr moˇzn´e dos´ahnout 100 % zaplnˇen´ı kontejneru, tato m´ıra zaplnˇen´ı proto ud´av´a, jak´e zaplnˇen´ı je dostateˇcn´e pro ukonˇcen´ı optimalizaˇcn´ıho v´ ypoˇctu (touto aproximac´ı algoritmu se zab´ yv´ a podkapitola 4.3).
5
2.2
Omezen´ı a krit´ eria pˇ ri v´ ypoˇ ctu optimalizace
Pˇri skl´ad´an´ı jednotliv´ ych modul˚ u do kontejneru nar´aˇz´ıme na ˇradu probl´em˚ u. V t´eto podkapitole je uveden jejich struˇcn´ y pˇrehled, kter´ y do znaˇcn´e m´ıry ovlivˇ nuje samotn´ y algoritmus v´ ypoˇctu.
2.2.1
Stohovatelnost
Zˇrejmˇe nejv´ıce omezuj´ıc´ım faktorem je hmotnost materi´alu uloˇzen´eho v modulu a tak´e konstrukce onoho modulu. Nesm´ı totiˇz doj´ıt k pˇret´ıˇzen´ı ˇci naruˇsen´ı modul˚ u um´ıstˇen´ ych vespod kontejneru, aby nedoˇslo ke znehodnocen´ı materi´alu. Pˇri skl´ad´an´ı jednotliv´ ych modul˚ u na sebe existuje jednoduch´e pravidlo. Na menˇs´ı bednu nesm´ı pˇrij´ıt vˇetˇs´ı z d˚ uvod˚ u jejich nosnosti. I zde existuj´ı vyj´ımky – syst´em modul˚ u GLT. Jedn´a se o vysokonosn´e bedny, kter´e sv´ ymi rozmˇery do sebe “zapadaj´ı”. Tyto moduly tvoˇr´ı kostru cel´eho kontejneru, a jako jedin´e je lze stavˇet na sebe zp˚ usobem, kdy pod velkou bednu pˇrijdou 2 aˇz 4 mal´e. Pˇrehled pravidel, jak lze takto moduly GLT stohovat je uveden v tabulce A.1.
2.2.2
Vkl´ ad´ an´ı mal´ ych modul˚ u do velk´ ych
Jedn´ım z ˇreˇsen´ı mal´e nosnosti ostatn´ıch modul˚ u je jejich vkl´ad´an´ı do GLT. V praxi se vkl´adaj´ı nˇekter´e menˇs´ı moduly KLT a MOD prim´arnˇe do GLT5754. Pouze pokud nen´ı do tohoto modulu dostateˇcn´ y poˇcet kus˚ u materi´alu, vkl´adaj´ı se do GLT5755. Po kolika kusech se tyto moduly do GLT modul˚ u vkl´adaj´ı je uvedeno v tabulce A.2. Zbyl´e moduly, kter´ ych nen´ı dostateˇcn´ y poˇcet, se pouˇz´ıvaj´ı k vyplnˇen´ı vrchn´ıch m´ıst v kontejneru.
2.2.3
Ostatn´ı omezen´ı
Dalˇs´ım zaj´ımav´ ym probl´emem byla moˇznost rotace modul˚ u, ty se totiˇz mohou ot´aˇcet pouze podle y osy, tedy nikoliv pˇrevracet. D˚ uvod je zˇrejm´ y, nesm´ı doj´ıt k poˇskozen´ı materi´ alu uvnitˇr. ˇ Mezi posledn´ı poˇzadavek Skody patˇr´ı moˇznost bezprobl´emov´eho naloˇzen´ı dan´ ych modul˚ u do kontejneru. Dveˇre kontejneru nesahaj´ı pˇres jeho celou ˇceln´ı stranu, ale odzhora chyb´ı pˇribliˇznˇe 20 cm. Tud´ıˇz nelze v posledn´ıch dvou metrech kontejneru skl´adat moduly aˇz ke stropu, vysokozdviˇzn´ y voz´ık by se tam nedostal. Tento probl´em odpad´a u vagon˚ u, kter´e se nakl´adaj´ı ze strany.
2.3
Poˇ zadavky na zobrazen´ı v´ ysledku
Pˇri zobrazen´ı v´ ysledku, tedy rozloˇzen´ı modul˚ u v kontejneru, je kladen d˚ uraz pˇredevˇs´ım na pˇrehlednost. Program by mˇel jednoduˇse zobrazit jednotliv´e moduly a postupnˇe zn´azornit jejich um´ıstˇen´ı do kontejneru. Tak´e mus´ı zobrazit veˇsker´e dostupn´e informace o dan´em modulu a materi´alu v nˇem, aby byla moˇzn´a jejich snadn´a identifikace. Program by si mˇel pamatovat vˇsechny dosud nevyexpedovan´e kontejnery, kter´e se identifikuj´ı pomoc´ı ID ˇc´ısla (pˇridˇeleno bˇehem optimalizaˇcn´ıho v´ ypoˇctu).
6
Kapitola 3
Pˇ r´ıbuzn´ e optimalizaˇ cn´ı metody Nyn´ı trochu odboˇc´ıme od naˇseho t´ematu. Pod´ıv´ame se detailnˇeji na r˚ uzn´e probl´emy, kter´e maj´ı urˇcit´e podobn´e vlastnosti jako naˇse optimalizace. Algoritmy ˇreˇs´ıc´ı probl´em kombinaˇcn´ı optimalizace jsou charakteristick´e t´ım, ˇze hledaj´ı maxim´aln´ı ze vˇsech nab´ızen´ ych moˇznost´ı limitovan´e nˇejak´ ym omezen´ım. Mezi nejzn´amˇejˇs´ı patˇr´ı Knapsack nebo Bin-packing problem. Pro mnoh´e optimalizaˇcn´ı probl´emy je vˇsak obt´ıˇzn´e navrhnout algoritmy, kter´e je vyˇreˇs´ı optim´alnˇe a z´aroveˇ n rychle (napˇr. pro NP-´ upln´e probl´emy). V takov´em pˇr´ıpadˇe studujeme tzv. aproximaˇcn´ı algoritmy, kter´e pracuj´ı rychle, a najdou ˇreˇsen´ı v´ıce ˇci m´enˇe bl´ızk´e optim´aln´ımu ˇreˇsen´ı. Takov´eto aproximace vyuˇz´ıv´a i algoritmus, kter´ y jsem pro v´ ypoˇcet pouˇzil (viz. podkapitola 4.3)
3.1
Knapsack
Mezi nejzaj´ımavˇejˇs´ı pˇr´ıklady kombinaˇcn´ıch algoritm˚ u patˇr´ı Knapsack problem, v ˇceˇstinˇe t´eˇz oznaˇcov´an jako probl´em batohu. Jedn´a se o libovolnˇe pˇresnˇe aproximovateln´ y probl´em. Zjednoduˇsenˇe ˇreˇceno vyb´ır´ame z kolekce poloˇzek, z nichˇz kaˇzd´e m´a svoji v´ahu a hodnotu, jejich nejlepˇs´ı kombinaci, kter´a se vejde do vymezen´eho prostoru (jiˇz zmiˇ novan´e omezen´ı), a pˇritom hodnota sloˇzek bude co moˇzn´a nejvˇetˇs´ı. Mezi z´akladn´ı verze patˇr´ı tzv. 0/1 knapsack problem. Zde poˇcet jednotliv´ ych poloˇzek m˚ uˇze nab´ yvat pouze hodnot nula nebo jedna, tedy bud’ je v ˇreˇsen´ı poloˇzka zahrnuta nebo nen´ı. Pokud omez´ıme poˇcet poloˇzek nˇejak´ ym ˇc´ıslem, mluv´ıme o bounded knapsack problem.
3.1.1
Form´ aln´ı definice 0/1 knapsack probl´ emu
Mˇejme n poloˇzek a m u ´loˇzn´ ych prostor˚ u, • pi,j hodnota poloˇzky j v prostoru i • wi,j v´aha poloˇzky j v prostoru i • ci kapacita prostoru i.
7
Hled´ame 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 n X fi (x) = pi,j ∗ xj , a kde
(3.2)
j=1 n X
∨i ∈ 1, 2, . . . , m :
wi,j ∗ xj ≤ ci .
(3.3)
(3.4)
j=1
Sloˇzitost ˇreˇsen´ı knapsack probl´emu pot´e z´aleˇz´ı na kapacitˇe jednotliv´ ych u ´loˇzn´ ych prostor˚ u. Pro testov´ a n´ ı a porovn´ a v´ a n´ ı rychlost´ ı jednotliv´ y ch algoritm˚ u se pouˇ z ´ ıv´ a obecnˇ e hodPn nota ci = 0.5 j=1 wi,j . [2] ˇ sen´ı m˚ Reˇ uˇze prob´ıhat mnoha metodami. Od “hrub´e s´ıly”, kdy se neust´ale zjiˇst’uje lepˇs´ı v´ ybˇer poloˇzek. Po ˇreˇsen´ı heuristikou podle pomˇeru hodnota/v´aha. Ta je d´ıky menˇs´ı asymptotick´e sloˇzitosti pouˇziteln´a i pro instance s vˇetˇs´ım poˇctem prvk˚ u. Danou heuristiku m˚ uˇzeme jeˇstˇe rozˇs´ıˇrit o tzv. testov´ an´ı nejcennˇejˇs´ı vˇeci.
3.2
Bin-packing problem
Pomoc´ı bin-packing probl´emu zkouˇs´ıme minimalizovat poˇcet u ´loˇzn´ ych prostor˚ u (tzv. bins) potˇrebn´ ych k naloˇzen´ı urˇcit´eho poˇctu poloˇzek. Ot´azku lze tak´e ovˇsem pojmout z opaˇcn´eho pohledu, pokusit se do jednoho u ´loˇzn´eho prostoru naskl´adat co nejv´ıce poloˇzek, resp. co nejl´epe vyplnit dan´ y prostor. Pr´avˇe tato varianta m´a mnoho spoleˇcn´eho s naˇs´ı optimalizac´ı a tud´ıˇz si ji detailnˇeji rozebereme. Mˇejme bin a mnoˇzinu krabic, jejichˇz celkov´ y objem je vˇetˇs´ı neˇz objem u ´loˇzn´eho ´ prostoru. Ukol je vybrat podmoˇzinu dan´ ych krabic a rozm´ıstit ji do prostoru tak, aby zabrala co nejv´ıce m´ısta. Pokud V je objem prostoru a Vb je celkov´ y objem vˇsech krabic, vyuˇzit´ı kaˇzd´e krabice je potom Vb /V . V z´avislosti na poˇctu rozmˇer˚ u krabic a prostoru pot´e hovoˇr´ıme o 2D bin-packing (pokud maj´ı pouze ˇs´ıˇrku a v´ yˇsku) nebo o 3D bin-packing probl´emu (pokud maj´ı i hloubku). V prvn´ım pˇr´ıpadˇe se jedn´a v podstatˇe o mnoˇzinu obd´eln´ık˚ u, ve druh´em pak o mnoˇzinu kv´adr˚ u. Zde u ´myslnˇe vynech´av´am moˇznosti, kdy se nejedn´a o symetrick´e tvary, jelikoˇz zde je v´ ypoˇcet jeˇstˇe daleko n´aroˇcnˇejˇs´ı. [1] Algoritmus v´ ypoˇctu je zaloˇzen na neust´al´em pˇrid´av´an´ı a odeb´ır´an´ı krabic do u ´loˇzn´eho prostoru, ˇcasto k tomu vyuˇz´ıv´a rekurzi. Pokud bychom nechali probˇehnout algoritmus cel´ y, tzn. naˇsel by vˇsechny moˇznosti, jak poloˇzky do prostoru um´ıstit, jednoduˇse bychom z nich vybrali tu nejlepˇs´ı. V naˇsem pˇr´ıpadˇe tu, kter´a zabrala nejv´ıce m´ısta. Ovˇsem jsou zde dva probl´emy. Kam um´ıstit prvn´ı poloˇzku, od kter´e se cel´ y v´ ypoˇcet prov´ad´ı?! Pokud bychom zkouˇseli um´ıstit do dan´eho prostoru vˇsechny poloˇzky (coˇz bychom museli, pokud chceme zjistit vˇsechny moˇznosti rozloˇzen´ı), a pˇritom je zkouˇseli postupnˇe um´ıstit do vˇsech ˇc´ast´ı prostoru, jiˇz pˇri pomˇernˇe mal´em poˇctu poloˇzek by byl v´ ypoˇcet ne´ unosnˇe ˇcasovˇe n´aroˇcn´ y. Zde pˇrich´az´ı na ˇradu jiˇz zmiˇ novan´a aproximace. Nejefektivnˇejˇs´ı m´ısto, kde v´ ypoˇcet zaˇc´ıt, je jeden z roh˚ uu ´loˇzn´eho prostoru. T´ım sn´ıˇz´ıme n´aroˇcnost v´ ypoˇctu. Druh´ y probl´em ovˇsem m˚ uˇze b´ yt, ˇze pokud m´ame nˇekolik tis´ıc poloˇzek (jako napˇr´ıklad v naˇsem pˇr´ıpadˇe), v´ ypoˇcet bude trvat i tak pˇr´ıliˇs dlouho. Druhou aproximac´ı m˚ uˇze b´ yt stanoven´ı urˇcit´e u ´rovnˇe, kdy lze povaˇzovat ˇreˇsen´ı za dostateˇcn´e. Ovˇsem to uˇz nemus´ı b´ yt nejlepˇs´ı moˇzn´e.
8
Kapitola 4
N´ avrh aplikace pro optimalizaci vˇ cetnˇ e grafick´ e reprezentace V t´eto kapitole budou detailnˇe pops´any jednotliv´e ˇc´asti aplikace, jejich funkce a vz´ajemn´ a komunikace, zejm´ena z pohledu uˇzivatele. Pops´ano bude chov´an´ı i ovl´ad´an´ı aplikace. Jak jiˇz bylo naznaˇceno v popisu poˇzadavk˚ u, aplikace je rozdˇelena do dvou na sobˇe nez´avisl´ ych ˇc´ast´ı. S ohledem na obecnost aplikace a moˇznost jej´ıho pozdˇejˇs´ıho ˇsirˇs´ıho vyˇzit´ı byla jeˇstˇe optimalizaˇcn´ı ˇc´ast rozdˇelena na dalˇs´ı dva celky. Kostru aplikace tak tvoˇr´ı samotn´ y optimalizaˇcn´ı program b2c.exe, kter´ y prov´ad´ı vlastn´ı v´ ypoˇcet uloˇzen´ı materi´alu v kontejneru. K tomu vyuˇz´ıv´a vˇsechny vstupn´ı soubory, kter´e jsou pops´any v sekci 4.1.1 a v´ ysledek ukl´ad´ a do souboru res.dat. Nadstavbou tohoto programu je grafick´e uˇzivatelsk´e rozhran´ı, kter´e slouˇz´ı k jednoduch´emu z´ısk´an´ı parametr˚ u od uˇzivatele. Vypoˇctenou optimalizaci n´aslednˇe program b2cII.jar zobraz´ı. Cel´ y optimalizaˇcn´ı cyklus vˇcetnˇe zobrazen´ı je zn´azornˇen na obr´azku 4.1.
4.1
Struktura soubor˚ u
Veˇsker´a komunikace jak mezi jednotliv´ ymi ˇc´astmi, tak mezi samotnou aplikac´ı a vnitˇrn´ımi ˇ syst´emy Skody, prob´ıh´a pomoc´ı soubor˚ u. V t´eto podkapitole budou detailnˇe pops´any struktury jednotliv´ ych soubor˚ u, kter´e jsou pro ˇcinnost aplikace nezbytn´e. Rozdˇelit bychom je mohli do tˇr´ı kategori´ı. Prvn´ı tvoˇr´ı vstupn´ı soubory, kter´e obsahuj´ı vstupn´ı data pro optimalizaci. Druhou pot´e v´ ystupn´ı soubory, kde jsou uloˇzeny v´ ysledky, a posledn´ı kategorii tvoˇr´ı konfiguraˇcn´ı soubory, kter´e obsahuj´ı potˇrebn´e informace pro ˇcinnost jednotliv´ ych ˇc´ast´ı aplikace.
4.1.1
Vstupn´ı soubory
Nejd˚ uleˇzitˇejˇs´ı vstupn´ı soubor je EXP_H_TETRIS.txt. Obsahuje jiˇz zmiˇ novan´ y seznam materi´alu, kter´ y je v danou chv´ıli moˇzn´e zahrnout do v´ ypoˇctu rozloˇzen´ı. Pˇr´ıklad obsahu tohoto souboru je v tabulce A.4. Soubor obsahuje: • k´od z´avodu, kam je materi´al expedov´an • den, kdy m´a b´ yt materi´al expedov´an, a k´od smˇeny • k´od materi´alu 9
VSTUPNÍ SOUBORY:
EXP_H_TETRIS.TXT
VÝSTUPNÍ SOUBORY:
GRAFICKÉ ROZHRANÍ
RES.DAT
ZOBRAZENÍ EXP_THI_MODUL.txt
OPTIMALIZAČNÍ APLIKACE
UNUSED.DAT
BCONFIG.DAT
MODULS.DAT
USED.DAT
CONFIG.XML
Obr´azek 4.1: Struktura optimalizaˇcn´ı cyklu
• poˇcet kus˚ u • z´avˇesku (tj. ˇc´ıslo krabice slouˇz´ıc´ı k identifikaci) • hmotnost jednoho kusu materi´alu Po zpracov´an´ı tˇechto informac´ı, vybr´an´ı odpov´ıdaj´ıc´ıch materi´al˚ u, je nutn´e jednotliv´e k´ody “rozluˇstit”, abychom vˇedˇeli, do jak´ ych modul˚ u je materi´al balen – tedy napˇr´ıklad kolik zab´ır´a m´ısta. K tomu slouˇz´ı dalˇs´ı dva soubory EXP_H_MODUL.txt a moduls.dat. V prvn´ım jmenovan´em souboru je ˇc´ıslovan´ y popis postupu balen´ı jednotliv´ ych materi´ al˚ u ˇrazen´ y vzestupnˇe, zn´azornˇeno v tabulce A.5. Tento “ofici´aln´ı” (nesnadno pochopiteln´ y) popis zjednoduˇsenˇe znamen´a, ˇze v souboru lze nal´est postup, jak s jednotliv´ ymi materi´ aly zach´azet, do ˇceho je postupnˇe ukl´adat a napˇr´ıklad jak´e bezpeˇcnostn´ı f´olie pouˇz´ıt. Na konci tohoto cyklu je pochopitelnˇe uveden i modul, ve kter´em je materi´al pˇrev´aˇzen (a pr´avˇe ten je d˚ uleˇzit´ y). Jelikoˇz je tento seznam ˇrazen vzestupnˇe (opaˇcnˇe neˇz se bal´ı), pro naˇsi optimalizaˇcn´ı aplikaci je potˇrebn´a pouze prvn´ı poloˇzka. Rozmˇery a nosnost jednotliv´ ych modul˚ u je pops´ana v druh´em souboru moduls.dat (viz. tabulka A.3). Po zpracov´an´ı souboru EXP_H_TETRIS.txt, a dohled´an´ı vˇsech potˇrebn´ ych informac´ı v dalˇs´ıch dvou souborech, z´ısk´ame u ´pln´ y seznam modul˚ u a materi´al˚ u v nich, ze kter´ ych 10
posl´eze poˇc´ıt´ame optim´aln´ı rozloˇzen´ı v n´akladov´em prostoru. Jak´ ym zp˚ usobem se z jednotliv´ ych soubor˚ u ˇctou u ´daje a v jak´em poˇrad´ı se zab´ yv´a podkapitola 4.3.
4.1.2
V´ ystupn´ı soubory
V tˇechto souborech jsou uv´adˇeny v´ ysledky optimalizaˇcn´ıho v´ ypoˇctu. Hlavn´ım souborem je res.dat. Jde o soubor, do kter´eho optimalizaˇcn´ı program uloˇz´ı vypoˇc´ıtan´e rozloˇzen´ı modul˚ u v kontejneru. Soubor pot´e vyuˇz´ıv´a zobrazovac´ı ˇc´ast aplikace. Struktura tohoto souboru je pops´ana v tabulce A.6. Mimo tento soubor se pˇri v´ ypoˇctu uloˇzen´ı materi´alu vytvoˇr´ı jeˇstˇe dalˇs´ı tˇri soubory, do kter´ ych je rozdˇelen materi´al ze vstupn´ıho souboru EXP_H_TETRIS.txt. Jedn´a se o soubory used.dat, unused.dat a error.dat. Jak n´azev napov´ıd´a, soubor used.dat slouˇz´ı k uloˇzen´ı informac´ı o materi´alu, kter´ y byl pouˇzit pˇri v´ ypoˇctu optimalizace, a je jiˇz uloˇzen v nˇejak´em kontejneru. Soubor slouˇz´ı pˇredevˇs´ım pro kontrolu. S t´ımto materi´alem se jiˇz nesm´ı v dalˇs´ım cyklu optimalizace poˇc´ıtat. Druh´ y soubor unused.dat obsahuje naopak materi´al, kter´ y nebyl vhodn´ ym zp˚ usobem naloˇzen do kontejner˚ u, a mus´ı tedy b´ yt zahrnut do v´ ypoˇctu v dalˇs´ım cyklu. Data se tam prakticky ukl´ad´aj´ı pr˚ ubˇeˇznˇe a na konci v´ ypoˇctu aktu´aln´ıho cyklu optimalizace jsou veˇsker´e materi´aly z tohoto souboru nakop´ırov´any zpˇet do vstupn´ıho souboru EXP_H_TETRIS.txt. Posledn´ı soubor z t´eto skupiny error.dat obsahuje materi´al, pro kter´ y nebyly pˇri naˇc´ıt´an´ı dohled´any vˇsechny potˇrebn´e informace, a neˇslo ho tedy zaˇradit do v´ ypoˇctu. Vˇetˇsinou se jedn´a o doplˇ nkov´ y materi´al. Tento probl´em si budou pracovn´ıci ˇreˇsit sami. Do dalˇs´ıho cyklu v´ ypoˇctu se tak tento materi´al jiˇz nezaˇrazuje.
4.1.3
Konfiguraˇ cn´ı soubory
Aplikace obsahuje dva konfiguraˇcn´ı soubory. Prvn´ı, config.xml, slouˇz´ı pˇr´ımo optimalizaˇcn´ımu programu. Obsahuje pouze poˇradov´e ˇc´ıslo kontejneru, pro kter´ y probˇehne dalˇs´ı cyklus v´ ypoˇctu. Po domluvˇe bylo zvoleno 7-mi m´ıstn´e ˇc´ıslo, tedy zaˇc´atek na 1 000 000. Druh´ y konfiguraˇcn´ı soubor bconfig.dat slouˇz´ı k uloˇzen´ı vˇsech dosud nevyexpedovan´ ych kontejner˚ u. Struktura tohoto souboru je shodn´a se souborem res.dat. Rozdˇelen´ı do dvou soubor˚ u je pˇredevˇs´ım z d˚ uvodu bezpeˇcnosti. Zat´ımco res.dat pouˇz´ıvaj´ı dva programy, kde jeden do nˇeho zapisuje a druh´ y z nˇeho ˇcte, bconfig.dat slouˇz´ı pouze zobrazovac´ı ˇc´asti aplikace.
4.2
Grafick´ e uˇ zivatelsk´ e rozhran´ı pro z´ısk´ an´ı poˇ zadavk˚ u pro optimalizaci
Tento program slouˇz´ı ke snadn´emu z´ısk´an´ı krit´eri´ı pro v´ ypoˇcet optimalizace. Hlavn´ı jeho funkc´ı je spustit se spr´avn´ ymi parametry probram b2c.exe, kter´ y pˇr´ımo prov´ad´ı v´ ypoˇcet. Uk´azka rozhran´ı je uvedena na obr´azku 4.2. a popis jednotliv´ ych ˇc´ast´ı je v n´asleduj´ıc´ı sekci 4.2.1 Po spuˇstˇen´ı, kter´e lze jednoduˇse prov´est pˇres z´astupce b2c.lnk, je otevˇreno okno o velikosti 350 × 350 pixel˚ u s n´azvem Optimalizaˇcn´ı aplikace.
4.2.1
Pˇ rehled jednotliv´ ych ˇ c´ ast´ı
V horn´ı ˇc´asti okna je um´ıstˇeno menu, kter´e obsahuje ovˇsem pouze tlaˇc´ıtko pro uzavˇren´ı. Jin´e moˇznosti nejsou potˇrebn´e. Menu jsem se rozhodl ponechat kv˚ uli uˇzivatel˚ um, kteˇr´ı jsou
11
Obr´azek 4.2: Screenshot rozhran´ı pro z´ısk´an´ı poˇzadavk˚ u pro optimalizaci
na tuto moˇznost ukonˇcen´ı program˚ u zvykl´ı. D´ale samotn´e okno obsahuje tˇri rolovac´ı liˇsty. Prvn´ı skr´ yv´a vˇsechny dny v t´ ydnu (Pondˇel´ı aˇz Nedˇele). Zvolen´a kolonka oznaˇcuje den, pro kter´ y se m´a optimalizace vypoˇc´ıtat. Lze vypoˇc´ıtat optimalizaci dopˇredu, maxim´alnˇe vˇsak o t´ yden, jelikoˇz program nerozliˇsuje datum, ale pouze den. Rozliˇsen´ı data je v tomto pˇr´ıpadˇe zbyteˇcn´e, protoˇze bal´ıc´ı pl´an je vytv´aˇren maxim´alnˇe nˇekolik dn´ı dopˇredu, tud´ıˇz v´ıce neˇz na t´ yden dopˇredu by stejnˇe nebyl zn´am potˇrebn´ y materi´al. Druh´ y rolovac´ı seznam obsahuje vˇsechny (dosud zn´am´e) mont´aˇzn´ı z´avody, do kter´ ych se m˚ uˇze dan´ y kontejner pos´ılat. Pokud je vybr´an z´avod z nab´ıdky, v pol´ıˇcku pod listboxem se zobraz´ı k´od z´avodu (napˇr. “74” pro Ukrajinu). Pokud je tˇreba zadat jin´ y z´avod, lze v seznamu zvolit moˇznost “. . . jin´ y z´avod”. Jiˇz zmiˇ novan´e pol´ıˇcko pod rolovac´ı liˇstou se zaktivn´ı a lze do nˇeho napsat k´od z´avodu ruˇcnˇe. Posledn´ı seznam obsahuje nˇekolik bˇeˇzn´ ych typ˚ u kontejner˚ u a vag´on˚ u, kter´e se pouˇz´ıvaj´ı pro pˇrepravu materi´alu. Tato rolovac´ı liˇsta je propojena se tˇremi pol´ıˇcky pod n´ı, takˇze po zvolen´ı nˇejak´e moˇznosti se zobraz´ı i velikost dan´eho n´akladov´eho prostoru. Pokud v seznamu nen´ı potˇrebn´ y kontejner, lze zadat opˇet moˇznost “. . . jin´ y rozmˇer” a do pol´ıˇcek pod seznamem vyplnit poˇzadovanou velikost ruˇcnˇe. Velikost n´akladov´eho prostoru je v centimetrech, to plat´ı i pro zad´av´an´ı velikosti ruˇcnˇe! Byla tak´e stanovena horn´ı hranice velikosti n´akladov´eho prostoru a to na 100 m ve vˇsech tˇrech rozmˇerech, coˇz je v´ıce neˇz postaˇcuj´ıc´ı. Pokud nen´ı zadan´a hodnota jak´ehokoliv rozmˇeru v intervalu 0 – 10 000 cm nebo ˇc´ıslo obsahuje chybn´ y znak, napˇr´ıklad p´ısmeno, program upozorn´ı uˇzivatele varovnou hl´aˇskou 4.4. V takov´em pˇr´ıpadˇe nelze pokraˇcovat ve v´ ypoˇctu, dokud nen´ı chyba odstranˇena. Po vyplnˇen´ı vˇsech pol´ıˇcek lze stisknout tlaˇc´ıtko “Spustit”, kter´e spust´ı samotn´ y optiypoˇctu nelze jakkoliv program malizaˇcn´ı program se zadan´ ymi parametry 4.3.1. Bˇehem v´ ovl´adat. Na u ´spˇeˇsn´e ukonˇcen´ı v´ ypoˇctu upozorn´ı hl´aˇska 4.3, kter´a obsahuje ˇc´ıslo kontejneru
12
Obr´azek 4.3: Hl´aˇska pˇri ukonˇcen´ı v´ ypoˇctu
Obr´azek 4.4: Varovn´a hl´aˇska
a jeho procentu´aln´ı zaplnˇen´ı. Dan´a optimalizace je jiˇz uloˇzena v souboru res.dat a lze ji zobrazit. Pokud vˇsechny zadan´e parametry jsou syntakticky spr´avnˇe, avˇsak z nˇejak´eho d˚ uvodu nelze rozloˇzen´ı vypoˇc´ıtat, zobraz´ı se informaˇcn´ı hl´aˇska 4.5. K tomuto m˚ uˇze doj´ıt napˇr´ıklad, pokud nen´ı dostateˇcn´e mnoˇzstv´ı materi´alu, ˇci pokud nelze materi´al vhodn´ ym zp˚ usobem uspoˇr´adat.
4.3
Optimalizaˇ cn´ı program
Tato podkapitola se zab´ yv´a j´adrem cel´eho projektu, a to programem, kter´ y vypoˇc´ıt´ av´ a rozloˇzen´ı modul˚ u ve zvolen´em n´akladov´em prostoru. Mimo zp˚ usobu, jak´ ym m´a b´ yt program spuˇstˇen, zde naleznete z´akladn´ı principy, jak program pracuje.
Obr´azek 4.5: Informaˇcn´ı hl´aˇska pˇri neproveden´ı optimalizace
13
4.3.1
Vstupn´ı parametry
Optimalizaˇcn´ı program b2c.exe je spouˇstˇen s mnoha parametry. Vˇetˇsina z nich jsou poˇzadavky uˇzivatel˚ u na proveden´ı v´ ypoˇctu. Jin´e jsou nastaveny grafick´ ym rozhran´ım na st´ ale stejnou hodnotu. Takov´e parametry na prvn´ı pohled nejsou v˚ ubec potˇrebn´e, dod´any tam vˇsak byly z d˚ uvodu moˇznosti dalˇs´ıho vyuˇzit´ı a rozvoje samotn´eho optimalizaˇcn´ıho programu (viz. kapitola 6.2). Po spuˇstˇen´ı jsou vˇsechny parametry pˇreˇcteny funkc´ı getParams() a jsou uloˇzeny do struktury params tak, aby k nim byl bˇehem cel´eho procesu v´ ypoˇctu moˇzn´ y pˇr´ıstup. Pokud pro spuˇstˇen´ı nepouˇzijeme grafick´e uˇzivatelsk´e rozhran´ı, lze program spustit tak´e s parametrem -h, tzn. ./b2c.exe -h. T´ım se vyp´ıˇse obrazovka s n´apovˇedou, jak lze jednotliv´e parametry zadat a co znamenaj´ı (viz. tabulka 4.1). Pˇr´ıklad pouˇzit´ı: b2c.exe -pocet_dnu (PO-NE) mira_uspesnosti -kontrola_vysledku cislo_zavodu cislo_kontejneru velikost_x velikost_y velikost_z -pocet_kontejneru. Parametr –pocet dnu (PO-NE) mira uspesnosti –kontrola vysledku cislo zavodu cislo kontejneru velikost x velikost y velikost z –pocet kontejneru
Popis poˇcet dn˚ u, kter´e se maj´ı vypoˇc´ıtat seznam poˇzadovan´ ych dn˚ u urˇcuje, kdy lze ukonˇcit v´ ypoˇcet poˇzadavek, zda se m´a pˇred ukonˇcen´ım odsouhlasit v´ ysledek zaplnˇen´ı ˇc´ıslo z´avodu, kam se materi´al pos´ıl´a poˇradov´e ˇc´ıslo kontejneru ˇs´ıˇrka n´akladov´eho prostoru v cm v´ yˇska n´akladov´eho prostoru v cm hloubka n´akladov´eho prostoru v cm poˇcet kontejner˚ u, kter´e se maj´ı vypoˇc´ıtat Tabulka 4.1: Popis vstupn´ıch parametr˚ u
ˇ Jak je patrn´e z poˇzadavk˚ u Skody, vypoˇc´ıt´av´a se v danou chv´ıli pouze jeden kontejner a v´ ysledek se nekontroluje. Pr´avˇe v tˇechto oblastech je pˇredpoklad dalˇs´ıho v´ yvoje aplikace. Program s tˇemito moˇznostmi vˇsak jiˇz pracuje a je moˇzn´e jej plnˇe vyuˇz´ıvat napˇr. pˇri testov´ an´ı ˇci v´ yzkumu.
4.3.2
Naˇ cten´ı a uchov´ av´ an´ı dat bˇ ehem v´ ypoˇ ctu
Po zpracov´an´ı parametr˚ u dojde k naˇcten´ı informac´ı o materi´alu funkc´ı readData(). Bˇehem v´ ypoˇctu mus´ı b´ yt vˇsechny informace neust´ale k dispozici. Byly proto vytvoˇreny dva seznamy, jejichˇz struktury vˇcetnˇe jednotliv´ ych sloˇzek jsou uloˇzeny v hlaviˇckov´em souboru b2c.h. Prvn´ı seznam obsahuje vˇsechny moduly, se kter´ ymi lze pˇri v´ ypoˇctu poˇc´ıtat. Kaˇzd´ y modul je zde reprezentov´an strukturou, kter´a je zn´azornˇena v tabulce 4.2 vˇcetnˇe popisu jednotliv´ ych poloˇzek. Uchov´av´any tak jsou veˇsker´e potˇrebn´e informace o materi´alu. Pro zrychlen´ı v´ ypoˇctu jsou poloˇzky v seznamu ˇrazeny podle velikosti od nejvˇetˇs´ıch po nejmenˇs´ı. Bylo tak´e nutn´e rozhodnout, jak´e datov´e typy budou postaˇcuj´ıc´ı pro dan´e poloˇzky. U vˇetˇsiny ˇc´ıseln´ ych hodnot byl pouˇzit unsigned int, kter´ y sv´ ym rozsahem je v´ıce neˇz dostaˇcuj´ıc´ı, napˇr. pro z´avˇesku ˇci v´ahu modulu.
14
Poloˇzka struktury unsigned int zaveska char matnb[19] tsize size unsigned int weight unsigned int max load int rotation tsize point unsigned int capacity int used char modul[10] int counting char fullstring[64] int pocetbal twrap wrap
Popis z´avˇeska slouˇz´ı k identifikaci modulu k´od materi´alu v modulu velikost modulu, vnoˇren´a struktura obsahuje tˇri rozmˇery v´aha modulu vˇcetnˇe materi´alu nosnost modulu pˇr´ıznak otoˇcen´ı modulu um´ıstˇen´ı v kontejneru objem modulu pˇr´ıznak pouˇzit´ı modulu pˇri v´ ypoˇctu oznaˇcen´ı modulu pˇr´ıznak zapoˇc´ıt´an´ı do v´ ysledku cel´ y ˇretˇezec s parametry pro snadn´e vypisov´an´ı poˇcet balen´ı materi´alu obsahuje poˇcet a n´azev vloˇzen´ ych modul˚ u Tabulka 4.2: Struktura box
Druh´ y seznam obsahuje ukazatele na poloˇzky prvn´ıho seznamu, kter´e jsou v danou chv´ıli pouˇzity v kontejneru (viz. sekce 4.3.3). Cel´ y v´ ypoˇcet je prov´adˇen rekurz´ı, tud´ıˇz je nutn´e zn´at poˇrad´ı, v jak´em se moduly vkl´adaj´ı do kontejneru, aby v pˇr´ıpadˇe ne´ uspˇeˇsn´eho v´ ypoˇctu mohly b´ yt zase jednotlivˇe odeb´ır´any.
4.3.3
Princip v´ ypoˇ ctu uloˇ zen´ı materi´ alu
V t´eto sekci bude pops´an z´akladn´ı princip v´ ypoˇctu optimalizace. Po zpracov´an´ı parametr˚ u a vytvoˇren´ı seznamu s informacemi o jednotliv´ ych modulech, zavol´a hlavn´ı funkce main() funkci optimalization(). T´eto funkci je jako parametr pˇred´an mimojin´e ukazatel na datov´ y typ tspace, ve kter´em jsou uloˇzeny informace o n´akladov´em prostoru, do kter´eho se optimalizace vypoˇc´ıt´av´a. Funkce v hlavn´ım cyklu “bere” jednotliv´e poloˇzky ze seznamu (4.2) a “vkl´ad´a” je do dan´eho prostoru (do lev´eho spodn´ıho rohu). Zda lze opravdu modul do prostoru vloˇzit, kontroluje funkce checkbox(). Pokud m˚ uˇze doj´ıt k vloˇzen´ı modulu do prostoru, vytvoˇr´ı se dalˇs´ı tˇri imagin´arn´ı n´akladov´e prostory, alokuj´ı se tˇri datov´e typy tspace, a vypln´ı se hodnotami. Jeden nad dan´ ym modulem, druh´ y vedle a tˇret´ı pˇred n´ım (obr´azek 4.6).Jak jiˇz bylo ˇreˇceno, algoritmus funguje na principu rekurze, tud´ıˇz v tomto m´ıstˇe funkce optimalization() vol´ a sama sebe. V podstatˇe se vol´a pr´avˇe tˇrikr´at, jako parametr ji je totiˇz pˇred´an pokaˇzd´e jeden z novˇe vytvoˇren´ ych prostor˚ u. Takto dojde k rozdˇelen´ı kontejneru na mal´e ˇc´asti, do kter´ ych jsou vkl´ad´any jednotliv´e moduly. Pokud ve vrchn´ıch patrech takto vytvoˇren´e pyramidy dojde k dostateˇcn´emu zaplnˇen´ı kontejneru, vrac´ı funkce do vrstvy pod sebou objem zaplnˇen´eho prostoru. Pokud k tomuto nedojde, postupnˇe se odeb´ıraj´ı z prostoru moduly, a funkce zkouˇs´ı do dan´eho prostoru vloˇzit jin´ y modul a v´ ypoˇcet opakovat. Takto algoritmus prob´ıh´a ve smyˇcce dokud se nedos´ahne v cel´em kontejneru dostateˇcn´eho zaplnˇen´ı (zadan´eho uˇzivatelem). Jiˇz zmiˇ novan´a funkce checkbox() nav´ıc bˇehem testov´an´ı, zda je modul moˇzn´e vloˇzit do dan´eho prostoru, tak´e zkoum´a, zda se nejedn´a o GLT modul. Tedy o modul, kter´ y lze stohovat podle specifick´ ych pravidel (viz. tabulka A.1). Pokud ano, vyzkouˇs´ı moˇznosti
15
Obr´azek 4.6: Rozloˇzen´ı prostor˚ u v kontejneru
“podloˇzen´ı” modulu. Jak jsou jednotliv´e moduly ukl´ad´any do kontejneru, vytv´aˇr´ı se na nˇe ukazatele a vkl´adaj´ı se do druh´eho seznamu. Takto lze pot´e jednoduˇse moduly zase odeb´ırat a m´ame neust´ ale pˇrehled, kter´e moduly jsou jiˇz do optimalizace zahrnuty a kter´e ne.
4.3.4
Uloˇ zen´ı v´ ysledku a ukonˇ cen´ı programu
Pokud v´ ypoˇcet probˇehne u ´spˇeˇsnˇe, tzn. m´ıra zaplnˇen´ı pˇres´ahla poˇzadovanou hranici, je nutn´e vˇsechna data vhodnˇe uloˇzit. To m´a na starosti funkce saveResult(). Nejdˇr´ıve je nutn´e vˇsak pˇrepoˇc´ıtat pouˇzit´ y materi´al. Proch´az´ı se oba seznamy a do soubor˚ u used.dat a unused.dat jsou rozdˇelov´any jednotliv´e moduly s materi´alem. K tomu slouˇz´ı funkce countingBoxes(). Dˇr´ıve popsan´ y zp˚ usob ukl´ad´an´ı poloˇzek do druh´eho seznamu s ukazateli naznaˇcil, ˇze takov´eto poˇrad´ı modul˚ u je vhodn´e pro v´ ypoˇcet. Ovˇsem pˇri zobrazen´ı by vznikl znaˇcn´ y chaos. Je proto nutn´e moduly pˇreskl´adat.N´asledovat po sobˇe mus´ı tak, jak by se optim´alnˇe skl´adali do kontejneru, tedy odzadu dopˇredu a odzdola nahoru. To zaˇrizuje funkce rangeResults(), kter´a vytvoˇr´ı pomocn´ y seznam a moduly pˇrerovn´a. Nyn´ı jiˇz m˚ uˇzeme vypoˇc´ıtan´e rozm´ıstˇen´ı modul˚ u v kontejneru uloˇzit do souboru res.dat. Nejdˇr´ıve jsou uloˇzeny vˇsechny informace o n´akladov´em prostoru, pot´e seznam vˇsech modul˚ u a jejich um´ıstˇen´ı. Pr˚ ubˇeˇznˇe funkce ’ uvolˇ nuje pamˇet alokovonanou sloˇzkami seznamu. Na konci se uvoln´ı veˇsker´e alokovan´e seznamy. Program jeˇstˇe na standartn´ı v´ ystup vytiskne m´ıru zaplnˇen´ı, kterou zobraz´ı grafick´e uˇzivatelsk´e rozhran´ı, a bezpeˇcnˇe se ukonˇc´ı.
4.4
Program pro zobrazen´ı kontejner˚ u a jejich naloˇ zen´ı
Tato podkapitola se zab´ yv´a zobrazen´ım vypoˇc´ıtan´eho rozloˇzen´ı modul˚ u v kontejneru. D˚ uraz byl kladen pˇredevˇs´ım na pˇrehlednost, aby pomoc´ı programu bylo moˇzn´e pˇr´ımo prov´adˇet nakl´adku kontejneru. Pro jednoduch´e spuˇstˇen´ı byl vytvoˇren odkaz b2cII.lnk v hlavn´ım adres´aˇri. Po spuˇstˇen´ı programu se otevˇre hlavn´ı okno, kter´e je zn´azornˇeno na obr´azku 4.7. Velikost okna je nastavena na 1024 × 735 pixel˚ u, tedy na takovou velikost, aby se na monitorech s nejpouˇz´ıvanˇejˇs´ım rozliˇsen´ım 1024 × 768 px zobrazilo pˇres celou obrazovku. Z d˚ uvod˚ u velikosti jednotliv´ ych vnoˇren´ ych ˇc´ast´ı, kter´e jsou pops´any v ˇc´asti 4.4.1, nelze velikost hlavn´ıho okna upravovat.
16
Obr´azek 4.7: Screenshot programu pro zobrazov´an´ı naloˇzen´ı kontejner˚ u
17
4.4.1
Pˇ rehled jednotliv´ ych ˇ c´ ast´ı
Okno s n´azvem “Zobrazen´ı kontejner˚ u” je rozdˇeleno do ˇctyˇr hlavn´ıch ˇc´ast´ı. Vlevo je um´ıstˇen stromov´ y seznam s aktu´aln´ımi kontejnery, kter´e jeˇstˇe nebyly vyexpedov´any. Vˇsechny jsou oznaˇcen´e sv´ ymi identifikaˇcn´ımi ˇc´ısly. Po kliknut´ı na ˇc´ıslo kontejneru se poloˇzka rozvine a objev´ı se seznam vˇsech modul˚ u, kter´e po v´ ypoˇctu optimalizace kontejner obsahuje. Toto je nejjednoduˇsˇs´ı zp˚ usob ovl´ad´an´ı. Aktivn´ı prvek, kontejner nebo modul, jsou oznaˇceny modr´ ym podkladem. Dalˇs´ı ˇc´ast tvoˇr´ı panel s nadpisem “Souhrn´e informace”. V nˇem se zobrazuj´ı vˇsechny d˚ uleˇzit´e informace o pr´avˇe aktivn´ım prvku v jiˇz zmiˇ novan´em seznamu. Rozdˇelen je do dvou ˇc´ast´ı, v horn´ı se zobrazuj´ı informace o kontejneru a ve spodn´ı ˇc´asti o aktu´aln´ım modulu. Pokud je aktivn´ı prvek v seznamu pˇr´ımo kontejner, ve spodn´ı ˇc´asti se samozˇrejmˇe nic nezobrazuje. U kontejner˚ u jsou zde informace o ID ˇc´ısle, dnu, kdy m´a b´ yt odesl´an, k´odu z´avodu, kam je pos´ıl´an, a jeho velikosti v centimetrech. Spodn´ı ˇc´ast, zobrazuj´ıc´ı informace o aktivn´ım modulu, naopak zobrazuje z´avˇesku, oznaˇcen´ı modulu, velikost modulu, poˇcet a druh vloˇzen´ ych modul˚ u, pokud nˇejak´e obsahuje. Jednou z nejd˚ uleˇzitˇejˇs´ıch ˇc´ast´ı cel´eho programu jsou okna, kde se naloˇzen´ı kontejneru pˇr´ımo zobrazuje. Jsou tˇri a jsou na sobˇe plnˇe z´avisl´a. Kaˇzd´e vˇsak zobrazuje kontejner z jin´eho pohledu. Prvn´ı menˇs´ı okno je um´ıstˇeno uprostˇred v horn´ı ˇc´asti a zobrazuje kontejner zepˇredu, tzn. ze strany, kde jsou dveˇre. Dalˇs´ı dvˇe vˇetˇs´ı okna jsou rozm´ıstˇena v doln´ı ˇc´asti hlavn´ıho okna a ukazuj´ı kontejner zprava, resp. zleva. Kde jsou dveˇre kontejneru zn´azorˇ nuje ˇsipka na stranˇe. Vˇsechna okna nav´ıc ve sv´ ych okrajov´ ych ˇc´astech obsahuj´ı informace o smˇeru pohledu, zvˇetˇsen´ı a velikosti kontejneru samotn´eho. Kontejnery jsou zde zn´azornˇeny modˇre, naloˇzen´e moduly v nich ˇzlutˇe a posledn´ı (aktivn´ı) modul ˇcervenˇe. Pokud bychom najednou zobrazili vˇsechny moduly v kontejneru, kter´e jsou jiˇz naloˇzen´e, nebylo by z obr´azku moˇzn´e t´emˇeˇr cokoliv vyˇc´ıst. Zobrazuj´ı se tud´ıˇz pouze moduly, kter´e jsou bezprostˇrednˇe nejbl´ıˇze aktivn´ımu modulu. Pokud je modul napˇr´ıklad ve vyˇsˇs´ı vrstvˇe, zobraz´ı se s n´ım pouze moduly pod n´ım. Pro jeˇstˇe lepˇs´ı zn´azornˇen´ı pˇresn´eho um´ıstˇen´ı modulu v kontejneru, obsahuje program dalˇs´ı dvˇe funkce. Jedna z nich je moˇznost zvˇetˇsen´ı pohledu. Velikost prvk˚ u v oknech se pot´e zvˇetˇs´ı, tud´ıˇz zobraz´ı vˇetˇs´ı detail. Implicitnˇe je pohled po zvˇetˇsen´ı zarovn´an na aktivn´ı modul, tud´ıˇz druhou d˚ uleˇzitou funkc´ı je moˇznost “pohybu” v zobrazovac´ıch oknech. Lze se pohybovat jednak po ose x, tzn. doprava a doleva, a tak´e ve smˇeru osy y, tud´ıˇz nahoru a dol˚ u. K pouˇzit´ı tˇechto funkc´ı slouˇz´ı bud’ tlaˇc´ıtka v ovl´adac´ım panelu (viz. d´ale) nebo nab´ıdka menu v z´aloˇzce Zobrazen´ ı. Jedin´e okno nepodl´ehaj´ıc´ı tˇemto u ´prav´am je horn´ı, kter´e zobrazuje ˇceln´ı pohled. Posledn´ı ˇc´ast´ı je jiˇz zmiˇ novan´ y ovl´adac´ı panel. Obsahuje tlaˇc´ıtka pro posun v seznamu s kontejnery (a to jak na dalˇs´ı modul, tak na dalˇs´ı kontejner a zpˇet). Zda se jedn´a o moˇznost t´ ykaj´ıc´ı se kontejner˚ u nebo modul˚ u, je zˇrejm´e z mal´eho c (z anglick´eho container ), resp. b (z anglick´eho box ). D´ale je zde tlaˇc´ıtko pro aktualizaci seznamu, tzv. “Refresh”. Po stisknut´ı program zkontroluje soubor res.dat, zda od doby spuˇstˇen´ı nedoˇslo k v´ ypoˇctu dalˇs´ıho kontejneru. Pokud ano, zaˇrad´ı nov´ y kontejner na konec aktu´aln´ıho seznamu kontejner˚ u a lze ho zobrazit. Tlaˇc´ıtko s oznaˇcen´ım “Uzavˇren´ı (vymaz´an´ı) kontejneru” slouˇz´ı k ukonˇcen´ı bal´ıc´ıho cyklu dan´eho kontejneru. Program kontejner vyˇrad´ı ze seznamu a jiˇz ho d´ale neukl´ad´a. Tud´ıˇz dan´ y kontejner jiˇz nelze zobrazit ani se k nˇemu nijak vracet. Ve spodn´ı ˇc´asti panelu jsou tlaˇc´ıtka umoˇzn ˇuj´ıc´ı jiˇz zmiˇ novan´ y pohyb a zvˇetˇsov´an´ı. K jednoduch´emu n´avratu slouˇz´ı tlaˇc´ıtko “V´ ychoz´ı”, po jehoˇz stisknut´ı jsou kontejnery opˇet vykresleny v p˚ uvodn´ı velikosti a pozici.
18
Vˇsechny tyto moˇznosti, kter´e obsahuje ovl´adac´ı panel, lze rovnˇeˇz nal´ezt v menu. To je tradiˇcnˇe um´ıstˇeno v horn´ı ˇc´asti okna a je rozdˇeleno do tˇr´ı z´akladn´ıch poloˇzek: Soubor, Navigace a Zobrazen´ ı.
4.4.2
3D zobrazen´ı
Velk´ ym specifikem cel´eho programu je moˇznost zobrazen´ı ve 3D s´ıt’ov´eho modelu kontejneru. Jde o samostatn´ y program spustiteln´ y pomoc´ı tlaˇc´ıtka v ovl´adac´ım panelu “3D zobrazen´ı”. ˇ Skoda p˚ uvodnˇe pl´anovala zaˇradit tento program jako souˇc´ast sv´ ych aplikac´ı a vlastn´ı zobrazovac´ı program, jak je pops´an v´ yˇse, v˚ ubec nevytv´aˇret. Zmˇena je ale ˇzivot, n´avrh pozdˇejˇs´ıho zobrazovac´ıho programu jiˇz s moˇznost´ı 3D zobrazen´ı nepoˇc´ıtal, pˇredevˇs´ım pro jej´ı obt´ıˇznost orientace pˇri bˇeˇzn´em pouˇz´ıv´an´ı. Avˇsak zˇrejmˇe bych aplikaci ochudil, kdybych moˇznost 3D zobrazen´ı nezahrnul v˚ ubec. Program je naps´an v OpenGL. Pˇri zobrazen´ı vyuˇz´ıv´a soubor bconfig.dat, do kter´eho zobrazovac´ı program ukl´ad´a seznam kontejner˚ u. Pˇri spuˇstˇen´ı zobraz´ı pouze jedno okno s dan´ ym kontejnerem. Ovl´ad´an´ı se prov´ad´ı pomoc´ı kl´avesnice, jak je pops´ano v tabulce 4.3. Pouze ot´aˇcen´ı kolem zadn´ıho doln´ıho bodu kontejneru se prov´ad´ı pomoc´ı stisknut´ı a pohybu myˇsi. Jako parametr pˇri spuˇstˇen´ı program oˇcek´av´a ˇc´ıslo kontejneru, kter´e se m´a naˇc´ıst a index aktivn´ıho modulu. Zobraz´ı tak kontejner shodnˇe, jako vˇsechna tˇri okna zobrazovac´ıho programu. Uk´azka programu je zn´azornˇena na obr´azku 4.8. Pˇri jak´ekoliv ˇcinnosti v hlavn´ım oknˇe zobrazovac´ıho programu, je okno 3D zobrazen´ı uzavˇreno. Kl´avesa f g u i p o d a w s q
Popis fullscreen velikost okna 500 × 500 px vloˇzen´ı dalˇs´ıho modulu odebr´an´ı posledn´ıho modulu vloˇzen´ı vˇsech modul˚ u vypr´azdnˇen´ı kontejneru pohyb doprava pohyb doleva pohyb nahoru pohyb dol˚ u uzavˇren´ı okna
Tabulka 4.3: Ovl´ad´an´ı programu pro 3D zobrazen´ı
19
Obr´azek 4.8: Zobrazov´an´ı pomoc´ı 3D s´ıt’ov´eho modelu
20
Kapitola 5
Implementace a testov´ an´ı Tato kapitola se zab´ yv´a popisem implementace cel´e aplikace, pouˇzit´ ych n´astroj˚ u a probl´em˚ u n´avrhu, kter´e bylo nutn´e vyˇreˇsit ˇci kter´e na vyˇreˇsen´ı jeˇstˇe ˇcekaj´ı. Pr˚ ubˇeˇznˇe bude zm´ınˇen postup pˇri testov´an´ı jednotliv´ ych ˇc´ast´ı, kter´ y bude na z´avˇer shrnut. Grafick´e rozhran´ı pro z´ısk´an´ı poˇzadavk˚ u i zobrazovac´ı program jsou naps´any v jazyce Java. To pˇrin´aˇs´ı i urˇcit´a opatˇren´ı, kter´a jsou potˇrebn´a pro jejich bezprobl´emov´e spuˇstˇen´ı, jako je napˇr. nutnost instalace Java Virtual Machine. To je v podstatˇe software, kter´ y vystupuje jako hardwarov´e zaˇr´ızen´ı a kter´e pˇrev´ad´ı bytov´ y k´od (kter´ y vytv´aˇr´ı pˇrekladaˇc jazyku Java) do nativn´ıch instrukc´ı pro dan´ y hostitelsk´ y poˇc´ıtaˇc. Zm´ınˇen´ y bytov´ y k´ od (nebo tak´e pseudok´od) je zjednoduˇsenˇe optimalizovan´a sada instrukc´ı. Velkou v´ yhodou je pˇrenositelnost tˇechto bytov´ ych k´od˚ u [3]. Oba programy psan´e v Javˇe byly testov´any v prostˇred´ı Java 2, Standart Edition SKD (JDK 1.4). Optimalizaˇcn´ı program je pot´e naps´an pomoc´ı standartn´ıch knihoven v jazyku C a program umoˇzn ˇuj´ıc´ı 3D zobrazen´ı naloˇzen´ı kontejner˚ u pot´e jeˇstˇe vyuˇz´ıv´a knihovny OpenGL. Oba tedy vyuˇz´ıvaj´ı pˇrekladaˇc, kter´ y je z´avisl´ y na typu procesoru a nezˇr´ıdka i na operaˇcn´ım syst´emu. Pˇrekladaˇc ale vytvoˇr´ı spustiteln´ y k´od, kter´ y je sobˇestaˇcn´ y. Nev´ yhodou je, ˇze takto vytvoˇren´e programy nelze pˇren´aˇset do jin´ ych prostˇred´ı. Na snadˇe je tedy ot´azka, proˇc nejsou vˇsechny ˇc´asti aplikace psan´e stejn´ ym programovac´ım jazykem. D˚ uvod je prost´ y, p˚ uvodnˇe nemˇel m´ıt optimalizaˇcn´ı program ˇz´adn´e grafick´e rozhran´ı, pˇres kter´e by se zad´avaly parametry. Tedy bylo jedno, v jak´em jazyce bude optimalizaˇcn´ı program naps´an a jazyk C se zd´ al postaˇcuj´ıc´ı.
5.1
Adres´ aˇ rov´ a struktura
ˇ Cel´a aplikace je vloˇzena do jedin´eho adres´aˇre. Ve Skodˇ e byl pro aplikaci urˇcen prostor v adres´aˇri \\skdambveot\eota$\eot6$\hala_U33. Pˇr´ımo zde jsou dva z´astupci b2c.lnk a b2cII.lnk. Prvn´ı spust´ı grafick´e rozhran´ı pro zad´av´an´ı poˇzadavk˚ u, jak je pops´ano v podkapitole 4.2. Druh´e pak zobrazovac´ı program popsan´ y v podkapitole 4.4. Ve sloˇzce data jsou pot´e um´ıstˇeny vˇsechny programy vˇcetnˇe soubor˚ u potˇrebn´ ych k jejich spuˇstˇen´ı. Zat´ımco ve druh´e sloˇzce sources se nach´azej´ı zdrojov´e k´ody.
21
5.2
Grafick´ e uˇ zivatelsk´ e rozhran´ı pro z´ısk´ an´ı poˇ zadavk˚ u pro optimalizaci
Program byl implementov´an podle n´avrhu popsan´em v podkapitole 4.2. V t´eto podkapitole se detailnˇeji pod´ıv´ame na zp˚ usob, jak´ ym byl program vytvoˇren pˇredevˇs´ım z pohledu program´atora. Jak jiˇz bylo ˇreˇceno, je cel´ y naps´an v Javˇe. Grafick´e komponenty byly vytvoˇreny pˇredevˇs´ım pomoc´ı knihovny Swing definovan´e v bal´ıˇcku javax.swing. Program tvoˇr´ı tˇri tˇr´ıdy. Tˇr´ıda Main obsahuje pouze funkci main() a slouˇz´ı k zobrazen´ı hlavn´ıho okna pomoc´ı funkce run(). Hlavn´ı tˇr´ıdou je tak BFrame, kter´a se pak star´a o vytvoˇren´ı a bˇeh tohoto okna. Na zaˇc´atku vytvoˇr´ı hlavn´ı r´amec (frame), do kter´eho um´ıst´ı vˇsechny komponenty jak jsou popsan´e v sekci 4.2.1. Rolovac´ı seznamy jsou vytv´aˇreny komponentou JComboBox, zat´ımco pol´ıˇcka pro zad´av´an´ı napˇr´ıklad c´ılov´eho mont´aˇzn´ıho z´avodu jsou vytv´aˇreny komponentou JTextField. Po vytvoˇren´ı tototo okna je nejd˚ uleˇzitˇejˇs´ı spr´avnˇe zachyt´avat vznikl´e ud´alosti. K tomu slouˇz´ı metoda actionPerformed(ActionEvent e), kter´a napˇr´ıklad pˇri stisknut´ı tlaˇc´ıtka “Spustit” vol´a funkce, kter´e vedou ke spuˇstˇen´ı optimalizaˇcn´ı aplikace. Jde pˇredevˇs´ım o funkci checkExe(), kter´a nejprve kontroluje zadan´e parametry. Pokud nastane nˇejak´a chyba, vyp´ıˇse chybovou hl´aˇsku. Pot´e spust´ı optimalizaˇcn´ı program a ˇcek´a na odpovˇed’. Posledn´ı tˇr´ıdou je BConfig. Konstruktor tˇr´ıdy na zaˇc´atku naˇcte konfiguraci, tedy pˇredevˇs´ım ˇc´ıslo kontejneru, jehoˇz naloˇzen´ı bude optimalizov´ano. D´ale se tak´e star´a o uloˇzen´ı aktu´aln´ı konfigurace napˇr´ıklad pˇri ukonˇcen´ı programu.
5.3
Optimalizaˇ cn´ı program
Optimalizaˇcn´ı program byl implementov´an podle n´avrhnu popsan´em v podkapitole 4.3 vˇcetnˇe vˇsech z´akladn´ıch princip˚ u. Jsou zde nast´ınˇeny i funkce a ovl´ad´an´ı programu. V t´eto podkapitole bych se proto v´ıce vˇenoval “bolav´ ym m´ıst˚ um”, kter´e pˇri implementaci vznikly. Nejvˇetˇs´ı z nich zrˇejmˇe je, ˇze aˇckoliv kontrola pˇret´ıˇzen´ı jednotliv´ ych modul˚ u v algoritmu ˇ je implementov´ana, lid´e ze Skody jeˇstˇe nezjistili v´ahu vˇsech materi´al˚ u. Nemohou je tedy uv´adˇet u vˇsech poloˇzek v souboru EXP_H_TETRIS.txt, a tud´ıˇz je tato funkce z programu zat´ım vyˇclenˇena. Program tak vypoˇc´ıt´av´a rozloˇzen´ı pouze s ohledem na velikost modul˚ u a moˇznost jejich stohov´an´ı. Tato skuteˇcnost se samozˇrejmˇe odrazila pˇredevˇs´ım na dobˇe v´ ypoˇctu. Lze pˇredpokl´adat, ˇze po zaˇclenˇen´ı t´eto funkce zpˇet vzroste ˇcas, kter´ y je k v´ ypoˇctu potˇreba. Nejde ani tak o samotnou funkci, kter´a pˇret´ıˇzen´ı kontroluje, ale pˇredevˇs´ım o to, ˇze bude vyhovovat pro dan´e um´ıstˇen´ı menˇs´ı procento modul˚ u, ˇcili se vhodn´ y modul bude hledat d´ele. T´ım nar´aˇz´ıme na dalˇs´ı probl´em. Jak stanovit dobu, po kterou je moˇzn´e na v´ ysledek jeˇstˇe ˇcekat? Omezit program ˇcasovˇe by bylo zˇrejmˇe kr´atkozrak´e, jelikoˇz by pot´e na kaˇzd´em typu procesoru provedl jin´ y poˇcet rekurz´ı. Omezen je tedy poˇcet rekurz´ı, kter´ y algoritmus provede. V glob´aln´ı promˇenn´e timer je inkrementov´ana hodnota pokaˇzd´em vol´an´ı funkce optimalization(), z´aroveˇ n je v tuto chv´ıli i dan´a promˇenn´a porovn´av´ana s promˇennou TIMER, ve kter´e je uloˇzena hodnota ud´avaj´ıc´ı maxim´aln´ı poˇcet rekurz´ı. V naˇsem pˇr´ıpadˇe stanovena na 20 000 000 a v pˇr´ıpadˇe pˇrekroˇcen´ı t´eto hodnoty provede program nezbytn´e kroky a ukonˇc´ı se. Jak je vidˇet pˇri testov´an´ı z tabulky A.8, kde je pˇrehled v´ ysledk˚ u testov´an´ı, je to v´ıce neˇz postaˇcuj´ıc´ı hodnota. Po zaˇclenˇen´ı kontroly pˇret´ıˇzen´ı modul˚ u bude nutn´e hodnotu opˇet uv´aˇzit, ale mysl´ım si, ˇze i pot´e bude 20 mil. postaˇcovat.
22
5.4
Program pro zobrazen´ı kontejner˚ u a jejich naloˇ zen´ı
Tato ˇc´ast aplikace je zˇrejmˇe nejvˇetˇs´ı, co se t´ yˇce ˇr´adk˚ u k´odu. Napsan´a je v jazyce Java. Obsahuje celkem 16 tˇr´ıd, kter´e se staraj´ı o bezprobl´emov´ y bˇeh programu, a jsou vˇsechny um´ıstˇeny v bal´ıku b2cii, coˇz odpov´ıd´a i organizaci adres´aˇre se zdrojov´ ymi k´ody. Vstupn´ı bod do programu je tˇr´ıda Main, kter´a obsahuje metodu main(). Jak bylo pops´ano v podkapitole 4.4, hlavn´ı okno aplikace obsahuje nˇekolik prvk˚ u. Kaˇzd´a komponenta je pot´e ovl´ad´ana samostatnou tˇr´ıdou, kter´a obsahuje vˇsechny potˇrebn´e metody. Neˇz si vˇsak uk´aˇzeme tˇr´ıdy, kter´e jsou v programu “vidˇet”, je d˚ uleˇzit´e popsat dvˇe tˇr´ıdy, se kter´ ymi ostatn´ı neust´ale pracuj´ı. Jedn´a se o tˇr´ıdy BContainer a BBox. Instance tˇechto tˇr´ıd tvoˇr´ı uzly stromov´eho seznamu s kontejnery a obsahuj´ı vˇsechny potˇrebn´e informace o kontejneru ˇci modulu. Hlavn´ı tˇr´ıdou programu pak je BMainWindow. Jej´ı konstruktor vytvoˇr´ı nejprve hlavn´ı okno a uprav´ı jeho nastaven´ı. Deklaruje promˇenn´e objektov´ ych typ˚ u, pomoc´ı oper´atoru new vytvoˇr´ı a pˇrid´a postupnˇe vˇsechny objekty, kter´e si d´ale jednotlivˇe rozebereme. Jednou z nejd˚ uleˇzitˇejˇs´ıch funkc´ı t´eto tˇr´ıdy je pr´avˇe propojen´ı onˇech objekt˚ u. Pokud v seznamu kontejner˚ u dojde k zachycen´ı ud´alosti, napˇr´ıklad posunu aktivn´ıho prvku, tato tˇr´ıda zajist´ı, aby se dan´a zmˇena projevila i v zobrazovac´ıch oknech. K tomu obsahuje tˇr´ıda metody setCont() na nastaven´ı aktivn´ıho kontejneru a setBox() na vykreslen´ı modul˚ u. Tˇr´ıda se d´ale tak´e metodou saveConfig() star´a o ukl´ad´an´ı aktu´aln´ıho stavu seznamu kontejner˚ u ˇci metodou Refresh() o zjiˇstˇen´ı novˇe vypoˇc´ıtan´ ych kontejner˚ u. A nyn´ı si projdeme jednotliv´e objekty. Tˇr´ıda BMenuBar vytv´aˇr´ı liˇstu menu. Z deklarace tˇr´ıdy je patrn´e, ˇze “rozˇsiˇruje” tˇr´ıdu JPanel z knihovny Swing. Konstruktor vytvoˇr´ı novou instanci tˇr´ıdy JMenuBar a postupnˇe do n´ı vloˇz´ı vˇsechny z´aloˇzky. Pomoc´ı rozhran´ı ActionListener jsou zde zachyt´av´any ud´alosti, tedy v naˇsem pˇr´ıpadˇe kliknut´ı tlaˇc´ıtka myˇsi na nˇejakou nab´ıdku v menu. O “obslouˇzen´ı” takov´eto ud´alosti se star´a metoda actionPerformed(). Dalˇs´ı komponentou v programu je stromov´ y seznam kontejner˚ u obsahuj´ıc´ı i dan´e moduly. O vytvoˇren´ı tohoto objektu se star´a konstruktor tˇr´ıdy BTreeStruct. Na zaˇc´atku dojde k naˇcten´ı dat ze soubor˚ u bconfig.dat a res.dat pomoc´ı stejn´e metody readData(), protoˇze oba soubory maj´ı shodnou strukturu. Jednotliv´e ˇr´adky soubor˚ u se mus´ı rozdˇelit na jednotliv´a slova reprezentuj´ıc´ı r˚ uzn´e informace. K tomu je vyuˇz´ıv´ana instance tˇr´ıdy StringTokenizer a jej´ı metoda hasMoreTokens(). Postupnˇe jsou data ukl´ad´ana do datov´ ych typ˚ u BContainer ˇci BBox a ty jsou pouˇzity k vytvoˇren´ı uzl˚ u stromu (datov´ y typ DefaultMutableTreeNode), kter´e jsou nakonci ukl´ad´any do instance tˇr´ıdy JTree. Uzly reprezentuj´ıc´ı kontejnery obsahuj´ı tak pot´e jeˇstˇe tzv. “listy”, kter´e reprezentuj´ı jednotliv´e moduly v kontejneru. Tento “strom” je pot´e vloˇzen pˇr´ımo do objektu BTreeStruct, ˇc´ımˇz se zobraz´ı dan´ y stromov´ y seznam. Tˇr´ıda BTreeStruct d´ale jeˇstˇe obsahuje metodu changeValue(), kter´a obsluhuje vznikl´e ud´alosti, a tak´e ˇradu metod, kter´e se staraj´ı o posouv´an´ı aktivn´ıho prvku ˇci smaz´an´ı uzl˚ u ve stromov´e struktuˇre. Dan´ y aktivn´ı prvek je pot´e d˚ uleˇzit´ y pro cel´ y program, jelikoˇz se jedn´a o aktu´aln´ı modul, kter´ y se m´a naloˇzit do kontejneru (nebo pˇr´ımo o samotn´ y kontejner). Informace o takov´emto prvku jsou zobrazov´any v informaˇcn´ım panelu, kter´ y je tvoˇren dvˇema ˇc´astmi. Prvn´ı, kter´ a zobrazuje informace o kontejneru, je objekt tˇr´ıdy BContPanel. Druh´a, zobrazuj´ıc´ı modul, je pot´e instance tˇr´ıdy BBoxPanel. V podstatˇe maj´ı stejnou u ´lohu. V konstruktorech jsou do instance tˇr´ıdy JPanel, kter´a je um´ıstˇena v hlavn´ım r´amci, vloˇzeny vˇsechny komponenty a nastaveny vlastnosti zobrazen´ı, jak je uvedeno v sekci 4.4.1. D˚ uleˇzitou roli zde ale hraj´ı metody setCont, resp. setBox, kter´e do pol´ıˇcek v panelu vkl´adaj´ı pˇr´ısluˇsn´ y text, kter´ y se 23
t´ yk´a aktu´aln´ıho prvku (uzlu) v seznamu kontejner˚ u. Vol´any jsou z hlavn´ı tˇr´ıdy programu BMainWindow vˇzdy, kdyˇz dojde k nˇejak´e zmˇenˇe. Nejd˚ uleˇzitˇejˇs´ı ˇc´ast programu jsou okna, ve kter´ ych se zn´azorˇ nuje naloˇzen´ı kontejner˚ u. Kaˇzd´e okno je pops´ano v jedn´e tˇr´ıdˇe. Horn´ı, kter´e zn´azorˇ nuje naloˇzen´ı kontejneru z ˇceln´ıho pohledu, je instanc´ı tˇr´ıdy BCenterView. Spodn´ı okna s boˇcn´ımi pohledy pak tˇr´ıdy BRightView, resp. BLeftView. Nejdˇr´ıve si pop´ıˇseme horn´ı okno, kter´e je z nich nejjednoduˇsˇs´ı, zobrazuje totiˇz naloˇzen´ı pouze ve 2D prostoru. Konstruktor tˇr´ıdy pouze nastav´ı pozad´ı okna na b´ılou barvu. Vykreslovac´ı metody jsou metody tˇr´ıdy Canvas, kterou tˇr´ıda BCenterView rozˇsiˇruje. Jedn´a se pˇredevˇs´ım o metodu paint(Graphics g), kter´a nejprve zjist´ı, jak´ y kontejner se m´a vykreslit. Do promˇenn´e pomer uloˇz´ı pomˇer ˇs´ıˇrky kontejneru k ˇs´ıˇrce okna (nebo v´ yˇsky kontejneru k v´ yˇsce okna v z´avislosti na tvaru kontejneru), toto d˚ uleˇzit´e ˇc´ıslo se pot´e pouˇz´ıv´a k urˇcen´ı velikosti vˇsech modul˚ u uvnitˇr. D´ale proch´az´ı pozp´atku stromov´ y seznam kontejner˚ u a od aktivn´ıho modulu vykresluje vˇsechny moduly naloˇzen´e pˇredn´ım. T´ım doc´ıl´ıme lepˇs´ı n´azornosti, kam m´a dan´ y modul pˇrij´ıt. Moduly se vykresluj´ı pomoc´ı metody draw2DBox. Metoda draw2DCont pot´e slouˇz´ı k vykreslen´ı kontejneru, metody vykreslitUdaje() a vykreslitVelikost() k zobrazen´ı u ´daj˚ u o vlastnostech do okraj˚ u okna. Dalˇs´ı dvˇe jiˇz zmiˇ novan´e tˇr´ıdy BLeftView a BRightView jsou v mnoh´em hodnˇe podobn´e tˇr´ıdˇe BCenterView. Princip zobrazov´an´ı je shodn´ y, pouze pomoc´ı 2D primitiv (vˇetˇsinou jednoduch´ ych ˇcar) je zobrazov´ana 3D perspektiva. Kontejner je nav´ıc vykreslov´an nadvakr´at, zadn´ı strana se zobrazuje pˇred vykreslov´an´ım modul˚ u, pˇredn´ı aˇz po nˇem. Aby nedoˇslo k neˇz´adouc´ım pˇrekryv˚ um. Tˇr´ıdy nav´ıc obsahuj´ı metody pro posun zobrazovan´ ych objekt˚ u vˇsemi smˇery a metody zmensit() a zvetsit() pro u ´pravu velikost´ı. Oproti norm´aln´ımu stavu lze zmenˇsit objekt na 50 %. Vˇetˇs´ı zmenˇsen´ı nem´a z pohledu pˇrehlednosti smysl. M´ıra zvˇetˇsen´ı omezena nen´ı, pˇresto nˇejak´e velk´e zvˇetˇsen´ı rovnˇeˇz nem´a v´ yznam. Po kaˇzd´e u ´pravˇe a pˇrepoˇc´ıt´an´ı rozmˇer˚ u se znovuvykreslen´ı prov´ad´ı metodou repaint(). Posledn´ı viditelnou ˇc´ast´ı programu je ovl´adac´ı panel v prav´e horn´ı ˇc´asti hlavn´ıho okna. Jde o instanci tˇr´ıdy BControlPanel. Konstruktor t´eto tˇr´ıdy se star´a o vloˇzen´ı vˇsech komponent, viz. sekce 4.4.1. D˚ uleˇzitou roli zde hraje metoda actionPerformed(), kter´a rozliˇsuje jednotliv´e ud´alosti a vol´a pˇr´ısluˇsn´e metody jin´ ych tˇr´ıd. T´ım je zajiˇstˇeno, ˇze pomoc´ı tˇechto tlaˇc´ıtek lze ovl´adat celou aplikaci. Tˇr´ıda mimojin´e tak´e zajiˇst’uje spouˇstˇen´ı jiˇz zmiˇ novan´eho programu pro zobrazen´ı s´ıt’ov´eho 3D modelu naloˇzen´ı kontejneru s moˇznost´ı pohybu v tomto prostoru, viz. sekce 4.4.2. Vedlejˇs´ı moˇznost´ı je tak´e zobrazen´ı dne a datumu, kter´e je v prav´em doln´ım rohu panelu.
5.4.1
Program pro 3D zobrazen´ı
Jak jiˇz bylo ˇreˇceno, program je ps´an v jazyce C s vyuˇzit´ım knihovny OpenGL. OpenGL (Open Graphics Library) je n´ızko´ urovˇ nov´a knihovna pro pr´aci s trojrozmˇernou grafikou. OpenGL pˇredstavuje jednotn´e API (Application Programming Interface) mezi programem a grafick´ ym hardware. Standard API popisuje mnoˇzinu funkc´ı a procedur s pˇresnˇe specifikovan´ ym chov´an´ım. Zdrojov´ y k´od tohoto programu je v souboru b2c_ogl.c. Nejdˇr´ıve jsou naˇcteny vˇsechny hlaviˇckov´e soubory, pˇredevˇs´ım GL/glut.h a GL/glext.h, coˇz jsou pr´avˇe knihovny OpenGL. Program podobnˇe jako optimalizaˇcn´ı program vyuˇz´ıv´a seznam, jehoˇz prvky reprezentuj´ı jednotliv´e moduly v kontejneru. Kter´ y kontejner se m´a naˇc´ıst ze souboru bconfig.dat, ud´av´a prvn´ı parametr, se kter´ ym je program spuˇstˇen. Nejdˇr´ıve jsou nastaveny vlastnosti okna a jsou registrov´any vˇsechny funkce, kter´e zaj´ıˇst’uj´ı obsluhu ud´alost´ı, jako napˇr´ıklad
24
taˇzen´ı myˇsi. Frekvence vykreslov´an´ı je nastavena na 40-kr´at za sekundu. Pot´e je spuˇstˇena nekoneˇcn´a smyˇcka, kter´a vykreslov´an´ı zajiˇst’uje. Ve funkci onDisplay() dojde k vykreslen´ı kontejneru a vˇsech modul˚ u, kter´e byly jiˇz “naloˇzeny”. Poˇcet naloˇzen´ ych modul˚ u ud´ av´ a druh´ y parametr, se kter´ ym byl program spuˇstˇen. Vykreslov´an´ı vˇsech hran modul˚ u ˇci kontejneru je prov´adˇeno funkc´ı glVertex3f().Ovl´ad´an´ı cel´eho programu stejnˇe jako popis jsou uvedeny v sekci 4.4.2.
5.5
Testov´ an´ı
Testov´an´ı prob´ıhalo v pr˚ ubˇehu cel´eho cyklu implementace po jednotliv´ ych ˇc´astech tak, aby byly odstranˇeny vˇsechny d´ılˇc´ı chyby. Po sestaven´ı aplikace do jednoho celku probˇehla druh´ a f´aze testov´an´ı, kter´a mˇela potvrdit bezchybovost a spr´avnost v´ ypoˇct˚ u. Aplikace byla vyv´ıjena i testov´ana na procesoru Intel Celeron, 2,4GHz. Bˇehem testov´ an´ı byla prov´adˇena r˚ uzn´a mˇeˇren´ı u ´daj˚ u, kter´e klasifikuj´ı vlastnosti optimalizaˇcn´ıho algoritmu. Nˇekter´e namˇeˇren´e v´ ysledky jsou samozˇrejmˇe ovlinˇeny frekvenc´ı procesoru a velikost´ı pamˇeti, jako napˇr´ıklad doba v´ ypoˇctu. Ostatn´ı, jako je poˇcet rekurz´ı ˇci poˇcet modul˚ u um´ıstˇen´ ych v kontejneru, vlastnostmi procesoru ovlivnˇeny nejsou. Vlastnosti algoritmu byly zkoum´any na tˇrech kategori´ıch test˚ u. Prvn´ı testovan´ı prob´ıhalo na r˚ uzn´ ych vstupn´ıch datech, tzn. s r˚ uzn´ ymi vstupn´ımi parametry ˇci s r˚ uzn´ ymi vstupn´ımi soubory. Poˇcet materi´al˚ u v aktu´aln´ı den je vˇzdy pˇribliˇznˇe stejn´ y, ovˇsem mˇen´ı se jejich druh, tedy i druh modul˚ u, kter´e se maj´ı naloˇzit. Pˇrehled v´ ysledk˚ u je uveden v tabulce A.7. Z tabulky lze vyˇc´ıst, ˇze naloˇzen´ı jednoho kontejneru z pˇribliˇznˇe 3500 kus˚ u modul˚ u trv´a pˇribliˇznˇe stejnou dobu. D˚ uvod je prost´ y, pomˇer mnoˇzstv´ı skuteˇcnˇe naloˇzen´ ych modul˚ u od poˇctu modul˚ u, ze kter´ ych se vyb´ır´a, je velk´ y. Tud´ıˇz je snadnˇejˇs´ı vybrat ty vhodn´e. Zaj´ımavˇejˇs´ı v´ ysledky pˇrineslo opakovan´e mˇeˇren´ı se stejn´ ymi vstupn´ımi parametry a stejn´ ym vstupn´ım souborem. Pˇri naloˇzen´ı kontejneru se samozˇrejmˇe pouˇzit´e moduly ze seznamu odebrali a v´ ypoˇcet se opakoval s niˇzˇs´ım poˇctem vstupn´ıch modul˚ u. Poˇcet rekurz´ı algoritmu v z´avislosti na poˇctu krabic je uveden v tabulce A.8. Doba v´ ypoˇctu (tedy i poˇcet rekurz´ı) se exponenci´alnˇe zvyˇsuje s klesaj´ıc´ım poˇctem modul˚ u. V jist´e u ´rovni jiˇz nelze naloˇzen´ı s danou procentu´aln´ı m´ırou zaplnˇen´ı vypoˇc´ıtat a v´ ypoˇcet je po 20 mil. rekurz´ı ukonˇcen (viz. sekce 4.3.3). V posledn´ı kategorii test˚ u jsem vyuˇzil moˇznost optimalizaˇcn´ıho programu potvrzovat vypoˇc´ıtan´ y v´ ysledek. Tato vlastnost sk´ yt´a jednu z moˇznost´ı dalˇs´ıho rozˇs´ıˇren´ı aplikace (viz. kapitola 6.2). Optimalizaˇcn´ı algoritmus provede v´ ypoˇcet, ale pˇred uloˇzen´ım v´ ysledku je uˇzivatel dot´az´an, zda s v´ ysledkem souhlas´ı. Pokud nesouhlas´ı, v´ ypoˇcet pokraˇcuje dokud nedos´ahne vyˇsˇs´ıho procenta zaplnˇen´ı. Z takto prov´adˇen´eho testu zjist´ıme, jak je m´ıra zaplnˇen´ı z´avisl´a na dobˇe v´ ypoˇctu (poˇctu rekurz´ı). Jak lze vyˇc´ıst z tabulky A.9, zv´ yˇsen´ı zaplnˇen´ı lze dos´ahnout, jedn´a se vˇsak ˇr´adovˇe o desetiny, maxim´alnˇe jednotky procent, kter´e nehraj´ı ve v´ ysledn´em naloˇzen´ı v´ yznamnou roli. Algoritmus se sice snaˇz´ı po odm´ıtnut´ı vkl´adat do kontejneru jin´e moduly, ovˇsem poˇcet stejn´ ych modul˚ u je znaˇcn´ y, tud´ıˇz ˇcasto dojde jen ke kosmetick´ ym u ´prav´am v naloˇzen´ı. To je d˚ uvod tak mal´eho zlepˇsen´ı. Jako vstupn´ı data jsem pouˇzil r˚ uzn´e dny ve stejn´em souboru, zn´azornˇeno t´eˇz v tabulce.
5.5.1
Vlastnosti optimalizaˇ cn´ıho algoritmu
Testov´an´ı do znaˇcn´e m´ıry splnilo oˇcek´av´an´ı. Namˇeˇren´e v´ ysledky potvrdili teoretick´ y pˇredpoklad, ˇze optimalizaˇcn´ı algoritmus m´a exponenci´aln´ı sloˇzitost v z´avislosti na poˇctu modul˚ u. 25
Kritick´a hodnota, kdy se exponenci´aln´ı kˇrivka “l´ame”, je nˇekde mezi 1 000 a 1 500 moduly v z´avislosti na skladbˇe modul˚ u. D´ale je tak´e patrn´e, ˇze pˇri vhodn´e skladbˇe modul˚ u prob´ıh´ a v´ ypoˇcet velmi rychle.
26
Kapitola 6
V´ ysledky a moˇ znosti dalˇ s´ıho v´ yvoje V t´eto posledn´ı kapitole shrnu dosaˇzen´e v´ ysledky pˇri v´ yvoji, splnˇen´ı poˇzadavk˚ u a moˇznosti dalˇs´ıho v´ yvoje aplikace. Jelikoˇz jsem aplikace jeˇstˇe nemohl plnˇe otestovat pˇr´ımo v provozu jedn´a se o d´ılˇc´ı u ´daje a subjektivn´ı n´azory odpovˇedn´ ych lid´ı, kteˇr´ı maj´ı zav´adˇen´ı aplikace na starosti.
6.1
Splnˇ en´ı poˇ zadavk˚ u
Po zaˇclenˇen´ı jiˇz zmiˇ novan´eho probl´emu s pˇretˇeˇzov´an´ım modul˚ u bude aplikace plnˇe vyˇ hovovat n´arok˚ um a spln´ı vˇsechny poˇzadavky, kter´e Skoda mˇela. M´am pˇrisl´ıbeno, ˇze tento probl´em bude doˇreˇsen v nejbliˇzˇs´ıch t´ ydnech tak, aby cel´a aplikace byla po otestov´ an´ı spustiteln´a k 1. ˇcervenci 2007. P˚ uvodn´ı term´ın spuˇstˇen´ı byl jaro 2007 s bl´ıˇze nespecifikovan´ ym datem. Toto se nepodaˇrilo dodrˇzet z d˚ uvod˚ u jin´ ych priorit v oddˇelen´ı EOT (Aplikace ˇ pracovn´ıch proces˚ u) spoleˇcnosti Skoda, zejm´ena pak zav´adˇen´ı syst´em˚ u v nov´ ych mont´aˇzn´ıch hal´ach v Indii, coˇz jsem nemohl ovlivnit. Grafick´a rozhran´ı aplikace obsahuj´ı dokonce nˇekter´e komponenty, kter´e v p˚ uvodn´ı specifikaci nebyly. Nejsou sice pˇr´ımo nezbytn´e, ale usnadn´ı pr´aci zamˇestnanc˚ u ˇci zpˇresn´ı v´ ypoˇcet optimalizace. Po dohodˇe jsem proto doplnil moˇznost zad´avat postaˇcuj´ıc´ı m´ıru zaplnˇen´ı ˇci zobrazen´ı 3D s´ıt’ov´eho modelu naloˇzen´ı kontejneru. Rychlost i zp˚ usob v´ ypoˇctu jsou postaˇcuj´ıc´ı k urˇcen´emu pouˇzit´ı. Vezmeme-li v u ´vahu, ˇze se bˇehem jednoho dne bal´ı a nakl´adaj´ı souˇc´astky do tˇrech aˇz ˇctyˇrech kontejner˚ u, nehraje p´ ar sekund v´ ypoˇctu naloˇzen´ı ˇz´adnou roli. Probl´em m˚ uˇze nastat, pokud dojde k nˇejak´e neˇcekan´e situaci. Napˇr´ıklad se do kontejneru na posledn´ı chv´ıli mus´ı vloˇzit jin´ y materi´al, neˇz kter´ y ˇ byl v pl´anu. Tento probl´em ovˇsem mus´ı a bude ˇreˇsit vnitˇrn´ı syst´em Skody, kter´ y nahrazen´ y materi´al zaˇrad´ı zpˇet do cyklu v´ ypoˇctu. Aplikace ze vstupn´ıch dat pouze vypoˇc´ıt´a rozloˇzen´ı modul˚ u v kontejneru a jiˇz se nestar´a, zda k naloˇzen´ı a vyexpedov´an´ı skuteˇcnˇe doˇslo . . .
6.2
Moˇ znosti dalˇ s´ıho v´ yvoje
I kdyˇz je aplikace jiˇz nyn´ı plnˇe vyuˇziteln´a, obsahuje velk´ y potenci´al rozˇs´ıˇren´ı a vyuˇzit´ı. Jako vstupn´ı data vyuˇz´ıv´a informace ze soubor˚ u (viz. sekce 4.1.1). Pokud bal´ıc´ı pl´an zaˇcne vyuˇz´ıvat jin´ y druh modul˚ u pro balen´ı souˇc´astek, nemus´ı se pˇreprogramov´avat aplikace, ale staˇc´ı pouze zmˇenit dan´e soubory. Proto lze vyuˇz´ıt aplikaci nejen ve skladech V8, kam byla 27
p˚ uvodnˇe urˇcena, ale i v jin´ ych ˇc´astech v´ yroby, kde ˇreˇs´ı podobn´ y probl´em s nakl´ad´an´ım souˇc´astek. Stˇeˇzejn´ı ˇc´ast aplikace je samotn´ y optimalizaˇcn´ı program a na nˇej se chci tak´e soustˇredit pˇri dalˇs´ım v´ yvoji. V ˇc´asti 4.3.1 jiˇz byly naznaˇceny tak´e moˇznosti jeho rozˇs´ıˇren´ı. Program pouˇz´ıv´a parametry, kter´e nejsou pro aplikaci potˇrebn´e, avˇsak lze je d´ale vyuˇz´ıt. Prvn´ı dva parametry ud´avaj´ı poˇcet dn˚ u, kter´e se maj´ı vypoˇc´ıtat. Lze tedy vytvoˇrit pole, kde pro kaˇzd´ y ˇ prvek je vypoˇc´ıt´ano samostatn´e naloˇzen´ı. C´ıslo kontejneru (ˇsest´ y parametr) pak ud´av´a ˇc´ıslo prvn´ıho vypoˇc´ıtan´eho kontejneru, dalˇs´ı maj´ı ˇc´ıslo vˇzdy o jedno vyˇsˇs´ı. D´ale lze vyuˇz´ıt ˇctvrt´ y parametr, kter´ y umoˇznuje dotazovat se uˇzivatele, zda s vypoˇc´ıtan´ ym v´ ysledkem souhlas´ı. T´eto vlastnosti bylo vyuˇzito i pˇri testov´an´ı optimalizaˇcn´ıho algoritmu, viz. podkapitola 5.5. Mimo tyto moˇznosti je zde urˇcit´ y prostor k zefektivnˇen´ı v´ ypoˇctu. A to napˇr´ıklad pokud bychom upravili pr˚ uchod seznamem modul˚ u ˇci zp˚ usob skl´ad´an´ı modul˚ u do kontejneru. Grafick´a rozhran´ı, at’ jiˇz pro zad´av´an´ı parametr˚ u nebo pro zobrazov´an´ı vypoˇc´ıtan´ ych rozm´ıstˇen´ı modul˚ u, sice lze tak´e d´ale vyv´ıjet, upravovat rozm´ıstˇen´ı komponent ˇci zlepˇsit zobrazov´an´ı modul˚ u v kontejneru. Nicm´enˇe jsem oba programy vytvoˇril tak, aby plnˇe vyhovovali a plnˇe postaˇcovali zp˚ usobu jejich pouˇzit´ı.
6.3
Z´ avˇ er
Probl´em efektivn´ı nakl´adky jak´ehokoliv materi´alu t´ıˇz´ı vˇetˇsinu nejen expediˇcn´ıch firem. Aplikaci jsem proto vyv´ıjel pˇredevˇs´ım s ohledem na obecnost. Po menˇs´ıch u ´prav´ach, kter´e se t´ ykaj´ı hlavnˇe druhu materi´alu a stohovatelnosti modul˚ u, vˇeˇr´ım, ˇze aplikace najde ˇsirok´e uplatnˇen´ı 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-constrained knapsack problem. Journal of Optimization Theory and Applications, (3), 2000. [3] B. Spell. Java - Programujeme profesion´ alnˇe. Computer Press, 2002. [4] Otevˇren´a encyklopedie Wikipedia. Optimalizace. [online]. Dostupn´e na: http://cs.wikipedia.org/wiki/Optimalizace.
29
Dodatek A
Tabulky Modul GLT5755/63 GLT54/56 GLT5764 GLT5740/41 GLT5744
Pod modul pod GLT5754/56/62/65 pod GLT5762/65 pro stohov´an´ı pouze jeden typ palet pro stohov´an´ı pouze tyto typ palet pro stohov´an´ı pouze jeden typ palet
Tabulka A.1: Stohov´an´ı GLT modul˚ u
Modul KLT001 KLT002 KLT003 KLT004 KLT005 MOD009 MOD010 MOD011 MOD012 MOD013 MOD014 MOD015 MOD016 MOD017 MOD018 MOD019 MOD020
Poˇcet kus˚ u do GLT5754 8 16 18 36 84 4 8 8 8 24 16 18 36 36 36 18 36
Poˇcet kus˚ u do GLT5755 4 8 8 16 40 1 2 4 3 9 6 6 12 12 12 4 9
Tabulka A.2: Seznam vkl´ad´an´ı modul˚ u KLT a MOD do modul˚ u GLT5754 a GLT5755
30
Modul GLT000 GLT001 GLT002 GLT003 GLT004 GLT5740 GLT5741 GLT5744 GLT5754 GLT5755 GLT5756 GLT5762 GLT5763 GLT5764 GLT5765 KLT001 KLT002 KLT003 KLT004 KLT005 MOD003 MOD004 MOD005 MOD006 MOD007 MOD008 MOD009 MOD010 MOD011 MOD012 MOD013 MOD014 MOD015 MOD016 MOD017 MOD018 MOD019 MOD020 MOD021 MOD022 MOD023
ˇıˇrka (rozmˇer x) S´ 1450 1450 2240 1096 1675 2000 1200 1685 1450 1130 1450 2260 1130 2260 2260 595 595 395 395 295 1040 1040 1040 1040 1040 1040 688 688 688 520 520 520 458 458 458 458 344 344 344 137 114
Hloubka (rozmˇer z) 1120 1120 720 688 1500 1200 800 1285 1130 825 1130 1450 725 1550 1450 395 395 295 295 195 688 688 688 458 458 458 520 520 520 344 344 275 346 346 260 173 346 346 346 130 115
V´ yˇska (rozmˇer y) 585 695 695 695 715 730 930 1100 730 730 830 730 370 730 1100 260 130 260 130 130 550 275 183 550 275 183 550 275 183 550 183 275 275 183 183 275 275 183 92 183 92
Tabulka A.3: Pˇrehled nejpouˇz´ıvanˇejˇs´ıch modul˚ u
31
Nosnost (kg) 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 78 78 65 40 34 122 122 122 113 113 113 102 102 102 86 45 43 43 43 41 38 40 40 0 0 0
Z´avod 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74
Smˇena a den 1NPO 1RPO 1OPO 1NPO 1RUT 1OUT 1OUT 1OST 1NPA 1NPA 1RPA 1OPA 1RPA 1OPA 1RPA 1NPA 1RPA 1OUT 1RPA 1OPA
K´od materi´alu 01M300032G 02J300047M 02J300048B 038100037H 038100054E 038105264H 06A100020MD 06A103724BD 06A119518G 06A133354G 191611715 191823395 191971790A 1C0906109A 1C0909601 1H0611797 1H0819465E 1H0867981 1H0877236 1H0919238
Poˇcet kus˚ u 7 173 15 29 1 173 3 1 1 1 1 1 2 1 9 1 7 2 1 1
Z´avˇeska 1000003161 1000003177 1000003178 1000003182 1000003183 1000003193 1000003260 1000003261 1000003263 1000003265 1000003291 1000003292 1000003296 1000003299 1000003300 1000003307 1000003308 1000003312 1000003313 1000003316
Pozn´amky 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K 1K
Tabulka A.4: Pˇr´ıklad obsahu souboru EXP H TETRIS.txt
Z´avod 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1 74 1
Materi´al 020110024A 020110024A 020110024A 020110024A 020110024A 02011024A 02011024A 02011024A 02011024A 02011024A 021117061B 021117061B 02A911023L 02A911023L 02A911023L 02A911023L 02A911023L
Den (21.11.05) (21.11.05) (21.11.05) (21.11.05) (21.11.05) (8.2.2005) (8.2.2005) (8.2.2005) (8.2.2005) (8.2.2005) (12.05.05) (12.05.05) (8.2.2005) (8.2.2005) (8.2.2005) (8.2.2005) (8.2.2005)
1 2 3 4 5 1 2 3 4 5 1 2 1 2 3 4 5
Balen´ı GLT5763 BSE040 ZLG003 GQG302 GLG201 GLT003 DGL003 PGL003 WSR100 BSE040 KLT003 BSN060 GLT003 DGL003 PGL003 WSR100 BSE040
Popis GLT 5763 (1130*725*370) ´ CEK ˇ VCI–SA Z HADICE (400) ˇ PROLOZKA GLT003 ˇ ˇ ´ICN ˇ Y ´ HREBEN 4 PR ˇ ´ ´ HREBEN 2 PODELNY GLT 3 (1096*688*695) V´IKO PRO GLT003 PALETA GLT3 ´ ROLOVANY ´ PAP´IR (1000) VLNITY ´ CEK ˇ VCI–SA Z HADICE (400) KLT 3 (395*295*260) ´ CEK ˇ PE–SA Z HADICE (600) GLT 3 (1096*688*695) V´IKO PRO GLT003 PALETA GLT3 ´ ROLOVANY ´ PAP´IR (1000) VLNITY ´ ˇ VCI-SACEK Z HADICE (400)
Tabulka A.5: Pˇr´ıklad obsahu souboru EXP THI MODUL.txt
32
Z´avˇeska 1000004965 1000004907 1000006540 1000004907 1000006104 1000004410 1000006540 1000004907 1000004397 1000004395 1000004907 1000006210 1000006106 1000006019 1000006540 1000006540 1000006540 1000006018 1000004119
Um´ıstˇen´ı 0 0 0 72 0 0 0 37 0 145 146 0 145 0 0 145 73 0 0 147 0 145 183 0 0 220 0 145 220 0 72 110 0 104 220 0 104 220 59 0 220 68 0 0 113 0 73 113 0 146 113 0 219 113 104 219 113
Rotace 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Velikost 72 37 113 72 37 113 145 73 113 72 37 113 82 73 113 82 73 113 145 73 113 72 37 113 104 18 68 68 18 104 72 37 113 39 13 59 34 18 52 104 18 45 145 73 113 145 73 113 145 73 113 104 18 45 39 13 59
Modul GLT5763 GLT5763 GLT5754 GLT5763 GLT5755 GLT5755 GLT5754 GLT5763 MOD005 MOD005 GLT5763 KLT002 MOD013 MOD008 GLT5754 GLT5754 GLT5754 MOD008 KLT002
Poˇcet 1 1 18 1 1 1 18 1 1 1 1 1 1 1 18 18 18 1 1
Vloˇzen´e GLT5763 GLT5763 KLT003 GLT5763 GLT5755 GLT5755 KLT003 GLT5763 MOD005 MOD005 GLT5763 KLT002 MOD013 MOD008 KLT003 KLT003 KLT003 MOD008 KLT002
Tabulka A.6: Pˇr´ıklad obsahu souboru res.dat Poˇcet modul˚ u na vstupu 3673 2634 1122 2892 3112 2923
Zaplnˇen´ı [ % ] 86,173 87,378 86,400 85,293 87,482 86,932
Poˇcet pouˇzit´ ych modul˚ u Poˇcet rekurz´ı 1153 3 736 633 2 649 166 499 821 2 120 1021 5 832 931 3 121
Tabulka A.7: Test ˇc. 1: Mˇeˇren´ı s r˚ uzn´ ymi vstupn´ımi daty ˇ ıslo v´ C´ ypoˇctu 1 2 3 4 1 2 3 1 2 3 4
Modul˚ u na vstupu 3 673 2 520 1 081 542 1 122 956 726 2 634 2 001 1 141 409
Zaplnˇen´ı [ % ] 86,173 87,759 85,021
Pouˇzit´ ych modul˚ u Poˇcer rekurz´ı 1153 3 736 1439 3 086 539 219 483
86,400 88,327
166 230
499 5618
87,378 85,239 86,127
633 854 732
2 649 1 246 42 316
Tabulka A.8: Test ˇc. 2: Opakovan´e mˇeˇren´ı se stejn´ ymi vstupn´ımi daty
33
ˇ ıslo mˇeˇren´ı Zaplnˇen´ı [ % ] Poˇcet rekurz´ı C´ 1 86,173 3 736 2 86,173 4 894 3 86,183 7 672 4 86,180 11 757 5 86,284 63 599 6 86,341 172 716 7 86,887 1 525 085 - pondˇel´ı, 3673 modul˚ u 1 86,277 649 2 86,298 914 3 86,355 1 155 4 86,350 1 541 5 86,360 1 941 6 86,512 478 924 7 87,718 1 415 200 -u ´ter´ y, 1321 modul˚ u 1 86,400 499 2 86,421 551 3 86,441 565 4 86,441 747 5 86,437 239 459 6 86,341 172 716 7 87,537 4 108 760 - stˇreda, 1122 modul˚ u 1 87,121 1 726 2 87,317 2 495 3 87,507 14 366 4 87,532 15 143 5 87,886 308 875 6 87,899 5 227 108 - ˇctvrtek, 1021 modul˚ u Tabulka A.9: Test ˇc. 3: V´ ypoˇcty optimalizace pˇri odm´ıt´an´ı v´ ysledku
34
Dodatek B
Uˇ zivatelsk´ y manu´ al D´ale bude n´asledovat uˇzivatelsk´ y manu´al, kter´ y je naps´an v MS Wordu, aby byl snadno ˇ aktualizovateln´ y dalˇs´ımi pracovn´ıky Skody. M´a proto samostan´e ˇc´ıslov´an´ı a m´ırnˇe odliˇsn´ y styl sazby. . .
35
