- Tytuł:
- Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
- Autorzy:
-
Pikies, T.
Kubale, Marek - Powiązania:
- https://bibliotekanauki.pl/articles/201958.pdf
- Data publikacji:
- 2019
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
approximation algorithm
graph coloring
incompatible job
polynomial algorithm
scheduling
uniform machine
unit-time jobs
algorytm aproksymacyjny
kolorowanie grafów
algorytm wielomianowy
planowanie
praca jednostkowa - Opis:
- 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.
- Źródło:
-
Bulletin of the Polish Academy of Sciences. Technical Sciences; 2019, 67, 1; 31-36
0239-7528 - Pojawia się w:
- Bulletin of the Polish Academy of Sciences. Technical Sciences
- Dostawca treści:
- Biblioteka Nauki
Artykuł