Method and device for allocating assemblies to placement lines

Abstract

Provided is a method for allocating assemblies to placement lines for placing components on the assemblies, wherein 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 and the expected number of pieces to be produced for each assembly type. The actual number of pieces to be produced arises according to a predeterminable probability distribution, wherein the possible allocations of assemblies to the placement lines are restricted by the existing infrastructure and/or by user defined specifications, and the allocation of the assemblies to the placement lines is calculated by means of an optimization method.

Claims

1. A method for producing assemblies using a plurality of component fitting lines, the method comprising: ascertaining an expected production time for each assembly type of the assemblies to be fitted with components and each component fitting line taking into consideration a respective cycle time for the assembly type on the component fitting line, and an expected number of items to be produced per assembly type, wherein an actual number of items to be produced arises according to a previously determinable probability distribution, wherein possible assignments of assemblies to component fitting lines are limited by at least one of the existing infrastructure and user-defined presets; computing the assignment of the assemblies to the component fitting lines by means of an optimization method, wherein the computing of the assignment is effected such that for probability distributions with respect to the expected production times per component fitting line that result from the probability distributions for the numbers of items, a sum of differences from the respective expected value of these resultant probability distributions is minimized, wherein the sum of differences of the respective expected values is expressed as a variance within a time period based on a product of a square of the differences from the respective expected values, and wherein the computed assignment balances expected utilization levels of each of the plurality of component fitting lines; and producing the assemblies using the computed assignment of the assemblies to the component fitting lines.

2. The method as claimed in claim 1, wherein the differences from the expected values of the resultant probability distributions assume at least one of substantially identical values and values having a difference within a maximum difference.

3. The method as claimed in claim 1, wherein the sum of the expected production times for the set of assemblies that is assigned to a component fitting line does not exceed a maximum utilization level of the respective component fitting line over time.

4. The method as claimed in claim 1, wherein the optimization method is integer linear programming.

5. The method as claimed in claim 1, wherein the difference from the sum of the expected production times of a component fitting line is limited to a prescribable maximum threshold value.

6. The method as claimed in claim 5, wherein the prescribable maximum threshold value is minimized.

7. The method as claimed in the preceding claim 5, wherein the prescribable maximum threshold value is prescribed in the form of an interval limited at at least one of the top and the bottom.

8. The method as claimed in claim 7, wherein a width of the interval is stipulated as a percentage on a basis of one of the values limiting the interval.

9. The method as claimed in claim 1, wherein each assembly type is assigned to precisely one component fitting line.

10. A production or assembly line arrangement for fitting assemblies with components, wherein the assignment of the assemblies is determinable according to a method as claimed in claim 1, and wherein the production or assembly line arrangement fits the assemblies with the components using the computed assignment of the assemblies to the component fitting lines.

11. An apparatus for controlling production of assemblies using a plurality of component fitting lines, the apparatus comprising: 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 a respective cycle time for the assembly type on the component fitting line and an expected number of items to be produced per assembly type, wherein an actual number of items to be produced arises according to a previously determinable probability distribution, wherein possible assignments of assemblies to component fitting lines are limited by at least one of the existing infrastructure and by user-defined presets; and a unit for computing the assignment of the assemblies to the component fitting lines by means of an optimization method, wherein the computing of the assignment is effected such that for probability distributions with respect to the expected production times per component fitting line that result from the probability distributions for the numbers of items, a sum of differences from the respective expected value of these resultant probability distributions is minimizable, wherein the sum of differences of the respective expected values is expressed as a variance within a time period based on a product of a square of the differences from the respective expected values, and wherein the computed assignment balances expected utilization levels of each of the plurality of component fitting lines; wherein the apparatus controls production of the assemblies using the computed assignment of the assemblies to the component fitting lines.

12. The apparatus as claimed in claim 11, wherein the differences from the expected values of the resultant probability distributions assume at least one of substantially identical values and values having a difference within a maximum difference.

13. The apparatus as claimed in claim 11, wherein the sum of the expected production times for the set of assemblies that is assigned to a component fitting line does not exceed a maximum utilization level of the respective component fitting line over time.

14. The apparatus as claimed in claim 11, wherein the optimization method is integer linear programming.

15. The apparatus as claimed in claim 11, wherein the difference from the sum of the expected production times of a component fitting line is limitable to a prescribable maximum threshold value.

16. The apparatus as claimed in claim 15, wherein the prescribable maximum threshold value is minimizable.

17. The apparatus as claimed in the preceding claim 15 wherein the prescribable maximum threshold value is prescribed in the form of an interval limited at at least one of the top and the bottom.

18. The apparatus as claimed in claim 17, wherein a width of the interval is stipulated as a percentage on a basis of one of the values limiting the interval.

19. The apparatus as claimed in claim 11, wherein each assembly type is assigned to precisely one component fitting line.

20. A computer program product comprising a non-transitory computer readable hardware storage device storing a computer readable program code, the computer readable program code comprising an algorithm that when executed by a computer processor of a computing system implements the method as claimed in claim 11.

21. A non-transitory computer-readable medium, comprising instructions that, when executed on the apparatus as claimed in claim 11, prompts the apparatus to perform a method for assigning assemblies to component fitting lines for fitting the assemblies with components.

Description

BRIEF DESCRIPTION

(1) Some of the embodiments will be described in detail, with references to the following Figures, wherein like designations denote like members, wherein:

(2) FIG. 1 shows a first exemplary assembly factory with component fitting lines for producing assemblies;

