Machine and Method for Manufacturing a Workpiece by a Computer-Controlled Manufacturing Machine with an Optimal Tool Configuration

Abstract

Method for manufacturing a workpiece with a predefined sequence of machine tools by a computer-controlled manufacturing machine with an optimal tool configuration, wherein the initial locations of the tools are allocated, first and second time transfer time functions are calculated for all tools, possible tool location sequences are generated, for possible tool location sequences a respective first cost factor is calculated, obtained tool location sequences are ranked in accordance with the respective first cost factor, the tools are transferred from their initial locations to the optimal locations in accordance with an optimal tool configuration, and the workpiece is manufactured with the optimal tool configuration by the manufacturing machine.

Claims

1-8. (canceled)

9. A method for manufacturing a workpiece with a predefined sequence of machine tools by a computer-controlled manufacturing machine with an optimal tool configuration, said machine tools being located at respective locations set by the optimal tool configuration and being assigned to respective, precalculated operation times, and a machine including a tool transfer point and a tool handler for moving a selected tool from a respective location of the respective locations to the transfer point, the method comprising: a) allocating initial locations of the machine tools, and calculating for all tools i) a first transfer time function, returning a time between the respective location and the transfer point, and ii) a second transfer time function, returning a time of a tool handler movement without moving a tool; b) generating possible tool location sequences as a random set of tool location sequences; c) calculating a respective first cost factor for possible tool location sequences utilizing a first cost function utilizing the first and second transfer time functions; d) ranking tool location sequences obtained in step c) in accordance with the respective first cost factor, a subset of the tool location sequences with a lowest first cost factor being utilized as a selected set of tool location sequences, new tool location sequences being explored based on the selected set of tool location sequences and the new tool location sequences being added to the selected set of tool location sequences, and step c) being continue to calculate the cost function and perform the ranking and selection and exploration until a predefined parameter for the number of iterations is reached, define the selected set of tool location sequences with the lowest cost function being defined as the optimal tool configuration; e) transferring the machine tools from their initial locations to the optimal locations in accordance with the optimal tool configuration; f) manufacturing the workpiece with the optimal tool configuration by the manufacturing machine.

10. Method according to claim 9, wherein the first cost function is defined in accordance with the following relationship: $C={\displaystyle {.Math.}_{i=2}^N\left(o_i+max\left(0,M{T}_i-o_i\right)\right)}$ with $M{T}_i=G\left(t_{i-1},v\left(t_{i-1}\right)\right)+R\left(v\left(t_{i-1}\right),v\left(t_{i+1}\right)\right)+G\left(t_{i+1},v\left(t_{i+1}\right)\right)$ where C is the first cost function, G is the first transfer time function, R is the second transfer time function, O is the operation time function, and MT is the moving time of tool changing device.

11. The method according to claim 9, wherein a respective second cost factor is calculated for the selected set utilizing a second cost function, considering further a time required for the reallocation of tools, utilizing the first cost factor, and further a reallocation factor regarding an impact of a single manufacturing step including a reallocation time on an optimization or alternatively a count factor regarding an impact of the number of occurrences of a single manufacturing step on an overall manufacturing process.

12. The method according to claim 11, wherein the second cost function is defined in accordance with the following relationship: $C{P}_1=C+\left(\alpha \times RT\right)$ with $RT={\displaystyle {.Math.}_{j=1}^{X}R\left(v\left(t{r}_j\right),vt\left(t{r}_j\right)\right)}$ where CP.sub.1 is the second cost function Type 1, R is the reallocation time, and RT is the total reallocation time.

13. The method according to claim 11, wherein the second cost function is defined in accordance with the following relationship: $C{P}_2=\left(C\times \rho \right)+RT$ with $RT={\displaystyle {.Math.}_{j=1}^{X}R\left(v\left(t{r}_j\right),vt\left(t{r}_j\right)\right)}$ where CP.sub.2 is the second cost function Type 2, R is the reallocation time, and RT is the total reallocation time.

14. The method according to claim 9, wherein the exploration of new tool location sequences includes the application of a genetic crossover function; and wherein two tool location sequences from the selected set are combined into a new tool location sequence.

15. The method according to claim 9, wherein the exploration of new tool location sequences includes an application of a mutation function; and wherein tool locations within a tool location sequence from the selected set are exchanged, preferably randomly exchanged.

16. The method according to claim 15, wherein tool locations within a tool location sequence from the selected set are randomly exchanged.

