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.
Wydawca
Rocznik
Tom
Strony
85--94
Opis fizyczny
Bibliogr. 10 poz., rys.
Bibliografia
- [ 1 ] Coffman E. Jr., Garey M., Johnson D., L aPaugh A.: Scheduling file transfers. SIAM J. Computing, 14, (1985), 744780
- [ 2 ] Giaro K., Kubale M.: Edgechromatic sum of trees and bounded cyclicity graphs. Inf. Process. Lett., 75, (2000), 6569
- [ 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), 8491
- [ 4 ] Isobe S., Zhou X ., Nishizeki T.: Cost total colorings of trees. IEICE Trans. INF. & SYST., v ol. E87, (2004), 337342
- [ 5 ] Kao M., L am T., Sung W., Ting H .: Allcavity maximum matchings. Proc. ISAAC97, L NCS, 1350, (1997), 364373
- [ 6 ] Krawczyk H ., Kubale M.: An approximation algorithm for diagnostic test scheduling in multi-computer systems. IEEE Trans. Comput., C34, (1985), 869872
- [ 7 ] Marx D.: The complexity of tree multicolorings. Proc. MFCS02, L NCS, 2420, (2002), 532542
- [ 8 ] Marx D.: List edge muticoloring in graphs with few cycles. Inf. Proc. L ett., 89, (2004), 8590
- [ 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), 1727
- [ 10 ] Zhou X ., Nishizeki T.: Algorithms for the cost edgecoloring of trees. L NCS, 2108, (2001), 288 297
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH1-0004-0089