Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines - Publikacja - MOST Wiedzy

Wyszukiwarka

Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines

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 4

    Scopus

Autorzy (2)

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 76 razy

Publikacje, które mogą cię zainteresować

Meta Tagi