METHOD FOR OPTIMIZING THE OCCUPANCY OF MAGAZINE SPACES BY TOOLS IN A COMPUTER-SUPPORTED MANNER

Abstract

Provided is a method for optimizing the occupancy of magazine spaces by tools within at least one tool magazine for a machine tool in a computer-supported manner, including: detecting a quantity of magazine spaces in at least one tool magazine, detecting a first quantity of tools which occupy at least one magazine space and the magazine spaces occupied by the tools, detecting a second quantity of tools which are to be additionally received in the at least one tool magazine, detecting the required space and optionally at least one other property for each tool, detecting a quantity of allowed magazines spaces for each tool, detecting a quantity of allowed magazine space pairs, wherein a first tool can be placed on a first magazine space of the magazine space pair, and optimizing the occupancy of the magazine spaces.

Claims

1. A method for a computer-aided optimization of an occupancy of magazine spaces with tools within at least one tool magazine for a machine tool, the method comprising: a) acquiring a set of magazine spaces in at least one tool magazine; b) acquiring a first set of tools that occupy at least one magazine space, and occupied magazine spaces, c) acquiring a second set of tools that are additionally to be received in the at least one tool magazine; d) acquiring a space requirement and at least one further property for each tool; e) acquiring a respective set of permissible magazine spaces for each tool, wherein a permissible magazine space depends on a space requirement and/or at least one further property of the tool and/or a property of the magazine space; f) acquiring a set of permissible magazine space pairs, wherein a first tool is able to be placed in a first magazine space of the magazine space pair that is permissible for the first tool, and a second tool is able to be placed in the second magazine space of the magazine space pair that is permissible for the second tool, without any collision with respect to respective space requirement, and acquiring a size of a free gap between the first already placed tool and the second already placed tool; and g) optimizing the occupancy of the magazine spaces with tools of the first set and at least one tool to be received from the second set, such that the number of relocations of the tools from the first set required due to a reception of the tool is minimized, wherein the required relocations and placements of the tools from the second set are performed in a compact manner such that a sum of the sizes of the free gaps between two adjacently placed tools is minimized and the magazine space pair of these adjacently placed tools is from the set of magazine space pairs permissible for the tool pair.

2. The method as claimed in claim 1, wherein the optimization step g) is repeated multiple times until all of the tools of the second set have been received in the magazine.

3. The method as claimed in claim 1, wherein the tools are picked up and/or relocated by a magazine device of the tool magazine in accordance with the optimized occupancy.

4. The method as claimed in claim 1, wherein a subset of the tools from the first set that are not allowed to be relocated in each case either by the optimization or by the reception of a tool in another magazine space is predefined.

5. The method as claimed in claim 1, wherein for a subset of the tools from the second set, additionally permissible magazine spaces are acquired and the optimization is performed such that these tools are placed in the respectively permissible acquired magazine spaces.

6. The method as claimed in claim 1, wherein the optimization is performed by way of mixed integer linear optimization.

7. A control apparatus for computer-aided optimization of the occupancy of magazine spaces with tools within at least one tool magazine for a machine tool, the control apparatus comprising: a) a first acquisition unit that is configured to acquire a set of magazine spaces in at least one tool magazine; b) a second acquisition unit that is configured to acquire a first set of tools that occupy at least one magazine space and occupied magazine spaces; c) a third acquisition unit that is configured to acquire a second set of tools that are additionally to be received in the at least one tool magazine; d) a fourth acquisition unit that is configured to acquire a space requirement for each tool and at least one further property for each tool; e) a fifth acquisition unit that is configured to acquire a respective set of permissible magazine spaces for each tool, wherein a permissible magazine space depends on the space requirement and/or at least one further property of the tool and/or a property of the magazine space; f) a sixth acquisition unit that is configured to acquire the set of permissible magazine space pairs, wherein a first tool is able to be placed in a first magazine space of the magazine space pair that is permissible for the first tool and a second tool is able to be placed in the second magazine space of the magazine space pair that is permissible for the second tool without any collision with respect to respective space requirement, and to acquire a size of a free gap between the first already placed tool and the second already placed tool, and g) an optimization unit that is configured to optimize the occupancy of the magazine spaces with tools of the first set and at least one tool to be received from the second set, such that the number of relocations of the tools from the first set required due to the reception of the tool is minimized, wherein the required relocations and placements of the tools from the second set is performed in a compact manner such that a sum of the sizes of free gaps between two adjacently placed tools is minimized and the magazine space pair of these adjacently placed tools is from the set of magazine space pairs permissible for the tool pair.

