Wyszukiwarka
Abstrakt
We consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.
Cytowania
-
9
CrossRef
-
0
Web of Science
-
1 5
Scopus
Autorzy (2)
-
Hanna Furmańczyk
- Wydział MFI, UG Instytut Informatyki
Cytuj jako
Pełna treść
pobierz publikację
pobrano 25 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2016.01.036
- Licencja
- Copyright (2016 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 234,
strony 210 - 217,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2018
- Opis bibliograficzny:
- Furmańczyk H., Kubale M.: Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines// DISCRETE APPLIED MATHEMATICS. -Vol. 234, (2018), s.210-217
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2016.01.036
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 131 razy