METHOD AND APPARATUS FOR ASSIGNING ASSEMBLIES TO COMPONENT FITTING LINES

Abstract

Provided is a method for allocating assemblies to placement lines for placing components on the assemblies, in order to achieve a minimum variation in components with a predefinable maximum capacity utilization in terms of time for each placement line, wherein the component variation is determined as the sum of the number of component types required on the placement lines and an expected production time is determined for each assembly type of the assemblies to be provided with components and for each placement line, taking into consideration each cycle time for the assembly type on the placement line, each reset time, the degree of utilization for each line and the expected number of pieces to be produced for each assembly type.

Claims

1. A method for assigning assemblies to component fitting lines for fitting the assemblies with components in order to achieve a minimal component variance for prescribed maximum utilization levels over time per component fitting line, wherein the component variance is determined as the sum of the numbers of component types needed on the component fitting lines, wherein an expected production time is ascertained for each assembly type of the assemblies to be fitted with components and each component fitting line taking into consideration the respective cycle time for the assembly type on the component fitting line, the respective conversion times, the respective level of line use and the expected number of items to be produced per assembly type, wherein the actual number of items to be produced arises according to a previously determinable probability distribution, wherein the sum of these expected total production times must not exceed the maximum utilization level of the respective component fitting line over time for the set of assemblies that is assigned to a line, wherein the possible assignments of assemblies to the component fitting lines are limited by the existing infrastructure or by user-defined presets, wherein the assignment is made such that for the probability distributions for the sum of the expected production times per component fitting line that result from the cited probability distributions for the numbers of items, the differences from the respective expected value of these resultant probability distributions are limited by a prescribable maximum threshold value, wherein the assignment of the assemblies to the component fitting lines is computed for the given presets by integer linear programming.

2. The method as claimed in claim 1, wherein the sum of the expected production times of the component fitting lines is minimized by integer linear programming.

3. The method as claimed in claim 1, wherein the cited differences from the expected values of the resultant probability distributions assume similar or like values.

4. The method as claimed in claim 1, wherein a difference from the sum of the expected production times of a component fitting line is expressed as a variance thereof.

5. The method as claimed in claim 1, wherein a weighted sum consisting of the component variance and the maximum difference from the sum of the expected production times is minimized.

6. The method as claimed in claim 1, wherein user-prescribed sets of assemblies are assigned to the same component fitting line.

7. The method as claimed in claim 1, wherein the input data used for the integer linear programming are the following data describing the infrastructure: number of component fitting lines, number of assemblies, number of assembly types, number of component types, set of component types to be fitted per assembly type, production time limit per respective component fitting line probability distributions for the expected numbers of items of the assembly types.

8. The method as claimed in claim 1, wherein the total production time for a respective assembly type on a respective component fitting line is computed from: the number of jobs to be expected, the batch sizes, the conversion times, the individual production times per assembly and component fitting line, minimum cycle times of the component fitting lines, levels of use of the component fitting lines.

9. The method as claimed in claim 1, wherein the linear programming is set by an integer linear program solved by the following steps: a) ascertaining a first current solution representing an assignment of assemblies to production lines, b) assigning a selected set of assemblies to the component fitting lines, based on a current solution, c) computing the new assignments by means of an optimization program or a standard solver based on integer linear programming.

10. The method as claimed in claim 9, wherein the steps are performed iteratively and a program termination takes place if a previously stipulated time limit or solution quality has been reached.

11. An apparatus for assigning assemblies to component fitting lines for fitting the assemblies with components, having: a unit for ascertaining an expected production time for each assembly type of the assemblies to be fitted with components and for each component fitting line taking into consideration the respective cycle time for the assembly type on the component fitting line and the expected number of items to be produced per assembly type, wherein the actual number of items to be produced can arise according to a previously determinable probability distribution, wherein the sum of these expected total production times must not exceed the maximum utilization level of the respective component fitting line over time for the set of assemblies that is assigned to a line, wherein the possible assignments of assemblies to component fitting lines can be limited by the existing infrastructure and/or by user-defined presets and wherein the component variance is determinable as the sum of the numbers of component types needed on the component fitting lines in order to achieve a minimum component variance for prescribed maximum utilization levels over time per component fitting line, and a unit for computing the assignment of the assemblies to the component fitting lines for the given presets by means of integer linear programming, wherein the computation of the assignment is effected such that for the probability distributions for the sum of the expected production times per component fitting line that result from the cited probability distributions for the numbers of items, the differences from the respective expected value of these resultant probability distributions are limitable by a prescribable maximum threshold value.

