Wyniki wyszukiwania - BazTech

1

Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines

Pikies T., Kubale Marek

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2019

|

Vol. 67, nr 1

31--36

EN

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1, G = bisubquartic|ΣCj, where m ϵ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.

2

A note on the density of the strong product of graphs

Pikies T.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2018

|

T. 23

97--103

EN

This paper presents some lower and upper bounds on the density of a graph in its strong powers. They were created using the basic graph parameters and using basic properties of the strong product. The created bounds were sufficient to make a general conclusion about how the density in the strong powers of a graph behaves. On the basis of these considerations a simple conclusion follows on the merit of graph algorithms sensitive to the number of edges for applications to this type of graphs.

PL

Praca zawiera pewne dolne oraz górne ograniczenia dla gęstości silnych potęg grafu. Zostały one wyznaczone przy pomocy podstawowych parametrów grafu oraz podstawowych własności silnego produktu. Wyznaczone ograniczenia są wystarczające do wysnucia prostych wniosków odnośnie zachowanie gęstości w silnych potęgach grafu. Wnioski te świadczą o zasadności stosowania algorytmów wrażliwych na ilość krawędzi przy badaniu silnych potęg grafów.

3

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.