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;
- 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 steps are performed in a processor.
Dependencies are inferred from the claim text.