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: wielomianowe algorytmy szeregujące

Sortuj według:

Ogranicz wyniki do:

Programowanie dynamiczne w rozw3iązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze

Giaro K., Kubale M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2002

z. 134

173-184

Rozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop, flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano posługując się jego modelem grafowym - w zakresie naszego zainteresowania leżą jedynie takie instancje problemów szeregowania, których modelami są grafy acykliczne.

We consider systems with nonpreemptable 2-processor tasks of unit execution times as well as systems of dedicated processors with zero-unit execution times. We are interested in systems whose scheduling graphs are acyclic. For such graphs we give a family of polynomial algorithms based on dynamic programming which yield optimal solutions with respect to a broad family of criterion functions.