17. A computer-controlled manufacturing machine with machine tools, comprising: a control device including memory for determining an optimal sequence of the machine tools for manufacturing a workpiece, the machine tools being located at respective locations and the machine tools being assigned to respective, precalculated operation times; wherein the machine includes a tool transfer point and a tool handler for moving a selected tool from a respective location of the respective locations to the transfer point; wherein the control device is configured to: a) allocate initial locations of the machine tools, and calculate for all tools i) a first transfer time function, returning a time between the respective location and the transfer point, and ii) a second transfer time function, returning a time of a tool handler movement without moving a tool; b) generate possible tool location sequences as a random set of tool location sequences; c) calculate a respective first cost factor for possible tool location sequences utilizing a first cost function utilizing the first and second transfer time functions; d) rank tool location sequences obtained in step c) in accordance with the respective first cost factor, a subset of the tool location sequences with a lowest first cost factor being utilized as a selected set of tool location sequences, new tool location sequences being explored based on the selected set of tool location sequences and the new tool location sequences being added to the selected set of tool location sequences, and step c) being continue to calculate the cost function and perform the ranking and selection and exploration until a predefined parameter for the number of iterations is reached, define the selected set of tool location sequences with the lowest cost function being defined as the optimal tool configuration; e) transfer the machine tools from their initial locations to the optimal locations in accordance with the optimal tool configuration; and f) manufacture the workpiece with the optimal tool configuration by the manufacturing machine.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0057] The invention is explained in more detail below with reference to an embodiment shown in the accompanying drawings, in which:

[0058] FIG. 1 an exemplary illustration of a tool handling sketch at a Computer Numeric Control (CNC) machine during machining; and

[0059] FIG. 2 is an embodiment of the method in accordance with the invention.

DETAILED DESCRPTION OF THE EXEMPLARY EMBODIMENTS

[0060] The total production time for machining a workpiece in Computer Numeric Control (CNC) machines considers two parts: [0061] i) a machining time when a tool is machining material, line cutting or drilling, and [0062] ii) a non-machining time when a robot arm is moving on a magazine to retrieve a succeeding tool or the tools are being switched by a gripper in the magazine.

[0063] The machining of a workpiece is performed with a specified sequence of tools and any tool can be used several times in this sequence.

[0064] While machining the workpiece, the preceding tool should be returned to its corresponding location. Then the robot arm should move to the location of the succeeding tool and eventually bring it to the tool transfer point, from which a selected tool is picked up by a tool holder, e.g., a spindle, of the machine, where the tool is operated.

[0065] Therefore, this is a three-step process to retrieve the succeeding tool for the next operation.

[0066] During this process, if the current tool operation finishes before the next tool is retrieved to the transfer point, then an idle time occurs in the spindle.

[0067] This idle time is called a waiting time, and no machining can be performed during this period.

[0068] To increase productivity the waiting time should be minimized as much as possible.

[0069] This problem is referred to as TIP and the solution requires consideration of the tool reallocation problem, TRP, together as mentioned before.

[0070] These problems are kind of combinatorial optimization problems and can be formulated as a generalized “Traveling Salesman Problem” (TSP), where cities in the TSP correspond to tools in the TIP and distances in the TSP correspond to transfer times of tools in the TIP.

[0071] While the cost function of the TSP minimizes the total distance traversed by the salesman, the TIP minimizes the total production time.

[0072] The main difference is that, while the city locations are fixed and the optimal solution path is sought in TSP, the tool location sequence is known, and optimal tool place indices are sought in the TIP.

[0073] Despite their differences, the main idea is the same in both problems, i.e., they both seek solutions to find optimal traversing times either by changing city paths or by changing tool places.

[0074] In the following sections, the constraints of these problems and their formulations are explained, and proposed a genetic algorithm (GA) implementation, steps are given in detail.

Constraints

[0075] Working with CNC machines and magazines brings some constraints that are conditions of the optimization problem by their nature, and they should also be satisfied in the solution and the formulation. In the present case, the following constraints are defined: [0076] Each tool should be located at different locations. There should not be any duplicate place in the result set. [0077] Each tool has a size to the left and size to the right parameters, which are defined in half locations. Usually, these sizes are one, which is the minimum value. For bigger tools that cannot fit into one tool place, these values will be bigger than one. The bigger tools occupy half locations of the neighboring places and no tool can be located on the overlapped places. [0078] The magazine places can be enabled or disabled by the machine operators. No tool can be located at the disable locations. [0079] There are two types of tools that can exist in the magazine, which is “heavy” and “light” tools. As their name implies, the distinction is implemented based on the weight of the tools. The tool weight affects the time of the tool movement on the tool magazine. Time for returning a tool from the transfer point to a location and time to fetch a tool from a location to the transfer point varies according to tool weight.

Problem Formulation

