Multilevel Linked Data Structure for the Multidimensional Orthogonal Packing Problem

Vladislav A. Chekanin; Alexander V. Chekanin

doi:10.4028/www.scientific.net/AMM.598.387

Paper Titles

An Improved Low-Offset and Low-Power Design of Comparator for Flash ADC
p.365

The Research of a Variable-Focus Ultrasonic Liquid Lens
p.371

Development of the Multimethod Genetic Algorithm for the Strip Packing Problem
p.377

Automatic Discovery Approach of Digital Image Topic
p.382

Multilevel Linked Data Structure for the Multidimensional Orthogonal Packing Problem
p.387

Fuzzy Classification Maximum Likelihood Clustering with T-Distributions
p.392

A Simplified Branch-and-Price Mechanism for a Three-Machine Dynamic PCB Assembly
p.398

Fast Calculation of Bayesian Unconditional Cramer-Rao Bounds in Case the State-Vector is Constant
p.404

The Coupling of RBF and FDM for Solving Higher Order Fractional Partial Differential Equations
p.409

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vol. 598Multilevel Linked Data Structure for the...

Multilevel Linked Data Structure for the Multidimensional Orthogonal Packing Problem

Abstract:

The actual NP-completed orthogonal bin packing problem is considered in the article. In practice a solution of a large number of different practical problems, including problems in logistics and scheduling comes down to the bin packing problem. A decision of an any packing problem is represented as a placement string which contains a sequence of objects selected to pack. The article proposes a new multilevel linked data structure that improves the effectiveness of decoding of the placement string and as a consequence, increases the speed of packing generation. The new data structure is applicable for all multidimensional orthogonal bin packing problems.

You might also be interested in these eBooks

Advanced Materials, Mechanics and Industrial Engineering

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volume 598)

Pages:

387-391

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.598.387

Citation:

Cite this paper

Online since:

July 2014

Authors:

Vladislav A. Chekanin*, Alexander V. Chekanin

Keywords:

Bin Packing Problem, Data Structure, Logistic, Orthogonal Packing, Packing, Packing Problem, Scheduling

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] M. Gary, D. Johnson: Computers Intractability: a Guide to the Theory of NP-completeness (W.H. Freeman, San Francisco 1979).

Google Scholar

[2] A. Lodi, S. Martello, M. Monaci: Two-dimensional packing problems: A survey. European journal of operational research. Vol. 141: 2 (2002), pp.241-252.

DOI: 10.1016/s0377-2217(02)00123-6

Google Scholar

[3] Y. Wu, W-K. Li, M. Goh, R. de Souza: Three dimensional bin packing problem with variable bin height. European journal of operational research. Vol. 202: 2 (2010), pp.347-355.

DOI: 10.1016/j.ejor.2009.05.040

Google Scholar

[4] G. Wascher, H. Haubner, H. Schumann: An improved typology of cutting and packing problems. European Journal of Operational Research. Vol. 183: 3 (2007), pp.1109-1130.

DOI: 10.1016/j.ejor.2005.12.047

Google Scholar

[5] A. Bortfeldt, G. Wascher: Constraints in container loading – A state-of-the-art review. European Journal of Operational Research. Vol. 229: 1 (2013), pp.1-20.

DOI: 10.1016/j.ejor.2012.12.006

Google Scholar

[6] A.V. Chekanin, V.A. Chekanin: Efficient algorithms for orthogonal packing problems. Computational Mathematics and Mathematical Physics. Vol. 53: 10 (2013), pp.1457-1465.

DOI: 10.1134/s0965542513100047

Google Scholar

[7] A.V. Chekanin, V.A. Chekanin: Improved packing representation model for the orthogonal packing problem. Applied Mechanics and Materials. Vol. 390 (2013), pp.591-595.

DOI: 10.4028/www.scientific.net/amm.390.591

Google Scholar

[8] Information on http: /people. brunel. ac. uk/~mastjjb/jeb/info. html.

Google Scholar

[9] S.P. Fekete, J. Schepers: New class of lower bounds for bin packing problems. Integer Programming and Computational Optimization (IPCO 98), Lecture Notes in Computer. Vol. 1412 (1998), pp.257-270.

DOI: 10.1007/3-540-69346-7_20

Google Scholar

[10] V.A. Chekanin, A.V. Chekanin: Optimization of the solution of the orthogonal packing problem. Applied informatics (Prikladnaya informatika). Vol. 4 (2012), pp.55-62, in Russian.

Google Scholar

[11] M.A. Weiss: Data Structures and Algorithm Analysis in C++ (Pearson Education 2014).

Google Scholar