Cespe UnB

Editorial Assistants:
W. Abrahão
G. Oliveira
L. Salgueiro

Editorial Technical Support:
D. H. Diaz
M. A. Gomez
J. Barbosa

Editorial management and production:

95/105= 0.91


A pattern reduction procedure in a one-dimensional cutting stock problem by grouping items according to their demands

doi: 10.6062/jcis.2009.01.02.0019(Free PDF)


Goncalo Renildo Lima Cerqueira and Horacio Hideki Yanasse



Cutting stock problem, computational heuristic method, pattern reduction procedure, linear programming.


[1] CUI Y, ZHAO X, YANG Y & YU P. 2008. A heuristic for the one dimensional cutting stock problem with pattern reduction. Proceedings of the Institution of Mechanical Engineers, v. 222, part B, Journal of Engineering Manufacture, doi:http://dx.doi.org/10.1243/09544054JEM966. 10.1243/09544054JEM966.

[2] DIEGEL A, CHETTY M, VAN SCHALKWYCK S & NAIDOO S. 1993. Setup combining in the trimloss problem - 3-to-2 & 2-to-1. Durban: Business Administration, University of Natal. Working Paper. First Draft.

[3] DYCKHOFF H. 1990. A typology of cutting and packing problems. European Journal of Operational Research, 44: 145-159. doi:10.1016/0377-2217(90)90350-K

[4] FARLEY AA & RICHARDSON KV. 1984. Fixed charge problems with identical fixed charges. European Journal of Operational Research, 18: 245-249. doi:10.1016/0377-2217(84)90190-5

[5] FOERSTER H & WASCHER G. 2000. Pattern reduction in one- š dimensional cutting stock problem. International Journal of Production Research, 38: 1657-1676. 10.1080/002075400188780

[6] GILMORE P & GOMORY R. 1961. A linear programming approach to the cutting-stock problem. Operations Research, 9: 849-859. 10.1287/opre.9.6.849

[7] GILMORE P & GOMORY R. 1963. A linear programming approach to the cutting-stock problem II. Operations Research, 11(6): 863-888.

[8] GAU T & WASCHER G. 1995. CUTGEN1: a problem generator for š the standard one-dimensional cutting stock problem. European Journal of Operational Research, 84: 572-579. doi:10.1016/0377-2217(95)00023-J

[9] HAESSLER RW. 1975. Controlling cutting pattern changes in onedimensional trim problems. Operations Research, 23: 483-493.

[10] HINXMAN AI. 1980. The trim loss and assortment problem: a survey. European Journal of Operational Research, 5: 8-18. doi:10.1016/0377-2217(80)90068-5

[11] JOHNSON DS. 1973. Near-optimal bin packing algorithms Cambridge, MA: Massachusetts Intitute of Technology. Tecnical Report MAC TR-109, Project MAC.

[12] McDIARMID C. 1999. Pattern minimisation in cutting stock problems. Discrete Applied Mathematics, 98: 121-130. doi:10.1016/S0166-218X(99)00112-2

[13] POLDI KC. 2003. Algumas extensoes do problema de corte de ˜ estoque. MS Dissertation, ICMC - USP, Sao Carlos, SP, Brazil. ˜

[14] STADTLER H. 1990. A one-dimensional cutting stock problem in the aluminium industry and its solution. European Journal of Operational Research, 44: 209-223. doi:10.1016/0377-2217(90)90356-G

[15] UMETAMI S, YAGIURA M & IBARAKI T. 2003. One-dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research, 146: 388-402. doi:10.1016/S0377-2217(02)00239-4

[16] VANDERBECK F. 2000. Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem. Operations Research, 48: 915-926.

[17] YANASSE HH & LIMEIRA MS. 2006. A hybrid heuristic to reduce the number of different patterns in cutting stock problems. Computers & Operations Research, 33: 2744-2756. 10.1016/j.cor.2005.02.026

[18] WALKER WE. 1976. A heuristic adjacent extreme point algorithm for the fixed charge problem. Management Science, 22: 587-596.