Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Zeszyty Naukowe. Automatyka / Politechnika Śląska

1 2002

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: zadania sprzężone

Sortuj według:

Ogranicz wyniki do:

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".