8. The control apparatus as claimed in claim 7, wherein a subset of the tools from the first set that are not allowed to be relocated in each case either by the optimization or by the reception of a tool in another magazine space is predefined.

9. A computer program product, comprising a computer readable hardware storage device having computer readable program code stored therein, said program code executable by a processor of a computer system to implement the method as claimed in claim 1 when it runs on a control apparatus or is stored on a computer-readable medium.

Description

BRIEF DESCRIPTION

[0053] Some of the embodiments will be described in detail, with references to the following Figures, wherein like designations denote like members, wherein:

[0054] FIG. 1 shows conventional spaces in a rack magazine, wherein the main side is arranged on the right and the opposite side is arranged on the left,

[0055] FIG. 2A shows a simplified example of a rack magazine with magazine spaces,

[0056] FIG. 2B shows one example of permissible and impermissible space assignments,

[0057] FIG. 3A shows a starting occupancy;

[0058] FIG. 3B shows a permissible occupancy following the addition of two tools;

[0059] FIG. 4A shows a simplified example of a rack magazine with magazine spaces;

[0060] FIG. 4B shows an exemplary magazine with subspaces; and

[0061] FIG. 4C shows an exemplary magazine with subspaces.

DETAILED DESCRIPTION

[0062] One special case of optimization methods is that of linear optimization. This deals with the optimization of linear objective functions over a set that is restricted by linear equations and inequalities. It forms the basis for (mixed) integer linear optimization solution methods. A so-called solver is a collective term for special mathematical computer programs that are able to numerically solve mathematical problems. In connection with MILP (mixed integer linear programming), standard solvers, such as for example CPLEX, Scip, Gurobi and Xpress, may be used for IP programs (integer optimization models).

[0063] One example is described below in which computer-aided optimization of the occupancy of magazine spaces with tools within at least one tool magazine for a machine tool is performed by way of an MILP (mixed integer linear programming) model. This process may be performed independently of the heuristics and repositioning methods described above.

[0064] Since the removal of tools only leads to additional free magazine spaces and also does not have any further influence or restrictions for the desired optimized occupancy of the magazine spaces, the removal of the tools is already ruled out in the example, and tools are only added to the magazine.

[0065] The optimization calculation therefore has to be performed by a control device quickly enough that it is able to be used as part of an interactive process in which the reception of the tools successively leads to a permissible result.

[0066] The following are acquired as input parameters:

[0067] The set of tools located in the magazine with their occupied magazine spaces.

[0068] The set of tools to be inserted into or received in the magazine.

[0069] For each tool located in or to be added to the magazine [0070] its space requirement, [0071] the magazine spaces permissible for this tool, [0072] the magazine spaces preferred for this tool, [0073] the set of magazine spaces available in the magazine.

[0074] The result is an optimized occupancy of the magazine spaces. In this case, the following values may be output: [0075] yes-no statement (1-0 value) as to whether there is a permissible magazine space assignment under the given requirements.

[0076] In the case of a yes statement regarding the permissibility, the following are furthermore output: [0077] For each tool to be inserted, its allocated magazine space. [0078] For each tool located in the magazine and to be relocated, its new allocated magazine space.

[0079] The complexity when filling the rack magazine results from the space restrictions to be complied with for the tools. On the one hand, not every tool is allowed to be stored in every space. For instance, in some magazines, there are special permissible spaces for the property “heavy” of the tools or the property “particularly long” of the tools. The set of magazine spaces in which a specific tool is able to be placed are referred to as magazine spaces permissible for the tool. The permissible magazine spaces for a tool are not all of the same good suitability. A subset of the permissible spaces may therefore be distinguished as preferred spaces for a tool. In addition to these restrictions, restrictions also arise due to the space requirement of the tools in the magazine. Tools may also protrude beyond the area of a magazine space due to their size. This may lead to restrictions for spaces at the magazine edge or caused by other tools in the magazine.

