Probabilistic analysis for stochastic Rectangle Packing Problem algorithm

• Autorzy: Kurpisz A.

Warianty tytułu

PL

Analiza probabilistyczna algorytmu dla stochastycznego problemu pakowania prostokątów

• Języki publikacji: EN

Abstrakty

EN

In this paper we consider a modified Rectangle Packing Problem where for each rectangle (module) its width and height come from uniform probability distribution between 0 and 1 - U(0,1). We provide a probabilistic analysis of a simple polynomial-time algorithm for Rectangle Packing Problem. At the end a comparison to the computer simulations is presented.

PL

W tej pracy rozważamy Problem Pakowania Bloków, który występuje w wielu gałęziach przemysłu, np. w projektowaniu układów scalonych, cięciu bloków kamiennych, przemyśle tekstylnym. Rozważamy zmodyfikowany problem, w którym wysokości i szerokości bloków są zadane jednostajnym, ciągłym rozkładem prawdopodobieństwa U(0,1). W tej pracy prezentujemy analizę probabilistyczną skuteczności algorytmu Prezentujemy również wyniki symulacji komputerowych i porównujmy je z wynikami teoretycznymi

Słowa kluczowe

EN

production engineering; optimization; Rectangle Packing Problem

PL

inżynieria produkcji; optymalizacja; Problem Pakowania Bloków; algorytm

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Interdisciplinary Journal of Engineering Sciences
• Rocznik: 2013
• Tom: Vol. 1, no. 1
• Strony: 24--27
• Opis fizyczny: Bibliogr. 3 poz., rys., tab.

Twórcy

autor

Kurpisz A.

• Institute of Mathematics and Computer Science, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław

Bibliografia

• [1] C. Blum, A. Roli Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35, (3), 2003, 268-308.
• [2] B. S. Baker, E. G. Coifman, R. L. Rivest Orthogonal packings in two dimensions. SIAM J. Comput., 9, (4), 1980, 846–855.
• [3] A. Kurpisz Simple Algorithms for Rectangle Packing Problem – from Theory to Experiments, Innovations in Management and Production Engineering, 2013, 207-214.