Algorithms for the Constrained Two-Staged Two-Dimensional Cutting Problem

This paper solves FC_2TDC, the two–staged fixed–orientation two–dimensional cutting stock problem. FC_2TDC is a variant of the constrained two–dimensional cutting problem where each piece is produced, in the final cutting pattern, by at most two cuts, and each piece has a fixed orientation. It is solved by an algorithm that combines a strip–generation procedure with beam search (BS). BS, which is a truncated branch–and–bound, investigates a subset of elite nodes and permanently fathoms the others. It chooses the elite nodes based on an evaluation operator. The importance of the evaluation operator on the performance of BS is highlighted by comparing a local beam search (LBS) that uses a priority cost–evaluation operator to a global beam search (GBS) that adopts a global cost–evaluation operator. Computational results, based on several medium and large instances, further show that LBS provides good solutions, whereas GBS gives (near) optimal solutions within reasonable computational time.