[0080] The problem is defined as follows: [0081] List of tools T = t.sub.1, t.sub.2, ..., t.sub.N, which are ordered in accordance with occurrences of the manufacturing process, [0082] List of magazine places P = p.sub.1, p.sub.2, ..., p.sub.M, where M > N, [0083] Location function v(t.sub.i), which returns magazine place of tool t.sub.i, [0084] Operation times of each tool 0 = o.sub.1,o.sub.2, ..., o.sub.N, which are precalculated running the NC program once, [0085] Transfer time function G(t.sub.i, p.sub.m) which returns transferring time of tool t.sub.i from one magazine location p.sub.m to transfer point (robot arm) or vice versa from transfer point (robot arm) to one magazine location p.sub.m, [0086] Transfer time function R(p.sub.n, p.sub.m) that returns transferring time of an empty robot arm from one magazine location pm to another magazine location p.sub.n,

[0087] Where the aim is to allocate appropriate locations for tools such that the total execution time of the NC program is minimum. The problem can be formulated as follows:

[0088] Find locations of tools, V, which minimizes the cost function:

[00007]$C={\displaystyle {.Math.}_{1=2}^N\left(o_i+max\left(0,M{T}_i-o_i\right)\right)}$

Where

[00008]$M{T}_i=G\left(t_{i-1},v\left(t_{i-1}\right)\right)+R\left(v\left(t_{i-1}\right),v\left(t_{i+1}\right)\right)+G\left(t_{i+1},v\left(t_{i+1}\right)\right)$

[0089] represents the moving time of the robot arm, which includes: [0090] Transference time of the previous tool that has finished its cutting from transfer point to its old place. [0091] Transference time of the empty robot arm from the place of the previous tool to the place of the next tool that will be retrieved. [0092] Transference time of the next tool from its place to the transfer point.

[0093] And the part max(0,MT.sub.i - o.sub.i) represents the waiting time of the t.sub.i, in case retrieval of the next tool t.sub.i+1 takes longer than the operation time of current tool t.sub.i.

[0094] The tool location sequence is predefined by a manufacturing process by the list of tools T = t.sub.1,t.sub.2, ..., t.sub.N.

[0095] The tools are arranged at locations represented by the location function v(t.sub.i), which is the objective of the invention.

[0096] FIG. 1 shows an exemplary tool movement at a CNC machine.

[0097] Here, spindle magazines SP1-SP6, SP10-SP14 and SP20-SP21 with predefined locations can be seen.

[0098] Three tools exist in this scenario, they are: [0099] i) tool T1, which is the previously used tool and it should be returned to its previous location, [0100] ii) tool T2, which is in the tool holder TH, i.e., the spindle and currently cutting a piece, and [0101] iii) tool T3, which is the next tool that will be used and should be retrieved to the transfer point TP.

[0102] In FIG. 1, the numbers below the tools T1, T2, T3 indicate the respective operation times o.sub.T1, o.sub.T2, o.sub.T3 in seconds.

[0103] For this example, [0104] the operation time o.sub.T2 of tool T2 is 9 s, [0105] the returning time of preceding tool G(t.sub.T1, v(t.sub.T1)), the so-called first transfer time function, is 3 s, [0106] the empty movement time from preceding tool location to the succeeding tool location R(v(t.sub.ry), v(t.sub.t3)), the so-called second transfer time function, is 4 s, and [0107] the pick-up time of succeeding tool to the transfer point G(t.sub.T3, v(t.sub.T3)) is 5s.

[0108] The waiting time for this example is 3 s by

[00009]$max\left(0,\left[\left(G\left(t_{T1},v\left(t_{T1}\right)\right)+R\left(v\left(t_{T1}\right),v\left(t_{T3}\right)\right)\right)+G\left(t_{T3},v\left(\left(t_{T3}\right)\right)\right)-o_{\text{T}2}\right]\right).$

TRP Joined TIP

[0109] The second problem is the TRP and it is jointly solved with the TIP.

[0110] Transferring tools from their initial locations to optimal index locations requires a significant amount of time in some cases, especially if the result contains a massive number of tool reallocations or contains long tool traveling distances.

[0111] Therefore, in such cases, instead of having a most optimal solution that requires many transferring times, having a slightly less optimal solution with less tool transferring time might be superior in terms of productivity.

[0112] This is an important part of the entire optimization.

[0113] The concept foresees addition of the time required for the reallocation of tools to the cost function of GA and adapt the algorithm.

[0114] Secondly, the number of manufactured pieced is also important, while considering the TRP from a profitability perspective.

[0115] Previously, it was said that the main goal is to reduce the waiting time in the spindle and increase productivity with extended GA solutions.

[0116] The resultant target allocation may cause the following case: Some tools must first be transported away from their original magazine location before any other tool can be placed in this location.

[0117] The question arises on how the initial tool allocation can be transferred to the target allocation such that the sum of all transfer times is minimized.

[0118] Therefore, besides the minimization of waiting times, the reallocation time of the tools is also considered in this problem in two perspectives:

