Využití grafických procesorů v úlohách celočíselného programování
| Název práce: | Využití grafických procesorů v úlohách celočíselného programování |
|---|---|
| Autor(ka) práce: | Hájek, Jan |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Černý, Michal |
| Jazyk práce: | Česky |
| Abstrakt: | Široká podskupina okružních úloh z teorie grafů je častým problémem, který řeší přepravní firmy, letecké společnosti, hi-tech firmy pro plánování výroby plošných spojů nebo společnosti z úplně jiného hospodářského odvětví. Během dřívějších nejrůznějších výzkumů těchto úloh bylo provedeno mnoho analýz a představeno mnoho způsobů řešení, jejichž nástin je uveden v této práci. Některé z nich podávají lepší či horší výsledky v delším či kratším výpočetním čase. Přestože se výkon procesorů a současných technologií nadále zvyšuje, je s některými algoritmy obtížné se dopočítat výsledku v rozumném čase. Proto se práce zabývá otázkou, zda je možné nalézt vhodný algoritmus, který by bylo možné aplikovat na jiné a rychlejší struktury výpočetních jednotek tak, aby se zajistilo mnohonásobné zvýšení výpočetní rychlosti než doposud. Pro tento výzkum byl vytvořen a implementován testovací algoritmus metody větvení a mezí s maticovou redukcí sazeb, který byl podroben počítačovým experimentálním testům, jejichž důsledky jsou zde uvedeny. |
| Klíčová slova: | grafická výpočetní jednotka; větvení a mezí; obchodní cestující |
| Název práce: | Solving vehicle routing problems and algorithm implementation on GPU |
|---|---|
| Autor(ka) práce: | Hájek, Jan |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Černý, Michal |
| Jazyk práce: | Česky |
| Abstrakt: | A very wide-ranging subgroup of vehicle routing problems from the graph theory is a common and frequent problem handled daily by transport companies, airline businesses, hi-tech companies with planning drilling of printed circuits boards or other companies from different industries. During numerous previous researches of these problems a lot of analyses were made and many solutions proposed -- of which an outline is in this paper. Some of them giving better or worse results in longer or shorter computing time. In spite of the fact that the processors and new technologies performance is increasing, with some algorithms we cannon compute the result in a reasonable time. That is why this paper is asking a question, if there can be found a fitting algorithm which could be applied on different and faster processing unit structures so it could be ensured a multiple computing speed increase so far. The analysis was carried out using computer experiments on a new build and implemented branch and bound algorithm with a matrix rate reduction. |
| Klíčová slova: | graphics processing unit; branch and bound; travelling salesman problem |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 23. 3. 2010 |
|---|---|
| Datum podání práce: | 5. 1. 2011 |
| Datum obhajoby: | 25. 1. 2012 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/27160/podrobnosti |