Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems
Operations Research · 1993 · Volume 41 · Issue 4
Abstract
Best-first search is a widely used problem solving technique in the field of artificial intelligence. The method has useful applications in operations research as well. Here we describe an application to constrained two-dimensional cutting stock problems of the following type: A stock rectangle S of dimensions ( L , W ) is supplied. There are n types of demanded rectangles r 1 , r 2 , …, r n , with the i th type having length l i , width w i , value v i , and demand constraint b i . It is required to produce, from the stock rectangle S , a i copies of r i , 1 ≤ i ≤ n , to maximize a 1 v 1 + a 2 v 2 + · + a n v n subject to the constraints a i ≤ b i . Only orthogonal guillotine cuts are permitted. All parameters are integers. A best-first tree search algorithm based on Wang's bottom-up approach is described that guarantees optimal solutions and is more efficient than existing methods.
Keywords
computers/computer science, artificial intelligence: search methods, production/scheduling, cutting stock/trim: rectangular stock sheets
Enable JavaScript for citation tools and additional paper interactions.