Metal working – Method of mechanical manufacture – Electrical device making
Reexamination Certificate
2001-06-07
2004-01-20
Arbes, Carl J. (Department: 3729)
Metal working
Method of mechanical manufacture
Electrical device making
C029S740000, C029S741000, C029S840000
Reexamination Certificate
active
06678947
ABSTRACT:
This application claims priority to International Application No. PCT/DE99/02536 which was published in the German language on Aug. 13, 1999.
DESCRIPTION
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a method and apparatus for computer-aided pipette selection for a placement head of an automatic placement machine, and in particular for allocation of components to the pipette types provided in a pipette selection.
BACKGROUND OF THE INVENTION
A method for checking the so-called consecutive ones characteristic, is described in W. L. HSU, A Simple Test for the Consecutive Ones Property, Lecture Notes in Computer Science: Algorithms and Computation, Vol. 650, pages 459-468, 1992. If the consecutive ones characteristic is present, then the method implicitly provides all the permissible associations to component types.
Various types of placement heads are normally used. One such placement head is, for example, the so-called SP head (
S
peed
P
lacer-head), by means of which a number of components can be picked up from the component store, transported and successively placed on the printed circuit board.
An SP placement head has a number of segments, (normally 6 or 12 segments), to each of which a pipette can be fitted. The pipettes allow components to be picked up and placed in position. There are various pipette types by means of each of which different types of components can be placed in position. The process of populating a printed circuit board with components by means of an SP placement head normally takes place in a number of iterations (cycles), in each of which the placement head first of all picks up as a maximum the number of components which can be processed and then places them down on the printed circuit board in the same sequence in which it picked them up. The time which is required for one cycle depends only to a minor extent on the number of components picked up and placed in position in this cycle, so that the smallest possible number of cycles for the placement process is the most time-critical criterion relating to the population process.
It is thus desirable to pick up and place in position as many components as possible in the individual cycles, that is to say to avoid “gaps” in the placement process, in association thus to minimize the number of cycles required to place all the components in position.
A method for checking the so-called consecutive ones characteristic, is described in [1]. If the consecutive ones characteristic is present, then the method from [1] implicitly provides all the permissible associations to component types.
A method for checking the so-called acyclic hypergraph characteristic, which has a linear complexity, is described in R. E. Taijan, M. Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM J, Comput., Vol. 13, pages 566-579, 1984.
A method for solving a flow problem is described in R. K. Ahuja et al., Network Flows, Prentice Hall, pages 207-242 and 255-258, 1993.
A so-called branch and cut method for optimum solution of an integer linear program is described in G. L. Nemhauser, L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, N.Y., pages 349-379, 1988.
SUMMARY OF THE INVENTION
In one embodiment of the invention, there is a method for computer-aided pipette selection for a placement head of an automatic placement machine and for allocation of components to different pipette types predetermined in a pipette selection for a given number of cycles z. The method using, a stored component type list B with a respectively associated number of components of the component type to be placed, a component type association based on the component types, a stored pipette type list P of available pipette types and an allocation list E which indicates which component types can be placed using what pipette types, and based on the component type association for the pipette types p&egr;P, a pipette type association is formed in such a manner that p
1
≦p
2
→(1(p
1
)<1(p
2
)) v ((1(p
1
)=1(p
2
)){circumflex over ( )}f(p
1
)p
2
))), where p
1
, p
2
&egr;P denote different pipette types, 1(p), p&egr;P, is defined by 1(p)=max{b&egr;B|(b, p)&egr;E}, f(p), p&egr;P, is defined by f(p)=min{b&egr;B|(b, p)&egr;E}, in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z, if any components of this component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In one aspect of the invention, there is a method for computer-aided pipette selection for a placement head of an automatic placement machine and for allocation of components to the pipette types predetermined in a pipette selection for a given number of cycles z, in which, using a stored component type list B with a respectively associated number of components of the component type to be placed, a stored pipette type list P of available pipette types and an allocation list E which indicates which component types can be placed using what pipette types, determining whether a permissible component type association by carrying out a check, such that (b
1
, p)&egr;E, (b
2
, p)&egr;E, b
1
≦b≦b
2
→(b, p)&egr;E, where b
1
, b
2
, b components in the component type list B are denoted, (b, p)&egr;E, b&egr;B , p&egr;P, denotes the situation where a component of component type b can be placed using a pipette of pipette type p, in which, based on the permissible component type association for the pipette types p&egr;P, a pipette type association is formed in such a manner that, p
1
≦p
2
→(1(p
1
)≦1(p
2
))v((1(p
1
)=1(p
2
)){circumflex over ( )}f(p
1
)≧f(p
2
))), where p
1
, p
2
&egr;P denote different pipette types, 1(p), p&egr;P, is defined by 1(p)=max{b&egr;B|(b, p)&egr;E}, f(p), p&egr;P, is defined by f(p)=min{b&egr;B|(b, p)&egr;E}, in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then the pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z; if any components of the component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and, in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In another aspect of the invention, in the situation where no permissible component type association exists, the allocation list E is reduced in size, based on the component types and the pipette types, as many components as possible are allocated successively for each pipette type to the respective pipette type so that a component type association to the component types exists for the resultant allocation list E in such a manner that: (b
1
, p)&egr;E, (b
2
, p)&egr;E, b
1
≦b≦b
2
→(b, p)&egr;E, in which, for the pipette types p&egr;P a pipette type as
Bauer Petra
Enders Reinhard
Arbes Carl J.
Morrison & Foerster / LLP
Siemens Aktiengesellschaft
LandOfFree
Method and device for computer assisted selection of suction... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for computer assisted selection of suction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for computer assisted selection of suction... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3250727