Szeregowanie zadań w systemach silnie uwarunkowanych czasowo metodą cyklicznego obciążenia

• Autorzy: Nawrocki J. R. , Czajka A.

Warianty tytułu

EN

Periodic loading approach to scheduling hard real-time tasks

• Konferencja: XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych, Zakopane, 24-27.09.1998
• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawione są wyniki badań dotyczących zastosowania metody minimalizacji obciążeń cyklicznych do szeregowania zadań silnie uwarunkowanych czasowo o okresach tworzących postęp binarny. Pokazano, że problem taki jest silnie NP-trudny i w związku z tym algorytm o złożoności wielomianowej nie istnieje. W tej sytuacji zaproponowana została prosta heurystyka zachłanna, która - jak wynika z przeprowadzonych eksperymentów obliczeniowych - zachowuje się lepiej od innych tego typu znanych heurystyk. Zastosowana do szeregowania zadań w samolocie F-16 dała w bardzo krótkim czasie optymalne rozwiązanie.

EN

In the paper scheduling hard real-time by minimising periodic loading is studied. It is assumed that task periods belong to a binary geometrical progression. It is shown that such a problem is strongly NP-hard. Thus, a simple greedy heuristics is proposed, which - due some computational experiments - is pretty effective and better than other greedy heuristics for the periodic loading problem. Applied to scheduling tasks for F-16 the heuristics returned an optimal solution in a very short time.

Słowa kluczowe

PL

szeregowanie zadań; zadania uwarunkowane czasowo; problem NP-trudny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 1998
• Tom: z. 123
• Strony: 169--179
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Nawrocki J. R.

autor

Czajka A.

• Instytut Informatyki Politechniki Poznańskiej 60-965 Poznań, ul.Piotrowo 3a tel. [phone]