×

Packing problems. (English) Zbl 0825.90355


MSC:

90B06 Transportation, logistics and supply chain management
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
90C39 Dynamic programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adamowicz, M.; Albano, A., A two-stage solution of the cutting-stock problem, Information Processing, 71, 1086-1091 (1972)
[2] Adamowicz, M.; Albano, A., A solution of the rectangular cutting-stock, IEEE Transactions on Systems, Man and Cybernetics, 6/4, 302-310 (1976) · Zbl 0322.90018
[3] Adamowicz, M.; Albano, A., Nesting two-dimensional shapes in rectangular modules, Computer Aided Design, 8, 27-33 (1976)
[4] Albano, A.; Orsini, R., A heuristic solution of the rectangular cutting stock problem, The Computer Journal, 23, 338-343 (1978)
[5] Albano, A.; Sapuppo, G., Optimal allocation of two-dimensional irregular shapes using heuristic search methods, IEEE Transactions on Systems, Man and Cybernetics, 10/5, 242-248 (1980)
[6] Art, R. C., An approach to the two dimensional, irregular cutting stock problem, IBM Cambridge Centre Report, 36.Y08 (1966)
[7] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packings in two dimensions, SIAM Journal on Computing, 9, 846-855 (1980) · Zbl 0447.68080
[8] Baker, B. S.; Coffman, E. G., A tight asymptotic bound for next-fit-decreasing bin-packing, SIAM Journal on Algebraic and Discrete Methods, 2, 147-152 (1981) · Zbl 0496.68049
[9] Baker, B. S.; Calderbank, E. G.; Coffman, J. R.; Lagarias, J. C., Approximation algorithms for maximizing the number of squares packed into a rectangle, SIAM Journal on Algebraic and Discrete Methods, 4, 383-397 (1983) · Zbl 0558.05002
[10] Baker, B. S.; Schwarz, J. S., Shelf algorithms for two-dimensional packing problems, SIAM Journal on Computing, 12, 508-525 (1983) · Zbl 0521.68084
[11] Barnes, F. W., Packing the maximum number of \(m\) × \(n\) tiles in a large \(p\) × \(q\) rectangle, Discrete Mathematics, 26, 93-100 (1979) · Zbl 0397.05015
[12] Barnett, S.; Kynch, G. J., Exact solution of a simple cutting problem, Operations Research, 15, 1051-1056 (1967)
[13] Bartholdi, J.; Vate, J.; Zhang, J., Expected performance of the shelf heuristic for 2P packing, Operations Research Letters, 8, 11-16 (1989) · Zbl 0673.90072
[14] Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, 33, 49-64 (1985) · Zbl 0569.90038
[15] Beasley, J. E., Bounds for two dimensional cutting, Journal of the Operational Research Society, 36, 71-74 (1985) · Zbl 0557.90046
[16] Beasley, J. E., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36, 297-306 (1985) · Zbl 0589.90040
[17] Bengtsson, B. E., Packing rectangular pieces - A heuristic approach, The Computer Journal, 25, 353-357 (1982)
[18] Biro, M.; Boros, E., Network flows and non-guillotine cutting patterns, European Journal of Operational Research, 16, 215-221 (1984) · Zbl 0542.05054
[19] Bischoff, E. E., Stability aspects of packing problems, (Presented at IFORS 90. Presented at IFORS 90, Athens (1990)), June · Zbl 1083.90033
[20] Bischoff, E. E.; Dowsland, W. B., An application of the micro to product design and distribution, Journal of the Operational Research Society, 33, 271-281 (1982)
[21] Bischoff, E. E.; Marriott, M. D., A comparative evaluation of heuristics for container loading, European Journal of Operational Research, 44, 267-276 (1990) · Zbl 0684.90083
[22] Böhme, D.; Graham, A., Practical experiences with semiautomatic, and automatic partnesting methods, (Kuo, C., Computer Applications in the Automation of Shipyard Operation and design (1979), III North-Holland: III North-Holland Amsterdam), 213-220
[23] Brooks, R. L.; Smith, C. A.B.; Stone, A. H.; Tutte, W. T., The dissection of rectangles into squares, Duke Mathematical Journal, 7, 312-340 (1940) · Zbl 0024.16501
[24] Brown, D. J., An improved BL lower bound, Information Processing Letters, 11/1, 37-39 (1979) · Zbl 0444.68062
[25] Carpenter, H.; Dowsland, W. B., Practical considerations of the pallet loading problem, Journal of the Operational Research Society, 36, 489-497 (1985) · Zbl 0566.90052
[26] Christofides, N., Optimal cutting of two-dimensional rectangular plates, (CAD74 Proceedings (1974)), 1-10
[27] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations Research, 25, 31-44 (1977) · Zbl 0369.90059
[28] Christofides, N.; Mingozzi, A.; Toth, P., Loading problems, (Christofides, N., Combinatorial Optimisation (1979), Wiley: Wiley New York), 339-369
[29] Chung, F. R.H.; Garey, M. R.; Johnson, D. S., On packing two-dimensional bins, SIAM Journal on Algebraic and Discrete Methods, 3, 66-76 (1982) · Zbl 0495.05016
[30] Cochard, D. D.; Yost, K. A., Improving utilisation of air force cargo aircraft, Interfaces, 15, 53-68 (1985)
[31] Coffman, E. G.; Leung, J. Y.T.; Ting, D. W., Bin packing: maximizing the number of pieces packed, Acta Informatica, 9, 263-271 (1978) · Zbl 0421.68065
[32] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin packing - an updated survey, (Ausiello, G.; Lucertini, N.; Serafini, P., Algorithm Design for Computer Systems Design (1984), Springer: Springer Vienna), 49-106 · Zbl 0558.68062
[33] Coffman, E. G.; Gilbert, E. N., Dynamic, first fit packings in two or more dimensions, Information and Control, 61, 1-14 (1984) · Zbl 0591.68074
[34] Coffman, E. G.; Lueker, G. S.; Rinnooy Han, A. H.G., Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics, Management Science, 34, 266-290 (1988) · Zbl 0638.90054
[35] Coffman, E. G.; Lagarias, J. C., Algorithms for packing squares: a probabilistic analysis, SIAM Journal of Computing, 18, 166-185 (1989) · Zbl 0671.68014
[36] Coffman, E. G.; Shor, P. W., Average-case analysis of cutting and packing in two dimensions, European Journal of Operational Research, 44, 134-145 (1990) · Zbl 0689.90059
[37] Conway, J. H., Mrs. Perkins’s quilt, (Proceedings of the Cambridge Philosophical Society, 60 (1964)), 363-368 · Zbl 0134.27404
[38] Dagli, C. H., Knowledge-based systems for cutting stock problems, Journal of Operational Research Society, 44, 160-166 (1990) · Zbl 0684.90075
[39] Daniels, J.; Ghandforoush, P., An improved algorithm for the non-guillotine-constrained cutting-stock problem, Journal of the Operational Research Society, 41, 141-150 (1990) · Zbl 0693.90043
[40] De Cani, P., A note on the two-dimensional rectangular cutting-stock problem, Journal of the Operational Research Society, 29, 703-706 (1978) · Zbl 0384.90062
[41] De Cani, P., Packing Problems in Theory and Practice, (Ph.D. Thesis (1979), University of Birmingham: University of Birmingham U.K)
[42] De Wit, J. R.; Rinnooy Han, A. H.G.; Wijmenga, R. T., Nonorthogonal twodimensional cutting patterns, Management Science, 33, 341-345 (1987) · Zbl 0629.90044
[43] Dori, D.; Ben-Bassat, M., Efficient nesting on congruent convex figures, Communications of the ACM, 27, 228-235 (1984)
[44] Dowsland, K. A., The three-dimensional pallet chart: An analysis of the factors affecting the set of feasible layouts for a class two-dimensional packing problems, Journal of the Operational Research Society, 35, 895-905 (1984) · Zbl 0546.90052
[45] Dowsland, K. A., Determining an upper bound for a class of rectangular packing problems, Computers and Operations Research, 12, 201-205 (1985) · Zbl 0608.90080
[46] Dowsland, K. A., A graph-theoretic approach to the pallet loading problem, New Zealand Operational Research, 13, 77-86 (1985)
[47] Dowsland, K. A., An exact algorithm for the pallet loading problem, European Journal of Operational Research, 31, 78-85 (1987) · Zbl 0614.90084
[48] Dowsland, K. A., A combined database and algorithmic approach to the pallet loading problem, Journal of the Operational Research Society, 38, 341-345 (1987) · Zbl 0608.90077
[49] Dowsland, K. A., Efficient automated pallet loading, European Journal of Operational Research, 44, 232-238 (1990) · Zbl 0684.90078
[50] Dowsland, W. B., The computer as an aid to physical distribution management, European Journal of Operational Research, 15, 160-168 (1984) · Zbl 0527.90040
[51] Dowsland, W. B., Two and three dimensional packing problems and solution methods, New Zealand Operational Research, 13, 1-17 (1985) · Zbl 0588.90061
[52] Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 145-160 (1990) · Zbl 0684.90076
[53] Dyckhoff, H.; Kruse, H. J.; Abel, D.; Gal, T., Trim loss and related problems, OMEGA, 13, 59-72 (1985)
[54] Eilon, E., Optimising the shearing of steel bars, Journal of Mechanical Engineering Science, 2, 129-142 (1960)
[55] Eilon, S.; Christofides, N., The loading problem, Management Science, 17, 259-268 (1971) · Zbl 0208.45701
[56] Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Information Processing Letters, 12, 133-137 (1981) · Zbl 0469.68053
[57] Freeman, H.; Shapira, A., Determining the minimum-area encasing rectangle for an arbitratry closed curve, Communications of ACM, 18, 409-413 (1975) · Zbl 0308.68084
[58] Friesen, D. K.; Langston, M. A., Variable sized bin packing, SIAM Journal on Computing, 15, 222-231 (1986) · Zbl 0589.68036
[59] Gehring, H.; Menschner, H.; Meyer, M., A computer-based heuristic for packing pooled shipment containers, European Journal of Operational Research, 44, 277-289 (1990) · Zbl 0684.90084
[60] George, J. A.; Robinson, D. F., A heuristic for packing boxes into a container, Computers and Operations Research, 7, 147-156 (1980)
[61] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem (Part 1), Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[62] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem (Part 2), Operations Research, 11, 863-888 (1963) · Zbl 0124.36307
[63] Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94-120 (1965) · Zbl 0128.39601
[64] Gilmore, P. C.; Gomory, R. E., The theory and computation of knapsack functions, Operations Research, 14, 1045-1074 (1966) · Zbl 0173.21502
[65] Golan, I., Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM Journal on Computing, 10, 571-582 (1981) · Zbl 0461.68076
[66] Golden, B. L., Approaches to the cutting stock problem, AIIE Transactions, 8, 265-274 (1976)
[67] Golomb, S., Polyominoes (1966), Allen and Unwin: Allen and Unwin London · Zbl 0143.44202
[68] Gurel, O., Additional considerations on market layout problem via graph theory, (IBM Scientific Centre Report (1968), IBM: IBM New York), 320-2945
[69] Gurel, O., Market layout problem via graph theory: an attempt for optimal layout of irregular patterns, (IBM Scientific Centre Report 320-2921 (1968), IBM: IBM New York) · Zbl 0188.22903
[70] Gurel, O., Circular graph of market layout, (IBM Scientific Centre Report 320-2965 (1969), IBM: IBM New York) · Zbl 0188.22903
[71] Haessler, R. W., A note on computational modifications to the GilmoreGomory cutting stock algorithm, Operations Research, 10, 1001-1005 (1980) · Zbl 0441.90066
[72] Haessler, R. W.; Talbot, F. B., Load planning for shipments of low density products, European Journal of Operational Research, 44, 289-299 (1990) · Zbl 0684.90085
[73] Hahn, S. G., On the optimal cutting of defective sheets, Operations Research, 16, 1100-1114 (1968)
[74] Haims, M. J.; Freeman, H., A multistage solution of the templatelayout problem, IEEE Transactions on Systems Science and Cybernetics, 6/2, 145-151 (1970) · Zbl 0217.26904
[75] Han, C. P.; Knott, K.; Egbelu, P. J., A heuristic approach to the three-dimensional cargo-loading problem, International Journal of Production Research, 27, 757-774 (1989) · Zbl 0667.90075
[76] Herz, J. C., Recursive computational procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 16, 462-469 (1972) · Zbl 0265.90057
[77] Hinxman, A. I., The trim-loss and assortment problems: a survey, European Journal of Operational Research, 5, 8-18 (1980) · Zbl 0442.90072
[78] Hodgson, T. T., A combined approach to the pallet loading problem, IIE Transactions, 14, 175-182 (1982)
[79] Hodgson, T. T.; Hughes, D. S.; Martin-Vega, L. A., A note on a combined approach to the pallet loading problem, IIE Transactions, 15, 268-271 (1983)
[80] Hofri, M., Two-dimensional packing: Expected performance of simple level algorithms, Information and Control, 45, 1-17 (1980) · Zbl 0443.05033
[81] Ikeda, Y.; Kokan, K. K., The pansy, an advanced interactive parts nesting system, (Kuo, C., Computer Applications in the Automation of Shipyard Operation and Ship Design, III (1979), North Holland: North Holland Amsterdam), 313-321
[82] Isermann, H., Ein Planungssystem zur Optimierung der Palettenbeladung mit kongruenten rechteckigen Versandgebinden, OR Spectrum, 9, 235-249 (1987)
[83] Israni, S.; Sanders, J. L., Performance testing of rectangular parts-nesting heuristics, International Journal of Production Research, 23, 437-456 (1985) · Zbl 0571.90029
[84] Kantorovich, L. V., Mathematical methods of organising and planning production, Management Science, 6, 366-422 (1939, 1960)
[85] Kämpke, T., Simulated annealing: use of a new tool in bin packing, Annals of Operations Research, 16, 327-332 (1988) · Zbl 0692.90086
[86] Lindgren, H., Geometric Dissections (1964), Van Nostrand Reinhold: Van Nostrand Reinhold New York
[87] Liu, N. C.; Chen, L. C., A new algorithm for container loading, (Compsac 81 - 5th International Computer Software and Applications Conference Proceedings (1981), IEEE: IEEE Chicago), 292-299
[88] Mannchen, K., Solution methods for two and three dimensional packing problems, (Dissertation (1989), Karlsruhe: Karlsruhe Germany)
[89] Martello, S.; Toth, P., Knapsack problems - algorithms and computer implementations (1990), Wiley: Wiley New York · Zbl 0708.68002
[90] Martin, R. R.; Stephenson, P. C., Putting objects into boxes, Computer Aided Design, 20, 506-514 (1988)
[91] Matson, J. O.; White, J. A., Operational research and material handling, European Journal of Operational Research, 11, 309-318 (1982)
[92] McRoberts, H., A search model for evaluating combinatorially explosive problems, Operations Research, 6, 1331-1349 (1971) · Zbl 0228.90021
[93] Metzger, R., Stock slitting, (Elementary Mathematical Programming (1958), Wiley: Wiley New York), Chapter 8
[94] Oliveira, J. F.; Ferreira, J. S., An improved version of Wang’s algorithm for two-dimensional cutting problems, European Journal of Operational Research, 44, 256-266 (1990) · Zbl 0684.90073
[95] Paull, A.; Walter, J., The trim problem: an application of linear programming to the manufacture of newsprint paper, (Proceedings of Annual Econometric Meeting. Proceedings of Annual Econometric Meeting, Montreal, Sept. 10th-13th (1954))
[96] Peleg, K., Computerised pallet stacking, Packaging Technology, September, 18-25 (1971)
[97] Peleg, K.; Peleg, E., Container dimensions for optimal utilization of storage and transportation space, Computer Aided Design, 8, 775-781 (1976)
[98] Puls, F. N.; Tanchoco, J. M.A., Robotic implementation of pallet loading patterns, International Journal of Production Research, 24, 635-645 (1986)
[99] Sculli, D.; Hui, C. F., Three dimensional stacking of containers, OMEGA, 16, 585-594 (1988)
[100] Short, P. J., Optimal batch execution on a multiprocessing computer - a 2D packing problem, (M.Sc. Thesis (1973), University of London)
[101] Smith, A.; De Cani, P., An algorithm to optimize the layout of boxes in pallets, Journal of the Operational Research Society, 31, 573-578 (1980)
[102] Sperling, B., Nesting is more than a layout problem, (Kuo, C., Computer Applications in the Automation of Shipyard Operation and Ship Design, III (1979), North Holland: North Holland Amsterdam), 287-294
[103] Steudel, H. J., Generating pallet loading patterns: a special case of the two-dimensional cutting stock problem, Management Science, 25, 997-1004 (1979) · Zbl 0465.90051
[104] Steudel, H. J., Generating pallet loading patterns with considerations of item stacking on end and side surfaces, Journal of Manufacturing Systems, 3, 135-143 (1984)
[105] Stone, D. C.; Moore, M. C., How to determine existence of acceptable pallet patterns, Package Development, September/October, 20-27 (1971)
[106] Stoyan, Y. G., Mathematical methods for geometry design, (Ellis, T.; Siemenkov, O., Advances in CAD/CAM (1983), North Holland: North Holland Amsterdam), 67-86, IFIP 83
[107] Sweeney, P. E.; Ridenour, E. L., Cutting and packing problems: A categorized, application-oriented research bibliography, (Working Paper 610 (1989), School of Business Administration, University of Michigan) · Zbl 0757.90055
[108] Tinarelli, G. U.; Addonizio, M., Un problema di caricamento di containers, (Proceedings AIRO (1978)), 217-231
[109] Tsai, R. D.; Malstrom, E. M.; Meeks, H. D., A two-dimensional palletizing procedure for warehouse loading operations, IIE Transactions, 20, 418-423 (1988)
[110] Van Delft, P.; Botermans, J., Creative Puzzles of the World (1978), Cassell: Cassell London
[111] Vasko, F. J., A computational improvement to Wang’s two-dimensional cutting stock algorithm, Computers in Industrial Engineering, 16, 109-115 (1989)
[112] Wang, P. Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 31, 573-586 (1983) · Zbl 0517.90093
[113] Wright, P. G., There may be a better pack for you, Australian Lithographer, 12, 33-34 (1973)
[114] Wright, P. G., A systems approach to packaging design, Australian Packaging, June, 27-33 (1973)
[115] Wright, P. G., Pallet loading configurations for optimum storage and shipping, Paperboard Packaging, December, 46-49 (1974)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.