EP0389985A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Object placement method and apparatus
Assignee: RJ Reynolds Tobacco Co
•
Filing: 1990-03-23
•
Granted: —
•
Expires: 2010-03-23
Abstract
Abstract An object placement method and apparatus which obtains efficiency and optimized placement by providing a library of object placement patterns, each pattern in said library representing a plurality of objects filling a pattern line or series of pattern lines of a three-dimensional space. For each pattern line, a first type object (for example, a first size object) to be placed is selected and the pattern which minimizes the portion of the three-dimensional space used to place a number of first type objects, subject to at least one constraint factor, is determined. A representation of the objects in the rows according to the determined pattern may be provided. According to another aspect of the invention, linking restrictions between the objects of differing sizes may be provided. The linking restrictions are patterns from the library which may not be employed with objects of differing types in a line of the three-dimensional space. The linking restrictions may reject patterns that lead to irregular pattern geometries, inefficient use of space, unstable characteristics or any other undesirable configuration of the two object types in a single pattern line. The element placement technique of the present invention determines the patterns which minimize the portions of the three-dimensional space used to place the objects consistent with at least one constraint factor without violating the linking restrictions.
Inventors
- 👤 Alexander J. Golub
- 👤 Oscar F. Garza
- 👤 Charles Pat Joiner
- 👤 Alan W. Neebe
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-31 09:02
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/08
Claims Analysis
Total Claims: 84
Claim 1
Independent Claim
173 words
A method for providing instructions for placement of objects of differing placement characteristic types in a three-dimensional space of predetermined size, comprising the steps of: (a) providing a library of object placement patterns, each pattern in said library representing placement of a plurality of objects; (b) selecting a given number of first type object to be placed in said three-dimensional space; (c) choosing from said library a pattern set comprising at least one pattern for placement of said first type object in said three-dimensional space which minimizes the portion of said three-dimensional space used to place said given number of first type objects within a portion of said three-dimensional space consistent with at least one constraint factor: (d) repeating steps (b) and (c) for the remaining objects to be placed in said three-dimensional space; and (e) feeding said pattern sets for all objects to means for generating a representation of a placement pattern being a combination of said pattern sets, or to handling means for locating the objects according to said pattern sets.
Claim 2
Independent Claim
173 words
A method for providing instructions for placement of objects of differing placement characteristic types in a three-dimensional space of predetermined size, comprising the steps of: (a) providing a library of object placement patterns, each pattern in said library representing placement of a plurality of objects; (b) selecting a given number of first type object to be placed in said three-dimensional space; (c) choosing from said library a pattern set comprising at least one pattern for placement of said first type object in said three-dimensional space which minimizes the portion of said three-dimensional space used to place said given number of first type objects within a portion of said three-dimensional space consistent with at least one constraint factor: (d) repeating steps (b) and (c) for the remaining objects to be placed in said three-dimensional space; and (e) feeding said pattern sets for all objects to means for generating a representation of a placement pattern being a combination of said pattern sets, or to handling means for locating the objects according to said pattern sets.
Claim 3
Dependent Claim
18 words
The method of Claim 1 wherein said selecting step (b) comprises selecting all objects of a first type.
Claim 4
Dependent Claim
80 words
The method of Claim 1 wherein said library of patterns comprises a plurality of patterns grouped into pattern types according to like object orientation; and wherein said choosing step comprises the steps of: identifying at least one pattern from each pattern type which maximizes the loading efficiency for said first type objects; and determining which of the identified patterns minimizes the portion of said three-dimensional space used to place said first type objects consistent with at least one predetermined constraint.
Claim 5
Dependent Claim
43 words
The method of Claim 1 further comprising the step of: for each pattern set, if area remains unfilled after said choosing step (c), determining a number of objects of a succeeding object type for placement within the remaining area of the pattern set.
Claim 6
Dependent Claim
21 words
The method of Claim 4 wherein said determining step further comprises: determining an arrangement for said number of succeeding object types.
Claim 7
Dependent Claim
20 words
The method of Claim 5 further wherein said arrangement maximizes the number of succeeding objects placed in the unfilled area.
Claim 8
Dependent Claim
20 words
The method of Claim 5 wherein said arrangement minimizes the amount of space used to place said succeeding type objects.
Claim 9
Dependent Claim
17 words
The method of Claim 4 wherein said area is a portion of space within a pattern line.
Claim 10
Dependent Claim
62 words
The method of Claim 1 further comprising the step of: for a pattern line which is to include at least two types of objects, selecting the particular patterns for that pattern line which minimizes the portion of said three-dimensional space used to place the given number of first type objects of at least two types to be included in said pattern line.
Claim 11
Dependent Claim
15 words
The method of Claim 1 wherein said differing placement characteristic types are different object dimensions.
Claim 12
Dependent Claim
90 words
The method of Claim 1 further comprising the step of providing linking restrictions between said objects of differing types, said linking restrictions comprising selected patterns from said library which may not be employed with said objects of differing types in a pattern of said three-dimensional space; and wherein said choosing step comprises the step of selecting at least one pattern which minimizes the portion of said three-dimensional space used to place said first type objects consistent with at least one constraint factor, and which does not violate said linking restrictions.
Claim 13
Dependent Claim
31 words
The method of Claim 11 wherein said different placement characteristic types are different object dimensions and wherein said linking restrictions are determined by comparing the dimensions of the differing object types.
Claim 14
Dependent Claim
27 words
The method of Claim 12 wherein said comparison is made to determine how to place said differing type objects within said three-dimensional space to obtain object stability.
Claim 15
Dependent Claim
25 words
The method of Claim 1 further comprising the step of generating a representation of first type objects in the pattern according to the determined pattern.
Claim 16
Dependent Claim
25 words
The method of Claim 14 further comprising the step of: adjusting said patterns if the total length of the patterns is outside a predetermined range.
Claim 17
Dependent Claim
31 words
The method of Claim 1 wherein said choosing step is preceded by the step of: adjusting at least one of said patterns for an irregularly shaped portion of said three-dimensional space.
Claim 18
Dependent Claim
22 words
The method of Claim 16 wherein said adjusted pattern has an area which differs from that of said patterns in said library.
Claim 19
Dependent Claim
23 words
The method of Claim 1 further comprising the step of: placing said objects into said three dimensional space according to the selected patterns.
Claim 20
Dependent Claim
25 words
The method of Claim 1 wherein said chosen pattern set has dimensions that are a predetermined dimension less than the dimensions of the three-dimensional space.
Claim 21
Dependent Claim
34 words
The method of Claim 1 wherein said selecting step is preceded by the step of: describing the three-dimensional space and the types and number of said objects to be placed in said three-dimensional space.
Claim 22
Dependent Claim
26 words
The method of Claim 1 wherein said selecting step is preceded by the step of: providing a description of objects grouped according to like placement characteristics.
Claim 23
Dependent Claim
28 words
The method of Claim 1 wherein said selecting step is preceded by the step of: providing a manifest identifying the objects to be placed in said three-dimensional space.
Claim 24
Dependent Claim
19 words
The method of Claim 1 wherein said constraint factor comprises object stability within said patterns of said three-dimensional space.
Claim 25
Dependent Claim
31 words
The method of Claim 11 wherein said placement characteristic is object dimensions and said linking restrictions apply when the differences in object dimensions between different size objects exceeds a predetermined range.
Claim 26
Dependent Claim
15 words
The method of Claim 1 wherein said three-dimensional space of predetermined size is a truck.
Claim 27
Independent Claim
258 words
A method for placing representations of objects of differing sizes in a representation of a three-dimensional space of a predetermined size, said objects having a front surface, a top surface, a side surface, and a flat surface, comprising the steps of: providing a library of object placement patterns, each pattern in said library representing placement of objects in a row of said three-dimensional space, which place a number of the objects in that row, said library of patterns having several different pattern types; determining which of said pattern types are feasible; selecting a pattern set comprising at least one pattern from each feasible pattern type which minimizes the portion of said three-dimensional space used to place a given number of first type objects within a portion of said three-dimensional space consistent with at least one constraint factor; choosing which of the selected patterns minimizes the portion of said representation of said three-dimensional space used to place a given number of representations of first type objects consistent with said constraint factor associated therewith; for each pattern set, if a pattern remains unfilled after all representations of objects of said first size are placed, determining which pattern minimizes the portion of said representation of said three-dimensional space used to place the representation of objects of a succeeding size in the unfilled pattern; and feeding said patterns sets for all objects to means for generating a representation of a placement pattern being a combination of said pattern sets, or to handling means for locating the objects according to said pattern sets.
Claim 28
Independent Claim
258 words
A method for placing representations of objects of differing sizes in a representation of a three-dimensional space of a predetermined size, said objects having a front surface, a top surface, a side surface, and a flat surface, comprising the steps of: providing a library of object placement patterns, each pattern in said library representing placement of objects in a row of said three-dimensional space, which place a number of the objects in that row, said library of patterns having several different pattern types; determining which of said pattern types are feasible; selecting a pattern set comprising at least one pattern from each feasible pattern type which minimizes the portion of said three-dimensional space used to place a given number of first type objects within a portion of said three-dimensional space consistent with at least one constraint factor; choosing which of the selected patterns minimizes the portion of said representation of said three-dimensional space used to place a given number of representations of first type objects consistent with said constraint factor associated therewith; for each pattern set, if a pattern remains unfilled after all representations of objects of said first size are placed, determining which pattern minimizes the portion of said representation of said three-dimensional space used to place the representation of objects of a succeeding size in the unfilled pattern; and feeding said patterns sets for all objects to means for generating a representation of a placement pattern being a combination of said pattern sets, or to handling means for locating the objects according to said pattern sets.
Claim 29
Dependent Claim
25 words
The method of Claim 26 wherein said second determining step further comprises: determining an arrangement for said representation of said number of succeeding object types.
Claim 30
Dependent Claim
21 words
The method of Claim 27 wherein said arrangement maximizes the number of representations of succeeding objects placed in the unfilled area.
Claim 31
Dependent Claim
22 words
The method of Claim 27 wherein said arrangement minimizes the amount of space used to place said representations of succeeding type objects.
Claim 32
Dependent Claim
98 words
The method of Claim 26 wherein said providing step further comprises the step of: providing linking restrictions between said representations of differing object sizes, said linking restrictions comprising pattern types which may not be employed for use with more than one object size in a pattern of said three-dimensional space, and wherein said second determining step comprises the steps of determining which of said patterns minimizes the portion of said representation of three-dimensional space used to place the number of objects of said first size consistent with said constraint factor, and which does not violate said linking restrictions.
Claim 33
Dependent Claim
26 words
The method of Claim 26 further comprising the step of: adjusting said pattern lines if the total length of the pattern lines exceeds a predetermined length.
Claim 34
Dependent Claim
31 words
The method of Claim 31 wherein said different placement characteristic types are different object dimensions and wherein said linking restrictions are determined by comparing the dimensions of the differing object types.
Claim 35
Dependent Claim
31 words
The method of Claim 32 wherein said comparison is made to determine how to place said differing type objects within said three-dimensional space to obtain maximum loading efficiency and maximum stability.
Claim 36
Dependent Claim
31 words
The method of Claim 26 wherein said selecting step is preceded by the step of: adjusting at least one of said patterns for an irregularly shaped portion of said three-dimensional space.
Claim 37
Dependent Claim
22 words
The method of Claim 34 wherein said adjusted pattern has an area which differs from that of said patterns in said library.
Claim 38
Dependent Claim
25 words
The method of Claim 26 further comprising the step of: placing said first and succeeding objects into said three dimensional space according to said patterns.
Claim 39
Dependent Claim
25 words
The method of Claim 26 wherein said chosen pattern set has dimensions that are a predetermined dimension less than the dimensions of the three-dimensional space.
Claim 40
Dependent Claim
14 words
The method of Claim 26 further comprising: providing a representation of said determined patterns.
Claim 41
Dependent Claim
34 words
The method of Claim 26 wherein the selecting step is preceded by the step of: describing the three-dimensional space and the types and number of said objects to be placed in said three-dimensional space.
Claim 42
Dependent Claim
26 words
The method of Claim 26 wherein said selecting step is preceded by the step of: providing a description of objects grouped according to like placement characteristics.
Claim 43
Dependent Claim
28 words
The method of Claim 26 wherein said selecting step is preceded by the step of: providing a manifest identifying the objects to be placed in said three-dimensional space.
Claim 44
Dependent Claim
18 words
The method of Claim 26 wherein said given number of first type objects comprise all first type objects.
Claim 45
Dependent Claim
18 words
The method of Claim 26 wherein said constraint comprises object stability within said patterns of said three-dimensional space.
Claim 46
Dependent Claim
31 words
The method of Claim 26 wherein said placement characteristic is object dimensions and said linking restrictions apply when the differences in object dimensions between different size objects exceeds a certain range.
Claim 47
Dependent Claim
12 words
The method of Claim 26 wherein said three-dimensional space is a truck.
Claim 48
Independent Claim
146 words
A method for providing instructions for placement of groups of objects of at least two differing placement characteristic types in a three-dimensional space of a predetermined size, comprising the steps of: providing a library of patterns, each pattern representing placement of objects within said pattern; determining linking restrictions between said objects of differing placement characteristic types, said linking restrictions comprising selected patterns which may not be employed for placement of differing object types in a pattern within said three-dimensional space; selecting a pattern for each group of set comprising at least one pattern, which places said differing placement characteristic type groups of objects without violating said linking restrictions; and feeding said pattern sets for all objects to means for generating a representation of a placement pattern being a combination of said pattern sets, or to handling means for locating the objects according to said pattern sets.
Claim 49
Independent Claim
146 words
A method for providing instructions for placement of groups of objects of at least two differing placement characteristic types in a three-dimensional space of a predetermined size, comprising the steps of: providing a library of patterns, each pattern representing placement of objects within said pattern; determining linking restrictions between said objects of differing placement characteristic types, said linking restrictions comprising selected patterns which may not be employed for placement of differing object types in a pattern within said three-dimensional space; selecting a pattern for each group of set comprising at least one pattern, which places said differing placement characteristic type groups of objects without violating said linking restrictions; and feeding said pattern sets for all objects to means for generating a representation of a placement pattern being a combination of said pattern sets, or to handling means for locating the objects according to said pattern sets.
Claim 50
Dependent Claim
26 words
The method of Claim 46 wherein said placement characteristic types are object sizes and said linking restrictions are determined based upon the difference in object dimensions.
Claim 51
Dependent Claim
41 words
The method of Claim 46 wherein said patterns are grouped into differing pattern types and wherein said linking restrictions comprise selected pattern types which may not be employed for placement of differing object types in a pattern within said three-dimensional space.
Claim 52
Dependent Claim
19 words
The method of Claim 46 wherein said pattern types are based on the orientation of objects within said patterns.
Claim 53
Dependent Claim
12 words
The method of Claim 46 wherein said three-dimensional space is a truck.
Claim 54
Dependent Claim
117 words
Apparatus for providing instructions for placement of objects of differing placement characteristic types in a three-dimensional space, comprising: (a) means for providing a library of object placement patterns, each pattern in said library representing placement of a plurality of objects: (b) means for selecting a given number of first type object to be placed in said three-dimensional space; and (c) means for choosing from said library a pattern set comprising at least one pattern for placement of said first type object in said three-dimensional space which minimizes the portion of said three-dimensional space used to place said given number of first type objects within a portion of said three-dimensional space consistent with at least one constraint factor.
Claim 55
Dependent Claim
117 words
Apparatus for providing instructions for placement of objects of differing placement characteristic types in a three-dimensional space, comprising: (a) means for providing a library of object placement patterns, each pattern in said library representing placement of a plurality of objects: (b) means for selecting a given number of first type object to be placed in said three-dimensional space; and (c) means for choosing from said library a pattern set comprising at least one pattern for placement of said first type object in said three-dimensional space which minimizes the portion of said three-dimensional space used to place said given number of first type objects within a portion of said three-dimensional space consistent with at least one constraint factor.
Claim 56
Dependent Claim
90 words
The apparatus of Claim 51 wherein said providing means (a) comprises means for providing a library of patterns comprising a plurality of patterns grouped into pattern types according to like object orientation; and wherein said choosing means (c) comprises: means for identifying at least one pattern from each pattern type which maximizes the loading efficiency for said first type objects; and means for determining which of the identified patterns minimizes the portion of said three-dimensional space used to place said first type objects consistent with at least one predetermined constraint.
Claim 57
Dependent Claim
55 words
The apparatus of Claim 51 further comprising: means for selecting the particular patterns for a pattern which is to include at least two types of objects, which minimizes the portion of said three-dimensional space used to place the given number of first type objects of at least two types to be included in said pattern.
Claim 58
Dependent Claim
15 words
The apparatus of Claim 51 wherein said differing placement characteristic types are different object dimensions.
Claim 59
Dependent Claim
90 words
The apparatus of Claim 51 further comprising means for providing linking restrictions between said objects of differing types, said linking restrictions comprising selected patterns from said library which may not be employed with said objects of differing types in a pattern of said three-dimensional space; and wherein said second providing means (c) comprises means for selecting at least one pattern which minimizes the portion of said three-dimensional space used to place said first type objects consistent with at least one constraint factor, and which does not violate said linking restrictions.
Claim 60
Dependent Claim
21 words
The apparatus of Claim 51 further comprising means for representing first type objects in the pattern according to the determined pattern.
Claim 61
Dependent Claim
24 words
The apparatus of Claim 51 further comprising: means for adjusting said patterns if the total length of the patterns is outside a predetermined range.
Claim 62
Dependent Claim
33 words
The apparatus of Claim 55 wherein said different placement characteristic types are different object dimensions and wherein said linking restrictions are determined by means for comparing the dimensions of the differing object types.
Claim 63
Dependent Claim
21 words
The apparatus of Claim 51 further comprising: means for determining a unique pattern for said first pattern of said three-dimensional space.
Claim 64
Dependent Claim
21 words
The apparatus of Claim 59 wherein said unique pattern has an area which differs from that of said library of patterns.
Claim 65
Dependent Claim
21 words
The apparatus of Claim 51 further comprising: means for placing said objects into said three-dimensional space according to the selected patterns.
Claim 66
Dependent Claim
29 words
The apparatus of Claim 51 wherein said selecting step is preceded by the step of: segregating the objects to be placed in said three-dimensional space by said placement characteristics.
Claim 67
Dependent Claim
19 words
The apparatus of Claim 51 wherein said constraint factor comprises object stability within said patterns of said three-dimensional space.
Claim 68
Dependent Claim
31 words
The apparatus of Claim 55 wherein said placement characteristic is object dimensions and said linking restrictions apply when the differences in object dimensions between different size objects exceeds a predetermined range.
Claim 69
Dependent Claim
13 words
The apparatus of Claim 51 wherein said three dimensional space is a truck
Claim 70
Dependent Claim
223 words
Apparatus for placing representations of objects of differing sizes in a representation of a three-dimensional space of a predetermined size, said objects having a front surface, a top surface, a side surface, and a flat surface, comprising: means for providing a library of object placement patterns, each pattern in said library representing placement of objects in a row of said three-dimensional space, which place a number of the objects in that row, said library of patterns having several different pattern types; means for determining which of said pattern types are feasible; means for selecting a pattern set comprising at least one pattern from each feasible pattern type which minimizes the portion of said three-dimensional space used to place a given number of first type objects within said three-dimensional space consistent with at least one constraint factor: first means for choosing which of the selected patterns minimizes the portion of said representation of said three-dimensional space used to place a given number of representations of first type objects consistent with said constraint factor associated therewith: means for identifying which pattern minimizes the portion of said representation of said three-dimensional space used to place the representation of objects of a succeeding size in the unfilled pattern for each row, if a pattern remains unfilled after all representations of objects of said first size are placed.
Claim 71
Dependent Claim
223 words
Apparatus for placing representations of objects of differing sizes in a representation of a three-dimensional space of a predetermined size, said objects having a front surface, a top surface, a side surface, and a flat surface, comprising: means for providing a library of object placement patterns, each pattern in said library representing placement of objects in a row of said three-dimensional space, which place a number of the objects in that row, said library of patterns having several different pattern types; means for determining which of said pattern types are feasible; means for selecting a pattern set comprising at least one pattern from each feasible pattern type which minimizes the portion of said three-dimensional space used to place a given number of first type objects within said three-dimensional space consistent with at least one constraint factor: first means for choosing which of the selected patterns minimizes the portion of said representation of said three-dimensional space used to place a given number of representations of first type objects consistent with said constraint factor associated therewith: means for identifying which pattern minimizes the portion of said representation of said three-dimensional space used to place the representation of objects of a succeeding size in the unfilled pattern for each row, if a pattern remains unfilled after all representations of objects of said first size are placed.
Claim 72
Dependent Claim
100 words
The apparatus of Claim 66 wherein said providing means further comprises: means for providing linking restrictions between said representations of differing object sizes, said linking restrictions comprising pattern types which may not be employed for use with more than one object size in a pattern of said three-dimensional space, and wherein said means for determining step comprises second means for determining which of said patterns minimizes the portion of representations of said representation of three-dimensional space used to place the number of objects of said first size consistent with said constraint factor, and which does not violate said linking restrictions.
Claim 73
Dependent Claim
23 words
The apparatus of Claim 66 further comprising: means for adjusting said rows if the total length of the rows exceeds a predetermined length.
Claim 74
Dependent Claim
21 words
The apparatus of Claim 66 further comprising means for selecting a unique pattern for said first row of said three-dimensional space.
Claim 75
Dependent Claim
16 words
The apparatus of Claim 66 further comprising: means for providing a representation of said determined patterns.
Claim 76
Dependent Claim
22 words
The apparatus of Claim 66 further comprising: means for segregating the objects to be placed in said three-dimensional space by placement characteristics.
Claim 77
Dependent Claim
18 words
The apparatus of Claim 66 wherein said constraint comprises object stability within said patterns of said three-dimensional space.
Claim 78
Dependent Claim
31 words
The apparatus of Claim 67 wherein said placement characteristic is object dimensions and said linking restrictions apply when the differences in object dimensions between different size objects exceeds a certain range.
Claim 79
Dependent Claim
12 words
The apparatus of Claim 66 wherein said three-dimensional space is a truck.
Claim 80
Dependent Claim
99 words
Apparatus for providing instructions for placement of objects of at least two differing placement characteristic types in a three-dimensional space, comprising: means for providing a library of patterns, each pattern representing placement of objects within said pattern; means for identifying linking restrictions between said objects of differing placement characteristic types, said linking restrictions comprising selected patterns which may not be employed for placement of differing object types in a pattern within said three-dimensional space; and means for selecting a pattern set comprising at least one pattern which places said differing placement characteristic type objects without violating said linking restrictions.
Claim 81
Dependent Claim
99 words
Apparatus for providing instructions for placement of objects of at least two differing placement characteristic types in a three-dimensional space, comprising: means for providing a library of patterns, each pattern representing placement of objects within said pattern; means for identifying linking restrictions between said objects of differing placement characteristic types, said linking restrictions comprising selected patterns which may not be employed for placement of differing object types in a pattern within said three-dimensional space; and means for selecting a pattern set comprising at least one pattern which places said differing placement characteristic type objects without violating said linking restrictions.
Claim 82
Dependent Claim
26 words
The apparatus of Claim 75 wherein said placement characteristic types are object sizes and said linking restrictions are determined based upon the difference in object dimensions.
Claim 83
Dependent Claim
41 words
The apparatus of Claim 75 wherein said library of patterns include differing pattern types and wherein said linking restrictions comprise selected pattern types which may not be employed for placement of differing object types in a pattern within said three-dimensional space.
Claim 84
Dependent Claim
12 words
The apparatus of Claim 75 wherein said three-dimensional space is a truck.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.