12. The apparatus as claimed in claim 11, wherein the cited differences from the expected values of the resultant probability distributions can assume similar or like values.

13. The apparatus as claimed in claim 11, wherein a difference from the sum of the expected production times of a component fitting line can be expressed as a variance thereof.

14. The apparatus as claimed in claim 11, wherein a weighted sum consisting of the component variance and the maximum difference from the sum of the expected production times is minimizable.

15. The apparatus as claimed in claim 11, wherein user-prescribed sets of assemblies can be assigned to the same component fitting line.

16. A production or assembly line arrangement for fitting assemblies with components, wherein the assignment of the assemblies to the production or assembly line is determinable according to claim 1.

17. The apparatus of claim 11, further comprising, a computer program having means for performing the ascertaining and computing steps when the computer program is executed on the apparatus or in means of the apparatus.

18. A computer program product, comprising a computer readable storage device storing a computer readable program code, the computer readable program code comprising program commands for the purposes of executing the method as claimed in claim 1.

Description

BRIEF DESCRIPTION

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

[0075] FIG. 1 shows a first exemplary assembly factory with component fitting lines for producing assemblies;

[0076] FIG. 2 shows a graph of the probability distributions for the numbers of items/production times of lines 1 and 2 for an assembly line assignment; and

[0077] FIG. 3 shows a graph of said probability distributions based on the optimization approach according to embodiments of the invention for an assembly line assignment.

DETAILED DESCRIPTION

[0078] FIG. 1 shows a first exemplary assembly factory or an assembly installation with component fitting lines BL1-BL2 for producing assemblies. A component fitting line BL1-BL2 usually consists of component fitting machines BA1-BA6 that are each connected to one another by a transport system FB1-FB2 (e.g. conveyor belts) for transporting the assemblies or printed circuit boards LP1-LP6 to be fitted with components. The components or subassemblies B1-B6 to be fitted to the assemblies LP1-LP6 are usually provided on the component fitting machines BA1-BA6 by means of conveyors F1-F11. In this case, a component fitting line BL1, BL2 can be assigned multiple assemblies LP1-LP6 of a particular assembly type r from a set of assembly types R.sup.(r R).

[0079] Component fitting machines BA1-BA6 e.g. for fitting substrates with components B1-B6 have supply apparatuses F1-F11 for components B1-B6 arranged at the side on a transport path for the substrates. A component fitting head of the component fitting machine BA1-BA6, which component fitting head is movable by a positioning system, collects the components B1-B6 from the supply apparatuses F1-F11, moves them to a component fitting area of the component fitting machine in which the substrate to be fitted with components is provided, and drops the components B1-B6 on the substrate. For providing the components B1-B6, e.g. what are known as belt feeders are used, which are suitable for transporting and supplying subassemblies stored in belts. These transport the subassemblies stored in pocket-like depressions to a collection position at which the subassemblies are collected from the belt pockets by the component fitting head. The empty belt leaves the supply apparatus F1-F11 at a suitable position.

[0080] In many factories in the area of electronics production, printed circuit boards or assemblies to be produced are assigned to the SMT (surface mounting technology) component fitting lines at the respective factories in the medium term. On the basis of technical restrictions, not every printed circuit board can be produced on every line. The printed circuit boards for the most part also have different production times on the lines. Also, the maximum production time capacities of the lines cannot be exceeded.

[0081] For the assignment, the following aims are pursued: [0082] The number of equipment families on the lines is supposed to be as small as possible in order to reduce the conversion time outlay. [0083] It is desirable for as little equipment as possible (e.g. conveyors) to be needed. [0084] The total production time should be as minimal as possible.

[0085] Attempts are usually made to achieve these aims by virtue of the highest possible component coverage of the printed circuit boards of a line being sought, or the sum of the component variances of the lines being minimized. The component variance of a line denotes the number of component types used on the line.

[0086] The text below describes IP (IP stands for integer programming or for integer program or integer optimization model) models for this problem. The mathematical optimization method used for this problem can be IP (IP stands for integer programming or for integer program or integer optimization model) models. Such IP approaches to a solution have the following advantages: [0087] Global optimization approach. [0088] Easily extendable. [0089] Very good commercial standard solvers (e.g. Cplex, Gurobi) that are widely used and proven in practice. [0090] The standard solvers are continually being improved, which means that it can be expected that the instances will be solvable even more quickly in future.

[0091] Further, an IP-based method is presented that allows solutions to be found therefor with a very good result quality in a relatively short period.

[0092] The IP model depicted below can be regarded only as a possible exemplary formulation and is not a limitation for the method.

