Allocation of printed circuit boards on fitting lines

Abstract

A fitting system is provided that includes a plurality of fitting lines for fitting printed circuit boards with electronic components. A method for allocating printed circuit boards to the fitting lines includes: (1) determining requirements for fitting each of a plurality of printed circuit boards with allocated components; and (2) allocating the printed circuit boards to fitting lines under predetermined conditions by integral linear programming. Equipment families are determined for the fitting lines on the basis of the allocation, and the allocation is repeated until a criterion has reached a predetermined threshold. The criterion is established on the basis of the number of equipment families of the fitting lines, where an equipment family includes a quantity of different components with which a fitting line may be fitted in order to fit a predetermined amount of printed circuit boards.

Claims

1. A method for allocating printed circuit boards to fitting lines of a fitting system for fitting the printed circuit boards with electronic components, the method comprising: detecting requirements for fitting a plurality of printed circuit boards with respectively allocated electronic components; allocating a subset of the printed circuit boards to fitting lines under predetermined specifications by integer linear programming; determining equipment families for the fitting lines on a basis of the allocation of the subset of the printed circuit boards; and carrying out a new allocation of a subset of the printed circuit boards until a criterion has reached a predetermined threshold, the criterion being formed on a basis of a number of equipment families of the fitting lines, wherein the criterion comprises a condition that: (1) the number of equipment families of each fitting line is greater than a respective predetermined threshold, (2) the number of equipment families of each fitting line is less than the respective predetermined threshold, or (3) differences between the number of equipment families of each fitting line are below the respective predetermined threshold.

2. The method as claimed in claim 1, wherein the condition is that the number of equipment families of each fitting line is greater than the respective predetermined threshold.

3. The method as claimed in claim 2, wherein the allocation of printed circuit boards in an equipment family to a fitting line is prevented when the equipment family is allocated less than a threshold number of printed circuit boards or less than a threshold track consumption.

4. The method as claimed in claim 2, wherein a change in the allocation of printed circuit boards of an equipment family to a fitting line is prevented when the equipment family is allocated greater than a threshold number of printed circuit boards or greater than a threshold track consumption.

5. The method as claimed in claim 1, wherein the condition is that the number of equipment families of each fitting line is less than the respective predetermined threshold.

6. The method as claimed in claim 5, wherein one of the predetermined thresholds is able to be individually predetermined for at least one of the fitting lines.

7. The method as claimed in claim 5, wherein the allocation of printed circuit boards in an equipment family to a fitting line is prevented when the equipment family is allocated less than a threshold number of printed circuit boards or less than a threshold track consumption.

8. The method as claimed in claim 5, wherein a change in the allocation of printed circuit boards of an equipment family to a fitting line is prevented when the equipment family is allocated greater than a threshold number of printed circuit boards or greater than a threshold track consumption.

9. The method as claimed in claim 2, wherein one of the predetermined thresholds is able to be individually predetermined for at least one of the fitting lines.

10. The method as claimed in claim 1, wherein the condition is that the differences between the number of equipment families of each fitting line are below the respective predetermined threshold.

11. The method as claimed in claim 1, wherein the allocation of printed circuit boards in an equipment family to a fitting line is prevented when the equipment family is allocated less than a threshold number of printed circuit boards or less than a threshold track consumption.

12. The method as claimed in claim 11, wherein a change in the allocation of printed circuit boards of an equipment family to a fitting line is prevented when the equipment family is allocated greater than the threshold number of printed circuit boards or greater than the threshold track consumption.

13. The method as claimed in claim 1, wherein a change in the allocation of printed circuit boards of an equipment family to a fitting line is prevented when the equipment family is allocated greater than a threshold number of printed circuit boards or greater than a threshold track consumption.

14. A computer program product with a program code on an execution device or stored on a computer-readable medium, the program code, when executed on the execution device, is configured to: detect requirements for fitting a plurality of printed circuit boards with respectively allocated components; allocate a subset of the printed circuit boards to fitting lines under predetermined specifications by integer linear programming; determine equipment families for the fitting lines on a basis of the allocation of the subset of the printed circuit boards; and carry out a new allocation of a subset of the printed circuit boards until a criterion has reached a predetermined threshold, the criterion being formed on a basis of a number of equipment families of the fitting lines, wherein the criterion comprises a condition that: (1) the number of equipment families of each fitting line is greater than a respective predetermined threshold, (2) the number of equipment families of each fitting line is less than the respective predetermined threshold, or (3) differences between the number of equipment families of each fitting line are below the respective predetermined threshold.

15. The computer program product as claimed in claim 14, wherein the condition is that the number of equipment families of each fitting line is greater than the respective predetermined threshold.

16. The computer program product as claimed in claim 15, wherein one of the predetermined thresholds is able to be individually predetermined for at least one of the fitting lines.

