Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs

Abstrakt

The problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines are considered first. An FPTAS for R2|G=bipartite|Cmax is provided. We also show that for any ϵ>0,b>0 and m≥3 , there is no polynomial-time algorithm of approximation ratio O(nbp1−ϵmax) for Rm|G = bipartite |Cmax , unless P = NP. Uniform machines are considered as second. For any ϵ>0 , we show that under P = NP assumption there is no polynomial-time O(n1/2−ϵ )-approximation algorithm, even in the case of unit time jobs. We also provide a polynomial-time Σpj−−−√ -approximation algorithm for the case of jobs of arbitrary lengths pj , matching the established bound. To enrich the analysis, bipartite graphs generated randomly according to Gilbert's model Gn,n,p(n) are considered. We show that there exists an algorithm producing a schedule with makespan almost surely at most twice the optimum for a broad class of p(n) functions. To the best of our knowledge, this is the first study of randomly generated graphs in the context of scheduling in the considered model.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 1

    Scopus

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Język:
angielski
Rok wydania:
2022
Opis bibliograficzny:
Pikies T., Furmańczyk H.: Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs// / : , 2022,
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/ipdps53621.2022.00070
Źródła finansowania:
  • COST_FREE
Weryfikacja:
Politechnika Gdańska

wyświetlono 77 razy

Publikacje, które mogą cię zainteresować

Meta Tagi