The invention related to a method for manufacturing a work- piece with a predefined sequence of machine tools by a com- puter-controlled manufacturing machine with an optimal tool configuration .

The so called "Tool Indexing Problem" (TIP) for Computer Nu- meric Control (CNC) machines arise in manufacturing due to highly-complex cutting operations and the need for optimal placement of tools in the magazine slots.

The sequence of machine tools defines the manufacturing pro- cedure of the workpiece.

The solution of TIP causes a new problem of how tools can be transferred from their initial locations, i.e. positions, to the optimized locations such that the sum of all transfer times is minimized, which can be named as "Tool Replacement Problem" (TRP).

It is a very complex and time-consuming task, especially for big magazines, which contains many tools. To have a complete optimization in the whole manufacturing process both problems should be considered together. In fact, in cases where tool replacement takes more time than the gain obtained by tool place indexing optimization, cannot be considered as an im- provement.

It is the objective of the invention to solve the "Tool Re- placement Problem" as described before in such a way, that it can be executed of edge devices, i.e. computing devices with limited calculation capabilities.

The problem is solved by a method as mentioned before, wherein the tools are located at respective locations set by the tool configuration, and which are assigned to respective, precalculated operation times, and the machine has a tool transfer point and a tool handler for moving a selected tool from the respective location to the transfer point, and fol- lowing steps are executed: a) Allocating the initial locations of the tools, and cal- culating for all tools al) a first transfer time function, returning the time between the respective location and the transfer point, a2) a second transfer time function, returning the 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 for possible tool location sequences a re- spective first cost factor using a first cost function using the first transfer time function and second transfer time function, d) Ranking of tool location sequences obtained in step c) according to the respective first cost factor, and using a subset of the tool location sequences with the lowest first cost factor as a selected set of tool location sequences, and exploring new tool location sequences based on the selected set of tool location sequences and add the new tool location sequences to the selected set of tool lo- cation sequences, continuing with step c) to calculate the cost function and perform the ranking and selection and exploration till a predefined parameter for the number of itera- tions is reached, define the selected set of tool location sequences with the lowest cost function as the optimal tool configura- tion, e) transferring the tools from their initial locations to the optimal locations according to the optimal tool configuration, f) manufacturing the workpiece with the optimal tool con- figuration by the manufacturing machine.

Thus, it is achieved that the optimal tool location sequence considers the initial tool arrangement as well as the tool movements of the tool handler and consequently, an overall optimized tool location sequence, or sequence of tool posi- tions, in applied to the manufacturing of the workpiece.

In the context of the present invention said machine tools relate to the tools used at a single computer-controlled man- ufacturing machine. Besides the tool indexing problem, re- placing tools from their initial locations to optimal loca- tions is another problem and takes a lot of time. Solving these two problems jointly will lead to higher time savings than solving individually. Having optimal tool places will reduce the running time of NC Program - in fact the manufac- turing time for workpieces - by decreasing the waiting time in the spindle. Moreover, those tools will be transferred to their optimal locations in an optimal way.

It is clear, that the optimal sequence becomes more relevant in the context of the invention when the number of used tools is increasing. In particular, the invention can play off its advantages if the number of used tools is at least three or five, preferably at least ten or twenty, more preferably at least fifty or hundred or more.

The invention solves these problems in a remarkably short time and needs less memory compared to brute force approaches, therefore more convenient for huge box magazines which contain hundreds of tools.

The invention can save time and enhance productivity compared to brute force approaches or studies in the literature which do not consider TRP with TIP jointly.

Further, there is no need for payment to 3rd party libraries. Moreover, this solution does not require the OSS clearing.

At a glance, the invention is suitable for software platforms with limited computing capabilities, like edge devices.

The invention starts with an arbitrary set of tool location sequences and develops improved new tool location sequences in order to find a tool location sequence with a relatively optional cost factor.

The result is not an absolute optimal solution, but allows the computation of a very good solution, but with signifi- cantly reduced costs.

