- Tytuł:
- Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
- Autorzy:
-
Furmańczyk, H.
Kubale, M. - Powiązania:
- https://bibliotekanauki.pl/articles/200295.pdf
- Data publikacji:
- 2017
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
equitable coloring
NP-hardness
polynomial algorithm
scheduling
uniform machine
kolorowanie grafów
twardość NP
algorytm wielomianowy
planowanie - Opis:
- 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.
- Źródło:
-
Bulletin of the Polish Academy of Sciences. Technical Sciences; 2017, 65, 1; 29-34
0239-7528 - Pojawia się w:
- Bulletin of the Polish Academy of Sciences. Technical Sciences
- Dostawca treści:
- Biblioteka Nauki
Artykuł