Improved Data Structure for the Orthogonal Packing Problem

Vladislav A. Chekanin; Alexander V. Chekanin

doi:10.4028/www.scientific.net/AMR.945-949.3143

Paper Titles

Lean Manufacturing in Operations Management in Improving the Efficiency of Manufacturing Processes
p.3117

Logistics Network Optimization of Import Crude Oil in China Based on Genetic Algorithm
p.3126

Solving the Problem of General Job Shop Problem by Using Improved Cellular Genetic Algorithm
p.3130

An Effective Method for Capacity Analysis of Aircraft Digital Assembly System
p.3136

Improved Data Structure for the Orthogonal Packing Problem
p.3143

Research on Lean Information System of Coal Enterprises
p.3147

Analysis of Machining Workshop Manufacturing Based on Unit K Means Clustering
p.3152

Modeling in Mixed-Model Assembly Lines Based on Object-Oriented Petri Net
p.3156

Study on Green Supply Chain Management Model of Chinese Home Appliances Enterprises
p.3163

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 945-949Improved Data Structure for the Orthogonal Packing...

Improved Data Structure for the Orthogonal Packing Problem

Abstract:

In paper is considered the actual in industry and engineering orthogonal multidimensional packing problem. This problem is NP-hard in strong sense therefore an important role is played effectiveness of the used packing representation model. To increase the speed of placement of a given set of orthogonal objects into containers is offered a new data structure – multilevel linked data structure. The carried out computational experiments demonstrate high time efficiency of the proposed data structure compared to the ordered simple linked list.

You might also be interested in these eBooks

Advances in Manufacturing Science and Engineering V

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 945-949)

Pages:

3143-3146

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.945-949.3143

Citation:

Cite this paper

Online since:

June 2014

Authors:

Vladislav A. Chekanin*, Alexander V. Chekanin

Keywords:

Data Structure, Multilevel Linked Data Structure, Orthogonal Packing Problem, Packing Problem, Resources Allocation, Three-Dimensional Packing Problem, Waste Minimization

Export:

RIS, BibTeX

Price:

Permissions:

Request Permissions

* - Corresponding Author

References

[1] 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

[2] 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

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

Google Scholar

[4] 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

[5] 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

[6] 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

[7] 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

[8] S. Martello, D. Pisinger, D. Vigo: The three-dimensional bin packing problem. Operations Research. Vol. 48: 2 (2000), pp.256-267.

DOI: 10.1287/opre.48.2.256.12386

Google Scholar

[9] T.G. Crainic, G. Perboli, R. Tadei: Extreme point-based heuristics for three-dimensional bin packing. INFORMS, Journal on Computing. Vol. 20: 3 (2008), pp.368-384.

DOI: 10.1287/ijoc.1070.0250

Google Scholar

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

Google Scholar