[0093] Let L be the set of all (component fitting) lines and R be the set of all assembly types and R.sub.1 be the set of assembly types that can have components fitted on line 1. Also, C is the set of component types c and R.sub.c expresses the set of assembly types with component type c.

[0094] The following parameters are used:

TABLE-US-00001 Time Limit.sub.l production time limit on the component fitting line l w.sub.S weighting factor for minimizing the component variance. w.sub.V weighting factor for minimizing the maximum production time variance.
Binary variables are:

TABLE-US-00002 Assign.sub.r, l assign the assembly type r to component fitting line l Setup.sub.c, l use a component c on a line l (during use, it assumes the value 1, otherwise the value 0).

[0095] In the planning period, a set of assemblies is supposed to be fitted with components of different component types on multiple SMT lines. For each assembly type r, it is estimated how many jobs there will be therefor. The actual number of items to be produced for an assembly type will arise according to a probability distribution that can be ascertained e.g. from historical data or forecasts. Using the cycle times on the various (component fitting) lines, the estimated conversion times and the levels of line use, it is possible to ascertain probability distributions for the total production times per assembly type and line, which can serve as an input. A maximum production time is also prescribed per line in the planning period. The expected production time per assembly type can be ascertained using a unit that is not depicted in the figures. Such a unit may be integrated in a component fitting machine e.g. BA1 of the component fitting line BL1. A unit, not depicted, for computing the assignment of the assemblies to component fitting lines may also be integrated in such a component fitting machine.

[0096] These units may also be implemented or integrated in a computer controlling the component fitting machines that is separate from the component fitting machines.

[0097] The aim is also to restrict production time fluctuations for the individual lines or to minimize them as far as possible.

[0098] In the exemplary embodiment, the following further parameters are used in the IP model:

TABLE-US-00003 n.sub.r independent random variable for the number of items n to be produced for the assembly type r within a particular period. c.sub.r fixed production time during the production of an arbitrary number of items at the assembly type r. t.sub.r, l cycle time for the production of an assembly of the assembly type r on line l. VarMax.sub.l maximum production time variance on the component fitting line l. p percentage for the maximum permissible differences in the production time variances on the lines.

[0099] Continuous auxiliary variables:

TABLE-US-00004 V.sub.Max maximum production time variance on all lines. V.sub.Min minimum production time variance on all lines.

[0100] It is assumed that the production time for an assembly on a line is t.sub.r,ln.sub.r+c.sub.r. In this case, c.sub.r is a constant component that includes the conversion times, for example. The production times for the assembly on a line are also independent random variables.

[0101] For a set R.sub.1 .Math. R.sub.l of assembly types r assigned to a line l, the production time is therefore also a random variable, for whose variance the following holds:

[00001] $\begin{matrix} Var (line .Math. .Math. l .Math. .Math. production .Math. .Math. time) = .Math. Var (\underset{r R_{l}^{}}{.Math.} .Math. .Math. t_{r, l} .Math. n_{r} + c_{r}) \\ = .Math. \underset{r R_{l}^{}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) \end{matrix}$

[0102] In an IP model, restrictions are normally used. The following restrictions of the IP model restrict the expected production time on the lines and ensure the permissibility of the solution:

[00002] $\underset{r R}{.Math.} .Math. .Math. EW (t_{r, l} .Math. n_{r} + c_{r}) .Math. {Assign}_{r, l} {TimeLimit}_{l} .Math. .Math. l L$

[0103] The restrictions

Assign.sub.r,l=0 l L,r R\R.sub.l

guarantee that assemblies can be assigned only to component fitting lines on which they can also have components fitted.

[0104] The restrictions

[00003] $\underset{l L}{.Math.} .Math. .Math. {Assign}_{r, l} = 1 .Math. .Math. r R$

assign each assembly type to precisely one component fitting line.

[0105] In the IP model, it is also possible for the production time variance of a component fitting line to be expressed as follows:

[00004] $Var (line .Math. .Math. l .Math. .Math. production .Math. .Math. time) = \underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} .Math. .Math. l L$

[0106] The following variants for limiting the maximum production time variance on the lines are possible: [0107] (1) Firmly prescribed parameters VarMax.sub.l allow the production time variances for all lines l to be limited by the additional restrictions

[00005] $\underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} Var .Math. .Math. {Max}_{l} .Math. .Math. l L$ [0108] (2) Using an auxiliary variable V.sub.max and additional restrictions

[00006] $\underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} V_{\max} .Math. .Math. l L$

it is possible to minimize V.sub.max to achieve the effect that the maximum production time variance of the lines is minimized as far as possible. V.sub.max can be included in the target function of the IP model in this case with a weight factor w.sub.v. [0109] (3) A further option is for the difference in the maximum and minimum variances of the lines to be restricted for a prescribed percentage p.

