Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi

• Autorzy: Obszarski P. , Kubale M.

Warianty tytułu

EN

Scheduling multiprocessor tasks with hyperedge coloring model

• Języki publikacji: PL

Abstrakty

PL

W artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.

EN

In this article we consider the problem of scheduling unit processing time multiprocessor tasks on dedicated processors with repetition and availability constraints. W present collected results of complexity of this problem for different types of instances and scheduling criteria. To describe the problem we use the model of edge coloring of hypergraphs.

Słowa kluczowe

PL

zadanie wieloprocesorowe; maszyny dedykowane; kolorowanie krawędzi hipergrafów

EN

multiprocessor tasks; dedicated machines; hypergraph edge coloring

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 513--519
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Obszarski P.

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

autor

Kubale M.

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

Bibliografia

• [1] Berge C, Graphs and Hypergraphs. Elsevier Science, 1985.
• [2] Brandstadt A., Le V.B., Spinard J.P., Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, 1999.
• [3] Giaro K., Kolorowanie sumacyjne i listowo-kosztowe krawędzi hiperdrzew. Raport badawczy na wydziale ETI Politechniki Gdańskiej, 2007.
• [4] Giaro K., Kubale M., Obszarski P., Graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints. Discrete Applied Mathematics, w druku).
• [5] Kramer A., Scheduling Multiprocessor Tasks on Dedicated Processors. Dissertation Fachbereich Mathematik/Informatik, Universitat Osnabriick, 1995.
• [6] Mant D., The complexity of tree multicolorings. Lecture Notes in Computer Science 2420, 2002, 32-542.
• [7] Obszarski P., Szeregowanie zadań wieloprocesorowych na procesorach dedykowanych w modelu hipergrafowym. Praca doktorska (w recenzji).
• [8] Obszarski P., Dąbrowski J., Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej, 10, 2006, 499-506.