×
Haessler, Robert W.; Sweeney, Paul E.

Cutting stock problems and solution procedures. (English) Zbl 0736.90062

Eur. J. Oper. Res. 54, No. 2, 141-150 (1991).
Summary: This paper discusses some of the basic formulation issues and solution procedures for solving one- and two-dimensional cutting stock problems. Linear programming, sequential heuristic and hybrid solution procedures are described. For two-dimensional cutting stock problems with rectangular shapes, we also propose an approach for solving large problems with limits on the number of times an ordered size may appear in a pattern.

Cited in 47 Documents

MSC:

90C27 Combinatorial optimization
90B30 Production models
90C05 Linear programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

one- and two-dimensional cutting stock; sequential heuristic; trim loss; pattern generation; two-dimensional knapsack
Cite Review PDF
Full Text: DOI Link

References:

[1] Beasley, J. E., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36, 297-306 (1985) · Zbl 0589.90040
[2] Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, 33, 49-64 (1985) · Zbl 0569.90038
[3] Beged Dov, A. G., Some computational aspects of the \(M\) paper mills and \(P\) printers paper trim problem, Journal of Business Administration, 1, 15-34 (1970)
[4] Christofides, N.; Whitlock, C., An algoritham for two-dimensional cutting problems, Operational Research, 2530-2544 (1977)
[5] Dyckhoff, H., A typology of cutting an packing problems, European Journal of Operational Research, 44, 145-159 (1990) · Zbl 0684.90076
[6] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 848-859 (1961) · Zbl 0096.35501
[7] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Part II, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307
[8] Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94-120 (1965) · Zbl 0128.39601
[9] Gilmore, P. C.; Gomory, R. E., The theory and computation of knapsack functions, Operations Research, 14, 1045-1074 (1966) · Zbl 0173.21502
[10] Hadjiconstantinou, E.; Christofides, N., An optimal algorithm for general, orthogonal, 2-D cutting problems, (Technical Report MS-91/2 (1991), Imperial College: Imperial College London) · Zbl 0959.90060
[11] Haessler, R. W., A heuristic programming solution to a nonlinear cutting stock problem, Management Science, 17, 793-802 (1971) · Zbl 0219.90021
[12] Haessler, R. W., A note on computational modifications to the Gilmore-Gomory cutting stock algorithm, Operations Research, 28, 1001-1005 (1980) · Zbl 0441.90066
[13] Haessler, R. W., A new generation of paper machine trim programs, TAPPI Journal, 71, 127-130 (1988), (August)
[14] Haessler, R. W.; Talbot, F. B., A 0-1 model for solving the corrugator trim problem, Management Science, 29, 200-209 (1983), (December)
[15] Kantorovich, L. V., Mathematical methods of organizing and planning production, Management Science, 6, 366-422 (1960), reprinted in · Zbl 0995.90532
[16] Pierce, J. F., Some Large Scale Production Problems in the Paper Industry (1964), Prentice-Hall: Prentice-Hall Englewood Cliffs, NY
[17] Rinnooy Kan, A. H.G.; De Wit, J. R.; Wijmenga, R. T., Nonorthogonal two-dimensional cutting patterns, Management Science, 33, 670-684 (1987) · Zbl 0629.90044
[18] Sweeney, P. E.; Paternoster, E. R., Cutting and packing problems: An updated literature review, (Working Paper No. 654 (1991), University of Michigan: University of Michigan School of Business)
[19] Sweeney, P. E.; Haessler, R. W., One-dimensional cutting stock decisions for rolls with multiple quality grades, European Journal of Operational Research, 44, 224-231 (1990) · Zbl 0684.90077
[20] Vasko, F. J., A computational improvement to Wang’s two-dimensional cutting stock algorithm, Computers and Industrial Engineering, 16, 109-115 (1989)
[21] Viswanathan, K. V.; Bagchi, A., An exact best-first search procedure for the constrained rectangular guillotine knapsack problem, (Proceedings of the American Association for Artificial Intelligence (1988)), 145-149
[22] Wang, P. Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 31, 573-586 (1983) · Zbl 0517.90093
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.