PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 15

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  tabu search algorithm
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Partial (Neighbourhood) Singleton Arc Consistency for Constraint Satisfaction Problems
Wallace Richard J.
Fundamenta Informaticae
|
2020
|
Vol. 174, nr 3/4
311--344
EN
Algorithms based on singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. Such consistencies, despite their partial character, are still well-characterized in that algorithms have unique fixpoints. Heuristic strategies for choosing an effective subset of variables are described and tested, the best being choice by highest degree and a more complex strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as the corresponding full version of the algorithm in terms of values discarded or problems proven unsatisfiable, while significantly reducing the effort required to achieve this.
2
Content available Scheduling of multiunit projects using tabu search algorithm
Podolski M.
Zeszyty Naukowe / Wyższa Szkoła Oficerska Wojsk Lądowych im. gen. T. Kościuszki
|
2015
|
Nr 1
110--122
EN
The paper describes problems of discrete optimization in scheduling of multiunit projects. A model of this kind of project with possibility of using many workgroups by the contractor has been presented. It leads to reduction of project duration. For solving NP-hard optimization problem, a tabu search algorithm has been applied in the model. The example of mod-el and application of the algorithm are also included in the paper.
3
Content available remote Project management in building process with uncertain tasks times
Bożejko W., Hejducki Z., Rajba P., Wodecki M.
Management and Production Engineering Review
|
2011
|
Vol. 2, No. 1
3-9
EN
In this paper there is presented a problem of scheduling of construction work in which certain projects must be executed. Every work consists of projects executed by separate teams. In a linear system the sequence of works is the same for every project. Uncertain tasks times are represented by fuzzy numbers or distribution of random variables. We present a tabu search algorithm and computational experiments which are aimed at checking the sustainability of set solutions.
4
Content available 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
PL
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ń.
EN
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.
5
Content available Weryfikacja poprawności działania algorytmu tabu search w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących
Powroźnik P.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 11
1345-1347
PL
W artykule przedstawiono ideę zastosowania algorytmu tabu search do wyznaczenia okresu zadań w elastycznym modelu szeregowania zadań. Wyniki przeprowadzonych symulacji dowodzą przydatność algorytmu w doborze parametrów czasowych w elastycznym modelu szeregowania zadań. Rozdział pierwszy zawiera tło zastosowania teorii szeregowania zadań w systemach pomiarowo - sterujących. Rozdział drugi wprowadza czytelnika do zastosowania elastycznego modelu szeregowania zadań w systemach pomiarowo - sterujących. Rozdział ten zawiera krótki przegląd literaturowy prezentowanej tematyki [1, 2, 3]. Rozdział trzeci przedstawia ideę zastosowania wybranego algorytmu heurystycznego tabu serach w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących. Rysunek pierwszy przedstawia schemat blokowy szeregowania zadań przy zastosowaniu algorytmu tabu search. Rozdział czwarty zawiera wyniki z przeprowadzonych symulacji zastosowania algorytmu tabu search w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących. Podsumowanie zawiera najważniejsze wnioski wynikające ze stosowania omawianego algorytmu w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących.
EN
In this paper use of a tabu search algorithm for elastic task model scheduling is presented. The results of simulations confirm usefulness of this method for assigning the time parameters in elastic task model scheduling. In the first section, the background of application of task model scheduling to control and measurement systems is outlined. The second section deals with introduction to using the elastic task model scheduling for control and measurement systems. This section provides a brief literature review of the presented subjects [1, 2, 3]. The third section presents an idea of applying the selected tabu search heuristic algorithm to the elastic task model scheduling in control and measurement systems. The block diagram of the elastic task model scheduling with use of the tabu search algorithm is shown in Fig. 1. The fourth section contains the results of simulations carried out for the elastic task model scheduling with use of the tabu search algorithm in control and measurement systems. At the end there are presented the main conclusions drawn from using the tabu search algorithm for assigning the task time parameters in the elastic task model scheduling in control and measurement systems.
6
Content available Harmonogramowanie robót budowlanych z zastosowaniem algorytmu Tabu Search z rozmytymi czasami wykonania zadań
Rogalska M., Bożejko W., Hejducki Z., Wodecki M.
Przegląd Budowlany
|
2009
|
R. 80, nr 7-8
76-80
PL
Praca ta stanowi kontynuację studiów różnych autorów nad zagadnieniami związanymi z uwzględnieniem niepewności w harmonogramowaniu robót budowlanych. Jednym ze sposobów reprezentowania niepewności jest zastosowanie elementów teorii zbiorów rozmytych, umożliwiających oszacowanie czasów wykonania prac oraz cyklu realizacji kompleksu robót.
EN
This paper continues the authors' work on issues relating to taking account of uncertainties in the scheduling of construction works. One way of representing uncertainty is to use elements of the theory of fuzzy sets, which make it possible to estimate work completion times and the execution cycle for a comprehensive series of works.
7
Problem dystrybucji z terminami dostaw
Bożejko W., Walczyński M., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
25-30
PL
W pracy przedstawiono algorytm oparty na metodzie przeszukiwania z tabu, rozwiązywania problemu dystrybucji z terminami dostaw. Jest on równoważny pewnemu jednomaszynowemu problemowi szeregowania, który w literaturze jest oznaczany przez 1|sij|ΣwiTi i należy do klasy problemów silnie NP-trudnych. Wykonano obliczenia na reprezentatywnej grupie danych, a otrzymane wyniki porównano z najlepszymi znanymi w literaturze.
EN
A tabu search algorithm is proposed in the paper to solve a distribution problem with due dates. It is equivalent to a single machine scheduling problem, which is described by 1|sij|ΣwiTi in the literature and it belongs to strongly NP-hard class. Calculations were done on representative group of test instances, obtained results were compared to the best known solutions from the literature.
8
Content available The Tabu Search approach in coherent co-synthesis of multiprocessors systems
Drabowski M., Czajkowski K.
Studia Informatica : systems and information technology
|
2006
|
Vol. 1(7)
31--45
EN
This paper presents the use of Tabu Search algorithm for solving the problems of coherent synthesis of multiprocessor computer systems. The paper includes a coherent solution of both optimization of partition resources and optimization of tasks scheduling. This publication shows results of computational experiments for different instances of system synthesis problems.
9
Content available Zagadnienie przepływowe z ograniczeniami "bez magazynowania". Algorytm tabu search z multiruchami
Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
95-104
PL
Dla zagadnienia przepływowego z ograniczeniami "bez magazynowania" przedstawiono w pracy model grafowy, własności problemu oraz algorytm oparty na technice tabu search. W proponowanym algorytmie wykorzystano idee bloków zadań oraz zastosowano całkowicie nowe pojęcie nazywane multiruchem. Wysoką skuteczność algorytmu potwierdzają wyniki badań eksperymentalnych dokonane na literaturowych danych testowych, w których aż dla 96 instancji spośród 120 uzyskano nowe rozwiązania referencyjne.
EN
The paper deal with flow-shop scheduling problem with no store constrains and the makespan criterion. Some properties, models of the problem and algorithm based on the taboo search method have been presented and discussed. In the proposed algorithm, the blocks of jobs ideas and new mechanism called multimove are used. The high efficiency of proposed mechanism confirm the results of the computation experiment, where for 96 over 120 instances are obtained new references solution.
10
Content available remote Zagadnienie kolejnościowe przepływowe z ograniczoną dostępnością maszyn
Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
113-119
PL
W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania zadań z kryterium minimalizacji zakończenia wszystkich zadań, w którym maszyny są dostępne w określonych terminach czasowych. Przedstawiono model zagadnienia wykorzystujący elementy teorii grafów oraz zaproponowano algorytmy konstrukcyjne i lokalnego przeszukiwania. Algorytmy te były testowane na trudnych problemach zaczerpniętych z literatury. Uzyskane wyniki porównano z rezultatami algorytmów zaproponowanych przez Błażewicza.
EN
The paper deal with the classical flowshop scheduling problem with makespan criterion where machines for processing are available in given time intervals. There are presented the graph model and the constructive and local search heuristics. The algorithms are tested on difficult test problem taken from literature. The computational results are compared with the results given by the algorithms proposed by Blazewicz.
11
Content available remote Warianty algorytmu Tabu Search w zastosowaniu do układania harmonogramów zajęć szkolnych
Piwakowski K., Szyfelbein D.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
229-236
PL
W niniejszej pracy przedstawiono warianty adaptacji przeszukiwania tabu wraz z wynikami eksperymentów obliczeniowych do układania szkolnych harmonogramów zajęć. W modelu teoretycznym uwzględniono zarówno ograniczenia krytyczne, np. konflikty czasowe uczestników zajęć (nauczyciele i uczniowie) oraz brak przerw w zajęciach (eliminacja okienek) wybranych uczestników, jak również niekrytyczne składniki funkcji celu, np. równomierne rozłożenie zajęć w tygodniu i możliwie mała rozpiętość czasowa harmonogramu w każdym dniu.
EN
In this paper we present variants of tabu search implementation for computing school timetables together with computational results. In the theoretical model critical conditions as for example participant's time conflicts and consecutive class's schedule, as well as not critical conditions as for example even distribution of lessons and short span in each day are considered.
12
Content available remote Nowa metoda dywersyfikacji w algorytmach tabu dla problemu przepływowego
Nowicki E.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
193-198
PL
W pracy rozważa się klasyczny problem minimalizacji terminu zakończenia wykonywania wszystkich zadań w przepływowym problemie szeregowania. Pewne własności szybkiego algorytmu TSAB Nowickiego i Smutnickiego zostały przedyskutowane. Następnie, wykorzystując nową metodę dywersyfikacji, algorytm TSAB został osadzony w bardziej zaawansowanym algorytmicznym schemacie, zwanym i-TSAB. Proponowana metoda dywersyfikacji ma pewne cechy wspólne z techniką path relinking. Algorytm i-TSAB jest szybki i dostarcza rozwiązań o lepszej jakości niż TSAB. Przykładowo, już w początkowych testach, w czasie kilku minut na komputerze klasy PC dostarczył 7 nowych górnych ograniczeń wśród 33 nie rozwiązanych do tej pory instancji Taillarda.
EN
The paper deals with the classic problem of finding a minimum makespan in a flow-shop. Some properties of the fast algorithm TSAB of Nowicki and Smutnicki have been discussed. Next, by introducing the original method of diversification, TSAB has been embedded in more advanced algorithmic framework i-TSAB, which has far analogy to path relinking technique. Newly proposed algorithm is faster and has better accuracy than TSAB, runs within time of minutes on a PC and already in preliminary tests provides 7 new upper bounds among 33 unsolved yet common Taillard's benchmarks.
13
Content available remote A new local search optimization algorithm for the job-shop problem
Grabowski J., Wodecki M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
121-128
EN
This paper deals with a classic job-shop scheduling problem with makespan criterion. We present some new theoretical properties of the problem associated with the blocks, moves and neighbourhood structure, and algorithm based on a tabu search approach. Computational experiments are given and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed solves the job-shop instances with high accuracy in a very short time.
PL
W referacie przedstawimy algorytm tabu oparty na idei bloków z drogi krytycznej, dla rozwiązywania ogólnego problemu szeregowania (ang. job-shop problem). Szacowanie wartości funkcji celu rozwiązań z otoczenia (bez konieczności dokładnego ich liczenia), znacznie przyspiesza zbieżność i skraca czas działania algorytmu. Przedstawimy pewne metody (perturbacje) pozwalające na bardzo szybką zmianę badanych obszarów zbioru rozwiązań dopuszczalnych oraz nowy sposób realizacji listy tabu, który zapobiega powstawaniu cykli w algorytmie (generowaniu tych samych rozwiązań po pewnej liczbie kroków algorytmu). Przeprowdzone eksperymenty obliczeniowe wskazują jednoznacznie, że wyżej przedstawione idee znacznie przyspieszają oraz poprawiają wyniki algorytmu.
14
Content available remote Nowy algorytm lokalnej optymalizacji dla zagadnienia kolejnościowego przepływowego
Bożejko W., Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
77-85
PL
W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Przedstawiono nowe własności zagadnienia oraz nowy rodzaj ruchu, którego wykonanie przesuwa jednocześnie co najmniej jedno zadanie w danej permutacji. Ruchy tego rodzaju mogą być stosowane w dowolnych algorytmach lokalnej optymalizacji szeregowania zadań. W niniejszej pracy zastosowano je do algorytmu opartego na technice tabu search. Przeprowadzono eksperymenty obliczeniowe a uzyskane rezultaty porównano z wynikami aktualnie najlepszych na świecie algorytmów opracowanych przez Nowickiego i Smutnickiego oraz Grabowskiego i Pemperę.
EN
The paper deals with the classic flow-shop scheduling problem with the makespan criterion. There are presented and discussed some new properties associated with the blocks and new definition of the move, by using of which at least one job is moved in a given permutation. This move can be applied in any local search algorithms. The algorithm based on tabu search approach is presented. Computational experiments are provided and compared with the results given by the best algorithms proposed by Nowicki & Smutnicki and Grabowski & Pempera.
15
Content available remote Nowy algorytm tabu search dla zagadnienia kolejnościowego przepływowego
Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
1999
|
T. 3, z. 1
125-133
PL
W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Przedstawiono nowe własności zagadnienia, które zastosowane do algorytmu opartego na technice tabu search doprowadziły do istotnego ograniczenia zbioru rozwiązań sąsiednich. Przeprowadzono eksperymenty obliczeniowe a uzyskane rezultaty porównano z wynikami aktualnie najlepszego na świecie algorytmu opracowanego przez Nowickiego i Smutnickiego.
EN
The paper deal with the classic flow-shop scheduling problem with the makespan criterion. There are presented and discussed some new properties associated with the blocks. These properties allow us to further significant reduction of the neighbourhood sizes, which can be applied in local search algorithms. The algorithm based on tabu search approach is presented. Computational experiments (up to 500, jobs and 20 machines) are provided and compared with the results given by the best algorithm proposed by Nowicki and Smutnicki.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.