17. The computer program product as claimed in claim 14, wherein the condition is that the number of equipment families of each fitting line is less than the respective predetermined threshold.

18. The computer program product as claimed in claim 17, wherein one of the predetermined thresholds is able to be individually predetermined for at least one of the fitting lines.

19. The computer program product as claimed in claim 14, wherein the condition is that differences between the number of equipment families of each fitting line are below the respective predetermined threshold.

20. A control device for allocating printed circuit boards to fitting lines of a fitting system, the control device configured to: detect requirements for fitting a plurality of printed circuit boards with respectively allocated components; allocate a subset of the printed circuit boards to fitting lines under predetermined specifications by integer linear programming; determine equipment families for the fitting lines on a basis of the allocation of the subset of the printed circuit boards; and carry out a new allocation of a subset of the printed circuit boards until a criterion has reached a predetermined threshold, the criterion being formed on a basis of the number of equipment families of the fitting lines, wherein the criterion comprises a condition that: (1) the number of equipment families of each fitting line is greater than a respective predetermined threshold, (2) the number of equipment families of each fitting line is less than the respective predetermined threshold, or (3) differences between the number of equipment families of each fitting line are below the respective predetermined threshold.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 depicts one embodiment of a fitting system.

(2) FIG. 2 depicts an embodiment of equipment families in the fitting system from FIG. 1.

(3) FIG. 3 depicts an embodiment of a flowchart of an optimization method using integer linear programming.

DETAILED DESCRIPTION

(4) Linear optimization is one of the main methods in the field of mathematical optimization and deals with the optimization of linear target functions over a set that is restricted by linear equations and inequalities. Linear optimization is the basis of the solution methods of (e.g., mixed) integer linear optimization.

(5) Advantages of linear optimization include the following features: (1) global optimization approach; (2) easily expandable, (3) good commercial standard solvers (e.g., SCIP, CPLEX, Ilog, Xpress), which are widespread and proven in practice; and (4) for a determined solution, it is known how far away it is at most from the optimal solution (e.g., gap).

(6) FIG. 1 depicts a fitting system 100. The fitting system 100 includes a plurality of fitting lines 110 and a control device 115 for allocating printed circuit boards 120 to the fitting lines 110. Each fitting line 110 may include a transport system 125 and one or more fitting machines 130. Each fitting machine 130 includes one or more fitting heads 135 that are each set up to receive components from a constant table 140 or a variable table 145 and to position them at a predetermined position on the printed circuit board 120 that is on the transport system 125.

(7) During the fitting process, the printed circuit board 120 may be still with respect to the fitting machine 130. The tables 140, 145 each include a multiplicity of feeding devices 150, only one of which is illustrated by way of example. Each feeding device 150 keeps a supply of components 155 of a predetermined type ready. Although each feeding device 150 may be configured to keep different components 155 ready and different feeding devices 150 are fitted to a table 140, 145, the tables 140, 145 may be completely exchanged for reasons of speed if a fitting machine 130 is supplied with components 155 that are not kept on one of the fitted tables 140, 145.

(8) Since such a change may be associated with a production standstill, the aim is to keep the number of tables 140, 145 to be changed low. If a table is not exchanged during a conversion process, it is referred to as a constant table 140, otherwise it is referred to as a variable table 145. Otherwise, there are no functional differences between a constant table 140 and a variable table 145.

(9) The printed circuit board 120 is to be fitted with a number of different components 155. In order to minimize frequent changing of variable tables 145 and ideally to maximize a number of constant tables 140, the control device 115 is set up to optimize the allocation of a printed circuit board 120 to one of the fitting lines 110. In this case, specific properties of each fitting line 110 and of each fitting machine 130 may be taken into account just like properties of the printed circuit boards 120 and of the components 155 to be fitted on the latter.

(10) FIG. 2 depicts an illustration 200 of equipment families, which are also called clusters. A first printed circuit board 205, a second printed circuit board 210, and a third printed circuit board 215, which each correspond to one of the printed circuit boards 120 in the fitting system 100 from FIG. 1, are considered. The first printed circuit board 205 is allocated a first set 220 of components 155, the second printed circuit board 210 is allocated a second set 225 of components 155, and the third printed circuit board 215 is allocated a third set 230 of components 155. In an exemplary manner, the sets 220 to 230 each include five different component types, of which components 155 are used in different numbers. Components 155 of one component type may not be distinguished from one another within the scope of the method 200 being considered. The sets 220 to 230 of components 155 are therefore allocated sets 235 to 245 of component types. Each of the components 155 in the allocated set 220 to 230 occurs only once in the sets 235 to 245.

