Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Approximation algorithms for selected problems of parallel resource allocation
Konferencja
XIIIKrajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
W pracy analizowane są własności uszeregowań dla wprowadzonego modelu systemu równoległego. W szczególnym przypadku, dla systemów równoległych z zadaniami dedykowanymi, ustaloną alokację zasobów możemy zamodelować wykorzystując tzw. grafy konfliktów. W chromatycznym modelu uporządkowań w czasie możemy sprowadzić znajdowanie uszeregowań optymalnych do znajdowania tych spośród multipokolorowań grafu konfliktów, których suma kolorów jest minimalna. Autorzy podają wstępną analizę własności modelu, wprowadzają algorytmy zachłanne oraz na podstawie uzyskanych lub cytowanych oszacowań pokazują algorytmy przybliżone.
In the paper we consider the problem of scheduling multiprocessor tasks on dedicated processors. Assuming that there is only one alocation of resources the proposed general model can be reduced to the chromatic model of sequencing of tasks. The authors analyze the properties of the sum multicoloring problem of conflicting graphs and give some new bounds on the (multi) chromatic sum. Based on the introduced greedy algorithm we propose approximation algorithms to the problem P | fix j, G, r j | Sigma Cj.
Słowa kluczowe
Rocznik
Tom
Strony
299--312
Opis fizyczny
Bibliogr. 14 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0008-0009