Iterative packing optimization

• US 10,108,751 B2
• Filed: 08/07/2014
• Issued: 10/23/2018
• Est. Priority Date: 04/26/2012
• Status: Active Grant

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Inventors: Tschanz, Michael, McNaull, Patrick, Boyle, Bryant, Ngo, J. Thomas
• Primary Examiner(s): Fernandez Rivas, Omar F
• Assistant Examiner(s): Luu, Cuong V
• Application Number:
  US14/453,758
• Publication Number:
  US 20140350898A1
• Time in Patent Office: 1,538 Days
• Field of Search: None
• CPC Class Codes: B29C 64/386 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: G05B 19/4097 characterised by using design data to control NC machines, e.g. CAD/CAM G05B19/4093 takes precedence
• CPC Class Codes: G05B 2219/35162 Determine workpiece placement, nesting in blank, optimize, minimize loss material
• CPC Class Codes: G05B 2219/49023 3-D printing, layer of powder, add drops of binder in layer, new powder
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]

Abstract

An iterative method and system for performing the method are described that implement a technique to fit irregularly shaped items into a defined space. In particular, one example may take the form of a method including predetermining one or more layouts for a defined space. Each layout has a plurality of shapes. The method also includes receiving a set having a plurality of items and determining one or more configurations formed by assigning to each shape in the layout an item from the set. The items match the shapes to which they are assigned. Additionally, the method includes scoring each configuration and selecting one configuration based at least in part upon the scoring.

Claims

1. A method comprising:

predetermining two or more layouts for a defined space of a print bed of a three dimensional printer, each layout of the two or more layouts comprising a plurality of shapes;

receiving a set comprising data representing physical properties of a plurality of items, wherein the set is stored in a computer readable medium;

determining two or more configurations of items with at least one configuration for each layout, each configuration of items formed by assigning items from the plurality of items to a plurality of shapes of a layout, wherein one item is assigned to one shape and two or more differently shaped items correspond to the layout shape;

scoring, by a processor, the two or more configurations of items;

selecting one of the two or more configurations of items based at least in part upon the scoring; and

printing by the three dimensional printer the items of the selected configuration of items, wherein the items are arranged in the print bed based on the selected configuration of items.

2. The method of claim 1, wherein the two or more layouts are predetermined using a morphological technique.

3. The method of claim 1 further comprising:

receiving user input, the user input including at least one layout; and

including the at least one layout with the predetermined two or more layouts.

4. The method of claim 1, wherein the set comprises one of a queue, a linear queue, a priority queue or a bag.

5. The method of claim 1, wherein the defined space comprises one of a two-dimensional space or a three-dimensional space.

6. The method of claim 1, wherein scoring the two or more configurations of items comprises at least one of:

determining a height cost for the two or more configurations of items;

computing an occupancy cost for items in the set not included in the two or more configurations of items; and

computing a shipment delay cost for items in the set not included in the two or more configurations of items.

7. The method of claim 1, wherein scoring the two or more configurations of items comprises summing a height cost, a bin-occupancy cost, and a shipment delay cost for the two or more configurations of items.

8. The method of claim 1, wherein each configuration of items comprises a subset of the set of the items, each item of each subset having an orientation and a position within the configuration of items.

9. The method of claim 1 wherein scoring further comprises:

updating the set upon selection of a configuration of items by removing from the set items included in the configuration of items; and

evaluating the updated set after removal of the items.

10. The method of claim 1 wherein the two or more configurations of items are generated using the set, wherein the set comprises one of a linear queue, a priority queue or a bag.

11. The method of claim 10 wherein the set is organized by at least one of a dollar value and fabrication priority.

12. The method of claim 10 wherein the two or more configurations of items are formed by greedily pulling items from the set.

13. The method of claim 2 wherein the morphological technique comprises successively placing layout shapes in the defined space while maintaining one or more system constraints defining placement of the layout shapes.

14. The method of claim 2 wherein the morphological technique comprises moving the layout shapes in the defined space in round-robin fashion.

15. The method of claim 13, wherein the system of constraints includes at least one of:

a minimum distance between the layout shapes, orientation of the layout shapes relative to the defined space, and orientation of the layout shapes relative to one another.

16. The method of claim 1, wherein predetermining the two or more layouts comprises utilizing a genetic technique.

17. The method of claim 1, wherein predetermining the two or more layouts comprises utilizing both a genetic technique and a morphological method.

18. The method of claim 1, wherein predetermining the two or more layouts further comprises:

selecting a portion of a first layout for subsequent use; and

implementing the portion of the first layout in a second layout.

19. A method comprising:

pre-computing at least two layouts using a morphological technique, each layout comprising a plurality of holes positioned within a defined space of a three dimensional printer;

receiving a queue comprising data representing physical properties of a plurality of irregularly shaped items, the queue stored in a computer readable medium, wherein two or more of the irregularly shaped items correspond to at least one of the plurality of holes;

iteratively determining a plurality of configurations fitting a subset of the queue into the defined space wherein the plurality of configurations comprises a different subset of the queue of irregularly shaped items and wherein there is at least one configuration for each layout;

scoring the plurality of configurations;

selecting one of the plurality of configurations based at least in part upon the scoring of the plurality of configurations; and

printing by the three dimensional printer the items of the selected configuration, wherein the items are arranged in the three dimensional printer based on, the selected configuration.

20. The method of claim 19 further comprising

implementing a heuristic technique to maintain selected configurations in the computer readable medium.

21. The method of claim 19 further comprising:

receiving user input corresponding to at least one layout; and

storing the user input with the pre-computed at least two layouts for use in determining the plurality of configurations.

22. A system comprising:

a computer storage device configured to store a set comprising data representing physical properties of a plurality of irregularly shaped items to be printed;

a processor in communication with the computer storage device, the processor configured to;

predetermine two or more layouts for a defined space, each layout comprising a plurality of shapes;

receive the set;

determine two or more configurations with at least one configuration for each layout, each configuration of items formed by assigning a items from the plurality of items to a plurality of shapes of a layout, wherein one item is assigned to one shape and two or more differently shaped items correspond to the layout shape;

score the two or more configurations;

select one configuration of the two or more configurations based at least in part upon the scoring; and

output instructions for printing in a three dimensional print bed the selected configuration, the three dimensional print bed corresponding to the defined space; and

a three dimensional printer in communication with the processor, wherein the three dimensional printer prints items corresponding to the selected configuration.

23. The system of claim 22, wherein the selected configuration corresponds to a defined space of a container for packing a subset of the plurality of items in the set.