Programowanie dynamiczne w rozwią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.

• Politechnika Gdańska, Gdańsk

autor

Kubale M.

• Politechnika Gdańska, Gdańsk

Bibliografia

• 1. Giaro K., Kubale M.: Edge-chromatic sum of trees and bounded cyclicity graphs. Inf. Process. Lett. 75 (2000), 65 - 69.
• 2. Giaro K.: Szeregowanie zadań w acyklicznym systemie otwartym. Zesz. Nauk. AGH, Ser. Autom. 5 (2001), 213-220.
• 3. Giaro K., Kubale M., Małafiejski M., Piwakowski K.: Dedicated scheduling of biprocessor tasks to minimize mean flow time. LNCS (to appear).
• 4. Gonzalez T., Sahni S.: Open shop scheduling to minimize finish time. J. Assoc. Comput Mach. 23 (1976), 665-679.
• 5. Kao M., Lam T. Sung W.: Ting H., All-cavity maximum matchings, in: Proc. ISAAC'97, LNCS 1350 (1997), 364-373.
• 6. Krawczyk H., Kubale M.: An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comput. C-34 (1985), 869-872.
• 7. Micali S., Vazirani V.: An O(mn^1/2) algorithm for finding maximum matching in general graphs. Proc. 21st Ann. IEEE Symp. on Found, of Comput. Sci. (1980), 17-27
• 8. Mitchem J., Morriss P.: On the cost-chromatic number o f graphs. Disc. Math. 171 (1997), 201-211.
• 9. Mitchem J., Morriss P., Schmeichel E.: On the cost chromatic number of outerplanar, planar and line graphs. Discussiones Mathematicae - Graph Theory 17 (1997) 1-13.
• 10. Zhou X., Nishizeki T.: Algorithm for the cost edge-coloring of trees. LNCS 2108 (2001), 288-297.