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

Znaleziono wyników: 8

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 Towards the boundary between easy and hard control problems in multicast Clos networks
Obszarski P., Jastrzębski A., Kubale M.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2015
|
Vol. 63, nr 3
739--744
EN
In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially solvable instances as well as a number of NP-complete cases. Our results warn of possible troubles arising in the control of Clos networks even if they are composed of small-size switches in outer stages. This is in sharp contrast to classical unicast Clos networks for which all the control problems are polynomially solvable.
2
Content available Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi
Obszarski P., Kubale M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
513-519
PL
W artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.
EN
In this article we consider the problem of scheduling unit processing time multiprocessor tasks on dedicated processors with repetition and availability constraints. W present collected results of complexity of this problem for different types of instances and scheduling criteria. To describe the problem we use the model of edge coloring of hypergraphs.
3
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
Obszarski P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
79-84
PL
Problem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować za pomocą hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy, jak za pomocą modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania oraz jak rozwiązać problemy dwukryterialne.
EN
Problem of scheduling multiprocessor tasks on dedicated machines can be modeled by hypergraphs. There are a few classes of hypergraphs for which polynominal time algorithms for scheduling with total cost criterion are known. Our aim is to show that other criteria and also bicriterial problems can be solved by the use of total cost criterion.
4
Hiperheurystyki w kolorowaniu grafów
Dąbrowski J., Obszarski P.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2007
|
T. 13
443-448
PL
Hiperheurystyki to jeden z nowych trendów w technice obliczeniowej. Można je zdefiniować jako algorytmy, które wykorzystują zdefiniowany zbiór prostych heurystyk do znalezienia przybliżonego rozwiązania. Celem algorytmu jest znalezienie takiej sekwencji uruchamiania tych prostych operacji, która będzie dawała najlepsze rozwiązanie dla danej instancji problemu lub danej klasy instancji problemu. W pracy zdefiniowano heurystyki dla problemu wierzchołkowego kolorowania grafów oraz przedstawiono algorytm genetyczny, w którym ewolucji podlegają sekwencje ich wyboru przy kolorowaniu zachłannym.
EN
Hyperheuristics are optimization algorithms that use sets of simple heuristic operations that can change the state of a solution. The goal of the algorithm is to find a good sequence of those operations that produces a good solution to the problem. This work presents low-level heuristics for the well known Graph Coloring Problem and a genetic algorithm that evolves sequences of choices for a greedy coloring algorithm.
5
Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych
Obszarski P.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2007
|
T. 13
449-456
PL
Problem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem NP-trudnym. W tym artykule podejmujemy próbę zastosowania i oceny różnych algorytmów heurystycznych dla kolorowania hipergrafów. Rozważania ogólne poparte są doświadczeniami komputerowymi. Testy zaimplementowanych algorytmów przeprowadzono na hipergrafach losowych.
EN
Problem of scheduling multiprocessor tasks on dedicated processors can be easily presented with hypergraph edge coloring problem. By a hypergraph we mean a generalization of a graph in which edges may contain any number of vertices. This model can be used in many theoretical and practical applications. Hypergraph edge coloring problem is generalization of graph edge coloring so it is NP-hard. In this paper we present and try to judge differ-ent types of heuristic algorithms for hypergraph edge coloring. General considerations are supported with com-puter experiment. Tests were conducted on random hypergraphs.
6
Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych
Obszarski P., Dąbrowski J.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2006
|
T. 10
499-506
PL
Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające tych parametrów.
EN
By a hypergraph we call a generalization of graph in which edges may contain any number of vertices. This model can be used in many theoretical and practical applications. In this paper we discuss edge coloring of hypertrees. We present results on the chromatic index of hypertrees and the edge chromatic sum of index of simple hypertrees. We also provide polynomial time algorithms for finding these parameters.
7
Zastosowanie algorytmów rojowych do kolorowania grafów
Obszarski P., Piwakowski K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
107-113
PL
Przedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.
EN
Adaptation of the Particle Swarm Optimization method for obtaining suboptimal vertex colorings of graphs is proposed. We present details of performed computational experiments and their results.
8
Kolorowanie hipergrafów
Kubale M., Obszarski P., Piwakowski K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
83-90
PL
Hipergraf to struktura stanowiąca pewne uogólnienie grafa. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności, złożoności oraz wskażemy zastosowania.
EN
A hypergraph is a generalization of a graph in which the edges may contain any number of vertices. In this paper we discuss a few models of hypergraph coloring, namely: edge coloring, vertex coloring and mixed coloring. We present some basic properties of these models, complexity and their possible applications.
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ć.