Uszeregowania zadań wieloprocesorowych minimalizujące średni czas przepływu

• Autorzy: Janczewski R. , Kuszner Ł. , Malafiejski M. , Nadolski A.
• Języki publikacji: PL

Abstrakty

PL

W artykule rozważane są problemy efektywnego wyznaczania uszeregowań wieloprocesorowych zadań jednostkowych na dedykowanych procesorach równoległych, które minimalizują średni czas przepływu. Przedstawiony zostanie teoriografowy model tego zagadnienia korzystający z pojęcia grafu konfliktów i jego sumy chromatycznej. Następnie skupimy naszą uwagę na pewnym szczególnym przypadku tego zagadnienia, mianowicie na przypadku prowadzącym do grafów konfliktów będących dopełnieniami grafów krawędziowych. Przedstawimy bieżący stan wiedzy na ten temat, w szczególności informacje o złożoności obliczeniowej, oszacowaniach i algorytmach przybliżonych.

EN

In the article we study the problem of scheduling unit execution time tasks on parallel processors that minimizes the average flow time. We present the graph-theoretical model of the problem that is based on the notion of a chromatic sum. Next we focus on a special case of the problem, present the state of-the-art about it including upper and lower bounds, computational complexity and efficient approximation algorithms.

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2003
• Tom: nr 2
• Strony: 481--485
• Opis fizyczny: Bibliogr. 4 poz., 1 rys.

Twórcy

autor

Janczewski R.

• Katedra Podstaw informatyki, Politechnika Gdańska

autor

Kuszner Ł.

• Katedra Podstaw informatyki, Politechnika Gdańska

autor

Malafiejski M.

• Katedra Podstaw informatyki, Politechnika Gdańska

autor

Nadolski A.

• Katedra Podstaw informatyki, Politechnika Gdańska

Bibliografia

• [1] Burer S., Monteiro R.: A projected gradient algorithm for solving the maxcut SDP relaxation, Optimization Methods and Software 15 (2001), s. 175-200.
• [2] Feige U., Lovasz L., Tetali P.: Approximating Min-sum Set Cover, APPROX 2002, LNCS 2462, s. 94-107, 2002.
• [3] Giaro K., Janczewski R., Kubale M., Małafiejski M.: A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs, APPROX 2002, LNCS 2462 (2002), s. 135-145.
• [4] Małafiejski M.: Uszeregowania zadań wieloprocesorowych minimalizujące średni czas przepływu. Rozprawa doktorska, Politechnika Gdańska, Wydział ETI, 2002.