[0080] The following input parameters may additionally expediently be added: [0081] The set of tools provided with a set magazine space. [0082] The set of tools to be inserted in a set space with their magazine spaces.

[0083] FIG. 2A shows a simplified rack magazine R with magazine spaces P, these being indicated by (1,1) to (1,5) for the first column, by (2,1) to (2,5) for the second and by (3,1) to (3,5) for the third column, by way of example.

[0084] The example thus depicts a rack magazine with 15 magazine spaces, arranged in three magazine columns and five magazine rows. FIG. 2A and FIG. 4A depict the indexing. For example, (2,3) thus denotes the magazine space in the second column and third row. FIG. 2B depicts permissible and impermissible magazine space assignments. In FIGS. 2B, 3A and 3B, tools are denoted by W1 to W9. The starting point in FIG. 2B is a magazine filled with a tool W1. W1 is denoted as a circle in terms of its space requirement, for example the tool radius. The tool W2 is additionally intended to be added to the magazine. W2 marked with (c) and W2 marked with (d) are permissible spaces and W2 marked with (a) and W2 marked with (b) are impermissible spaces. The space (1,1) is impermissible since W2(a) collides with the magazine edge there. The space (3,2) is likewise impermissible, since W2(b) collides with the tools W1 there. The spaces (1,3) and (2,4) are for example permissible, since W2(c) and W2(d) would not collide either with the edge or with W1 there.

[0085] FIGS. 3A and 3B illustrate a specific situation including a permissible space assignment by way of example. FIG. 3A depicts the starting situation of a magazine equipped with seven tools W1 to W7. The tools W2 and W7, with a dashed circle, are not allowed to be allocated to a new space. These accordingly each remain in a set space. All of the other tools are able to be relocated. Two further tools W8 and W9 are intended to be inserted into this magazine. Due to its space requirement, W9 cannot be stored on an upper or lower edge space (1,1), (2,1), (3,1), (1,5), (2,5), (3,5). W9 is also not able to be stored in the spaces (1,3), (2,3), (3,2) since it would collide with the non-movable tools W2 and W7 there. W8 on the other hand cannot be stored in the spaces (2,1) and (2,3), since it would collide with W2 there.

[0086] FIG. 3B depicts a permissible space assignment. Three tools located in the magazine have been relocated, these being illustrated in striped form, and the two new tools W8 and W9 have been inserted. The three tools W3, W4 and W6 have been relocated in order to create space for the tool W9.

[0087] The described problem is able to be solved in two stages. In the first stage, preprocessing, the problem is transformed into an equivalent simplified problem such that no further space restrictions caused by the magazine edge need to be taken into consideration. In the second stage, the simplified problem is formulated as an integer linear problem (MILP) and solved using a suitable solver. In the event of success, a permissible space assignment is determined in which the minimum possible number of tools located in the magazine is assigned to a new space. In the event of failure, there is no permissible space assignment for all of the tools to be added.

[0088] Two types of space restriction have been described in the above example: firstly collisions with the magazine edge and secondly collisions between tools in the magazine. The first type of restriction, magazine edge, depends only on the tool and the selected space. In other words, this type of restriction may be considered equivalently through space permissibility. Preprocessing removes, from the set of spaces permissible for a tool, all of the spaces at which there are collisions with the magazine edge. Following the preprocessing, each tool may thus be stored in an empty magazine in any space permissible for the tool.

[0089] The following designations apply in the MILP formulation:

[0090] Indices: [0091] L Set of all magazine spaces [0092] T Set of all tools [0093] T.sub.N Set of all tools to be inserted [0094] T.sub.O Set of all tools present in the magazine [0095] T.sub.F Set of all tools fixed in a set space, T.sub.F⊂T.sub.N∪T.sub.O. [0096] L.sub.t Set of all permissible spaces for tool t

[0097] Parameters [0098] l.sub.t The set space of tool t∈T.sub.F. [0099] l.sub.t The original space of tool t∈T.sub.O. [0100] cov.sub.t,l.sup.t Covered portion of the gap between the spaces l and l.sub.1, [0101] when tool t is located in space l, 0≤cov.sub.t,l.sup.t≤1.

