×

Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution. (English. Russian original) Zbl 1233.90242

Autom. Remote Control 72, No. 1, 141-159 (2011); translation from Avtom. Mekh. 2011, No. 1, 154-173 (2011).
Summary: It is considered the one-dimensional bin packing problem under the conditions for heterogeneity of the items put into bins and contiguity of choosing identical items for the next bin. The branch-and-bound method using the “next fit” principle and the “linear programming” method are proposed to solve it. The problem and its solution may be used to construct an improved lower bound in the problem of two-dimensional packing.

MSC:

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mukhacheva, E.A., Mukhacheva, A.S., and Chiglintsev, A.V., Block-structure Genetic Algorithm in the Problems of Two-dimensional Packing, Inf. Tekhnol., 1999, no. 11, pp. 13–18.
[2] Martello, S., Monachi, M., and Vigo, D., An Exact Approach to the Strip-Packing Problem, INFORMS J. Comput., 2003, no. 15(3), pp. 310–319. · Zbl 1238.90116
[3] Mukhacheva, E.A. and Mukhacheva, A.S., The Rectangular Packing Problem: Local Optimum Search Methods Based on Block Structures, Autom. Remote Control, 2004, no. 2, pp. 248–257. · Zbl 1066.90110
[4] Kartak, V.M., Mesyagutov, M.A., Mukhacheva, E.A., and Filippova, A.S., Local Search of Orthogonal Packings Using the Lower Bounds, Autom. Remote Control, 2009, no. 6, pp. 1054–1066. · Zbl 1181.93011
[5] Zhitnikov, V.P. and Filippova, A.S., Problem of Orthogonal Packing in Half-infinite Strip: Search in the Neighborhood of the Local Lower Bound, Inf. Tekhnol., 2007, no. 5, pp. 55–62.
[6] Hartmann, S., Project Scheduling under Limited Resources, Berlin: Springer, 2000.
[7] Garey, M.L. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco: Freeman, 1979. Translated under the title Vychislitel’nye machiny i trudnoreshaemye zadachi, Moscow: Mir, 1982.
[8] Martello, S. and Toth, P., Knapsack Problems: Algorithms and Computer Implementations, Chichester: Wiley, 1990. · Zbl 0708.68002
[9] Belov, G. and Scheithauer, G., A Cutting Plane Algorithm for the One-dimensional Cutting Stock Problem with Multiple Stock Lengths, Eur. Oper. Res., 2002, no. 14(2), pp. 274–294. · Zbl 1081.90590
[10] Hopper, E. and Turton, B., A Review of the Application of Metaheuristic Algorithms to 2D Regular and Irregular Strip Packing Problems, Artific. Intelligent., 2001, no. 16, pp. 257–300. · Zbl 1032.68721
[11] Belov, G., Scheithauer, G., and Mukhacheva, E.A., One-dimensional Heuristics Adapted for Twodimensional Rectangular Strip Packing, J. Oper. Res. Soc., 2008, no. 59, pp. 823–832. · Zbl 1153.90444
[12] Mukhacheva, E.A. and Nazarov, D.A., Design of Rectangular Packings: Block Structure-based Reconstruction Algorithm, Autom. Remote Control, 2008, no. 2, pp. 262–277. · Zbl 1156.90433
[13] Booth, K. and Lueker, G., Testing for the Consecutive Ones Property, Interval Graphs, and Planarity Using PQ-Tree Algorithms, J. Computat. Sys. Sci., 1976, no. 13, pp. 335–379. · Zbl 0367.68034
[14] Bortfeld, A., A Genetic Algorithm for the Two-dimensional Strip Packing Problem with Rectangular Prices, Eur. J. Oper. Res., 2006, no. 172, pp. 814–837.
[15] Berkey, J. and Wang, P., Two Dimensional Finite Bin Packing Algorithms, J. Oper. Res. Soc., 1987, no. 38, pp. 423–429. · Zbl 0611.90079
[16] Martello, S. and Vigo, D., Exact Solution of the Two-dimensional Finite Bin Packing Problem, Manage. Sci., 1998, no. 44, pp. 388–399. · Zbl 0989.90114
[17] Kartak, V., Refreshed Lower Bound for the Problem of Packing Rectangulars in Half-infinite Strip, Vest. UGATU, Ser. Upravlen. Vychislit. Tekhn. Informat., 2008, no. 10, 2(27), pp. 154–159.
[18] Baldacci, R. and Boschetti, M., A Cutting-plane Approach for the Two-dimensional Orthogonal Nonguillotine Cutting Problem, Eur. J. Oper. Res., 2007, no. 183(3), pp. 1136–1149. · Zbl 1138.90433
[19] Fekete, S. and Schepers, J., A General Framework for Bounds for Higher-dimensional Orthogonal Packing Problems, Math. Met. Oper. Res., 2004, no. 60, pp. 311–329. · Zbl 1076.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.