Method for determining a sequence for drilling holes according to a pattern using global and local optimization
AssigneeMitsubishi Electric Research Laboratories, Inc.
InventorsTyler Garaas, Matthew Brand
Life of this patent
Estimating the term…
Abstract
A method determines a sequence for drilling holes in a workpiece according to a pattern by first partitioning the holes in the pattern into packets. A global sequence of the packets is determined by solving a global traveling salesman problem (TSP), and a local sequence of the holes in each packet is determined by solving a local TSP for each packet. Then, the local sequences of the holes are joined according to the global sequence of the packets to determine a complete sequence for drilling the holes.
Claims16
A method for determining a sequence of drilling holes in a workpiece according to a pattern, wherein the pattern is partitioned into packets and the holes are drilled by a drilling machine, comprising:
- determining a global sequence of the packets by solving a global traveling salesman problem (TSP);
- determining a local sequence of the holes in each packet by solving a local TSP for each packet;
- joining the local sequences of the holes according to the global sequence of the packets to determine a complete sequence of drilling the holes by a drilling machine;
- and
- adapting the partitioning to equalize a density of the holes in each packet, wherein the steps are performed in a processor.
A method for determining a sequence of drilling holes in a workpiece according to a pattern, wherein the pattern is partitioned into packets and the holes are drilled by a drilling machine, comprising:
- determining a global sequence of the packets by solving a global traveling salesman problem (TSP);
- determining a local sequence of the holes in each packet by solving a local TSP for each packet;
- and
- joining the local sequences of the holes according to the global sequence of the packets to determine a complete sequence of drilling the holes by a drilling machine,
- wherein the global TSP is solved using a global graph, wherein the vertices in the global graph represent a location of each packet, and the vertices in the local graph represent a location for a previous packet and a location for a next packet with respect to a current packet in the global sequence, and the holes, wherein the location of the packet is center of mass of the packet with respect to holes, and wherein the steps are performed in a processor.
Dependencies are inferred from the claim text.