zbMATH — the first resource for mathematics

Practical adaptations of the Gilmore-Gomory approach to cutting stock problems. (English) Zbl 0642.90050
Summary: The delayed pattern generation approach to the solution of cutting stock problems was first proposed by P. C. Gilmore and R. E. Gomory [Oper. Res. 9, 849-859 (1961; Zbl 0096.355); ibid. 11, 863-888 (1963; Zbl 0124.363)]. The most significant barrier to its widespread acceptance in commercial applications is its inflexibility in dealing with objectives other than waste minimization. The adaptations of the basic Gilmore-Gomory approach presented in this article increase its flexibility. The adaptations relate to initial pattern generation, multiple solutions per knapsack problem, explicit valuation of undersupply and oversupply, and waste having a value. While some adaptations improve the basic approach, all adaptations lead to the ability to handle objectives more complex than solely waste minimization.

90B30 Production models
90C05 Linear programming
65K05 Numerical mathematical programming methods
90C90 Applications of mathematical programming
90C10 Integer programming
Full Text: DOI
[1] Adamowicz M, Albano A (1976) A solution of the rectangular cutting-stock problem. IEEE Trans Syst Man Cybern SMC-6:302–310 · Zbl 0322.90018
[2] Beasley JE (1985a) An exact two-dimensional non-guil-lotine cutting tree search procedure. Oper Res 33:49–64 · Zbl 0569.90038 · doi:10.1287/opre.33.1.49
[3] Beasley JE (1985b) Algorithms for unconstrained two-dimensional guillotine cutting. J Oper Res Soc 36:297–306 · Zbl 0589.90040
[4] Biro M, Biros E (1984) Network flows and non-guillotine cutting patterns. E J Oper Res 16:215–221 · Zbl 0542.05054 · doi:10.1016/0377-2217(84)90075-4
[5] Chambers ML, Dyson RG (1976) The cutting stock problem in the flat glass industry selection of stock sizes. Oper Res Q 27:949–957
[6] Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper Res 25:30–44 · Zbl 0369.90059 · doi:10.1287/opre.25.1.30
[7] De Cani P (1978) A note on the two-dimensional rectangular cutting stock problem. J Oper Res Soc 29:703–706 · Zbl 0384.90062
[8] Dyckhoff H (1981) A new linear programming approach to the cutting stock problem. Oper Res 29:1092–1104 · Zbl 0474.90059 · doi:10.1287/opre.29.6.1092
[9] Dyson RG, Gregory AS (1974) The cutting stock problem in the flat glass industry. Oper Res Q 25:41–53
[10] Farley AA (1981) The trim-loss problem in the canvas industry. Proceedings of the 5th Australian Society Operations Research National Conference, pp 191–206
[11] Farley AA (1983a) Trim-loss pattern rearrangement and its relevance to the flat-glass industry. E J Oper Res 14:386–392 · Zbl 0521.90056 · doi:10.1016/0377-2217(83)90238-2
[12] Farley AA (1983b) A note on modifying a two-dimensional trim-loss algorithm to deal with cutting restrictions. E J Oper Res 14:393–395 · Zbl 0521.90057 · doi:10.1016/0377-2217(83)90239-4
[13] Farley AA (1985) Algorithms for solving cutting stock problems. Ph.D. Thesis, Monash University Melbourne, Australia
[14] Farley AA, Richardson KV (1984) Fixed charge problems with identical fixed charges. E J Oper Res 18:245–249 · Zbl 0544.90078 · doi:10.1016/0377-2217(84)90190-5
[15] Gehring H, Gal T, Rödder W (1979) Produktions-und Lagerbestandsplanung mit einem mehrstufigen Produktionsmodell. Proc Oper Res 8:390–396
[16] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper Res 9:849–859 · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[17] Gilmore PC, Gomory RE (1963) A linear programming approach to the cutting-stock problem, Part II. Oper Res 11:863–888 · Zbl 0124.36307 · doi:10.1287/opre.11.6.863
[18] Gilmore PC, Gomory RE (1965) Multistage cutting stock problems of two and more dimensions. Oper Res 13:94–120 · Zbl 0128.39601 · doi:10.1287/opre.13.1.94
[19] Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper Res 14:1045–1074 · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045
[20] Haessler RW (1971) An heuristic programming solution to a non-linear cutting stock problem. Manage Sci 17:B793-B802 · Zbl 0219.90021 · doi:10.1287/mnsc.17.12.B793
[21] Haessler RW (1975) Controlling cutting pattern changes in one-dimensional trim problems. Oper Res 23:483–493 · Zbl 0301.90030 · doi:10.1287/opre.23.3.483
[22] Haessler RW (1978) A procedure for solving the 1.5-dimensional coil slitting problem. AIIE Trans 10:70–75
[23] Haessler RW (1979) Solving the two-stage cutting stock problem. OMEGA 7:145–151 · doi:10.1016/0305-0483(79)90102-6
[24] Haessler RW (1980) A note on computational modifications to the Gilmore-Gomory cutting stock algorithm. Oper Res 28:1001–1005 · Zbl 0441.90066 · doi:10.1287/opre.28.4.1001
[25] Haessler RW, Talbot FB (1983) A 0–1 model for solving the corrugator trim problem. Manag Sci 29:200–209 · doi:10.1287/mnsc.29.2.200
[26] Hahn SG (1968) On the optimal cutting of defective sheets. Oper Res 16:1100–1114 · doi:10.1287/opre.16.6.1100
[27] Haims MJ, Freeman H (1970) A multistage solution to the template layout problem. IEEE Trans Systems Sci Cybern SSC-6:145–151 · Zbl 0217.26904 · doi:10.1109/TSSC.1970.300290
[28] Heicken K, König W (1980) Integration eines heuristisch-optimierenden Verfahrens zur Lösung eines eindimensionalen Verschnittproblems in einem EDV-gestützten Produktionsplanungs- und -steuerungssystems. OR Spektrum 1:251–259 · doi:10.1007/BF01719502
[29] Herz J (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J Res Develop 16:462–469 · Zbl 0265.90057 · doi:10.1147/rd.165.0462
[30] Johnston RE (1986) Rounding algorithms for cutting stock problems. Asia, Pacific Oper Res J 3:166–171 · Zbl 0616.90044
[31] Litton CD (1977) A frequency approach to the onedimensional cutting problem for carpet rolls. Oper Res Q 28:927–938 · Zbl 0379.90058
[32] Madsen OBG (1979) Glass cutting in a small firm. Math Prog 17:85–90 · Zbl 0403.90055 · doi:10.1007/BF01588227
[33] Page E (1975) A note on a two-dimensional dynamic programming problem. Oper Res Q 26:321–324 · Zbl 0301.90048
[34] Smithin T, Harrison P (1982) The third dimension of two-dimensional cutting. OMEGA 10:81–87 · doi:10.1016/0305-0483(82)90088-3
[35] Wang PY (1983) Two algorithms for constrained two-dimensional cutting stock problems. Oper Res 31:573–586 · Zbl 0517.90093 · doi:10.1287/opre.31.3.573
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.