(11) An equipment family includes those printed circuit boards 120 that are allocated for being fitted with components on a fitting line 100. In the example from FIG. 2, the printed circuit boards 205 and 210 are allocated to the same fitting line 110 and form a first equipment family 250. The first equipment family 250 therefore requires first equipment 260 with component types of the combination set of the sets 235 and 240 that are allocated to the printed circuit boards 205 and 210. In the example illustrated, the first equipment 260 includes six component types. With the provision of the component types of the first equipment 260, the printed circuit boards 205 and 210 in the first equipment family 250 may be fitted on the fitting line 110 without conversion.

(12) The third printed circuit board 215 is allocated to a different fitting line 110 and alone forms a second equipment family 255. Second equipment 265 allocated to the second equipment family 255 includes five component types.

(13) If the sets 220 and 225 include many components 155 of the same component type, the first equipment 260 only includes a small number of different component types. An attempt may be made to allocate the printed circuit boards 120 to equipment families 250, 255 in such a manner that as many different printed circuit boards 120 as possible may be processed with the fitting line 110.

(14) The third printed circuit board 215 is allocated to a different fitting line 110 and alone forms a second equipment family 255. Second equipment 265 allocated to the second equipment family 255 includes five component types.

(15) If the third printed circuit board 215 was allocated to the same equipment family as the printed circuit boards 205 and 210, the equipment allocated to the resulting equipment family would contain the component types of the combination set of the sets 235 to 245, that is to say seven component types in the present example. If the fitting line 110 has only receiving capacities for six different components 155, for example, the equipment family formed in this manner may not be allocated to the fitting line 110 and the third printed circuit board 215 no longer fits in the equipment family allocated to the fitting line 110.

(16) An equipment change is required in order to fit printed circuit boards 120 in another equipment family with components on the fitting line 110. In this case, one or more feeding elements, (in particular, a variable table 145 or a conveyor 150), may be changed on a fitting machine 130 of the fitting line 110.

(17) The number of equipment changes may be reduced and a number of constant tables 140 may be increased by reducing the number of equipment families 250, 255 of the fitting line 110. This may be achieved by skillful allocation of the printed circuit boards 120 to the equipment families 250, 255. The optimization of the allocation of printed circuit boards 120 to the equipment families 250, 255 is explained in more detail below with reference to FIG. 3.

(18) A method 300 for allocating printed circuit boards 120 to fitting lines 110 is illustrated in the form of a flowchart in FIG. 3.

(19) At act 305, a starting allocation of printed circuit boards 120 on fitting lines 110 is determined and a current allocation is equated with the starting allocation. Different heuristics that may also include manual specifications or restrictions are possible for determining the starting allocation.

(20) At act 310, a subset of printed circuit boards 120 is selected from the printed circuit boards 120 to be allocated. This selection may be made in such a manner that different subsets are selected during successive runs through the method 300.

(21) At act 315, one or more alternative allocations of printed circuit boards 120 in the subset to the fitting lines 110 are formed, (e.g., using integer linear programming). These allocations are made with respect to FIG. 2 in such a manner that the sum of the numbers of equipment families 250, 255 is minimized across all fitting lines 110. A weighted criterion of a plurality of individual criteria may also be used for the allocation, with the result that yet further parameters may also be minimized or maximized as far as possible in order to achieve an optimized allocation.

(22) At act 320, in this case, the quality of the determined allocations is determined by forming an individual or combined criterion. The criterion is formed on the basis of a number of equipment families for the fitting lines 110. In one embodiment, a method that is separate from the integer linear programming is called for this purpose, which method first of all forms the equipment families for the fitting lines on the basis of the determined allocation and then forms the sum of the determined equipment families over all fitting lines 110.

(23) In yet another embodiment, the criterion may include the compliance with a predetermined condition. For example, the condition may include the fact that the number of equipment families of each fitting line 110 is greater or less than a predetermined threshold, the threshold respectively being able to be individually allocated to a fitting line 110. If the condition has been met, the criterion may be set to a first predetermined value, otherwise it may be set to a second value. It is therefore possible to prevent an allocation from being accepted if the condition has not been met.

(24) In further embodiments, it may also be required as a condition that differences between the numbers of equipment families of each fitting line 110 are below a predetermined threshold. This threshold may be zero, in particular. In one variant, the differences may also be expressed in a quantified manner as a criterion, with the result that the method 300 may carry out optimization with respect to the criterion.

(25) In further embodiments, the criterion may be composed of a plurality of individual criteria that may be added together or multiplied by one another using weighting factors to form an overall criterion. For example, individual criteria may relate to one or more of the above-mentioned criteria, a degree of utilization of a fitting machine 130, the ratio of constant tables 140 to variable tables 145 or a degree of utilization of a fitting machine 130.

(26) At act 325, a check is then carried out in order to determine whether a predetermined abort criterion has been reached. The abort criterion has been satisfied if the criterion or the overall criterion from act 320 has reached a predetermined threshold value. The allocation may also be aborted if a predetermined determination time for the method 300 has expired. This makes it possible to prevent endless optimization of the allocation.

