Szeregowanie zadań sprzężonych metodą kolorowania grafów

• Autorzy: Furmańczyk H. , Kubale M.

Warianty tytułu

EN

Scheduling of coupled tasks by means of graph coloring

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważyliśmy problem szeregowania zadań sprzężonych na pojedynczym procesorze. Zadanie nazywamy sprzężonym (coupled task), jeżeli składa się z dwóch operacji oraz przerwy pomiędzy nimi, czyli druga z operacji może być wykonana dopiero po ściśle określonym czasie od zakończenia wykonywania operacji pierwszej. Pomiędzy zadaniami określona jest relacja kolejności ich wykonywania. Mamy dwa rodzaje ograniczeń kolejnościowych - silne i słabe. W pracy tej rozważyliśmy model, w którym czas wykonywania każdej operacji jest ten sam, równy 1, oraz długość przerwy jest stała dla wszystkich zadań. Ograniczenia kolejnościowe przyjęliśmy jako silne, a kryterium minimalizacyjnym jest łączny czas wykonywania zadań. Z takim zagadnieniem spotykamy się w systemach sterowania urządzeniami radarowymi, gdzie pierwsza operacja odpowiada wysłaniu sygnału, natomiast druga odebraniu jego echa. W przypadku ogólnym problem szeregowania zadań sprzężonych jest NP-trudny. Rozważyliśmy przypadki, gdy ograniczenia kolejnościowe definiują częściowy porządek na zadaniach oraz odpowiadający graf ma postać grafu permutacyjnego, kografu, grafu dwudzielnego lub drzewa, czyli uogólniając - grafu porównywalnego. W niektórych przypadkach rozważany problem można rozwiązać w czasie wielomianowym. Odpowiednie uszeregowanie uzyskaliśmy wykorzystując modele kolorowania grafów - ograniczonego i sprawiedliwego.

EN

In this paper we have considered a problem of coupled task scheduling on one processor. A task is called coupled if it contains two operations and a gap between them, so that the second operation has to be processed some time after a completion of the first one. There are defined precedence constraints between processing tasks. We have got two kinds of precedence constraints: strict and weak. In this work we have considered the model where tasks are identical with processing time of operations equal to 1 and the length of the gap being constant and the same for all tasks. The precedence constraints are strict and the optimization criterion is to minimize the schedule length. This problem often appears in radar-like devices, where the first operation is the transmission of a pulse and the second is the reception of its echo. In general, the problem of coupled task scheduling is NP-hard. We have considered cases where precedence constraints define partial order on task set and the associated graph is a permutation graph, cograph, bipartite graph or tree, so generally a comparability graph. In some cases our problem is shown to be solvable in polynomial time. We obtain schedules of coupled tasks using appropriate models of graph coloring - bounded and equitable.

Słowa kluczowe

PL

grafy; grafy permutacyjne; szeregowanie zadań sprężonych

EN

graph; permutation graph; scheduling of coupled tasks

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 97--104
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Furmańczyk H.

• Instytut Matematyki, Uniwersytet Gdański

autor

Kubale M.

• Wydział FTI, Politechnika Gdańska

Bibliografia

• [1] Błażewicz J., Ecker K.., Kis T., Tanaś M.: Scheduling coupled tasks on a single processor. Zeszyty Naukowe Politechniki Śląskiej, Seria: Automatyka 134, 2002, 53-66
• [2] Bodleander H.L., Jansen K.: Restrictions of graph partition problems. Theoretical Computer Science, 148, 1995,93-109
• [3] Comeil D.G., Perl Y., Stewart L.K.: A linear recognition algorithm for cographs. SIAM J. Comput., 4, 1985, 926-934
• [4] Hansen R, Hertz A., Kuplinsky J.: Bounded vertex colorings of graphs. Discrete Mathematics, 111, 1993, 305-312
• [5] Jansen K.: The mutual exclusion scheduling problem for permutation and comparability graphs. STACS 98, Lecture Notes in Comput. Sci., 1373, 1998, 287-297
• [6] Jarvis M., Zhou B.: Bounded vertex coloring of trees. Discrete Mathematics, 232, 2001, 145-151
• [7] Johnson D.S.: The NP-completeness column: an ongoing guide. Journal of Algorithms, 6, 1985, 434-451
• [8] Lih Ko-Wei: The equitable coloring of graphs, [in:] Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 3, 1998, 543-566
• [9] Orman A.J., Shahani A.K., Moore A.R.: Modelling for the control of a complex radar system. Computers Ops. Res., 25, 1998, 239-249
• [10] Seinsche D.: On a property of the class of n-colorable graphs. J. Combin. Theory, Ser. B 16, 1974, 191-193
• [11] Shapiro R.D.: Scheduling coupled tasks. Naval Res. Logist. Quart., 27, 1980, 477-481
• [12] Milojevic D.J., Popovic B.M.: Improved algorithm for the interleaving of radar pulses. IEE Proceedings F, 139, 1992, 98-104