The exploration of new tool location sequences is advanta- geous since new assessments of tool location sequences can be performed based of tool location sequences, which are already identified as good tool location sequences with a low fitness function value. Consequently, it is foreseen, that two se- lected tools sequences are combined in a way that a new se- quence is obtained with parts from selected sequences. The probability is high, that such combinations provide also a good new sequence with a low fitness function value.

In a further development of the invention, it is foreseen that the first cost function is defined according to the fol- lowing dependency: with where

C ... first cost function,

G ... first transfer time function,

R ... second transfer time function,

0 ...operation time function,

MT ...moving time of tool changing device.

The first cost function allows a simple calculation of a fit- ness function, which can be used to assess the performance of a dedicated tool location sequence. However, other fitness functions are applicable for the assessment of the cost for accessing a tool.

In a further development of the invention, it is foreseen that a respective second cost factor is calculated for the selected set using a second cost function, considering fur- ther the time required for the reallocation of tools, using the first cost factor, and further a reallocation factor re- garding the impact of a single manufacturing step including the reallocation time on the optimization or alternatively a count factor regarding the impact of the number of occur- rences of a single manufacturing step on the overall manufac- turing.

This aspect allows further to improve the calculation of the applied cost function related to specific embodiments, like the incorporation of a relocation factor related to specific tool which are expensive to change, or a count factor related to the number of produced workpieces. In a further development of the invention, it is foreseen that the second cost function is defined according to the following dependency:

CP ₁ = C+ αXRT) with where

CP ₁ ... second cost function Type 1 (relocation factor), α reallocation factor

R reallocation time,

RT ... total reallocation time.

This aspect allows to improve the cost function by incorpo- rating a relocation factor related to specific tool which are expensive to change, and thus, which e.g. shouldn't be con- sidered within the optimization procedure at all or at least with a low priority, i.e. weight.

In a further development of the invention, it is foreseen that the second cost function is defined according to the following dependency:

CP ₂ = (C X p)+ RT with where

CP ₂ ... second cost function Type 2 (count factor),

P count factor

R reallocation time

RT total reallocation time. This aspect allows to improve the cost function by incorpo- rating a count factor related to the number of produced work- pieces which has a high impact on the optimization procedure when repeated frequently.

In a further development of the invention, it is foreseen that the exploration of new tool location sequences includes the application of a genetic crossover function, where two tool location sequences from the selected set are combined to a new tool location sequence. Genetic crossover is described further below.

Thus, the exploration of new tool location sequences can be performed in an easy way by combining already identified good tool location sequences with a low value of the cost factor.

In a further development of the invention, it is foreseen that the exploration of new tool location sequences includes the application of a mutation function, where tool locations within a tool location sequence from the selected set is ex- changes, preferably randomly exchanged.

Thus, the exploration of new tool location sequences can be performed in an easy way by mutations, which is described further below.

Crossover functions are known in the art but applying an or- dered crossover function can lead in the context of the in- vention to an improved selection of the candidate for the op- timal tool location sequence.

In genetic algorithms (GA) 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 gen- erate new solutions from an existing population, and analo- gous to the crossover that happens during sexual reproduction in biology. In some genetic algorithms, not all possible chromosomes rep- resent valid solutions. In some cases, it is possible to use specialized crossover and mutation operators that are de- signed to avoid violating the constraints of the problem. The problem is solved by a computer-controlled manufacturing machine with machine tools, comprising a control device with a memory for determining an optimal sequence of the tools for manufacturing a workpiece, wherein the tools are located at respective locations and which are assigned to respective, precalculated operation times, and the machine has a tool transfer point and a tool handler for moving a selected tool from the respective location to the transfer point, wherein the control device is configured to execute the method ac- cording to the invention. The invention is explained in more detail below with refer- ence to an embodiment shown in the accompanying drawings. In the drawings shows:

Fig. 1 an example of a tool handling sketch at a CNC ma- chine during machining, Fig. 2 an embodiment of the method according to the inven- tion.

The total production time for machining a workpiece in CNC machines considers two parts: i) the machining time when the tool is machining mate- rial, line cutting or drilling, and ii) the non-machining time when the robot arm is moving on the magazine to retrieve the succeeding tool or the tools are being switched by the gripper in the magazine. The machining of a workpiece is done with a specified se- quence of tools and any tool can be used several times in this sequence.

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 even- tually bring it to the tool transfer point, from which a se- lected tool is picked up by a tool holder, e.g. a spindle, of the machine, where the tool is operated.

