Vše
Vše

Co hledáte?

Vše
Projekty
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Od přesných metod k heuristikám

Popis výsledku

V této práci jsou popsány typické problémy rozvrhování výrobních procesů, návrhu logických obvodů, síťové optimalizace a robotiky. Zaměřili jsme se na problémy kombinatorické povahy, resp. takové problémy, které lze na problémy kombinatorické optimalizace převést. Bylo ukázáno, že pro malé instance lze použít deterministické metody, jako jsou metoda větví a mezí. Ve speciálním případě lze využít i přístup založený na dynamickém programování. Na druhé straně vzhledem k NP-úplnosti metoda větví a mezí a dynamické programování nejsou efektivní na řešení těchto problémů, jestliže mají velký počet vstupních parametrů, protože při použití metody větví a mezí exponenciálně roste čas výpočtu a u dynamického programování nároky na operační paměť pro statická pole. Ověřili jsme, že komerční softwarové nástroje, jako je GAMS, na velkých instancích těchto problémů rovněž selhávají. V těchto případec

Klíčová slova

optimisationNP-hard problemsheuristic methodsgenetic algorithmschedulingroboticscomputational geometryVoronoi diagramDelaunay triangulation

Identifikátory výsledku

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    From Exact Methods to Heuristics

  • Popis výsledku v původním jazyce

    In this work, typical problems of manufacturing-process scheduling, logical circuit design, network optimisation and robotics were described. We focused on problems of combinatorial nature or on those that can be reduced to problems of combinatorial optimization. It was shown that, for small instances, deterministic methods such as the branch-and-bound method and, in a special case, the dynamic programming approach may also be used. On the other hand, due to NP-completeness, the branch-and-bound methodand dynamic-programming approach are not efficient in solving these problems if they have a high number of input parameters because of the exponentially growing time in branch-and-bound method calculations and high memory requirements for static arrays in the dynamic-programming approach. We verified that commercial software tools, such as GAMS, fail for large instances of these problems, too. In these cases, we chose heuristic techniques, mainly stochastic heuristics (or metaheuristics)

  • Název v anglickém jazyce

    From Exact Methods to Heuristics

  • Popis výsledku anglicky

    In this work, typical problems of manufacturing-process scheduling, logical circuit design, network optimisation and robotics were described. We focused on problems of combinatorial nature or on those that can be reduced to problems of combinatorial optimization. It was shown that, for small instances, deterministic methods such as the branch-and-bound method and, in a special case, the dynamic programming approach may also be used. On the other hand, due to NP-completeness, the branch-and-bound methodand dynamic-programming approach are not efficient in solving these problems if they have a high number of input parameters because of the exponentially growing time in branch-and-bound method calculations and high memory requirements for static arrays in the dynamic-programming approach. We verified that commercial software tools, such as GAMS, fail for large instances of these problems, too. In these cases, we chose heuristic techniques, mainly stochastic heuristics (or metaheuristics)

Klasifikace

  • Druh

    Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

  • CEP obor

    BB - Aplikovaná statistika, operační výzkum

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

  • Návaznosti

    Z - Vyzkumny zamer (s odkazem do CEZ)

Ostatní

  • Rok uplatnění

    2008

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název periodika

    Vědecké spisy Vysokého učení technického v Brně Edice Habilitační a inaugurační spisy

  • ISSN

    1213-418X

  • e-ISSN

  • Svazek periodika

    2008

  • Číslo periodika v rámci svazku

    276

  • Stát vydavatele periodika

    CZ - Česká republika

  • Počet stran výsledku

    40

  • Strana od-do

  • Kód UT WoS článku

  • EID výsledku v databázi Scopus

Druh výsledku

Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

Jx

CEP

BB - Aplikovaná statistika, operační výzkum

Rok uplatnění

2008