(27) At act 330, the determined allocations are output if the abort criterion has been satisfied.

(28) At act 335, otherwise, those allocations from the determined allocations that are intended to be optimized further may be selected. For example, the allocation determined last may be dropped in favor of an allocation determined in a previous run if the older allocation has a better criterion or overall criterion.

(29) At act 340, in this case, the current allocation is set to one of the allocations to be optimized and the method 300 may run through again from act 310. If a plurality of allocations that may be optimized have been selected, the method 300 may also be accordingly branched repeatedly in a parallel manner.

(30) Mathematical Background

(31) The use of exact mathematical methods makes it possible to achieve considerably better solutions than with heuristics previously used in practice. In further contrast thereto, good production times may also be achieved with these methods.

(32) When allocating printed circuit boards 120 or subassemblies to a fitting line 110, not every printed circuit board 120 may be produced on every fitting line 110 on account of technical restrictions. The printed circuit boards may also have different production times on the fitting lines 110. In addition, the maximum production time capacities of the fitting lines 110 is not exceeded.

(33) When allocating printed circuit boards 120 on fitting lines 110, the following aims may be pursued: (1) as many printed circuit boards 120 as possible may be able to be produced using constant tables 140 in order to reduce the conversion effort; (2) the number of equipment families (clusters) on the fitting lines 110 may be as small as possible in order to reduce the amount of conversion time; (3) as little equipment as possible (for example conveyor 150) may be required; and (4) the total production time for the printed circuit boards 120 may be as minimal as possible.

(34) An attempt may be made to achieve these aims by striving for the best possible component coverage of the printed circuit boards 120 of a fitting line 110 or minimizing the sum of component variances of the fitting lines 110.

(35) IP models (IP stands for integer programming or integer program or integer optimization model) are used to determine an optimized allocation of printed circuit boards 120 to fitting lines 110. This determination may be carried out using a known standard solver.

(36) Indices

(37) L Set of SMT fitting lines 110 of the system 100 R Set of printed circuit boards 120 C Set of component types 155 R.sub.c Set of printed circuit boards with component type c R.sub.l Set of printed circuit boards that may be fitted with components on line l
Parameters
Time.sub.r,l Total production time for printed circuit board r on line l
TimeLimit.sub.l Production time limit on line l
Binary Variables
Assign.sub.r,l Allocation of printed circuit board r to line l
Setup.sub.c,l Use of a component c on a line l
IP Formulation

(38) $\mathrm{minimize}\underset{cC}{\overset{}{.Math.}}\underset{lL}{\overset{}{.Math.}}{\mathrm{Setup}}_{c,l}$$s.t.\text{:}$$\underset{lL}{\overset{}{.Math.}}{\mathrm{Assign}}_{r,l}=1rR$${\mathrm{Assign}}_{r,l}=0lL,rR/R_l$$\underset{r{R}_c}{\overset{}{.Math.}}{\mathrm{Assign}}_{r,l}{\mathrm{Setup}}_{c,l}.Math.R_c.Math.cC,lL$$\underset{rR}{\overset{}{.Math.}}{\mathrm{Assign}}_{r,l}{\mathrm{Time}}_{r,l}{\mathrm{TimeLimit}}_{l}lL$${\mathrm{Setup}}_{c,l}\left\{0,1\right\}cC,lL$${\mathrm{Assign}}_{r,l}\left\{0,1\right)rR,lL$

(39) In order to improve the allocation of printed circuit boards 120 to fitting lines 110, the solver may be provided with conditions. The conditions imposed are aimed at optimizing the allocation of printed circuit boards 120 on the fitting lines 110 in such a manner that the sum of the numbers of equipment families of all fitting lines 110 of the fitting system 100 is minimized.

(40) Using this specification makes it possible to achieve an improved distribution of the printed circuit boards 120 across the fitting lines 110, in which case balanced sizes of equipment families may be achieved. The fitting system 100 may therefore be operated with improved efficiency or utilization. In addition, the allocations may be determined more quickly than previously known with the described approach using an IP solver.

(41) Although the invention was illustrated and described more specifically in detail by the exemplary embodiments, the invention is 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 the invention.

(42) It is to be understood that the elements and features recited in the appended claims may be combined in different ways to produce new claims that likewise fall within the scope of the present invention. Thus, whereas the dependent claims appended below depend from only a single independent or dependent claim, it is to be understood that these dependent claims may, alternatively, be made to depend in the alternative from any preceding or following claim, whether independent or dependent, and that such new combinations are to be understood as forming a part of the present specification.

(43) While the present invention has been described above by reference to various embodiments, it may be understood that many changes and modifications may be made to the described embodiments. It is therefore intended that the foregoing description be regarded as illustrative rather than limiting, and that it be understood that all equivalents and/or combinations of embodiments are intended to be included in this description.