Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych

Giaro, K.; Kubale, M.

Artykuł - szczegóły

Tytuł artykułu

Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych

Autorzy

Giaro K. , Kubale M.

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

Warianty tytułu

Scheduling in sparse systems of 1- and 2-processor UET tasks within time windows

Języki publikacji

Abstrakty

W artykule rozważono rozrzedzone systemy niepodzielnych zadań 1- i 2-procesorowych o jednostkowych czasach wykonywania. Przedstawiono wielomianowe algorytmy wykorzystujące programowanie dynamiczne, pozwalające na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano, posługując się jego modelem grafowym - w zakresie naszego zainteresowania leżą jedynie takie instancje problemów szeregowania, których modelami są grafy o ograniczonej liczbie cyklomatycznej. Istotnym elementem opracowanych procedur są algorytmy rozwiązujące pewne zagadnienia związane z wyszukiwaniem skojarzeń w grafach.

In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.

Słowa kluczowe

algorytm wielomianowy kolorowanie grafów NP-zupełność okna czasowe szeregowanie zadań zadania wieloprocesorowe

polynomial algorithm graph coloring time windows task scheduling multiprocessor tasks NP-completeness

Wydawca

Wydawnictwa AGH

Czasopismo

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

Rocznik

2005

Tom

T. 9, z. 1-2

Strony

85--94

Opis fizyczny

Bibliogr. 10 poz., rys.

Twórcy

autor

Giaro K.

Politechnika Gdańska, Wydział ETI, Katedra Algorytmów i Modelowania Systemów

autor

Kubale M.

Politechnika Gdańska, Wydział ETI, Katedra Algorytmów i Modelowania Systemów

Bibliografia

[ 1 ] Coffman E. Jr., Garey M., Johnson D., L aPaugh A.: Scheduling file transfers. SIAM J. Computing, 14, (1985), 744–780
[ 2 ] Giaro K., Kubale M.: Edgechromatic sum of trees and bounded cyclicity graphs. Inf. Process. Lett., 75, (2000), 65–69
[ 3 ] Giaro K., Kubale M., Piwakowski K.: Complexity results on open shop scheduling to minimize total cost of operations. Inter. J. Comp. Sys. Sign, v ol. 3, (2002), 84–91
[ 4 ] Isobe S., Zhou X ., Nishizeki T.: Cost total colorings of trees. IEICE Trans. INF. & SYST., v ol. E–87, (2004), 337–342
[ 5 ] Kao M., L am T., Sung W., Ting H .: Allcavity maximum matchings. Proc. ISAAC’97, L NCS, 1350, (1997), 364–373
[ 6 ] Krawczyk H ., Kubale M.: An approximation algorithm for diagnostic test scheduling in multi-computer systems. IEEE Trans. Comput., C–34, (1985), 869–872
[ 7 ] Marx D.: The complexity of tree multicolorings. Proc. MFCS’02, L NCS, 2420, (2002), 532–542
[ 8 ] Marx D.: List edge muticoloring in graphs with few cycles. Inf. Proc. L ett., 89, (2004), 85–90
[ 9 ] Micali S., Vazirani V.: An O(mn 1/2 ) algorithm for finding maximum matching in general graphs. Proc. 21 st Ann. IEEE Symp. on Foundations of Computer Science, (1980), 17–27
[ 10 ] Zhou X ., Nishizeki T.: Algorithms for the cost edge–coloring of trees. L NCS, 2108, (2001), 288– 297

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-AGH1-0004-0089