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

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Permutation, no-wait, no-idle flow shop problems
Makuchowski M.
Archives of Control Sciences
|
2015
|
Vol. 25, no. 2
189--199
EN
The paper compares the schedules of different variants of the flow shop problem, i.e. permutation, no waiting and no idle flow shop problems. It is assessed the impact of the constraints on the extension of the schedules and correlations of the length of the schedules for these variants. It is also examined the effectiveness of a set of insert type algorithms. The efficiency of the algorithms is tested on well-known literature benchmarks.
2
Content available Perturbation algorithm for a minimax regret minimum spanning tree problem
Makuchowski M.
Operations Research and Decisions
|
2014
|
Vol. 24, No. 1
37--49
EN
The problem of finding a robust spanning tree has been analysed. The problem consists of determining a minimum spanning tree of a graph with uncertain edge costs. We should determine a spanning tree that minimizes the difference in costs between the tree selected and the optimal tree. While doing this, all possible realizations of the edge costs should be taken into account. This issue belongs to the class of NP-hard problems. In this paper, an algorithm based on the cost perturbation method and adapted to the analysed problem has been proposed. The paper also contains the results of numerical experiments testing the effectiveness of the proposed algorithm and compares it with algorithms known in the literature. The research is based on a large number of various test examples taken from the literature.
3
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.
4
Content available Modelowanie i algorytm rozwiązywania problemu przepływowego z transportem
Tyński A., Makuchowski M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
643-651
PL
W pracy rozważany jest elastyczny system produkcyjny o strukturze przepływowej, w którym maszyny zorganizowane są w układ typu "pętla". W systemie do transportów między maszynami wykorzystuje się zbiór identycznych wózków AGV. Dla systemu zostały przedstawione reprezentacje matematyczne oraz metoda przybliżonego rozwiązywania wykorzystująca schemat tabu search. Algorytm został poddany badaniom, mającym określić jakość generowanych rozwiązań w zależności od liczby uwzględnionych wózków AGV.
EN
In the paper the flexible manufacturing system with the flowshop structure is considered in which machines are arranged into the single loop layout. In the system all transports between the machines are performed by the set of identical AGV vehicles. For the system the mathematical representations and the heuristic solution method utilizing tabu search scheme have been presented. The algorithm has been tested numerically to determine the quality of the generated solutions in the relation to the number of AGV vehicles utilized.
5
Content available Automatyczna mutacja w algorytmach ewolucyjnych
Makuchowski M., Tyński A.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
443-452
PL
W pracy prezentuje się ogólną metodologię automatycznego bieżącego doboru prawdopodobieństwa mutacji w algorytmach ewolucyjnych. Omawiana metoda przedstawiona jest na przykładzie algorytmu genetycznego dedykowanego problemowi gniazdowemu z ograniczeniem bez czekania. W pracy dokonano porównania klasycznego algorytmu ewolucyjnego z tradycyjnie dobieranymi parametrami z algorytmem zaopatrzonym w prezentowaną modyfikację. Praca zakończona jest przedstawieniem wyników przeprowadzonych badań numerycznych.
EN
In this paper a general method for determining a probability of mutation in evolutionary algorithms is given. The presented method if illustrated by a genetic algorithm for no wait job shop problem. We compare experimentally a classical evolutionary algorithm with parameters determined in a standard way with an evolutionary algorithm equipped with the proposed method.
6
Problem gniazdowy z ograniczeniem bez czekania. Równoległe algorytmy tabu
Makuchowski M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
175-181
PL
W pracy opisane są równoległe algorytmy poszukiwania z zabronieniami, dedykowane gniazdowemu problemowi z ograniczeniem bez czekania. Proponowane algorytmy zbudowane są z nadrzędnego algorytmu bazującego na wspomnianej technice oraz sterowanego algorytmu konstrukcyjnego. Poszukiwania ograniczone są tylko do rozwiązań możliwych do wygenerowania przez wspomniany algorytm konstrukcyjny. W pracy przedstawia się analizę porównawczą zaproponowanych algorytmów.
EN
This paper deals with parallel tabu search algorithms for a job shop problem with a no-wait constraint and a makespan criterion. The proposed algorithms consist of a master algorithm based on the mentioned technique and slave constructive algorithm. This approach reduces the number of solutions to check only to solutions that can be generated by means of the constructive algorithm. In this paper a comparative analysis of the proposed algorithms is presented.
7
Problem gniazdowy z ograniczeniem bez czekania. Algorytmy konstrukcyjne
Makuchowski M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
167-173
PL
W pracy opisana jest pewna procedura konstrukcji rozwiązania dla problemu gniazdowego z ograniczeniem bez czekania. Pokazano także sposób jej wykorzystania do budowy bardzo wydajnych algorytmów zarówno konstrukcyjnych, jak i popraw. W pracy prezentuje się algorytmy konstrukcyjne, bazujące na wspomnianej procedurze. Ich efektywność przebadano na dobrze znanych w literaturze przykładach testowych.
EN
This paper describes some solution constructive procedure dedicated to a job shop problem with the no-wait constraint and a makespan criterion. Very efficient heuristic algorithms based on the presented procedure are discussed. The efficiency of the algorithms is tested on well-known literature benchmarks.
8
Content available Algorytm genetyczny dla problemu gniazdowego z ograniczeniem bez czekania
Makuchowski M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
127-137
PL
W pracy analizuje się problem gniazdowy z ograniczeniem bez czekania z kryterium optymalizacji będącym terminem zakończenia wykonywania wszystkich zadań. Przedstawia się klasę rozwiązań superaktywnych oraz jej rozszerzenie - klasę rozwiązań pseudoaktywnych. Na bazie omówionych klas rozwiązań proponuje się dwa algorytmy genetyczne. Jakość proponowanych algorytmów ocenia się na podstawie przeprowadzonych badań numerycznych, wykorzystując literaturowe przykłady testowe.
EN
The paper deals with the no-wait job shop scheduling problem with the makespan criterion. The new class of so called "super-active" solution is introduced. Two genetic algorithms SGA and PGA, based on aforementioned class, and the class of "pseudo-active" schedules, are proposed. These algorithms are tested on "easy" and "hard" benchmarks well-know in literature. Results of computational experiments are given and they are compared with results yielded by the best genetic algorithm discusses in literature.
9
Content available remote Pewien algorytm konstrukcyjny dla problemu gniazdowego z operacjami wielomaszynowymi nierównocześnie wykorzystującymi maszyny
Nowicki E., Makuchowski M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
199-204
PL
W pracy rozważa się uogólniony problem gniazdowy z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Uogólnienie polega na zamodelowaniu operacji wielomaszynowych nierównocześnie wykorzystujących maszyny. Problem jest NP-trudny, co uzasadnia stosowanie algorytmów heurystycznych. W pracy przedstawia się pewien konstrukcyjny algorytm oparty na technice wstawień. Dodatkowo prezentuje się wyniki eksperymentów numerycznych oraz porównania z rezultatami dostarczanymi przez najlepsze znane z literatury algorytmy konstrukcyjne.
EN
The paper deals with the general job-shop problem of finding a minimum makespan. The generalization based on models multimachine operations with non-simultaneously used machines. The problem belongs to class NP-hard problems what justifies searching for heuristic algorithms. Some constructional algorithm is presented. Computational experiments are given and compared with the result yielded by the best algorithms discusses in the literature.
10
Algorytm tabu dla problemu gniazdowego z operacjami wielomaszynowymi nierównocześnie wykorzystującymi maszyny
Makuchowski M., Nowicki E.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
287-297
PL
W pracy rozważa się problem gniazdowy z operacjami wielomaszynowymi, nierównocześnie wykorzystującymi maszyny. Przedstawia się jego model permutacyjno-grafowy. Następnie prezentuje się algorytm przybliżony typu tabu zwracając szczególną uwagę na definicję sąsiedztwa oraz atrybuty zapisywane na listę tabu. Przeprowadza się badania eksperymentalne zaproponowanego algorytmu na przykładach testowych powszechnie stosowanych w literaturze.
EN
The paper discusses the job shop multimachine operations problem with non-simultaneously used machines. Its permutation-graph model is shown. The algorithm based on a tabu search technique with a specific neighborhood definition and suitable attributes written to taboo list is presented. Moreover, the algorithm is examined on well-known literature examples.
11
Content available remote Krajobraz przestrzeni rozwiązań problemu gniazdowego
Nowicki E., Makuchowski M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
449-456
PL
W pracy bada się krajobraz przestrzeni rozwiązań problemu gniazdowego. Przedstawia się dwa typy ruchów (zamień i wstaw) oraz odpowiadające im miary odległości. Następnie dla różnych instancji problemu gniazdowego testuje się korelacje pomiędzy wartością funkcji celu lokalnego minimum, a jego średnią odległością od wszystkich innych badanych lokalnych minimów (lub odległością do najlepszego minimum lokalnego). Otrzymane rezultaty potwierdzają hipotezę, że zbiór lokalnych minimów ma strukturę "dużej doliny" oraz że jest umiejscowiony w obszarze stanowiącym bardzo niewielką część przestrzeni rozwiązań.
EN
The paper deals with the landscape of the solution space of the job shop problem. Two types of moves (swap and insert) are defined and the resulting distance metrics examined. Next, for instances of the job shop problem, the correlation between the cost of a local minimum and its average distance to all other local minima (as well as its distance to the best-found local minimum) is tested. Obtained results confirm hypothesis that the set of local minima has a "big valley" structure and is confined to a tiny portion of the solution space.
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ć.