[0110] In this regard, let V.sub.min be a further auxiliary variable. Additional restrictions are

[00007] $V_{\min} \underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} .Math. .Math. l L$ $and$ $V_{\max} - V_{\min} \frac{p}{100} .Math. V_{\max}$

[0111] The restrictions depicted above for the variants (1) and (3) can also each be used to extend the IP model from DE 10 2011 076 565 B4, WO2014/005741 A1, WO2014/005743 A1, WO2014/005744 A1. The methods known from the cited documents are examples of optimization methods by means of MIP for assignments of assemblies to component fitting lines.

[0112] Accordingly, production time fluctuations can be limited in these IP models too. Variant (2) can likewise be used to extend these IP models by virtue of V.sub.max, in addition to the new restrictions, also being included in the target function with a chosen weighting.

[0113] The integer linear programming can be solved by the following steps: [0114] a) ascertaining a starting solution or first current solution, [0115] b) assigning a selected set of assemblies LP1-L6 to the component fitting lines BL1-BL2, based on a current solution, [0116] c) computing the new assignments by means of an optimization program or a standard solver based on integer linear programming.

[0117] The steps can be performed iteratively and a program termination takes place if a previously stipulated time limit or result quality is reached.

[0118] The following variants of the extended IP formulation are possible:

IP formulation for the variant (1):

[00008] $minimize .Math. .Math. \underset{c C}{.Math.} .Math. .Math. \underset{l L}{.Math.} .Math. .Math. {Setup}_{c, cl}$

[0119] Under the conditions:

[00009] $\begin{matrix} \underset{l L}{.Math.} .Math. .Math. {Assign}_{r, l} = 1 & r R \\ {Assign}_{r, l} = 0 & l L, r R r .Math. R_{l} \\ \underset{r R_{c}}{.Math.} .Math. .Math. {Assign}_{r, l} .Math. R_{c} .Math. .Math. {Setup}_{c, cl} & c C, l L \\ \underset{r R}{.Math.} .Math. .Math. EW (t_{r, l} .Math. n_{r} + c_{r}) .Math. {Assign}_{r, l} {TimeLimit}_{l} & r R \\ \underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} Var .Math. .Math. {Max}_{l} & l L \\ {Setup}_{c, cl} {0, 1} & c C, l L \\ {Assign}_{r, l} {0, 1} & r R, l L \end{matrix}$

and IP formulation for variants (2) and (3):

[00010] $minimize .Math. .Math. w_{v} .Math. V_{Max} + w_{s} .Math. \underset{c C}{.Math.} .Math. .Math. \underset{l L}{.Math.} .Math. .Math. {Setup}_{c, cl}$

[0120] Under the conditions:

[00011] $\begin{matrix} \underset{l L}{.Math.} .Math. .Math. {Assign}_{r, l} = 1 & r R \\ {Assign}_{r, l} = 0 & l L, r R .Math. \ .Math. R_{l} \\ \underset{r R_{c}}{.Math.} .Math. .Math. {Assign}_{r, l} .Math. R_{c} .Math. .Math. {Setup}_{c, cl} & c C, l L \\ \underset{r R}{.Math.} .Math. .Math. EW (t_{r, l} .Math. n_{r} + c_{r}) .Math. {Assign}_{r, l} {TimeLimit}_{l} & r R \\ \underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} V_{Max} & l L \\ \underset{r R_{l}}{.Math.} .Math. .Math. t_{r, l}^{2} .Math. Var (n_{r}) .Math. {Assign}_{r, l} V_{Min} & l L \\ V_{Max} - V_{Min} \frac{p}{100} .Math. V_{Max} & l L \\ {Setup}_{c, cl} {0, 1} & c C, l L \\ {Assign}_{r, l} {0, 1} & r R, l L \\ V_{Max} 0 \\ V_{Min} 0 \end{matrix}$

[0121] The text below explains a simplified example intended to explain the optimization process, depicted in complex fashion above, for the minimization of the component variance under the restriction of production time fluctuations in a simplified manner for comprehension, without being restricted to this simplified example. If the simple example with few instances described below is transferred to larger instances or more complex problems, a good or precise selection of parameters in the IP model with the restrictions to be applied or the user-defined presets is fundamental in order to be able to attain a solution to the complex problem with the aforementioned standard solvers in the first place or in optimized fashion.

