Analiza współczynnika straty algorytmów pakowania first fit oraz best fit przy ładunkach o rozkładzie Gaussa

• Autorzy: Horzelski W. , Doliwa D. , Frydrych M.

Warianty tytułu

EN

Analysis of the loss rate of first fit and best fit packing algorithms by charges with Gauss distribution

• Języki publikacji: PL

Abstrakty

PL

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. Jest to zadanie z klasy problemów NP-trudnych. Do klasycznych algorytmów dla takiego problemu on-line należą metody First Fit oraz Best Fit. W pracy przedstawiono wyniki badań zachowania się współczynnika straty dla tych algorytmów przy założeniu, iż ładunki mają rozkład normalny na przedziale (0,1].

EN

The task of packing in the classic take consists in laying the list of L= cargoes out {and 1, and 2, …, an} about not exceeding sizes 1 in the minimal number of containers about the individual size, they demand in addition that none of containers is overloaded. There is this assignment on the class of problems NP-trudnych. For such a problem on-line First Fit methods and Best Fit belong to classic algorithms.

Słowa kluczowe

PL

algorytmy pakowania; współczynnik straty; metoda First Fit; Best Fit; ładunek o rozkładzie Gaussa

• Wydawca: Wyższa Szkoła Informatyki i Umiejętności
• Czasopismo: Zeszyty Naukowe Wyższej Szkoły Informatyki
• Rocznik: 2010
• Tom: Vol. 9, Nr 2
• Strony: 92--101
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Horzelski W.

autor

Doliwa D.

autor

Frydrych M.

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

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] Chan, Wun-Tat; Lam, Tak-Wah; Wong, Prudence W. H. Dynamic bin packing of unit fractions items. Automata, languages and programming, 614--626
• [4] Karg, Ch., Köbler J., Schuler R., The complexity of generating test instances. STACS 97 (Lübeck), 375--386, Lecture Notes in Comput. Sci., 1200, Springer, Berlin, 1997.
• [5] Knuth D. E., The Art of Computer Programming – Seminumerical Algorithms, Addison-Wesley 1997, 1998
• [6] Kenyon C., Mitzenmacher, Michael Linear waste of best fit bin packing on skewed distributions. Probabilistic methods in combinatorial optimization. Random Structures Algorithms 20 (2002), no. 3,441--464. Analysis of Algorithms for Bin Packing Problems, Journal of Algorithms 12 (1991), 189-203