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

Znaleziono wyników: 31

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
Duraj S., Kopeć P., Kubale M., Pikies T.
Decision Making in Manufacturing and Services
|
2017
|
Vol. 11, no. 1-2
53--61
EN
In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
2
Content available Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
Furmańczyk H., Kubale M.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2017
|
Vol. 65, nr 1
29--34
EN
In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.
3
Content available Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Furmańczyk H., Jastrzębski A., Kubale M.
Archives of Control Sciences
|
2016
|
Vol. 26, no. 3
281--295
EN
In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
4
Content available remote On the independence number of some strong products of cycle-powers
Jurkiewicz M., Kubale M., Ocetkiewicz K.
Foundations of Computing and Decision Sciences
|
2015
|
Vol. 40, No. 2
133--141
EN
In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers α((C210)⊠3) = 30 and α((C414)⊠3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish new exact values and/or lower bounds on the Shannon capacity of noisy channels.
5
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.
6
Content available Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Furmańczyk H., Kubale M.
Archives of Control Sciences
|
2015
|
Vol. 25, no. 1
109--116
EN
In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.
7
Content available remote Some lower bounds on the Shannon capacity
Jurkiewicz M., Kubale M., Turowski K.
Journal of Applied Computer Science
|
2014
|
Vol. 22, nr 2
31--42
EN
In the paper we present a measure of a discrete noisy channel, named the Shannon capacity, which is described in the language of graph theory. Unfortunately, the Shannon capacity C0 is difficult to calculate, so we try to estimate the value of C0 for specific classes of graphs, i.e. circular graphs.
8
Content available remote Modele i metody kolorowania grafów. Część II
Kubale M.
Przegląd Elektrotechniczny
|
2012
|
R. 88, nr 11a
51-55
PL
Niniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podano potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.
EN
This is the second of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show various criteria and modifications of classical coloring model. Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.
9
Content available remote A note on Shannon capacity for invariant and evolving channels
Jurkiewicz M., Kubale M.
Journal of Applied Computer Science
|
2011
|
Vol. 19, nr 2
19-29
EN
In the paper we discuss the notion of Shannon capacity for invariant and evolving channels. We show how this notion is involved in information theory, graph theory and Ramsey theory.
10
Content available Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
Ocetkiewicz K. M., Kubale M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
T. 15, z. 2
375-380
PL
Niniejszy artykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. Model matematyczny, który tutaj zastosowano, to szeregowanie zadań uwarunkowanych czasowo. Przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. Pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie.
EN
The article is devoted to scheduling jobs of fire fighting squads dealing with forest fire. Time-dependent scheduling is employed as a mathematical model. The complexity of two optimization criteria was discussed: the makespan and the total completion time. It is shown that, in general case, there are no ideal schedules that guarantee minimization of both of these goals simultaneously.
11
Scheduling jobs to contain natural disaster model and complexity
Kubale M., Ocetkiewicz K.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2010
|
T. 18
333-338
EN
This paper is devoted to the problem of scheduling suppression units so that a natural disaster is dealt with as efficient as possible. The concept of deteriorating jobs is adopted, that is, the formal model of scheduling represents linearly increasing value loss as the disaster remains unsuppressed and increasing time for its suppression. More precisely, two different goals are considered: finding a suppression schedule of a minimal length, and finding a suppression schedule minimizing the total completion time. The former goal is advantageous to the suppression brigade, while the latter realizes the interest of the environment. We show that these two objectives are often in conflict. Then we review the state of the art concerning efficient solutions to the problem.
PL
Artykuł poświęcony jest problemowi szeregowania pracy oddziałów ratowniczych tak, aby jak najefektywniej zminimalizować skutki katastrofy naturalnej. Zastosowana jest koncepcja zadań uwarunkowanych czasowo, tj. formalny model szeregowania uwzględnia liniowy wzrost kosztów i czasu potrzebnego na zwalczenie skutków katastrofy. Rozważone są dwa różne kryteria: znalezienie harmonogramu o najmniejszej długości oraz wyznaczenie sekwencji działań minimalizującej całkowity czas wykonywania. Pierwsze kryterium reprezentuje interes oddziału, drugie zaś interes środowiska. Pokazujemy, że kryteria te często pozostają ze sobą w konflikcie. Przedstawiamy przegląd wiedzy na temat efektywnych rozwiązań przedstawionych problemów.
12
Content available remote Modele i metody kolorowania grafów. Część I
Kubale M.
Przegląd Elektrotechniczny
|
2010
|
R. 86, nr 9
115-117
PL
Niniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano: (1) co można kolorować w grafie (np. wierzchołki, krawędzie, końcówki, ściany, jednocześnie wierzchołki i krawędzie) oraz (2) jak można kolorować (np. dzielenie kolorów, zawijanie kolorów). Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podajemy potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.
EN
This is the first of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show: (1) what elements of a graph can be colored (e.g. vertices, edges, faces, incidences) and (2) how these elements can be colored (e.g. fractional coloring, circular coloring). Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.
13
Content available remote A new optimal algorithm for a time-dependent scheduling problem
Kubale M., Ocetkiewicz K. M.
Control and Cybernetics
|
2009
|
Vol. 38, no 3
713-721
EN
In this article a single machine time-dependent scheduling problem with total completion time criterion is considered. There are n given jobs, j1,...,jn, and the processing time pi of the i-th job is given by pi = 1 + biSi, where si is the starting time of the i-th job, i = 1,...n. If all jobs have different and non-zero deterioration rates and bi [wzór], where bmin = min{bi}, then an optimal schedule can be found in O(n log n) time. The conducted computational experiments show that the presented algorithm performs very well even on data not satisfying the assumed constraints.
14
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.
15
Content available Model formalny dla problemu lokalizacji błędów w kodzie programu
Dereniowski D., Kubale M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2007
|
T. 11, z. 1-2
81-88
PL
Istnieje szereg sposobów badania poprawności programów komputerowych. W artykule podejmujemy problem automatycznego testowania oprogramowania przy założeniu, że dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu oraz rozważamy model teoretyczny oparty na teorii grafów, w szczególności jej chromatyczne aspekty oraz pewien model przeszukiwania grafu opisującego strukturę programu.
EN
There are several criteria for testing program correctness. In this paper we deal with the problem of automatic software testing under the assumption that the set of tests (assertions) is given for selected blocks of code. We simplify the analysis by assuming that the program being tested contains exactly one bug, but this does not lead to loss of generality. We consider some practical aspects of the above problem and a graph-theoretical model in general as well as some chromatic aspects of a graph searching model in particular.
16
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.
17
Parallel tabu search for graph coloring problem
Dąbrowski J., Kubale M.
Prace Naukowe Politechniki Warszawskiej. Elektronika
|
2006
|
z. 156
87-95
EN
Tabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of parallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experirnental results are based on graphs available from the DIMACS benchmark suite.
18
Content available remote Efficient Parallel Query Processing by Graph Ranking
Dereniowski D., Kubale M.
Fundamenta Informaticae
|
2006
|
Vol. 69, nr 3
273-285
EN
In this paper we deal with the problem of finding an optimal query execution plan in database systems. We improve the analysis of a polynomial-time approximation algorithm due to Makino et al. for designing query execution plans with almost optimal number of parallel steps. This algorithm is based on the concept of edge ranking of graphs. We use a new upper bound for the edge ranking number of a tree to derive a better worst-case performance guarantee for this algorithm. We also present some experimental results obtained during the tests of the algorithm on random graphs in order to compare the quality of both approximation ratios on average. Both theoretical analysis and experimental results indicate the superiority of our approach.
19
Content available remote The Complexity of Equitable Vertex Coloring of Graphs
Furmańczyk H., Kubale M.
Journal of Applied Computer Science
|
2005
|
Vol. 13, nr 2
95-106
EN
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by X=(G). In the paper we give formulas for the equitable chromatic number of some highly-structured graphs and some graph products. We present also two polynomial-time algorithms for equitable graph coloring with suboptimal number of colors.
20
Content available Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych
Giaro K., Kubale M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
85-94
PL
W artykule rozważono rozrzedzone systemy niepodzielnych zadań 1- i 2-procesorowych o jednostkowych czasach wykonywania. Przedstawiono wielomianowe algorytmy wykorzystujące programowanie dynamiczne, pozwalające 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 o ograniczonej liczbie cyklomatycznej. Istotnym elementem opracowanych procedur są algorytmy rozwiązujące pewne zagadnienia związane z wyszukiwaniem skojarzeń w grafach.
EN
In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.
first rewind previous Strona / 2 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ć.