Algorytmy przybliżone dla wybranych problemów równoległego przydziału zasobów

• Autorzy: Janczewski R. , Małafiejski M.

Warianty tytułu

EN

Approximation algorithms for selected problems of parallel resource allocation

• Konferencja: XIIIKrajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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

PL

maszyny równoległe; rozdział zasobów; algorytm przybliżony

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 299--312
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Janczewski R.

autor

Małafiejski M.

• Politechnika Gdańska, Gdańsk