Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: wielomianowe algorytmy optymalne

Sortuj według:

Ogranicz wyniki do:

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

Małafiejski M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2001

T. 5, z. 1/2

403-409

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).

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.