Scheduling coupled tasks on a single processor

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

Warianty tytułu

PL

Szeregowanie zadań sprzężonych na jednym procesorze

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: EN

Abstrakty

EN

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.

PL

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

Słowa kluczowe

PL

szeregowanie zadań; zadania sprzężone

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 53--66
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Błażewicz J.

autor

Ecker K.

autor

Kis T.

autor

Tanaś M.

• Institute of Computing Science Poznań University of Technology, Poznań