From Exact Methods to Heuristics

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F08%3APU76872" target="_blank" >RIV/00216305:26210/08:PU76872 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

From Exact Methods to Heuristics

Original language description

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)

Czech name

Od přesných metod k heuristikám

Czech description

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

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

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

Name of the periodical

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

ISSN

1213-418X

e-ISSN

—

Volume of the periodical

2008

Issue of the periodical within the volume

276

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

40

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—