Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap

Ecker K., Tanaś M.

Foundations of Computing and Decision Sciences

2007

Vol. 32, No. 3

199-212

The coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has an exact even length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper containts a solution for the problem of coupled tasks scheduling with assumption that the precedence constraints graph has a form of chains and it presents an algorithm which can solve the problem with such assumption in time O(n log n).

Scheduling coupled tasks on a single processor

Błażewicz J., Ecker K., Kis T., Tanaś M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2002

z. 134

53-66

This paper considers a problem of coupled task scheduling on one processor, where all processing times are equal to 1, the gap has exact length h, precedence constraints are strict and the criterion is to minimize the schedule length. This problem is introduced e.g. in systems controlling radar operations. We show that the general problem is NP-hard. This paper also shows a fast approximation algorithm for chain precedence constraints.

W referacie zaprezentowano problem szeregowania zadań sprzężonych na jednym procesorze, z jednostkowymi czasami wykonywania operacji, stałą długością przerwy pomiędzy operacjami, gdzie celem jest minimalizacja długości uszeregowania. Problem ten często występuje w praktyce w systemach sterowania urządzeniami radarowymi. W referacie pokazujemy NP-trudność problemu w przypadku ogólnych ograniczeń kolejnościowych oraz szybki algorytm aproksymacyjny dla ograniczeń kolejnościowych typu "łańcuch".