BEST-1ST SEARCH METHODS FOR CONSTRAINED 2-DIMENSIONAL CUTTING STOCK PROBLEMS
成果类型：
Article
署名作者：
VISWANATHAN, KV; BAGCHI, A
署名单位：
Indian Institute of Management (IIM System); Indian Institute of Management Calcutta; New Jersey Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.4.768
发表日期：
1993
页码：
768-776
关键词：
摘要：
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 r1, r2,..., r(n), with the ith 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 less-than-or-equal-to i less-than-or-equal-to n, to maximize a1v1 + a2v2 + ... + a(n)v(n) subject to the constraints a(i) less-than-or-equal-to 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.