Selected problems and methods for the probabilistic analysis of sequencing tasks

• Autorzy: Gawiejnowicz Stanisław

Identyfikatory

DOI

10.14708/ma.v24i38.1837

Warianty tytułu

PL

Wybrane problemy i metody probabilistycznej analizy algorytmów szeregowania zadań

• Języki publikacji: EN

Abstrakty

PL

W artykule przedstawiono problem szeregowania zadań na równoległych procesorach oraz wybrane metody jego probabilistycznej analizy. Umieszczone w tekście przykłady dotyczą algorytmów LS i LPT badanych w oparciu o kryterium Cmax.

Słowa kluczowe

EN

scheduling theory; deterministic

PL

szeregowanie zadań; analiza probabilistyczna

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Matematyka Stosowana : matematyka dla społeczeństwa
• Rocznik: 1995
• Tom: Nr 38
• Strony: 101--112
• Opis fizyczny: Bibliogr. 11 poz., tab.

Twórcy

autor

Gawiejnowicz Stanisław

• Wydział Matematyki i Informatyki Uniwersytetu im. Adama Mickiewicza, ul. Matejki 48/49, 60-769 Poznań

Bibliografia

• [1] J. Błażewicz, Złożoność obliczeniowa problemów kombinatorycznych, WNT 1988.
• [2] E. G. Coffman jr., G. W. Fredericson, G. S. Leuker, A Note of Expected Make spans for Largest-First Sequence of Independent Tasks on Two Processors, Math. Oper. Res., 9(1984), 260-266.
• [3] E. G. Coffman jr., D. S. Johnson, P. W. Shor, G. S. Leuker, Probabilistic Analysis of Packing and Related Partitioning Problems, [w:] Probability and Algorithms, National Academy Press 1992.
• [4] E. G. Coffman jr., G. S. Leuker, A. H. G. Rinnooy Kan, Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics, Man. Sci., 34(1988), 266-290.
• [5] H. A. David, Poriadkowyje statistiki, Nauka 1979.
• [6] W. Feller, Wstęp do rachunku prawdopodobieństwa, tom 2, PWN 1978.
• [7] J. B. Frenk, A. H. G. Rinnooy Kan, The Asymptotic Optimality of the LPT Rule, Math. Oper. Res., 12(1987), 241-254.
• [8] R. L. Graham, Bounds for Certain Multiprocessing Anomalies, Bell System Tech. J., 45(1966), 1563-1584.
• [9] R. L. Graham, Bounds on Multiprocessing Timing Anomalies, SIAM J. Appl. Math., 17(1969), 263-269.
• [10] R. Loulou, Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling, Math. Oper. Res., 9(1984), 142-150.
• [11] Teoria szeregowania zadań [pod red. E. G. Coffmanajra], WNT 1980.