Source: https://patents.google.com/patent/US5390283?oq=5435091
Timestamp: 2018-02-23 05:33:29
Document Index: 774260811

Matched Legal Cases: ['§4', 'art:   868', 'art:   908', 'art:   888', 'art:   890', 'art:   889', 'art:   880', 'art:   879', 'art:   900', 'art:   899', 'art:                     891', 'art:                            883', 'art:                            885', 'art:                            904', 'art:                            903', 'art:                            863', 'art:                            864']

US5390283A - Method for optimizing the configuration of a pick and place machine - Google Patents
US5390283A
US5390283A US07965474 US96547492A US5390283A US 5390283 A US5390283 A US 5390283A US 07965474 US07965474 US 07965474 US 96547492 A US96547492 A US 96547492A US 5390283 A US5390283 A US 5390283A
US07965474
A genetic algorithm is used to search for optimal configurations of a computer controlled pick and place machine, which places parts on printed circuit boards. Configurations include: assigning grippers to pipettes of the machine; assigning parts, destined for the printed circuit boards, to feeders of the machine; assigning parts to pipettes; and determining time intervals and orders in which parts are to be placed. The genetic algorithm is applied to chromosome strings representing parameters for determining machine configuration. A heuristic layout generator generates machine configurations from the chromosome strings.
Electronic component placement machines, sometimes called pick-and-place machines, are known. They are typically used to load chip components onto a printed circuit board (PCB) for subsequent processing, such as by soldering the components to the PCB traces.
The chief object of the invention is a method based on a computer-controlled algorithm that is able to produce high-quality configurations for arbitrary tasks for machines of the type described.
The method of the invention is generally applicable to any placement machine having a plurality of part-grasping devices on one or more heads movable in three dimensions sequentially but usually simultaneously picking up parts fed from a plurality of feeders and placing them on one or more boards under computer control. As the number of part-grasping devices increases, the complexity of providing a good machine configuration increases. In general, the method of the invention will be needed--prove faster or superior to a manual approach--with a class of machines whose number of part-grasping devices exceeds three. The invention will be explained in its application to providing high-quality configurations for two commercial placement machines in this class, but it will be understood that the invention is not limited to such machines but will be generally applicable to any machines in the class as defined, and those skilled in the art will be able to apply the principles as described herein to other machines in this class. The two machines for which detailed explanations will be given are Philips Modular Component Placement Machines, Models MCM-VII and FCM.
Heuristic H2 involves a precomputed desirability for each gripper on each PM and a preference-- bit in the chromosome for each gripper. The desirabilities are computed once as soon as the parts are known and the FCM line is defined, including any preassignments. The gripper-PM desirability represents the opportunities a gripper has to place its parts on that PM. It is a count that is incremented for each part that may potentially be placed in each slot in each index step. To be potentially placeable, a proper feeder type must have been preassigned or a slot must be free. In addition, the part's× position must be accessible in the index strip. This desirability reflects the differences that sometimes arise between PMs as to which x-positions are exposed in two successive index steps when a 40 mm board movement occurs.
TABLE 3______________________________________The Part Sort Controlbits    integer         sort order______________________________________0000    0               ppt × st × pt0001    1               ppt × st × gt × pt0011    2               ppt × pt × st0010    3               ppt × gt × st × pt0110    4               ppt × gt × pt × st0111    5               st × ppt × pt0101    6               st × ppt × gt × pt0100    7               st × pt × ppt1100    8               st × gt × ppt × pt1101    9               pt × ppt × st1111    10              pt × st × ppt1110    11              gt × ppt × st × pt1010    12              gt × ppt × pt × st1011    13              gt × st × ppt × pt1001    14              gt × st × pt × ppt1000    15              gt × pt × ppt × st______________________________________ ppt = pp.sub.-- time st = stripe pt = part type gt = gripper type
The fcm.best file is overwritten during a search whenever a new solution is found that is better than the previous best. It consists of a series of "paragraphs" each describing a different aspect of the solution. The first paragraph summarizes the PCB information provided in the parts.list file. An example is given below:
The next paragraph depicts the parts actually placed during each index step of the solution. Below shows the beginning of such a paragraph. First the index stepping is described with an "E" marking the step where EVA occurs (a visual inspection), and "F" marking the step in which parts are first placed on a new board by PM[0]. Below this, each bucket is listed showing the board stripes it sees,"the heartbeat time (pp-- time estimates ignoring the movement of the transport system), the sum of the estimated pp-- times for all parts placed in the bucket, and the slack-- time (heartbeat--pp-- time). All times are in milliseconds. Then the part numbers of the parts placed are listed in the order they are placed. After each part number, three characters appear in brackets [abc] where a is the slot and b is the pick position from which it is taken, and c is "x", "y" or "p" depending on whether the pp-- time is bound by the x-, Y-, or phi- servo- Note that the slots in alternating index steps are arranged alternatively left-to-right and right-to-left reflecting the simple heuristic for step 5 of the HLG (see §4).
______________________________________SOLUTION______________________________________index steps:     0         1      2        3    4size (mm):     40        80     80       80   80                E     FFCM[0] PM[0]stripes:    5,6      7,8      0,1    2,3    4,5heartbeat:    9561     8471     12582  14127  12177pp.sub.-- time:    7783     3494     8205   13267  8952slack.sub.-- time:    1778     4977     4377   860    3225part:   868[00y] 910[10y] 862[00y]                            894[40y]                                   866[00y]part:   908[10y] 909[10x] 861[00y]                            896[40y]                                   865[00x]part:   888[20y] 869[00x] 901[10y]                            893[40p]                                   867[00y]part:   890[20y] 870[00y] 902[10p]                            895[40x]                                   906[10y]part:   889[20p]          882[20y]                            873[30p]                                   905[10x]part:   880[30y]          881[20p]                            876[30p]                                   907[10p]part:   879[30x]          872[30y]                            874[30y]                                   887[20p]part:   900[40y]          871[30p]                            875[30y]                                   878[30y]part:   899[40x]          892[40y]                            884[20y]                                   877[30p]part:                     891[40p]                            886[20y]                                   898[40y]part:                            883[20x]                                   897[40p]part:                            885[20p]part:                            904[10y]part:                            903[10x]part:                            863[00x]part:                            864[00y]______________________________________
______________________________________LOWER BOUND PICK & PLACE TIME (ignoring gripper-type   allocations & transport): 51200 millisecondsLOWER BOUND PICK & PLACE TIME (considering gripper-type   allocations, but ignoring transport):                  55745 millisecondsGT: 1 min.sub.-- PMs 3 assigned.sub.-- PMs 10 opt.sub.-- PMs                  10.5GT: 2 min.sub.-- PMs 2 assigned.sub.-- PMs 2 opt.sub.-- PMs                  2.2GT: 3 min.sub.-- PMs 1 assigned.sub.-- PMs 3 opt.sub.-- PMs                  2.5GT: 4 min.sub.-- PMs 1 assigned.sub.-- PMs 1 opt.sub.-- PMs                  0.8TOTAL PICK & PLACE TIME (including transport): 57607   millisecondspercent above lower bound = 3.340210kost= 57607 found at experiment 0 trial 46128______________________________________
__________________________________________________________________________Pseudocode for CHCprocedure CHCbegint = 0;d = L/4;initialize P(t);evaluate structures in P(t);while termination condition not satisfied dobegint = t + 1;select C(t) from P(t-1);recombine structures in C(t) forming  C'(t)evaluate structures in C'(t);select P(t) from C'(t) and P(t-1);if P(t) equals P(t-1)  d-;if d < 0begin  diverge P(t);  d = r × (1.0 - r) × L;endendend.procedure selectbegin  copy all members of P(t-1) to C(t) in random order;end.procedure selectbegin form P(t) from P(t-1)by replacing the worst members of P(t-1)with the best members of C'(t) until no remaining member of C'(t)is any better than any remaining member of P(t-1);end.procedure recombinebegin for each of the M/2 pairs of structures in C(t) begindetermine the Hamming distanceif (Hamming distance/2) > dswap half the differing bits at random;elsedelete the pair of structures from C(t);end end.procedure divergebegin replace P(t) with M copies of the best member of  P(t-1); for all but one member of P(t) begin  flip r × L bits at random;  evaluate structure; endend.variablesM population sizeL string lengtht generationd difference thresholdr divergence rate For the MCM:HLG control parameters for MCM machinestargeted number of pipettes and feeders per gripper type:P.sub.-- num.sub.-- pipettes.sub.-- targeted[gt]          number of pipettes per gripper typeP.sub.-- num.sub.-- feeders.sub.-- targeted[gt]          number of feeders per gripper typeP.sub.-- num feeders.sub.-- per.sub.-- pipette[gt] number of feeders perpipette for          gripper typeflags for each gripper type controlling how parts are assignedP.sub.-- use.sub. -- all.sub.-- feeders[gt]          whether all available feeders are          to be usedP.sub.-- packing.sub.-- criterion[gt]          whether reachability or number is          major criterion for packing partsweights for selecting gripper typeP.sub.-- gripper.sub.-- type.sub.-- wt[gt]          priority of each gripper typeP.sub.-- gripper.sub.-- type.sub.-- feeder.sub.-- wt          importance of availability of          feedersweights for selecting pipettesP.sub.-- reachability.sub.-- wt          importance of reachabilityP.sub.-- fit.sub.-- wt          importance of tightness of fitP.sub.-- multi.sub.-- wt          importance of multiplace (in          general)P.sub.-- multi.sub.-- wt1          importance of potential multiplaceP.sub.-- multi.sub.-- wt2          importance of not blocking          multiplace for rival gripper typesmiscellaneous parametersP.sub.-- first.sub.-- pip          first pipette to be assigned          gripperP.sub.-- low.sub.-- 1fu          whether to assign feeders to large parts beginning with low (1st) or high (4th) logical feed unitP.sub.-- single.sub.-- align          whether to try to make sure that at most one alignment for a chargeHLG algorithm for MCM machinesmainassign.sub.-- grippers to pipettes and allocate feedersassign.sub.-- components to feeders and group components intochargesassign.sub.-- grippersdo until breakfor each gripper type (gt)  determine desirability.sub.-- of.sub.-- gripper.sub.-- type(gt)if no gripper type with positive desirability  breakelse  choose gripper type with highest desirabilityif chosen gripper type (gt) is the first gripper type chosen choose pipette indicated by parameter P.sub.-- first.sub.-- pipelse for each pipette (pip) determinedesirability.sub.-- of.sub.-- pipette(gt,pip)  if some pipette with positive desirabilitychoose pipette with highest desirabilityassign chosen gripper type to chosen pipetteallocate feeders as indicated byP.sub.-- num.sub.-- feeders.sub.-- per.sub.-- pipette[gt] and P.sub.--low.sub.-- 1fuelse for each pipette with same gripper type andavailable feeders determinedesirability.sub.-- of.sub.-- next.sub.-- available.sub.-- feeder(gt,pip)if no feeder with positive desirability  breakelse  choose feeder with highest desirability and  allocate feederdesirability.sub.-- of.sub.-- gripper.sub.-- type(gt)if num.sub.-- feeders.sub.-- available > 0desirability = P.sub.-- gripper.sub.-- type.sub.-- wt[gt] +      (P.sub.-- gripper.sub.-- type.sub.-- feeder.sub.-- wt *      P.sub.-- num.sub.-- feeders.sub.-- targeted[gt] /      num.sub.-- feeders.sub.-- available)else desirability = 0.0if num.sub.-- pipettes.sub.-- assigned[gt] >= P.sub.-- num.sub.--pipettes.sub.-- targeted[gt] desirability *= 0.1desirability.sub.-- of.sub.-- pipette(gt,pip)if pip already assigned a gripper desirability = 0.0else if part needs to be aligned and even numbered pip and P.sub.-- single.sub.-- align desirability = 0.0elsedesirability =      P.sub.-- multi.sub.-- wt * desire.sub.-- multi(gt,pip) +      P.sub.-- reachability.sub.-- wt * desire.sub.-- reachability+      P.sub.-- fit.sub.-- wt * desire.sub.-- fitdesire.sub.-- multi(gt,pip)if n.sub.-- boards > 1examining the siblings of pip that can be used for  multiplace:  num.sub.-- actual.sub.-- multi = count of sibling pipettes with  same gt  num.sub.-- potential.sub.-- mult = count of sibling pipettes with  no gt  num.sub.-- rivals = count of sibling pipettes with  different gt  num.sub.-- rivals blocked = count of sibling pipettes with  different gt  that could use pip for multiplacedesirability =      [num.sub.-- actual.sub.-- multi +      P.sub.-- multi.sub.-- wt1 * num.sub.-- potential.sub.-- multi      +      P.sub.-- multi.sub. -- wt2 * (num.sub.-- rivals -      num.sub.-- rivals.sub.-- blocked)]     / (num.sub.-- boards - 1)else desirability = 1.0;desire.sub.-- reach(gt,pip)if pipette cannot reach board position of any of components of gt desirability = 0else desirability = num.sub.-- pipettes to nearest neighbor of samegriptype / 27desire.sub.-- fit(gt,pip)desirability =1 -  num.sub.-- feeders.sub.-- available.sub.-- to.sub.-- pipette -P.sub.-- num.sub.-- feeders.sub.-- per.sub.-- pipette[gt] /4desirability.sub.-- of.sub.-- next.sub.-- available.sub.-- feeder(gt,pip)2desirability = 0.5 * num.sub.-- feeders.sub.-- allocated[gt.sub.-- of.sub.-- 1st.sub.--neighbor]/ P.sub.-- num.sub.-- feeders.sub.-- targeted[gt.sub.-- of.sub.-- 1st.sub.-- neighbor] +0.5 * num.sub.-- feeders.sub.-- allocated[gt.sub.-- of.sub.-- 2nd.sub.--neighbor]/ P.sub.-- num.sub.-- feeders.sub.-- targeted[gt.sub.-- of.sub.-- 2nd.sub.-- neighbor]assign.sub.-- componentsfor each gripper type (gt) group.sub.-- components(gt) onto tapes assign.sub.-- tapes(gt) to feedersgroup.sub.-- components(gt)determine number of tapes to be allocated to each component type of same gt so that the largest number of any components on tape iskeptto a minimum and  if P.sub.-- use.sub.-- all feeders[gt] so that all assigned feeders are usedassign.sub.-- tapes(gt)if num.sub.-- boards > 1do while there are unassigned tapes with parts groupedbyboard and properly spaced available feeders  assign set of tapes with largest number ofcomponents  do while there are unassigned tapes and available feeders if P.sub.-- packing.sub.-- criterion[gt] is 0  assign tape whose components are the mostconstrained    with regard to reachability (fewest number of pipettes can   reach coordinates) else if P.sub.-- packing.sub.-- criterion[gt] is 1  assign tape with the greatest number of componentsFor the FCM:/*** chromosome format:for each gripper type        3 bits PM weight [1/8-8/8]        1 bit PM preference bit        for each feeder type 3 bits FT weight [1/8-8/8]4 bits for sort option4 bits for sort bits (ascending/descending)1 bit for each part group for bucket selection***/__________________________________________________________________________
1. A method for optimizing configuration of a computer-controlled part pick-and-place machine for placing parts on a PCB, said machine comprising a support for the PCB, a plurality of gripping devices, a plurality of numbered feeders for holding parts for placing on the PCB, and means for activating the gripping devices to pick up selected parts from selected feeders and place them on selected positions on the PCB in accordance with one of a plurality of charges, each charge representing a specific set of parts which are picked and placed as a group and each group movement constituting one charge and a list of charges necessary to place on the parts on the PCB constituting a charge map capable of controlling operation of the machine, the method comprising the steps of:
(a) creating an initial population of chromosome strings each representing a set of parameters that control how a charge map is generated for controlling operation of the machine in order to place a given set of parts at given part locations on a given PCB,
(b) providing a charge map generator, responsive to a given chromosome string, for generating the configuration and for computing a placement time for placing the given set of parts-on the given PCB, with the machine in the configuration,
(c) using a genetic algorithm to generate from the chromosome strings new chromosome strings,
(d) evaluating the new chromosome strings generated in step (c) by supplying same to the charge map generator,
(e) iterating steps (c) and (d) substituting those new chromosome strings for the chromosome strings if the new chromosome strings result in a lesser placement time than the chromosome strings, until a specified number of chromosome strings have been generated and evaluated or the chromosome population has been brought to convergence, and
(f) outputting a best chromosome string found through iteration as representing a desired machine configuration.
(g) configuring the machine in accordance with the best chromosome string outputted in step (f), and
(h) operating the machine to place the given set of parts on PCBs in accordance with the charge map generated in step (b) after the last iterating step.
3. The method of claim 1, wherein step (a) uses at least the following parameters represented in the chromosome string:
(ai) parameters for controlling priority of assigning gripper types and a number of feeders ideally associated with each gripper type,
(aii) parameters for controlling assignment of pipette positions to gripper types by assigning the priority to the following criteria: reachability limitations, tightness of fit, multiplace opportunities,
(aiii) parameters for controlling how feeders are allocated to pipettes by specifying an initial number of feeders per pipette position assigned per gripper type and for controlling in what order feeders are assigned,
(aiv) parameters for controlling how parts are distributed over feeder positions by controlling how tightly parts are packed or how the distribution is permitted,
(av) parameters for controlling which parts are assigned to which feeders by controlling the order that part types are assigned.
4. The method of claim 3, wherein each gripping device comprises a pipette and a gripper mounted on the pipette and the charge generator of step (b) uses the following steps to generate a charge map:
(i) until all feeder slots have been allocated:
choose a gripper type gt, based on ai
choose a pipette position pp for gt, based on aii
allocate feeders reachable by pp, based on aiii
(ii) for each gripper type assigned:
determine how many feeders will be assigned to each part type, based on aiv
assign parts to specific feeders, based on av.
5. The method of claim 1, wherein the genetic algorithm used in step (c) is a genetic algorithm eliminating incestuous matings between parent chromosome strings, applying crossover to pairs of parent strings to create new offspring and employing survival of the fittest involving both parent and child chromosome strings, and applying population mutation only when the new chromosome strings converge after a limited number of iterations.
6. The method of claim 1, wherein each gripping device comprises a pipette and a gripper mounted on the pipette and the chromosome represents at least the following parameters:
a first weight for each gripper type, which weight influences the order in which gripper-to-pipette decisions are made;
a pipette preference bit for each gripper type, which pipette preference influences the gripper-to-pipette decisions when more than one pipette are equally desirable;
a second weight for each feeder type gripper type pair, which second weight influences the order of decisions on feeder types to feeder slots;
sort parameters for influencing an order in which the parts are considered when the parts are assigned to feeder slots and index step; and
a preference bit for each part, which preference bit influences the choice of feeder location and index step.
7. A method for optimizing configuration of a computer-controlled part pick-and-place machine for placing parts on a PCB, said machine comprising a support for the PCB, a plurality of numbered pipettes exceeding six in number, a plurality of numbered grippers for different sized or shaped parts, each gripper being capable of being mounted on an associated pipette, a plurality of numbered feeders for holding the parts needed for populating the PCB, and means for activating the pipettes to move them, as a group, to pick up with their associated gripper selected parts from selected feeders and place the selected parts on selected positions on the PCB in accordance with one of a plurality of charges stored in the machine, each charge representing a specific set of parts which are picked as a group and each group movement constituting one charge and a list of charges necessary to place the parts a PCB constituting a charge map capable of controlling the operation of the machine, comprising the steps:
(a) creating an initial population of chromosome strings each represented by a plurality of bits and sets of bits, each chromosome string representing a set of parameters that control how a charge map is generated for controlling operation of the machine in order to place a given set of parts at given part locations on a given PCB, with a bit or set of bits in the chromosome string representing at least the following parameters:
i) parameters for controlling priority of assigning gripper types and a number of feeders ideally associated with each gripper type;
ii) parameters for controlling assignment of pipette positions to gripper types by assigning the priority to the following criteria: reachability limitations, tightness of fit, multiplace opportunities;
iii) parameters for controlling how feeders are allocated to pipettes by specifying an initial number of feeders per pipette position assigned per gripper type and for controlling in what order feeders are assigned;
(iv) parameters for controlling how parts are distributed over feeder positions by controlling how tightly parts are packed;
(v) parameters for controlling which parts are assigned to which feeders by controlling the order that part types are assigned;
(b) providing a charge map generator, responsive to a given chromosome string, for generating the configuration and for computing a placement time for placing the given set of parts on the given PCB, with the machine in the configuration, the charge map generator using the following steps to generate a charge map:
choose a pipette position pp for gt, based on aii if pipette position pp available:
8. A method for optimizing configuration of a computer-controlled part pick-and-place machine for placing parts on a PCB, said machine comprising a support for at least one PCB, at least one numbered pipette, a plurality of numbered grippers for different-sized or different-shaped parts, each gripper being capable of being mounted on an associated pipette, a plurality of numbered feeders for holding the parts for placing on the PCB, and means for activating the at least one pipette to pick up with the associated gripper selected parts from selected feeders and place the selected parts on selected positions on the PCB in accordance with a layout stored in the machine, comprising the steps of:
(a) creating a population of chromosome strings each represented by a plurality of bits and sets of bits, the chromosome strings representing a plurality of parameters for controlling a heuristic layout generator the chromosome string also representing one complete machine configuration to place given parts on a given PCB,
(b) providing a heuristic layout generator which is capable, when supplied with a given chromosome string representing a given machine configuration, of computing a complete layout, and from the complete layout computing a placement time for populating a PCB with the machine in said given configuration,
(c) using a genetic algorithm to generate chromosome strings representing possible solutions to the problem of determining a machine configuration to minimize placement time
(d) iterating steps (b) and (c) until a chromosome string is generated representing a machine configuration which places the given parts on the given PCB in an acceptably short time.
9. The method of claim 8, wherein there are at least 3 pipettes and the parameters of step (a) include a target number of pipettes to be assigned to each gripper, which also influences the order of the gripper-to-pipette decisions.
10. The method of claim 8 wherein the genetic algorithm is CHC and comprises producing new offspring solutions from previously tested parent solutions
by crossing over some of the bits in their chromosomes,
eliminating incestuous matings between parents whose chromosomes are too similar,
employing survival of the fittest involving both parent and offspring chromosome strings, and
applying population mutation only when the generated solutions converge after a limited number of iterations.
11. The method of claim 8 wherein the chromosome string represents at least the following parameters:
a first weight for each gripper type, which first weight influences the order in which gripper-to-pipette decisions are made;
a pipette preference indication for each gripper type, which pipette preference indication influences the gripper-to-pipette decisions when more than one pipette are equally desirable;
a second weight for each feeder type for each gripper type, which second weight influences the order of decisions on feeder types to feeder slots;
sort parameters for influencing the order in which the parts are considered when assigning the parts to feeder slots and index step and
a preference indication for each part, which preference indication influences the choice of feeder location and index step.
12. A method for optimizing configuration of a computer-controlled part pick-and-place machine for placing parts on a PCB, said machine comprising a support for the PCB, a plurality of numbered pipettes exceeding six in number, a plurality of numbered grippers for different sized or shaped parts, each gripper being capable of being mounted on an associated pipette, a plurality of numbered feeders for holding the parts needed for populating the PCB, and means for activating the pipettes to pick up with their associated gripper selected parts from selected feeders and place them on selected positions on the PCB in accordance with a layout stored in the machine, comprising the steps of:
(a) creating a population of chromosome strings each represented by a plurality of bits and sets of bits, each chromosome string representing a layout for the machine, with a bit or set of bits in the chromosome string representing at least the following parameters: pipette number, feeder number, part number, gripper number assigned to pipette number, part number to be picked up by pipette at a particular time, and part numbers assigned to feeder numbers, the chromosome string also representing one complete machine configuration to a given set of parts on a given PCB,
(b) providing a heuristic layout generator which is capable, when supplied with a given chromosome string representing a given machine configuration, of computing the placement time for populating a PCB with the machine in said given configuration,
(c) using a genetic algorithm, CHC, to generate chromosome strings representing possible solutions to the problem of determining a machine configuration to minimize placement time, said genetic algorithm eliminating incestuous matings between parent and child chromosome strings, employing survival of the fittest involving both parent and child chromosome strings, and applying population mutation only when the generated solutions converge after a limited number of iterations,
(d) testing solutions generated in step (c) by supplying same to the heuristic layout generator,
(e) iterating steps (c) and (d) until a chromosome string is generated representing a machine configuration producing a desired shortened placement time.
13. A method for optimizing configuration of a computer-controlled part pick-and-place machine for populating a PCB, said machine comprising a support for a PCB, a plurality of pipettes, at least one gripping device for holding parts, a plurality of numbered feeders for holding the parts needed for populating the PCB, and means for activating the gripping device to pick up selected parts from selected feeders and place the selected parts on selected positions on the PCB in accordance with a digital specification, the method comprising the following steps:
a) creating an initial population of chromosome strings, each representing a respective candidate digital specification;
b) using a genetic algorithm to generate new chromosome strings;
c) evaluating the new chromosome strings;
d) repeating steps b) and c) until a stopping criterion is reached; and
e) outputting the best chromosome string found after step d) as representing a desired machine configuration.
14. The method of claim 13 wherein each chromosome string comprises an indication of an allocation of the parts to the feeders.
16. The method of claim 13 wherein each gripping device comprises a pipette and a gripper and each chromosome string comprises
an indication of an allocation of the grippers to the pipettes; and
an indication of an allocation of the parts to the feeders.
17. The method of claim 16 wherein the pick-and-place machine populates a family of PCBs and the digital specification corresponds to all of the PCBs, whereby the configuration indicates a single layout for the family.
the pick-and-place machine includes a plurality of gripping devices;
the digital specification includes a plurality of charges, each charge representing a specific set of parts which are picked and placed as a group, each group movement constituting one charge, and a list of charges necessary to place a given set of parts on a given PCB constitutes a charge map capable of controlling the operation of the machine; and
each chromosome string includes an indication of a charge map.
each chromosome string controls how a digital specification is generated; and
the method further comprises the step of using a generator to generate the respective candidate digital specification from the chromosome string and compute the placement time for populating the PCB using the pick-and-place machine using the respective candidate digital specification; and
the evaluating step includes supplying each chromosome string to the generator.
each gripping device includes a pipette and a gripper;
the digital specification includes a plurality of charges, each charge representing a specific set of parts which are picked and placed as a group, each group movement constituting one charge, and a list of charges necessary to place a given set of parts on a given PCB constitutes a charge map capable of controlling the operation of the machine;
each chromosome string includes
an indication of an allocation of grippers to pipettes;
an indication of an allocation of parts to feeders; and
an indication of a charge map.
21. The method of claim 13 wherein at least one gripping device makes a plurality of trips to the feeders to pick up parts and each chromosome string includes an indication of which parts to pick up on which trip.
US07965474 1992-10-23 1992-10-23 Method for optimizing the configuration of a pick and place machine Expired - Fee Related US5390283A (en)
US07965474 US5390283A (en) 1992-10-23 1992-10-23 Method for optimizing the configuration of a pick and place machine
DE1993627505 DE69327505D1 (en) 1992-10-23 1993-10-15 Configuration method and apparatus of a component placement machine
EP19930202898 EP0594251B1 (en) 1992-10-23 1993-10-15 Method and apparatus for configuring a component placement machine
DE1993627505 DE69327505T2 (en) 1992-10-23 1993-10-15 Configuration method and apparatus of a component placement machine
JP26631793A JP3320523B2 (en) 1992-10-23 1993-10-25 Configuration optimization method for computer-controlled mounting machine
US5390283A true US5390283A (en) 1995-02-14
ID=25510017
US07965474 Expired - Fee Related US5390283A (en) 1992-10-23 1992-10-23 Method for optimizing the configuration of a pick and place machine
US (1) US5390283A (en)
JP (1) JP3320523B2 (en)
DE (2) DE69327505D1 (en)
EP (1) EP0594251B1 (en)
WO1998028963A1 (en) * 1996-12-23 1998-07-02 Koninklijke Philips Electronics N.V. Method and apparatus for optimizing the layout and charge maps of a flowline of pick and place machines
WO1998028964A1 (en) * 1996-12-23 1998-07-02 Koninklijke Philips Electronics N.V. Method and apparatus for optimizing the layout and charge maps of a flowline of pick and place machines
WO1999014608A1 (en) * 1997-09-15 1999-03-25 Tellabs Denmark A/S A method of controlling test probes in a testing apparatus for electronic printed circuit boards, and an apparatus for performing the method
US6260178B1 (en) * 1999-03-26 2001-07-10 Philips Electronics North America Corporation Component placement machine step size determination for improved throughput via an evolutionary algorithm
US20020013776A1 (en) * 2000-06-28 2002-01-31 Tomoaki Kishi Method for controlling machine with control mudule optimized by improved evolutionary computing
WO2002056125A2 (en) * 2001-01-12 2002-07-18 Koninklijke Philips Electronics N.V. Modular optimizer with precedence constraint-handling feature for optimization of component placement machines
US6594531B2 (en) 2000-12-22 2003-07-15 Koninklijke Philips Electronics N.V. Modular optimizer with foreign module learning feature for optimization of component placement machines
US7076313B2 (en) 2003-06-06 2006-07-11 Visteon Global Technologies, Inc. Method for optimizing configuration of pick-and-place machine
KR100722622B1 (en) 2005-09-28 2007-05-28 삼성전기주식회사 Intelligence DES Machine and method thereof
US20120165972A1 (en) * 2009-09-11 2012-06-28 Daniel Wappling Pick And Place
CN103717007A (en) * 2014-01-22 2014-04-09 哈尔滨工业大学 Multiple-suction-nozzle chip mounter mounting process optimization method based on clustering analysis and genetic algorithm
FR2767396B1 (en) * 1997-08-14 2001-10-19 Aerospatiale Method for interleaving elementary pieces in one or more panels to be machined
L. J. Eshelman, "The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination", Foundations of Genetic Algorithms & Classifier Systems, Calif., 1991 (Philips TR-90-006).
L. J. Eshelman, The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination , Foundations of Genetic Algorithms & Classifier Systems, Calif., 1991 (Philips TR 90 006). *
PA 1004, MCM 8, Philips. Mar. 6, 1992. *
Task scheduling for flexible manufacturing systems based on genetic algorithm Edwin S. H. Hou et al. 13 16 Oct. 1991. *
Task scheduling for flexible manufacturing systems based on genetic algorithm Edwin S. H. Hou et al. 13-16 Oct. 1991.
Use of genetic algorithm for economic optimization of a manufacturing system. R. F. Tenga Apr. 18, 1988. *
US6275815B1 (en) 1996-12-23 2001-08-14 Philips Electronic North America Corp. Apparatus for optimizing the layout and charge maps of a flowline of pick and place machines
WO2002056125A3 (en) * 2001-01-12 2003-03-20 Koninkl Philips Electronics Nv Modular optimizer with precedence constraint-handling feature for optimization of component placement machines
EP2149929A1 (en) * 2008-07-28 2010-02-03 Sony Corporation Electric field coupler, communication apparatus, communication system, and fabrication method for electric field coupler
US8198960B2 (en) 2008-07-28 2012-06-12 Sony Corporation Electric field coupler, communication apparatus, communication system, and fabrication method for electric field coupler
CN101640554B (en) 2008-07-28 2013-07-03 索尼株式会社 Electric field coupler, communication apparatus, communication system, and fabrication method for electric field coupler
US8565912B2 (en) * 2009-09-11 2013-10-22 Abb Technology Ltd. Pick and place
CN102648442B (en) * 2009-09-11 2015-03-11 Abb技术有限公司 Improved pick and place
EP0594251A2 (en) 1994-04-27 application
JPH06215087A (en) 1994-08-05 application
DE69327505D1 (en) 2000-02-10 grant
JP3320523B2 (en) 2002-09-03 grant
EP0594251A3 (en) 1994-11-09 application
EP0594251B1 (en) 2000-01-05 grant
DE69327505T2 (en) 2000-08-24 grant
Liu et al. 2007 An effective PSO-based memetic algorithm for flow shop scheduling
Gehring et al. 2002 A parallel genetic algorithm for solving the container loading problem
Gottlieb et al. 1998 Genetic algorithms for the fixed charge transportation problem
Kim et al. 1996 Sequencing in mixed model assembly lines: a genetic algorithm approach
Mendes et al. 2002 Comparing meta-heuristic approaches for parallel machine scheduling problems
Merz et al. 2000 Fitness landscape analysis and memetic algorithms for the quadratic assignment problem
Gen et al. 2014 Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey
Chutima et al. 2012 Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimisation with negative knowledge
Gordon et al. 1993 Serial and parallel genetic algorithms as function optimizers
Grötschel et al. 2001 Online optimization of complex transportation systems
Diwold et al. 2011 Performance evaluation of artificial bee colony optimization and new selection schemes
Hopper et al. 2001 A review of the application of meta-heuristic algorithms to 2D strip packing problems
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:ESHELMAN, LARRY J.;SCHAFFER, JAMES D.;REEL/FRAME:006310/0593
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:PHILIPS ELECTRONICS NORTH AMERICA CORPORATION;REEL/FRAME:014990/0337
Free format text: CORRECTIVE ASSIGNMENT TO CORRECT THE INCORRECT SERIAL NO. 09/773,898 PREVIOUSLY RECORDED AT REEL: 014990 FRAME: 0337. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNMENT;ASSIGNOR:PHILIPS ELECTRONICS NORTH AMERICA CORPORATION;REEL/FRAME:038129/0368