Analiza probabilistyczna wybranych sekwencyjnych algorytmów pakowania

• Autorzy: Horzelski W.

Warianty tytułu

EN

Probabilistic analysis of some sequential algorithms for binpacking problem

• Języki publikacji: PL

Abstrakty

PL

Streszczenie – Zadanie pakowania w klasycznym ujęciu polega na rozmieszczeniu listy ładunków L={a1,a2,…,an} o rozmiarach nieprzekraczających 1 w minimalnej ilości pojemników o rozmiarze jednostkowym, wymaga się przy tym, aby żaden z pojemników nie był przeładowany. Wśród metod rozwiązania takiego zadania jest też klasa algorytmów sekwencyjnych. Od algorytmu sekwencyjnego wymaga się dodatkowo aby zadania umieszczane w pojemniku tworzyły sekwencję: Dla każdego i należy do Jn for all j,k,l należy do Di j należy do A(Li) (s)iloczyn logiczny l należy do A(Li) (s) iloczyn logiczny j mniejsze niż k mniejsze niż l implikacja k należy do A(Li)(s), dla s element of J IA(Li)I W niniejszej pracy przedstawiono przykład algorytmu sekwencyjnego S1k oraz przeprowadzono pełną analizę jego zachowania. Dowiedziono twierdzenia określającego wartość współczynnika sprawności algorytmu (RS1kwiększe lub równe 0.5) dla najgorszego przypadku. Analiza probabilistyczna przeprowadzona została dla nieskończonego ciągu niezależnych zmiennych losowych o jednakowym rozkładzie L={E1,E2,......}. W pracy pokazano ograniczenie dla asymptotycznego współczynnika nadwyżki algorytmu S1k (R nieskończoność S1k,U(0,1) większe niż 0.7288).

EN

The bin-packing problem in the classical approach is to arrange the list of tasks L={a1,a2,…,an} of a size not exceeding 1 in the minimum number of bins of size 1, however, that none of the bins was overloaded. Among the ways to do such a task is a class of sequential algorithms. From sequential algorithm is required in addition to pack the tasks in such a way that tasks placed in each container (bin) consisted of a sequence: For all i element of Jn for all j,k,l element of Di j element of A(Li) (s)logical and l element of A(Li) (s) logical and j less than k less than l implication k element of A(Li)(s), dla s element of J IA(Li)I In this paper is an example of sequential algorithm called S1k and carried out a full analysis of its behavior. It demonstrate the value of lower bound for efficiency factor of the algorithm (R S1k greater-than or equal to 0.5). Probability analysis was carried out for the infinite sequence of independent random variables of equal distribution L={E1,E2,......}. This paper also show a bound of asymptotic waste ratio of S1k (R infinity S1k,U(0,1) greater than 0.7288).

Słowa kluczowe

PL

algorytm sekwencyjny pakowania; analiza probabilistyczna; zmienne losowe

• Wydawca: Wyższa Szkoła Informatyki i Umiejętności
• Czasopismo: Zeszyty Naukowe Wyższej Szkoły Informatyki
• Rocznik: 2008
• Tom: Vol. 7, Nr 1
• Strony: 39--48
• Opis fizyczny: Bibliogr. 4 poz., rys.

Twórcy

autor

Horzelski W.

• Uniwersytet Łódzki, Katedra Informatyki Stosowanej, Wyższa Szkoła Informatyki w Łodzi

Bibliografia

• [1] Lee C., Lee D.: A simple packing algorithm, Journal of the ACM 32, 1985, 562-575
• [2] Hoffman E.G., Leuker G.S.: Probabilistic Analysis of Packing and Partitioning Algorithms, John Wiley &Sons, New York 1991
• [3] Horzelski W.: Algorytmy sekwencyjne dla zadania pakowania, Rozprawa doktorska obroniona na Wydziale Matematyki UŁ
• [4] Cirik J., Frenk J., Galambos G. i Rinoy Kan A.: Probabilistic Analysis of Algorithms for Bin Packing Problems, Journal of Algorithms 12 (1991), 189-203