Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems

K. V. Viswanathan and A. Bagchi
Additional contact information
K. V. Viswanathan: Indian Institute of Management, Calcutta, India
A. Bagchi: Indian Institute of Management, Calcutta, India and New Jersey Institute of Technology, Newark, New Jersey

Operations Research, 1993, vol. 41, issue 4, 768-776

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 (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.4.768 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:4:p:768-776

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().