Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: metoda poszukiwania z zabronieniami

Sortuj według:

Ogranicz wyniki do:

Algorytm poszukiwania z zabronieniami dla problemu centralnego drzewa rozpinającego

Makuchowski M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2011

T. 15, z. 2

319-326

W pracy analizuje się problem znajdowania centralnego drzewa rozpinającego. Problem ten polega na znalezieniu takiego drzewa rozpinającego graf, aby największa odległość od wszystkich pozostałych drzew była możliwie najmniejsza. Odległość pomiędzy drzewami jest miarą zliczającą różnice w zbiorze krawędzi porównywanych drzew. Zagadnienie to należy do klasy problemów NP-trudnych. W pracy proponuje się algorytm, oparty na metodzie poszukiwania z zabronieniami, dedykowany rozpatrywanemu problemowi. Praca zawiera także wyniki eksperymentów numerycznych testujących efektywność proponowanego algorytmu oraz porównuje go z algorytmem dokładnym opartym na metodzie podziału i ograniczeń.

In this paper the central spanning tree problem is considered. The problem consists in finding a spanning tree in a graph, that minimizes the maximum distance to all other spanning trees. The distance between two trees is measured by means of the symmetric difference of their edge sets. The problem is known to be NP-hard. The algorithm based on the tabu search approach is proposed. Computational experiments are conducted and compared with results obtained by a branch and bound algorithm.

Block approach-local search algorithm for single machine total weighted tardiness problem

Bożejko W., Grabowski J., Wodecki M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2005

T. 9, z. 1-2

25--35

This paper deals with the single-machine scheduling problem to minimize total weighted tardiness of jobs. Some new properties of the problem have been presented and discussed. These properties allow us to propose a new fast tabu search approach with a specific neighborhood which employs blocks of jobs and a compound moves technique. The proposed algorithm is empirically evaluated and found to be relatively more effective in finding good solutions in a shorter time than existing algorithms.

W pracy rozpatrujemy problem szeregowania zadań na jednej maszynie z minimalizacją sumy kosztów opóźnień. Przedstawiamy szereg nowych własności pozwalających na rozbicie permutacji (rozwiązania dopuszczalnego) na podciągi, zwane blokami. Dzięki temu, z otoczeń generowanych przez ruchy typu zamień lub wstaw, eliminujemy wiele rozwiązań nie gwarantujących poprawę wartości funkcji celu. Algorytm oparty na metodzie poszukiwania z zabronieniami (tabu search), w którym stosuje się te otoczenia, działa bardzo szybko, a otrzymane wyniki są lepsze niż inne wyniki opisane w literaturze algorytmów.