[0119] I. The first one is the effect of a reallocation factor α on optimization results. In order to investigate the effect of the reallocation factor α, the cost function as defined above as C is extended following: [0120] a list of tools to be placed in a target location that differs from initial location Tr = tr.sub.1, tr.sub.2, ..., tr.sub.X, [0121] a target location function vt(tr.sub.j), which returns target location for tool tr.sub.j, [0122] the reallocation factor α is in the range between 0 and 1, allowing to reformulate the cost function: where represents total reallocation time RT for a solution.

[0123] In other words, the relocation factor is a representation whether a relocation of a tool from a first location to a second location is expensive, e.g., time consuming. Consequently, such a tool relocation should be avoided, which is expressed by a respective high weight of the relocation factor at the optimization process.

[0124] The relocation factor is a weight value between zero and one.

[0125] II. The second one is the productivity perspective. The estimated count for NC Program execution is taken as a parameter to the GA solution and, in accordance with this run count, the most optimized solution is provided as a result.

[0126] In order to consider reallocation time over productivity, the cost function as defined above is extended, with ρ as the estimated count factor for NC Program execution, as following:

[00012]$C{P}_2=\left(C\times \rho \right)+RT$

In other words, the count factor is a representation of whether a tool is often used within a predefined manufacturing sequence. Consequently, the weight of the dedicated manufacturing step is high if often used, i.e., the weight within the optimization procedure is important and the respective count factor value is also high.

[0127] The count factor is a weight value between zero and one.

GA Steps

[0128] GA is a type of metaheuristic algorithms and has proved that it is very effective in optimization problems.

[0129] The GA implementation includes five main steps: [0130] 1. Random initial population creation: The very first step of the GA is to start with randomly generated chromosomes. The number of the initial population is defined by the “initial population” hyperparameter. The created solutions are composed of tool location sequences, which are called “genes”. The length of the solution is defined by the number of tools used in the NC program used for the cutting. [0131] 2. Ranking the solutions: The ranking is the second step of the GA method. It is done based on the “fitness” function, whose details will be provided below. The solutions with less cutting time in total are ranked before the others. [0132] 3. Selection: The third step of the GA is to select the solutions for the next generation and for the mutation. Solutions with low fitness function scores are eliminated in this step. Elite chromosomes/solutions are always carried to the next generation without any modification or mutation. The size of the elite ones is determined by another hyperparameter called “elite size”. The selection methodology used here is “Fitness proportionate selection” also known as “roulette wheel selection”. This selection method aims to select potentially useful solutions for the next generations. After the elites are directly carried to the next generation, other solutions are selected by giving chance proportional to their fitness score and carried to the next generation after crossover and mutation. Therefore, the solution having a lower cost (i.e., the better solution) has a better chance of being selected with this selection method. [0133] 4. After the selection, the next step is to apply crossover, where different options for this are applicable. Ordered Crossover (OX) outperforms the other crossover techniques known in the art, because it selects more uniformly distributed genes over parents. [0134] 5. Mutation: The last step is the mutation of the found solutions. “mutation rate” hyperparameter is used here to decide whether to mutate the current solution or not. [0135] 6. The above process is repeated as a predefined “generation count” hyperparameter.

[0136] In genetic algorithms and evolutionary computation, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new solutions from an existing population and is analogous to the crossover that happens during sexual reproduction in biology.

[0137] Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions are typically mutated before being added to the population.

[0138] A mutation in the context of the present invention designates a change of a tool location within a tool location sequence used within the optimization procedure.

[0139] FIG. 2 shows an embodiment of the method in accordance with the invention.

[0140] The GA method starts with generating in step A “initialPopulation()” of a randomized initial set 1 of possible solutions.

[0141] Each solution is represented using a “gene”.

[0142] Next, in step B “rankPossibleSolutions()”, the solutions are ranked according to the “fitness” function as ranked, i.e., sorted population data 2.

[0143] At this stage, in step C “selection()”, using specialized selection methods, solutions of low fitness are eliminated, and selected individuals 3 are further processed.

[0144] The next-generation solutions are developed by a process in step D “treedPopulation()”, which mimics mutation and mating in natural selection and result in a new population with children and elites 4.

[0145] The cycle is accordingly repeated for the next, mutated population 5, performed at step E, until a predefined termination criterion is achieved.

[0146] Thus, while there have been shown, described and pointed out fundamental novel features of the invention as applied to a preferred embodiment thereof, it will be understood that various omissions and substitutions and changes in the form and details of the methods described and the devices illustrated, and in their operation, may be made by those skilled in the art without departing from the spirit of the invention. For example, it is expressly intended that all combinations of those elements and/or method steps which perform substantially the same function in substantially the same way to achieve the same results are within the scope of the invention. Moreover, it should be recognized that structures and/or elements and/or method steps shown and/or described in connection with any disclosed form or embodiment of the invention may be incorporated in any other disclosed or described or suggested form or embodiment as a general matter of design choice. It is the intention, therefore, to be limited only as indicated by the scope of the claims appended hereto.