Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych

• Autorzy: Obszarski P.

Warianty tytułu

EN

Heuristic algorithms for scheduling multiprocessor tasks on dedicated processors

• Języki publikacji: PL

Abstrakty

PL

Problem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem NP-trudnym. W tym artykule podejmujemy próbę zastosowania i oceny różnych algorytmów heurystycznych dla kolorowania hipergrafów. Rozważania ogólne poparte są doświadczeniami komputerowymi. Testy zaimplementowanych algorytmów przeprowadzono na hipergrafach losowych.

EN

Problem of scheduling multiprocessor tasks on dedicated processors can be easily presented with hypergraph edge coloring problem. By a hypergraph we mean a generalization of a graph in which edges may contain any number of vertices. This model can be used in many theoretical and practical applications. Hypergraph edge coloring problem is generalization of graph edge coloring so it is NP-hard. In this paper we present and try to judge differ-ent types of heuristic algorithms for hypergraph edge coloring. General considerations are supported with com-puter experiment. Tests were conducted on random hypergraphs.

Słowa kluczowe

PL

hipergrafy; kolorowania krawędzi hipergrafów; algorytmy heurystyczne; hipergtafy losowe

EN

hypergraphs; hypergraph edge coloring; heuristic algorithms; random hypergraphs

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 449--456
• Opis fizyczny: Bibliogr. 4 poz. rys.

Twórcy

autor

Obszarski P.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] Brandstadt A, Bang Le V., Spinrad J. P.: Graph Classes: A Survey, SIAM, 2000
• [2] Obszarski P., Dąbrowski J.: Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych, Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej 10, (2006), s. 499-506.
• [3] Giaro K., Kubale M.: Chromatic scheduling of 1- and 2-processor VET tasks on dedicated machines with availability constrains, Lecture Notes in Computer Science 3911 (2006) s.855-862.
• [4] Kruskal J. 80: On the shortest spanning subtree and the traveling salesman problem, Proc. Am. Math. Soc. 7 (1956) 48-50.