Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: metoda podziału i ograniczeń

Sortuj według:

Ogranicz wyniki do:

Przyspieszanie metody podziału i ograniczeń dla problemu podziału funkcjonalności na sprzęt i oprogramowanie

100%

Strachacki M.

2008

tom T. 15

55-60

Niniejsza praca przedstawia analizę wrażliwości metody podziału i ograniczeń B&B (ang. branch and bound) używanej do podziału funkcjonalności na sprzęt i oprogramowanie. Zbadano teoretyczny wpływ wszystkich parametrów B&B na czas obliczeń. Wyniki eksperymentów ujawniły, że najwrażliwszymi parametrami są: funkcja ograniczenia dolnego, reguła wyboru podproblemu, reguła podziału oraz rozwiązanie początkowe. Aby skrócić czas obliczeń metody B&B należy odpowiednio zoptymalizować parametry przy użyciu algorytmu symulowane-go wyżarzania. Testy wykazały, że dla rozmiaru problemu n = 30 uzyskano średnio 130-krotne przyspieszenie obliczeń. Opisana optymalizacja hybrydowa jest najwydajniejszą z metod dotychczas zaprezentowanych w literaturze.

This paper presents sensitivity analysis of branch and bound (B&B) method used for hardware/software partitioning task. The impact of all B&B parameters on computation time is theoretically analyzed and results of experiments are presented. Results show that most sensitive parameters are a lower bound function, a selection rule, a branching rule and an initial solution. To shorten B&B computation time these parameters have to be set properly and additional preoptimization step should be applied. This pre-optimization step uses simulated annealing to set parameters in limited time. Results of experiments show that the computation time speedup x 130 is achieved on average. This hybrid optimization is the most efficient presented so far.

Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania

84%

Janiak A. , Kołodka P. , Krysiak T.

2010

tom R. 86, nr 9

91-96

Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ograniczeń oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.

The paper deals with a problem of scheduling jobs with changeable job values and non-zero release dates on a single machine. A power model of job values and the criterion of maximization of the total job values are analyzed. The above problem is at least NP-hard. Thus, a branch and bound exact algorithm and some heuristic algorithms (constructive and improving type) have been developed. Their efficiency have been examined experimentally.

Application of intelligent search strategy in the branch and bound method with the use of the example of cost optimization for an electric power network with high load variability

84%

Oprzędkiewicz I.

2001

tom T. 30, nr 1/2

3-18

Cost optimization for losses in an electric power network with high load variability is a NP-hard. In problems of this category it is of relevance to devise effective algorithms, which will enable us to promptly find a solution. Obtaining a precise solution in this case is very difficult, since even a minor growth of the problem's volume results in an exponential increase in the calculation time. The chief method in search of optimal solutions to NP-hard problems is the branch and bound method. The paper deals with an analysis of effectiveness improvement formulae of the algorithm based on that method, through the reduction of the search path in the sub-problem tree. A method has been presented, in which the decision to select the sub-problem for analysis depends on the hitherto course of calcultions. As a criterion for this selection the assessment of the usability of the defined selection principles has been assumed (closely related with the problem being resolved). The algorithm is complimented by a meta-heuristics module, which is used to improve the currently known as the best solution.

Optymalizacja kosztów strat w sieci elektroenergetycznej o dużej zmienności obciążenia jest zagadnieniem NP-trudnym. W problemach tej klasy duże znaczenie ma opracowanie efektywnych algorytmów, które pozwalają szybko znaleźć rozwiązanie. Uzyskanie rozwiązania dokładnego jest w tym przypadku bardzo trudne, gdyż niewielki wzrost rozmiaru problemu powoduje wykładniczy wzrost czasu obliczeń. Podstawową metodą poszukiwania optymalnych rozwiązań problemów NP-trudnych jest metoda podziału i ograniczeń. W pracy zajęto się badaniem i analizą metod poprawy efektywności algorytmu opartego na tej metodzie poprzez skrócenie drogi przeszukiwania w drzewie podproblemów. Przedstawiono metodę, w której decyzja o wyborze podproblemu do analizy zależy od dotychczasowego przebiegu obliczeń. Jako kryterium wyboru przyjęto ocenę przydatności zdefiniowanych reguł wyboru (ściśle związanych z rozwiązywanym zagadnieniem). Algorytm uzupełniono dodatkowym modułem zawierającym metaheurystykę i wspomagającym proces wyznaczania wartości odcinających.