Method for optimizing the configuration of a pick and place machine

• US 5,390,283 A
• Filed: 10/23/1992
• Issued: 02/14/1995
• Est. Priority Date: 10/23/1992
• Status: Expired due to Fees

• Current Assignee: Assembleon B.V.
• Original Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Inventors: Schaffer, James D., Eshelman, Larry J.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): DORVIL, RICHEMOND
• Application Number:
  US07/965,474
• Time in Patent Office: 844 Days
• Field of Search: 395/13, 395/21, 364/468, 364/482, 364/402
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06Q 10/043 Optimisation of two dimensional placement, e.g. cutting of clothes or wood
• CPC Class Codes: H05K 13/085 Production planning, e.g. of allocation of products to machines, of mounting sequences at machine or facility level

Abstract

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.

Claims

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.

2. The method of claim 1, further comprising the steps of:

(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

if pipette position pp available;

allocate feeders reachable by pp, based on aiii

else

allocate unused feeder for a pipette already assigned gt

(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;

(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 if pipette position pp available;

allocate feeders reachable by pp, based on aiii

else

allocate unused feeder for a pipette already assigned gt

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

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.

15. 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.

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.

18. The method of claim 13 wherein

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.

19. The method of claim 13 wherein

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.

20. The method of claim 13 wherein

the pick-and-place machine includes a plurality of gripping devices;

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.