Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines - Publikacja - MOST Wiedzy

Wyszukiwarka

Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

Abstrakt

The problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to optimality in polynomial time. The same algorithm returns a solution of value at most 2 times optimal provided that s1>2s2.

Cytowania

  • 0
    CrossRef
  • 1
    Web of Science
  • 1
    Scopus

Hanna Furmańczyk, Marek Kubale. (2017). Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines, 65(1), 29-34. https://doi.org/10.1515/bpasts-2017-0004

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 65, strony 29 - 34,
ISSN: 0239-7528
Język:
angielski
Rok wydania:
2017
Opis bibliograficzny:
Furmańczyk H., Kubale M.: Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines// Bulletin of the Polish Academy of Sciences-Technical Sciences. -Vol. 65, nr. 1 (2017), s.29-34

wyświetlono 9 razy

Publikacje, które mogą cię zainteresować

Meta Tagi