Therefore, this is a three-step process to retrieve the suc- ceeding tool for the next operation.

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.

It is called waiting time, and no machining can be performed during this period.

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

This problem is called as TIP and the solution requires to consider tool reallocation problem, TRP, together as men- tioned before.

These problems are kind of combinatorial optimization prob- lems and can be formulated as a generalized "Traveling Sales- man Problem" (TSP), wherein cities in TSP correspond to tools in TIP and distances in TSP correspond to transfer times of tools in TIP.

While the cost function of the TSP minimizes the total dis- tance traversed by the salesman, the TIP minimizes the total production time.

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 indi- ces are sought in TIP.

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

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

Working with CNC machines and magazines brings some con- straints that are conditions of the optimization problem by their nature and they should be satisfied in the solution and the formulation as well. In the present case following con- straints are defined:

• Each tool should be located at different locations.

There should not be any duplicate place in the result set.

• Each tool has a size to the left and size to the right parameters, which are defined in half locations. Usu- ally, 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.

• The magazine places can be enabled or disabled by the machine operators. No tool can be located at the disable locations .

• There are two types of tools can exist in the magazine, which is "heavy" and "light" tools. As their name im- plies the distinction is done 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 ac- cording to tool weight.

Problem Formulation

The problem is defined as follows:

List of tools T = t ₁ , t ₂ , ... , t _N , which are ordered according to occurrences of the manufacturing process,

List of magazine places P = p ₁ ,p ₂ , ... ,p _M , where M > N,

Location function ν(t _i ), which returns magazine place of tool t _{i ,}

Operation times of each tool 0 = 0 ₁ , 0 ₂ , ..., 0 _N , which are precalculated running the NC program once,

Transfer time function G(t _i ,p _m ) which returns transfer- ring time of tool t _i from one magazine location p _m to transfer point (robot arm) or vice versa,

Transfer time function R(p _n, P _m ) which returns transfer- ring time of empty robot arm from one magazine location pm to another magazine location p _n , 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:

Find locations of tools, V, that minimizes the cost func- tion:

Where represents the moving time of the robot arm, which includes:

• Transferring time of the previous tool that has finished its cutting from transfer point to its old place.

• Transferring time of the empty robot arm from the place of the previous tool to the place of the next tool which will be retrieved.

• Transferring time of the next tool from its place to the transfer point.

And the part max(0,MT _i — O _i ) represents the waiting time of the t _i , in case of retrieving the next tool t _i+1 takes longer than the operation time of current tool t _i .

The tool location sequence is predefined by a manufacturing process by said list of tools T = t ₁ , t ₂ , ... , t _N .

The tools are arranged at locations represented by said loca- tion function ν(t _i ) , which is the objective of the invention.

Fig . 1 shows an example for a tool movement at a CNC machine.

Spindle magazines SP1-SP6, SP10-SP14 and SP20-SP21 with pre- defined locations can be seen.

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

In the figure, the numbers below the tools Tl, T2, T3 indi- cate the respective operation times 0 _T1 ,0 _T2 ,0 _T3 in seconds.

For this example, • the operation time 0 _T2 of tool T2 is 9s,

• the returning time of preceding tool G(t _T1 , v(t _T1 )), the so- called first transfer time function, is 3s, the empty movement time from preceding tool location to the succeeding tool location R(v(t _T1 ),v(t _T3 )), the so- called second transfer time function, is 4s, and

• the pick-up time of succeeding tool to the transfer point G(t _T3 , v(t _T3 )) is 5s.

The waiting time for this example is 3s by

TRP joined TIP

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

Transferring tools from their initial locations to optimal index locations requires lots of time in some cases espe- cially if the result contains a massive number of tool real- locations or contains long tool traveling distances.

Therefore, in such cases instead of having a most optimal so- lution which requires many transferring times, having a slightly less optimal solution with less tool transferring time might be superior in terms of productivity.

