Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines - Publikacja - MOST Wiedzy

Wyszukiwarka

Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines

Abstrakt

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|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p j = 1, G = bisubquartic|ΣC j , 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.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
Bulletin of the Polish Academy of Sciences-Technical Sciences nr 67, strony 31 - 36,
ISSN: 0239-7528
Język:
angielski
Rok wydania:
2019
Opis bibliograficzny:
Pikies T., Kubale M.: Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines// Bulletin of the Polish Academy of Sciences-Technical Sciences. -Vol. 67, iss. 1 (2019), s.31-36
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.24425/bpas.2019.127335
Źródła finansowania:
Weryfikacja:
Politechnika Gdańska

wyświetlono 21 razy

Publikacje, które mogą cię zainteresować

Meta Tagi