(3) FIG. 2 shows a graph of the probability distributions for the numbers of items/production times of the component fitting lines 1 and 2 of FIG. 2 for an assembly line assignment; and

(4) 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

(5) 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 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 (r∈R).

(6) 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.

(7) The text below describes, as the mathematical optimization method, IP (IP stands for integer programming or for integer program or integer optimization model) models for this problem. The use of exact mathematical methods allows much better solutions to be obtained than with heuristics and optimization methods used to date. IP approaches to a solution have the following advantages: Global optimization approach. Easily extendable. Very good commercial standard solvers (e.g. Ilog, Xpress) that are widely used and proven in practice. 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.

(8) These methods can be used to achieve good production times.

(9) 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 r, it is estimated how many jobs there will be therefor and how often in total they have to be produced in the planning period. 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 estimated total production times per assembly 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.

(10) These units may also be implemented or integrated in a computer controlling the component fitting machines that is separate from the component fitting machines.

(11) The IP model depicted is intended to be regarded only as one possible exemplary formulation and is not a limitation for the method.

(12) The aim is to restrict production time fluctuations for the individual lines or to minimize them as far as possible.

(13) In the exemplary embodiment, the following parameters are used in the IP model:

(14) Let L be the set of all (component fitting) lines and R be the set of all assembly types and R.sub.l be the set of assembly types to which components can be fitted on line l.

(15) Further parameters are: 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 TimeLimit.sub.l production time limit on component fitting line l Assign.sub.r,l assignment of assembly type r to component fitting line l

(16) 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.

(17) For a set R.sub.l′.Math.R.sub.l of assembly types assigned to a line l, the production time is therefore also a random variable, for whose variance the following holds:

(18) $\begin{matrix} Var (line I production time) = Var (\underset{r \in R_{l}^{'}}{.Math.} t_{r, l} n_{r} + c_{r}) \\ = \underset{r \in R_{l}^{'}}{.Math.} t_{r, l}^{2} Var (n_{r}) \end{matrix}$

(19) 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:

(20) $\underset{r \in R}{.Math.} EW (t_{r, l} n_{r} + c_{r}) {Assign}_{r, l} \leq {TimeLimit}_{l} l \in L$

(21) The restrictions
Assign.sub.r,l=0l∈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.

(22) The restrictions

(23) $\underset{l \in L}{.Math.} {Assign}_{r, l} = 1 r \in R$
assign each assembly type to precisely one component fitting line.

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

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

(26) The following variants for limiting the maximum production time variance on the lines are possible:

(27) (1) Firmly prescribed parameters VarMax.sub.l allow the production time variances for all lines l to be limited by the additional restrictions

(28) $\underset{r \in R_{l}}{.Math.} t_{r, l}^{2} Var (n_{r}) {Assign}_{r, l} \leq {VarMax}_{l} l \in L$
(2) if VarMax.sub.l is selected as a variable, then using an auxiliary variable V.sub.max and additional restrictions
VarMax.sub.l≤V.sub.maxl∈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.
(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.

(29) In this regard, let V.sub.min be a further auxiliary variable. Additional restrictions are

(30) $V_{\min} \leq {VarMax}_{l} l \in L$ $and$ $V_{\max} - V_{\min} \leq \frac{p}{100} V_{\max}$

(31) 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.

(32) The patent application “Method and Apparatus for assigning assemblies to component fitting lines” with the same priority as the present patent application discloses the extension cited above.

(33) 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.

(34) The integer linear programming can be solved by the following steps: a) ascertaining a starting solution or first current solution, b) assigning a selected set of assemblies LP1-L6 to the component fitting lines BL1-BL2, 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.

(35) The steps can be performed iteratively and a program termination takes place if a previously stipulated time limit or result quality is reached.

(36) The text below explains a simplified example intended to explain the optimization process, depicted in complex fashion above, 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.

(37) 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: the forecast value n is assumed with a probability of 0.8. a 10% difference in the value n at the top or bottom is assumed with a probability of 0.1 in each case.

(38) Six different assembly types are supposed to be assigned to two lines BL1 and BL2. The forecast numbers of items n are:

(39) TABLE-US-00001 r1 r2 r3 r4 r5 r6 2000 2000 1000 1000 1000 1000

(40) The assignment is supposed to be made such that the two lines have the same utilization level, i.e. 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.

(41) As a possible starting solution, r1 and r2 may be assigned to the line BL1 and the assemblies r3 to r6 may be assigned to the line BL2. 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.

(42) TABLE-US-00002 Probability Probability distribution distribution of BL1 of 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

(43) 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.

(44) If, on the other hand, the two assembly types r1 and r2 are split over the lines BL1 and BL2, then, 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.

(45) TABLE-US-00003 Probability Probability distribution distribution of BL1 of 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

(46) The maximum variance in the case of the first assignment is
2*(400.sup.2*0.01+200.sup.2*0.16)=16000
and
decreases by 25% in the case of the second assignment to
2*(400.sup.2*0.001+300.sup.2*0.016+200.sup.2*0.074+100.sup.2*0.144)=12000

(47) 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.

(48) 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.

(49) 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.

(50) 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 device for allocating assemblies to placement lines

Assignee

Inventors

Cpc classification

Classification Explorer

G06Q50/04

PHYSICS

Classification Explorer

Y02P90/30

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

Classification Explorer

H05K13/085

ELECTRICITY

Classification Explorer

G06Q10/04

PHYSICS

International classification

Classification Explorer

H05K13/08

ELECTRICITY

Classification Explorer

G06Q50/04

PHYSICS

Classification Explorer

G06Q10/04

PHYSICS

Abstract

Claims

Description