[0102] Variables: [0103] setup.sub.t,l Space assignment of tool t to space l. (Value 1 when the tool is allocated to the space, and 0 otherwise.)

[0104] Using this notation, the problem may be formulated as the following integer linear program. The number of tools no longer located in their original space is to be minimized.

[0105] Minimization Function:

[00001]$\underset{t\in T_O}{.Math.}1-{\mathrm{setup}}_{t,l}$

[0106] Additional Conditions:

[0107] (1) Each tool must be allocated to a magazine space.

[00002]$\underset{t\in L}{.Math.}{\mathrm{setup}}_{t,l}=1,t\in T$

[0108] (2) No magazine space is allowed to be allocated multiple times.

[00003]$\underset{t\in T}{.Math.}{\mathrm{setup}}_{t,l}\le 1,l\in L$

[0109] (3) Only permissible magazine spaces are allowed to be allocated.

[00004]$\underset{t\in L\backslash L_T}{.Math.}{\mathrm{setup}}_{t,l}=0,t\in T$

[0110] (4) Fixed tools must be assigned to their set space.

setup.sub.t,l.sub.t=1, t∈T.sub.F

[0111] (5) Spaces covered by a tool are not allowed to be occupied by tools and two tools are not allowed to collide.

[00005]$\underset{t\in T}{.Math.}{\mathrm{cov}}_{l_1,l_2}^t.Math.{\mathrm{setup}}_{t,l_1}+\underset{t\in T}{.Math.}{\mathrm{cov}}_{t_2,t_1}^t.Math.{\mathrm{setup}}_{t,l_2}\le 1,l_1,l_2\in L,l_1\ne l_2$

[0112] These inequalities ensure that two tools are placed in a permissible magazine space pair. Magazine space pairs acquired or determined as permissible guarantee collision-free occupancy thereof with tools in terms of their respective space requirement.

[0113] This integer program has exactly one solution when there is a permissible space assignment of the tools in the magazine in which the fixed tools are each assigned their set space.

[0114] The last-mentioned group of restrictions (5), for taking into consideration the space requirements of the tools, comprise a large number of superfluous inequalities. For many magazine space pairs l.sub.1,l.sub.2∈L,l.sub.1≠l.sub.2, these inequalities are always met because the two magazine spaces of the magazine space pair lie very far apart from one another. It makes sense to consider magazine space pairs in which there is a tool pair that is able to be stored in these magazine spaces and collides. If there is not such a tool pair, then the inequalities do not have any restrictive character and may be omitted.

[0115] Solutions to the above mathematical program may contain a large number of unwanted small empty spaces or free gaps between the placed tools. In particular when the magazine is not yet very full, the tools may be stored at a large number of different positions. When subsequently adding further tools to the magazine, the empty positions that are present may be too small for the new tools and force relocation of the tools already located in the magazine. It is therefore advantageous, right from the beginning of magazine occupancy, to act such that, where possible, small free gaps between tools are avoided. In order to achieve compact magazine occupancies as a solution, the above mathematical program may be expanded.

[0116] Variables: [0117] b.sub.l.sub.1.sub.,l.sub.2 Simultaneous occupancy of both spaces l.sub.1 and l.sub.2 by tools, such that no/small empty positions (the smallest possible size of the gap or no gap) remains between the tools. (Value 1 when both spaces are occupied without an empty position, and 0 otherwise.).

[0118] Additional Conditions:

[0119] (6) Identifying empty positions between tools.

[00006]$\underset{t\in T}{.Math.}{\mathrm{cov}}_{l_1,l_2}^t.Math.{\mathrm{setup}}_{t,l_1}+\underset{t\in T}{.Math.}{\mathrm{cov}}_{l_2,l_1}^t.Math.{\mathrm{setup}}_{t,l_2}\ge \alpha .Math.b_{l_1,l_2},l_1,l_2\in L,l_1\ne l_2$

