Wybrane problemy harmonogramowania procesów w oparciu o dwudzielne grafy konfliktowe

• Autorzy: Małafiejski M.

Warianty tytułu

EN

On the multiprocessor tasks scheduling with resource conflicts modelled by bipartite graphs

• Języki publikacji: PL

Abstrakty

PL

W pracy dokonano podsumowania większości znanych wyników dotyczących problemu minimalizacji średniego czasu przepływu zadań w systemie wieloprocesorowych zadań współdzielących zasoby (pliki, procesory, maszyny). Konflikty w dostępie do współdzielonych zasobów modelują tzw. grafy konfliktowe. W szczególności dla zadań, które można podzielić na dwa zbiory (zadania typu I oraz II) tak, że żadne dwa zadania jednego typu nie współdzielą tego samego zasobu, grafy konliktowe są dwudzielne. Konstrukcję optymalnych uszeregowań można równoważnie sprowadzić do konstrukcji pokolorowań grafów konfliktowych realizujących sumę (multi)chromatyczną. Wykorzystując bogaty aparat teorii grafów dla wybranych klas grafów dwudzielnych można skonstruować wielomianowe algorytmy optymalne (drzewa, pełne, regularne), korzystając dodatkowo z technik dowodzenia NP-zupełności można rozstrzygnąć problem złożoności obliczeniowej wybranych problemów decyzyjnych (np. grafy dwudzielne z ograniczonych maksymalnym stopniem). Dodatkowo przedstawione zostały problemy otwarte związane z prezentowaną tematyką, w szczególności problemy złożoności uszeregowania zadań całkowitych (ścieżki, drzewa).

EN

In the paper the author considers the problem of scheduling multiprocessor tasks with resource conflicts modelled by bipartite graphs. Consider the following scenario that exemplifies the problem. Given n jobs executed in a distributed computing environment. Suppose that each job running on different processor requires exclusively a subset of the set of files stored in the network file system. The execution time of each job is multiplicity of the unit execution time. The jobs and the conflicts between them in accesses to the shared files are represented by vertices and edges of the graph, respectively. The associated graph we call a conflicting graph. Based on the graph theory and NP-complete results the author presents polynomial time and NP-complete results. Moreover, the author states some new open questions concerning the problem.

Słowa kluczowe

PL

graf konfliktowy dwudzielny; wielomianowe algorytmy optymalne

EN

bipartite graphs; conflicting graph

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2001
• Tom: T. 5, z. 1/2
• Strony: 403--409
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Małafiejski M.

• Katedra Podstaw Informatyki, Wydział Elektroniki, Telekomunikacji i Informatyki, Politechnika Gdańska