Analiza algorytmu sekwencyjnego dla zadania pakowania

• Autorzy: Horzelski W.
• Języki publikacji: PL

Abstrakty

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. In dual version we need to maximized number of bins, assuming that all of them must be fully loaded (1 or more). 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: [wzór]. 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 [wzór] and a bound of asymptotic waste ratio of ...[wzór]. Paper presents result of the algorithm with list of tasks uniformly distributed on the (0.1]. Shows that its computational complexity is O(n) and carried out a comparison with the results achieved by the algorithm DNF.

Słowa kluczowe

PL

zadanie pakowania; analiza prawdopodobieństwa

EN

bin packing; probabilistic analysis

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 1 (18)
• Strony: 29--39
• Opis fizyczny: Bibliogr. 9 poz., rys., tab.

Twórcy

autor

Horzelski W.

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

Bibliografia

• [1] C. Lee, D. Lee, A simple packing algorithm, Journal of the ACM 32, 1985, 562-575.
• [2] E.G. Hoffman, G.S. Leuker, Probabilistic Analysis of Packing and Partitioning Algorithms, John Wiley &Sons, New York 1991.
• [3] W. Horzelski, Analiza probabilistyczna wybranych sekwencyjnych algorytmów pakowania, Zeszyty Naukowe WSInf Vol 7. Nr 1. 2008. 39-49
• [4] J. Cirik, J. Frenk, G. Galambos i A. Rinoy Kan, Probabilistic Analysis of Algorithms for Dual Bin Packing Problems, Journal of Algorithms 12 (1991), 189-203.
• [5] Z. Degraeve, M. Peeters. Optimal integer solutions to industrial cutting-stock problems: Part 2. benchmark results. INFORMS Journal on Computing. 15:58–81. 2003.
• [6] J. Boyar. L. M. Favrholdt. K. S. Larsen, M. N. Nielsen. The competitive ratio for on-line dual bin packing with restricted input sequences. Nordic J. of Comp. 8:463–472. 2001.
• [7] L. Epstein, S. Seiden, R. van Stee. New bounds for variable sized and resource augmented online bin packing. In ICALP. LNCS 2380. p. 306–317. Springer. 2002.
• [8] D. Hong, J.C. Birget. Approximation of some NP-hard optimization problems by finite machines. in probability. Theor. Comp.Sci.. 259:323–339. 2001.
• [9] N. Menakerman, R. Rom. Average case analysis of bounded space bin packing algorithms. Technical Report CCIT 340. Technion EE. 2001.