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

• Autorzy: Giaro K. , Kubale M.

Warianty tytułu

EN

Dynamic programming to solve scheduling problems in systems with acyclic structure

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

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

szeregowanie zadań; programowanie dynamiczne; system o acyklicznej strukturze; wielomianowe algorytmy szeregujące

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

Twórcy

autor

Giaro K.

autor

Kubale M.

• Politechnika Gdańska, Gdańsk