This is an important part of the whole optimization.

The concept foresees to add the time required for the reallo- cation of tools to the cost function of GA and adapt the al- gorithm.

Secondly, the number of manufactured pieced is also important while considering the TRP from a profitability perspective. Previously, it was said that the main goal is to reduce the waiting time in the spindle and increase productivity with extended GA solutions.

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.

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.

Therefore, besides the minimization of waiting time, the re- allocation time of tools is also considered in this problem in two perspectives:

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 de- fined above as C is extended following:

• a list of tools to be placed in a target location that differs from initial location

• a target location function vt(tr _j ), which returns target location for tool tr _j ,

• the reallocation factor a is in the range between 0 and 1, allowing to reformulate the cost function:

CP ₁ = C + (α X RT) where represents total reallocation time RT for a solution. In other words, the relocation factor is a representa- tion whether a relocation of a tool from a first loca- tion to a second location is expensive, e.g. time con- suminq. Consequently, such a tool relocation should be avoided, which is expressed by a respective high weight of the relocation factor at the optimization process.

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

II. The second one is the productivity perspective. The esti- mated count for NC Program execution is taken as a param- eter to the GA solution and according to this run count, the most optimized solution is provided as a result.

In order to consider reallocation time over productivity, the cost function as defined above is extended, with p as the estimated count factor for NC Program execution, as following: cp ₂ = (C X p)+ RT

In other words, the count factor is a representation whether a tool is often used within a predefined manufac- turing sequence. Consequently, the weight of the dedi- cated 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.

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

GA Steps

In this section implementation details of the GA are ex- plained. GA is a type of metaheuristic algorithms and has proved that it is very effective in optimization problems.

The GA implementation includes five main steps:

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 de- fined by the "initial population" hyperparameter. The created solutions are composed of tool location se- quences, which are called "genes". The length of the so- lution is defined by the number of tools used in the NC program used for the cutting. Ranking the solutions: The ranking is the second step of the GA method. It is done based on the "fitness" func- tion, whose details will be provided below. The solutions with less cutting time in total are ranked before the others. Selection: The third step of the GA is to select the so- lutions for the next generation and for the mutation. So- lutions with low fitness function scores are eliminated in this step. Elite chromosomes/solutions are always car- ried to the next generation without any modification or mutation. The size of the elite ones is determined by an- other hyperparameter called "elite size". The selection methodology used here is "Fitness proportionate selec- tion" also known as "roulette wheel selection". This se- lection method aims to select potentially useful solu- tions for the next generations. After the elites are di- rectly carried to the next generation, other solutions are selected by giving chance proportional to their fit- ness 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. After the selection, the next step is to apply crossover, wherein different options for this are applicable. Or- dered Crossover (OX) outperforms the other crossover techniques known in the art, since it selects more uni- formly distributed genes over parents. 5. Mutation: The last step is the mutation of the found so- lutions. "mutation rate" hyperparameter is used here to decide whether to mutate the current solution or not.

6. The above process is repeated as a predefined "generation count" hyperparameter.

In genetic algorithms and evolutionary computation, crosso- ver, 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.

Solutions can also be generated by cloning an existing solu- tion, which is analogous to asexual reproduction. Newly gen- erated solutions are typically mutated before being added to the population.

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.

Fig . 2 shows an embodiment of the method according to the in- vention .

The GA method starts with generating in step A "initialPopu- lation ()" of a randomized initial set 1 of possible solu- tions.

Each solution is represented using a "gene".

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

At this stage, in step C "selection () ", using specialized se- lection methods, solutions of low fitness are eliminated, and selected individuals 3 are further processed. The next-generation solutions are developed by a process in step D "treedPopulation () ", that mimics mutation and mating in natural selection and result in a new population with children and elites 4. The cycle is repeated according for the next, mutated popula- tion 5, performed at step E, until a predefined termination criterion is achieved.

List of Reference Numerals:

1-5 data output

A-E method steps, function calls

SP1-SP6, SP10-SP14 SP20-SP21 spindle magazine, predefined locations

T1, T2, T2 tool

TH tool holder, spindle

TP tool transfer point