Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Bulletin of the Polish Academy of Sciences. Technical Sciences

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: uniform machine

Sortuj według:

Ogranicz wyniki do:

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

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.

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

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.