A tree-search method for solving a cutting stock assignment problem

N. R. Smith, F. Al-Khayyal, Paul Griffin

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Many production environments such as carpet or flat glass manufacturing have linked operations that perform completely different activities. In this paper, we consider a two-stage manufacturing process involving a cutting operation, followed by an assignment operation. Raw material is cut to meet product demand with minimum trim loss, and assignments are made to minimize resource requirements. This cutting stock assignment problem is formulated as a large-scale, mixed-integer nonlinear programming problem. We propose a solution methodology based on decomposition and tree search heuristic strategies. We report on extensive computational experiments on a wide range of problems, and apply statistical techniques to determine significant factors. For all small-size problems tested, our method found the exact optimal solution. For practical-size problems, our method was about two orders of magnitude faster and produced solutions that were one-third better than tabu search.

Original languageEnglish (US)
Pages (from-to)1557-1578
Number of pages22
JournalInternational Journal of Production Research
Issue number7
StatePublished - 2000

All Science Journal Classification (ASJC) codes

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A tree-search method for solving a cutting stock assignment problem'. Together they form a unique fingerprint.

Cite this