Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Probabilistic analysis of some sequential algorithms for binpacking problem
Języki publikacji
Abstrakty
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).
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
Czasopismo
Rocznik
Tom
Strony
39--48
Opis fizyczny
Bibliogr. 4 poz., rys.
Twórcy
autor
- 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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUJ5-0050-0091