[0120] The left-hand part of term (6), due to the above additional conditions (5), is able to be 1 at most. If a suitable number less than or equal to 1 is selected as α, then b.sub.l.sub.1.sub.,l.sub.2 is only able to adopt the value 1 when at least one component of α of the space between the positions l.sub.1, l.sub.2 is covered by the tools placed there. In other words, the variables b.sub.l.sub.1.sub.,l.sub.2 count the number of tools that are placed very close to one another. Using the following objective function:

[00007]$\underset{l_1,l_2\in L,l_1\ne l_2}{.Math.}{b}_{l_3,l_2}$

[0121] the tools are always placed as close as possible or adjacent to another tool in an optimum solution.

[0122] The control systems of machine tools offer various types of rack magazine management. One possible type, for example in sinumetric control systems, is the half-space model. A half-space is a special form of subspace. The subspace model allows for example a magazine space to be partially occupied by a tool. For the sake of clarity, consideration is given below to a magazine, shown for example in FIG. 4A, in which the columns are independent. In other words, in the example, only half-spaces above and below are considered. FIG. 4B schematically illustrates a magazine R with two columns and five rows. The spaces are indicated in FIG. 4A and the division into half-spaces HP is illustrated in FIG. 4B. FIG. 4C shows collision-free occupancy with three tools t1, t2 and t3 in the spaces (1,2), (1,4) and (2,1).

[0123] One special feature in the half-space model is that tools do not have to be symmetric. Tool t1 takes up two half-spaces upwardly and downwardly, respectively. On the other hand, tool t2 takes up two half-spaces upwardly and three half-spaces downwardly (cf. FIG. 4C). Both tools overlap the space (1,3) but do not collide there, since they each cover only the upper, respectively lower, half-space.

[0124] The coverage parameter cov.sub.l,l.sup.t may be determined using the size of the gap as quotient of the size of the gap covered by t and the overall size of the gap. As a specific form with half-spaces, this coverage parameter corresponds to the quotient of the number of half-spaces located between them and covered by t and the total number of half-spaces located between them.

[0125] Although embodiments of the invention has been described and illustrated in more detail through the preferred exemplary embodiment, embodiments of the invention are not restricted by the disclosed examples, and other variations may be derived therefrom by a person skilled in the art without departing from the scope of protection of embodiments of the invention.

[0126] The processes or method sequences described above may be implemented on the basis of instructions that are present on computer-readable storage media or in volatile computer memories (referred to below collectively as computer-readable memories). Computer-readable memories are for example volatile memories such as caches, buffers or RAM and non-volatile memories such as interchangeable data carriers, hard drives, etc.

[0127] The functions or steps described above may in this case be present in the form of at least one set of instructions in/on a computer-readable memory. The functions or steps are in this case not tied to a particular set of instructions or to a particular form of sets of instructions or to a particular storage medium or to a particular processor or to particular execution schemes, and may be executed by software, firmware, microcode, hardware, processors, integrated circuits etc. operating on their own or in any combination. In this case, a wide variety of processing strategies may be used, for example serial processing by an individual processor or multiprocessing or multitasking or parallel processing, etc.

[0128] The instructions may be stored in local memories, but it is also possible to store the instructions on a remote system and access this via a network.

[0129] “Computer-aided” in connection with embodiments of the invention should be understood to mean for example an implementation of the method in which a processor in particular executes at least one method step of the method.

[0130] The term “processor”, “central signal processing”, “control unit” or “data evaluation means” as used here comprises processing means in the broadest sense, that is to say for example servers, universal processors, graphics processors, digital signal processors, application-specific integrated circuits (ASICs), programmable logic circuits such as FPGAs, discrete analog or digital circuits and any combinations thereof, including all other processing means known to a person skilled in the art or developed in the future. Processors may in this case consist of one or more devices or apparatuses or units. If a processor consists of multiple devices, these may be designed or configured for the parallel or sequential processing or execution of instructions. A “storage unit” in connection with embodiments of the invention may be understood to mean for example a memory in the form of working memory (random access memory, RAM) or a hard disk.

[0131] Although the present invention has been disclosed in the form of preferred embodiments and variations thereon, it will be understood that numerous additional modifications and variations could be made thereto without departing from the scope of the invention.

[0132] For the sake of clarity, it is to be understood that the use of “a” or “an” throughout this application does not exclude a plurality, and “comprising” does not exclude other steps or elements.