[0122] In the example below, it is assumed that, for an assembly type given a forecast number of items of n, the number of items actually to be produced or have components fitted fluctuates according to the following probability distribution: [0123] the forecast value n is assumed with a probability of 0.8. [0124] a 10% difference in the value n at the top or bottom is assumed with a probability of 0.1 in each case.

[0125] Six different assembly types are supposed to be assigned to two lines BL1 and BL2. The forecast numbers of items n are:

TABLE-US-00005 r1 r2 r3 r4 r5 r6 2000 2000 1000 1000 1000 1000

[0126] The assembly types are supposed to be fitted with the component types c1-c9 according to the following table:

TABLE-US-00006 c1 c2 c3 c4 c5 c6 c7 c8 c9 r1 X X r2 X X r3 X X r4 X X X r5 X X r6 X X

[0127] The assignment is supposed to be made such that the two lines have the same utilization level, i.e. have the same expected production times. The cycle times are 1 min for all assembly types, and therefore e.g. the production time is 1000 min when the number of items is 1000.

[0128] If the target criterion is minimization of the component variance, then r1 and r2 are assigned to the line BL1 and the assemblies r3 to r6 are assigned to the line BL2, since this means that the component types c1-c3 are needed on the line BL1 and the component types c4-c9 are needed on the line BL2 and a minimum component variance of 9 is obtained overall. The following probability distributions W1 and W2 for the numbers of items/production times on the two lines BL1 and BL2 are thus obtained, as depicted in the table below and in FIG. 2.

TABLE-US-00007 Probability distribution of Probability distribution of BL1 BL2 3600 0.01 0.0001 3700 0.0032 3800 0.16 0.0388 3900 0.2144 4000 0.64 0.487 4100 0.2144 4200 0.16 0.0388 4300 0.0032 4400 0.01 0.0001

[0129] On line BL1, the two assembly types with large numbers of items mean that a large range of fluctuation is obtained for the numbers of items/production times.

[0130] The variance for the production time on the line BL1 is at a maximum and is:

2*(400.sup.2*0.01+200.sup.2*0.16)16 000

[0131] If the variances for the production times are additionally restricted to 12 000 on all lines by the restrictions listed in (1), then the assembly types r1, r3 and r4 are assigned to the line BL1 and the assembly types r2, r5 and r6 are assigned to the line BL2.

[0132] Thus, the following probability distributions W1 and W2 for the numbers of items/production times on the two lines BL1 and BL2 are obtained, as depicted in the table below and in FIG. 3.

TABLE-US-00008 Probability distribution of Probability distribution of BL1 BL2 3600 0.001 0.001 3700 0.016 0.016 3800 0.074 0.074 3900 0.144 0.144 4000 0.53 0.53 4100 0.144 0.144 4200 0.074 0.074 4300 0.016 0.016 4400 0.001 0.001

[0133] The maximum variance for the production times decreases by 25% in the case of this second assignment to

2*(400.sup.2*0.001+300.sup.2*0.016+200.sup.2*0.074+100.sup.2*0.144)=12 000

[0134] In the middle and at the edge, the values of the distributions for line BL1 and line BL2 in the case of the second assignment of lines for assemblies are much lower than the values of the distribution for line BL1 in the case of the first assignment of lines for assemblies. At the edge, the probability is even now only a tenth.

[0135] In the case of the second assignment, the component types c1-c2 and c4-c6 are needed on the line BL1 and the component types c2-c3 and c7-c9 are needed on the line BL2. All in all, a component variance of 10 is therefore obtained.

[0136] In comparison with the first assignment, the sum of component types needed on the lines has only increased from 9 to 10, whereas the maximum variance for the production times on the lines has decreased significantly from 16 000 to 12 000.

[0137] Given a suitable choice of parameters, it is specifically possible for the second assignment of lines for assemblies explained above to be ascertained. The steps of the optimization can be performed iteratively and a program termination can take place effected if a previously stipulated time limit or a prescribable result quality is reached.

[0138] Although the invention has been illustrated and described in greater detail with reference to the preferred exemplary embodiment, the invention is not limited to the examples disclosed, and further variations can be inferred by a person skilled in the art, without departing from the scope of protection of the invention.

[0139] 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.

METHOD AND APPARATUS FOR ASSIGNING ASSEMBLIES TO COMPONENT FITTING LINES

Inventors

Cpc classification

Classification Explorer

G05B2219/50148

PHYSICS

Classification Explorer

H05K13/085

ELECTRICITY

Classification Explorer

G05B2219/40111

PHYSICS

Classification Explorer

G05B19/41865

PHYSICS

International classification

Classification Explorer

H05K13/08

ELECTRICITY

Classification Explorer

G05B19/418

PHYSICS

Abstract

Claims

Description