Data processing: generic control systems or specific application – Specific application – apparatus or process – Article handling
Reexamination Certificate
2003-02-26
2004-12-14
Tran, Khoi H. (Department: 3651)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Article handling
C414S273000, C414S900000
Reexamination Certificate
active
06832129
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed generally to a system and method for solving packing and component layout problems, and more particularly to packing rectangular strips.
BACKGROUND OF THE INVENTION
In manufacturing, it is frequently necessary to lay out patterns on a large piece of stock, and then to cut the stock into smaller pieces of various sizes to make a finished product. Typically, the component pieces must be located in such a manner that certain spatial constraints are satisfied. These spatial constraints often include orientation, proximity, and overlap. This is generally known as the “packing” problem.
For example, an article of clothing is usually made from various irregularly shaped pieces cut from a bolt of fabric. Similarly, a piece of furniture may require specific rectangular pieces of glass or wood cut from a large sheet of glass or plywood. In all cases, it is desired to minimize both the amounts of stock and waste.
Although the two-dimensional (2D) rectangular strip packing problem is more constrained than the general case of irregular shaped pieces, it is still important to many engineering and manufacturing applications, see Coffman et al., “Approximation algorithms for bin-packing: an updated survey,”
Algorithm Design for Computer Systems Design
, Springer-Verlag, Ausiello et al. editors, pp. 49-106 1984, and Dyckhoff, “Typology of cutting and packing problems,” European Journal of Operational Research, 44, pp. 145-159, 1990.
When a computerized method is used to solve the 2D rectangular strip packing problem, the input is typically a permuted list of n input rectangles along with their dimensions, and a target width W. The object is to pack the n input rectangles, without overlap, into a single target rectangle of width W, and a minimum height H. A spatial constraint requires that all rectangles are placed orthogonally and parallel to the horizontal and vertical axes, i.e., the rectangles cannot be rotated, other than in 90° steps. Like most packing problems, 2D rectangular strip packing, even with these spatial constraints, is NP-hard, because the number of different permutations that are possible is exponentially large in the number of rectangles.
One method for packing takes the list of input rectangles, and sorts them according to width or height, and greedily place the sorted rectangles, one by one, on the target rectangle. Perhaps, the most studied and effective heuristic, with the above constraints, is the bottom-left (BL) heuristic, where rectangles are placed sequentially, first as close to the bottom as possible, and then as far to the left as the rectangles can fit.
However, for some problems, the BL heuristic cannot find the optimal packing, nor does it perform well when applied to random instead of sorted orderings, see Baker et al., “Orthogonal packings in two dimensions,” SIAM Journal on Computing, 9:846-855, 1980, and Brown, “An improved BL lower bound,” Information Processing Letters, 11:37-39, 1980.
However, a very successful approach applies the BL method to permutations of rectangles that are ordered by decreasing height, width, perimeter, and area, and returns the best of the four packings that result see Hopper, “Two-Dimensional Packing Utilising Evolutionary Algorithms and other Meta-Heuristic Methods,” Ph.D. Thesis, Cardiff University, UK, 2000. That method is referred to as bottom-left-decreasing (BLD).
A natural alternative approach would find good orderings of the rectangles for BL or other similar heuristics, using standard search techniques such as simulated annealing, genetic algorithms, or tabu search. However, despite significant efforts in this area, the large search space has not proven amenable to such search techniques, see Hopper et al., “An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem,” European Journal of Operational Research, 128(1):34-57, 2000.
Another approach uses an approximation procedure. The BL heuristic has been shown to be a 3-approximation when the rectangles are sorted by decreasing width. However, that approach is not competitive when sorted by decreasing height. Other approaches give an asymptotic 5/4-approximation, see Baker et al., “A 5/4 algorithm for two-dimensional packing,” Journal of Algorithms, 2:348-368, 1981, and an absolute 5/2-approximation, see Sleator, “A 2.5 times optimal algorithm for packing in two dimensions,” Information Processing Letters, 10:37-40, 1980. A fully polynomial approximation scheme has also been described, see Kenyon et al., “Approximate Strip-Packing,” Proceedings of the 37
th
Annual Symposium on Foundations of Computer Science,” pp. 31-36, 1996.
For many practical applications, humans usually outperform the best computerized methods, particularly for irregular shapes. Because humans still appear to be able to do better than automated methods, it is desired to provide an interactive system and method where the user can improve upon solutions provided by a computerized method.
SUMMARY OF THE INVENTION
The invention provides a method for optimally packing input rectangles into a target rectangle. The method can be used in a divide-and-conquer process for packing problems with a large number of rectangles. In addition, an interactive interface can be used to improve upon computer generated solutions.
A method packs input rectangles into a target rectangle. The rectangles are permuted into one or more an ordered list according to dimensions of the rectangles, e.g., width, height, perimeter, and area.
The rectangles are then marked as unaccepted. A next unaccepted rectangle is selected from the ordered list beginning with a first rectangle in the list. Accepting the next rectangle if it is the last unaccepted rectangles.
Otherwise, accepting the next rectangle with a probability p, and marking the next rectangle as accepted, and repeating the steps until all rectangles have been accepted.
REFERENCES:
patent: 4692876 (1987-09-01), Tenma et al.
patent: 5050090 (1991-09-01), Golub et al.
patent: 5473545 (1995-12-01), Schausten
patent: 6286656 (2001-09-01), Huang et al.
Coffman et al., “Approximation algorithms for bin-packing: an undated survey,”Algorithm Design for Computer Systems Design, Springer-Verlag, Ausiello et al. editors, pp. 49-106 1984.
Hopper et al., “An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem,” European Journal of Operational Research, 128(1) : 34-57, 2000.
Lesh Neal B.
Marks Joseph W.
Mitzenmacher Michael D.
Brinkman Dirk
Curtin Andrew
Mitsubishi Electric Research Laboratories Inc.
Tran Khoi H.
LandOfFree
Method for packing rectangular strips does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for packing rectangular strips, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for packing rectangular strips will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3290618