PL
 |
EN
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
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 remote Szeregowanie zadań w acyklicznym systemie otwartym
100%
Giaro K.
|
2001
|
tom T. 5, z. 1/2
213-220
PL
Celem artykułu jest podsumowanie znanych dotychczas oraz zaprezentowanie nowych wyników dotyczących złożoności obliczeniowej problemu poszukiwania optymalnego uszeregowania w systemie otwartym. Przy tym interesują nas systemy rzadkie, to jest takie, których graf jest acykliczny, czyli stanowi drzewo lub las. Rozważanymi kryteriami optymalizacji harmonogramu są: standardowa długość uszeregowana C(max) oraz średni czas zakończenia operacji. Badamy model ogólny niepodzielnych operacji o dowolnych długościach, system o operacjach podzielnych oraz system o zero-jedynkowych czasach wykonania. Innym rozważanym tu nieklasycznym modelem jest harmonogramowanie zwarte, tj. wymagające obustronnego braku przestojów w pracy, tak po stronie zadań, jak i procesorów. Szeregowanie takie jest bowiem zawsze wykonalne w przypadku systemów acyklicznych.
EN
Our aim is summarizing of already known and presenting of some new results on the complexity of optimal task scheduling in open shop. So we are interested in sparse systems, it means that their graphs are acyclic forming a tree of a forest. Our optimization criteria are the standard length of schedule C(TAX) and the average time of finish for operations. We consider the general model of operations with arbitrary length, a system with preemptive operations and finally a system with zero-one execution times. Another model under consideration is compact scheduling, where time breaks are imposed for both points of view: tasks and processors. It is because this kind of schedule could be always constructed for acyclic open shops.
2
Szeregowanie zadań na procesorach dedykowanych bez przestojów
100%
Giaro K.
|
1998
|
tom z. 123
133-144
PL
W praktycznym szeregowaniu zadań dość często spotykamy się z koniecznością zapewnienia nieprzerwanej pracy poszczególnym podmiotom naszego systemu. Szeregowanie takie nazywa się szeregowaniem bez przestojów. Zadaniem tej pracy jest zasygnalizowanie skali trudności obliczeniowej, jaką wymusza powyższe założenie. Wykażemy, że szereg podstawowych problemów decyzyjnych i optymalizacyjnych dotyczących istnienia lub najprostszych parametrów harmonogramu w szeregowaniu bez przestojów staje się NP-trudny, nawet dla systemów o grafach szeregowannia tak prostych jak ścieżka i cykl. Rozważania nasze będą dotyczyć modeli open show, flow shop oraz systemu zadań dwuprocesorowych.
EN
In practical task scheduling it is sometimes required that the elements of a system perform consecutively. Such a scheduling is called scheduling without waiting periods or no-wait and/or no-idle. In this article we study the complexity of some simplified scheduling problems of this kind. In particular, we show that many trivial questions about scheduling become NP-hard, even if the scheduling graph of a system is path, or a cycle. Our consideration concern the following models: open shop, flow shop and 2-procesor tasks system.
3
Zwarte kolorowanie małych grafów dwudzielnych. Eksperymenty komputerowe
100%
Giaro K.
|
2000
|
tom z. 131
75-83
PL
Rozważamy pewien stosunkowo nowy model kolorowania krawędziowego grafów zwany zwartym kolorowaniem. Polega on na przypisaniu krawędziom grafu liczb naturalnych w taki sposób, by kolorowanie to było legalne oraz kolory krawędzi incydentnych do dowolnego wierzchołka tworzyły zwarte przedziały. Okazuje się, że nie wszystkie grafy można kolorować w sposób zwarty. Praca prezentuje w skrócie podstawowe własności zwartego kolorowania. Dalsza część opisuje przebieg kilku doświadczeń komputerowych mających na celu weryfikację pewnych hipotez dotyczących zwartego kolorowania na małych grafach dwudzielnych.
EN
In this paper we consider some relatively new model of edge coloring called compact. It consists in ascribing natural numbers to the edges of a graph in such a way that obtained coloring is legal and colors of edges incident to any vertex constitute compact intervals. It occurs that not all graphs can by colored in this way. This article shortly describes basic properties of compact coloring and presents a few computer experiments performed to verify on small bipartite graphs some hypotheses concerning compact coloring.
4
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
63%
Giaro K. , Janczewski R.
|
2002
|
tom z. 136
67-73
PL
Problem przydziału częstotliwości to zagadnienie, które formułuje się zazwyczaj następująco: na pewnym obszarze znajduje się grupa nadajników radiowych, którym trzeba przydzielić częstotliwości w taki sposób, żeby nie zakłócały się podczas nadawania i aby szerokość wykorzystanego przez nie pasma częstotliwości była minimalna. Zagadnienie to modeluje się zazwyczaj na gruncie teorii grafów za pomocą trzech pojęć: grafów interferencji, kontrastowych pokolorowań i T-rozpiętości. Niniejszy artykuł poświęcony jest złożoności obliczeniowej tego modelu; zawiera jego dokładny opis, dowód tego, że wyznaczanie T-rozpiętości i optymalnych pokolorowań kontrastowych jest NP-trudne nawet dla grafów dwudzielnych oraz wielomianowy algorytm wyznaczający optymalne pokolorowania kontrastowe dla tzw. częściowych k-drzew.
EN
Frequency assignment problem (FAP) can be formulated as follows: there is a group of transmitters situated in a certain region of a plane; a channel is to be assigned to each of them in such a way that there is no interference during transmitting and the span of used frequency band is minimal. The paper is devoted to the computational complexity of the graph-theoretical model of FAP based on three notions: interference graphs, T-colorings and the T-span. We describe the model, prove that the problem of computing the T-span is NP-hard even for bipartite graphs and present a polynomial time algorithm for finding optimal T-coloring for the socalled partial k-trees.
5
Zwarte szeregowanie zadań w rozrzedzonym systemie otwartym
63%
Giaro K. , Szyfelbein D.
|
2000
|
tom z. 129
73-82
PL
W pracy rozważamy szeregowanie zadań w rozrzedzonym systemie otwartym bez obustronnych przestojów o jednostkowym czasie wykonania operacji. Problem ten modelujemy za pomocą zwartego kolorowania krawędziowego grafów dwudzielnych. Stopień rozrzedzenia systemu otwartego mierzymy za pomocą liczby cyklomatycznej odpowiadającego mu grafu. Praca opisuje w skrócie przebieg eksperymentu komputerowego weryfikującego hipotezę dotyczącą zwartego kolorowania grafów o liczbie cyklomatycznej nie większej niż 8.
EN
In the paper we consider compact scheduling of tasks in sparse open shop with zero-one execution time of operations. We model this problem with consecutive edge coloring of bipartite graphs. Sparse factor of open shop is measured as cyclomatic number of corresponding graph. We shortly describe computer experiments which verify hypotheses that concern consecutive coloring of graphs with cyclomatic number not greater than 8.
6
Comparing arbitrary unrooted phylogenetic trees using generalized Matching Split distance
63%
Bogdanowicz D. , Giaro K.
|
2010
|
tom T. 18
493-498
EN
In the paper, we describe a method for comparing arbitrary, not necessary fully resolved, unrooted phylogenetic trees. The proposed method is based on finding a minimum weight matching in bipartite graphs and can be regarded as a generalization of well-known Robinson-Foulds distance. We present some properties and advantages of the new distance. We also investigate some properties of the presented distance in a common biological problem of finding a single phylogenetic tree (consensus tree) that reliably represents a set of various phylogenetic trees. Finding a consensus tree (or a small set of such trees) is an important phase in the phylogenetic research, especially if a method that is chosen for the construction process returns a set of trees (for example the very popular Bayesian approach).
PL
W pracy zaprezentowano dwie metody porównywania dowolnych (niekoniecznie binarnych) drzew filogenetycznych. Przedstawione metryki opierają się na zagadnieniu poszukiwania najlżejszego doskonałego skojarzenia w grafach dwudzielnych i mogą być postrzegane jako rozszerzenie klasycznej metody porównywania drzew, określanej jako metryka Robinsona-Foluds'a. Przedstawiona analiza dotyczy podstawowych własności i zalety proponowanych metod. Pewne cechy rozważanych metod przedstawiono także w kontekście wykorzystania proponowanych metryk w zagadnieniu poszukiwania drzewa konsensusu. Problem poszukiwania drzew konsensusu pełni istotną rolę w analizie filogenetycznej, zwłaszcza, jeśli przyjęta metoda konstrukcji generuje zbiór drzew, co ma miejsce, np. w przypadku bardzo popularnych metod Bayesowskich.
7
Content available remote Złożoność zwartego szeregowania zadań jednostkowych w systemie otwartym, przepływowym i mieszanym
63%
Kubale M. , Giaro K.
|
2001
|
tom T. 5, z. 1/2
329-334
PL
W artykule przedyskutowano złożoność obliczeniową problemu zwartego szeregowania zadań (operacji) jednostkowych na procesorach dedykowanych w systemie otwartym, przepływowym i mieszanym. Modelem matematycznym jest tu zwarte kolorowanie krawędzi grafu dwudzielnego. Ponieważ w ogólności zwarte pokolorowanie krawędzi nie zawsze jest możliwe (a rozstrzygnięcie tego jest NP-zupełne), koncentrujemy się na takich szczególnych typach grafów szeregowania, które posiadają rozwiązania wielomianowe.
EN
In this article we discuss the computational complexity of the problem of compact scheduling of unit execution tasks (operations) in open, flow and mixed shop. A mathematical model of such a problem is a compact (consecutive) coloring of the edges of a bipartite graph. Since in general a compact coloring is not always possible (and it is an NP-complete problem), we concentrate on those graph families that admit polynomial time solutions.
8
Programowanie dynamiczne w rozw3iązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze
63%
Giaro K. , Kubale M.
|
2002
|
tom z. 134
173-184
PL
Rozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop, flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano posługując się jego modelem grafowym - w zakresie naszego zainteresowania leżą jedynie takie instancje problemów szeregowania, których modelami są grafy acykliczne.
EN
We consider systems with nonpreemptable 2-processor tasks of unit execution times as well as systems of dedicated processors with zero-unit execution times. We are interested in systems whose scheduling graphs are acyclic. For such graphs we give a family of polynomial algorithms based on dynamic programming which yield optimal solutions with respect to a broad family of criterion functions.
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ć.