Wyniki wyszukiwania - BazTech

Ograniczanie wyników

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

1 2003

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: grafy permutacyjne

Sortuj według:

Ogranicz wyniki do:

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

Furmańczyk H., Kubale M.

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

2003

T. 7, z. 1-2

97-104

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.

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.