Apparatus for optimizing the layout and charge maps of a flowline of pick and place machines

• US 5,864,833 A
• Filed: 12/23/1996
• Issued: 01/26/1999
• Est. Priority Date: 12/23/1996
• Status: Expired due to Fees

• Current Assignee: Assembleon B.V.
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Mani, Murali, Schaffer, J. David
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/772,392
• Time in Patent Office: 764 Days
• Field of Search: 364/474.11, 364/474.15, 364/474.23, 395/13, 395/81, 395/82, 395/51, 706/13, 706/45
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H05K 13/04 Mounting of components , e.g. of leadless components

Abstract

An apparatus uses a computer-controlled algorithm that enables production of high-quality layouts and charge maps or, set-ups for arbitrary printed circuit boards for electronic component placement machines alone or as one of many in a production line. A class of algorithms known as genetic algorithms employing an initial population of chromosomes are used. Each chromosome represents a set of parameters that control how a layout and charge maps are generated. Problem descriptors, based on one time code are generated. An adaptive searcher searches parameters and generates trial solutions as chromosomes and a heuristic layout generator interprets these chromosomes to generate the layout and charge maps using the problem descriptors.

Claims

1. An optimizer for generating layout and charge maps of a flowline of component placement machines, the optimizer comprising:

means for creating an initial population of chromosomes, each chromosome representing a set of parameters that control how layout and charge maps are generated;

means for generating problem descriptors based on one time code;

an adaptive searcher for searching parameters and generating trial solutions as chromosomes; and

a heuristic layout generator interpreting these chromosomes to generate the layout and charge maps using the problem descriptors, determining a merit measure for each generated layout and charge map and returning the merit measure for respective chromosomes to the adaptive searcher,

the adaptive searcher generating new chromosomes based on the merit measure and prior chromosomes, and

the heuristic layout generator providing final optimized charge maps and a layout when prespecified criteria based on the merit measures are met.

2. An optimizer as recited in claim 1, wherein the heuristic layout generator comprises:

means for assigning grippers to pipette modules; and

if a nozzle exchange unit is present in any of the component placement machines, means for assigning nozzles to slots in the nozzle exchange unit.

3. An optimizer as recited in claim 1, wherein the heuristic layout generator comprises:

means for assigning feeder bars to specific component placement machines;

means for assigning feeders to available slots on feeder bars; and

if a tray stacker is present in any of the component placement machines, means for assigning pallets and trays to available slots on the tray stackers.

4. An optimizer as recited in claim 1, wherein the heuristic layout generator comprises:

means for assigning each part to be placed on a printed circuit board, to a gripper of a plurality of grippers having an appropriate pipette module and an appropriate nozzle of a plurality of nozzles.

5. An optimizer as recited in claim 1, wherein the heuristic layout generator comprises:

means for assigning grippers to pipette modules and, if a nozzle exchange unit is present in any of the component placement machines, assigning nozzles to slots in the nozzle exchange unit and associating each nozzle to a respective pipette module;

means for assigning feeders to available slots on feeder bars, and if a tray stacker is present in any of the component placement machines, assigning pallets and trays to available slots on tray stackers;

means for assigning each part to be placed on a printed circuit board, to a gripper of a plurality of grippers having an appropriate pipette module and a nozzle of a plurality of nozzles; and

means for calculating a merit measure.

6. An optimizer for generating layout and charge maps of a flowline of component placement machines, the optimizer comprising:

a pre-processor creating problem descriptors based on at least one file containing a parts list, a definition of the flowline, the flowline including multiple machines and different types of machines, and specifications of all hardware based on specified information; and

a problem solver including an adaptive searcher and a heuristic layout generator, for finding layouts and charge maps meeting prespecified criteria.

7. An optimizer as recited in claim 6, wherein the adaptive searcher analyzes chromosomes based on initially randomly assigned chromosomes, and produces new chromosomes in a simulation of an evolutionary search for high performance sets.

8. An optimizer as recited in claim 7, wherein:

the heuristic layout generator evaluates a fitness of each chromosome and communicates at least one fitness value of each chromosome to the adaptive searcher; and

the adaptive searcher produces new chromosomes in response to the fitness values received.

9. An optimizer as recited in claim 6, wherein:

the charge map specifies which parts are to be placed, by which gripper and in what order;

the file sets forth problem descriptors, for each part type, a package type, and a number of those parts required to be placed; and

the preprocessor produces an accommodation matrix based on the file produced by the preprocessor, the accommodation matrix setting forth nozzles, and phi placement units useable by each package type.

10. An optimizer as recited in claim 9, wherein:

the problem solver determines a composition of phantom grippers based on the accommodation matrix;

problem descriptors are computed for each phantom gripper; and

the heuristic layout generator comprises;

a calculator calculating gripper desirability for each gripper in the flowline and assigns grippers to pipette modules;

a first analyzer analyzing feeder types and feeder slots and assigning each feeder type to a feeder slot;

a second analyzer assigning parts to charges including which gripper and feeder are to be used; and

a timing processor running a timing model to produce merit measures.

11. An optimizer as recited in claim 10, wherein the first analyzer includes:

means for establishing minimum conditions for a feasible layout; and

means for establishing an allocation of grippers to enable an optimal leveling of workload.

12. An optimizer as recited in claim 11, wherein the means for establishing minimum conditions for a feasible layout comprises:

a) means for determining a number of grippers to assign;

b) means for determining for each gripper, a desirability of each gripper;

c) means for determining for a most desirable gripper based on the desirabilities determined, a desirability of each pipette module not yet assigned;

d) means for assigning the most desirable gripper to a most desirable pipette module including tallying feeder bar shares for each phantom gripper; and

e) means for ascertaining that each gripper has been assigned.

13. An optimizer as recited in claim 11, wherein:

at least one component placement machine comprises a nozzle exchange unit for holding nozzles, the nozzle exchange unit having slots for holding nozzles; and

the means for establishing minimum conditions for a feasible layout comprises;

a) means for determining a number of grippers to assign;

b) means for determining for each gripper, a desirability of each gripper;

c) means for determining for a most desirable gripper based on the desirabilities determined, a desirability of each pipette module not yet assigned;

d) means for assigning the most desirable gripper to a most desirable pipette module including tallying feeder bar shares for each phantom gripper; and

e) means for ascertaining that each gripper has been assigned.

14. An optimizer as recited in claim 13, wherein:

each feeder bar has slots and each gripper is one of a plurality of gripper types;

the calculator for calculating the desirability of each gripper, includes a summer for summing a nozzle slot opportunity value for each part handled by a gripper for each feeder bar slot on the pipette module, comprising;

means for determining for a given slot on a preassigned feeder bar, a pipette module, a gripper type and a status of a given slot;

means for calculating a ceiling of a ratio of a number of parts covered by the gripper whose part type differs from the given part'"'"'s part type; and

means for calculating the nozzle slot opportunity value using the ceiling of the ratio the number of parts and a slot value representing an approximation of slots covered by the feeder type of the given part plus one.

15. An optimizer as recited in claim 10, wherein the calculator performs desirability calculations to make gripper assignment decisions based on a minimum required feeder bar space.

16. An optimizer as recited in claim 10, wherein the calculator performs desirability calculations to make gripper assignment decisions based on a prorated share of a pick and place workload each gripper can accomplish.

17. An optimizer as recited in claim 10, wherein the calculator comprises:

means for computing a desirability of each gripper;

means for determining a most desirable gripper and a respective machine of the most desirable gripper, and computing a desirability of each pipette module not assigned and a desirability of each nozzle exchange unit slot not assigned, if a nozzle exchange unit is present on a component placement machine of the flowline;

means for assigning the most desirable gripper to the most desirable pipette module, placing a respective nozzle in the most desirable nozzle exchange unit slot, if a nozzle exchange unit is present on the respective machine; and

means for tallying phantom feeder bar shares.

18. An optimizer as recited in claim 17, wherein the means for tallying phantom feeder bar shares includes assigning each contending phantom a prorated share of a respective feeder bar based on feeder bar share weights of each contending phantom.

19. An optimizer as recited in claim 10, wherein the first analyzer comprises:

a grouper grouping different feeder types based on part types specified in the program descriptors into feeder groups and assigning a specific order for processing of the feeder groups; and

a feeder type assigner for assigning feeder types, the feeder type assigner including;

means for computing a desirability of each phantom gripper;

means for selecting a most desirable phantom gripper based on the computed desirability and computing a desirability of each feeder type;

means for selecting a slot combination on a feeder bar assigned to the phantom gripper;

means for assigning a most desirable feeder type to a most desirable slot and for tallying the most desirable slot to the phantom gripper;

means for updating a feeder bar space assigned value; and

means for recalculating flowline feeder bar space available.

20. An optimizer as recited in claim 10, wherein the first analyzer comprises:

a slot calculator calculating a slot desirability; and

a tray assigner assigning trays to a tray stacker in a prespecified pattern.

21. An optimizer as recited in claim 10, wherein the second analyzer comprises:

a leveler for leveling time buckets associated with an FCM machine and charges within a charge map for an ACM machine.

22. An optimizer as recited in claim 6, wherein prespecified criteria includes minimum placement times and at least one of:

minimum feeders, and minimum amount of hardware.

23. An optimizer as recited in claim 6, wherein the adaptive searcher includes a machine controller for specifying to which machine type each part type is assigned.

24. The apparatus of claim 6 in which the adaptive searcher selects multiple sets of initial conditions.

25. The apparatus of claim 6 in which the adaptive searcher adapts multiple sets of new initial conditions based on comparing the results of previous initial conditions.

26. An optimizer for producing a layout and charge maps for a flowline of component placement machines, each machine having a plurality of grippers, each gripper having a pipette module, a phi placement unit, and a nozzle, and at least one feeder bar having a plurality of feeders, the optimizer comprising:

a pre-processor for creating problem descriptors based on at least one file containing a parts list, a definition of the flowline, and specifications of all hardware based on specified information;

a problem solver for finding a layout and charge maps meeting prespecified criteria, comprising;

an adaptive searcher and

a heuristic layout generator.

27. An optimizer as recited in claim 26, wherein a user may preassign specifications in the at least one file.

28. An optimizer as recited in claim 27, wherein the preassigned specifications may include at least one of the following:

a phi placement unit to a specific pipette module;

a phi placement unit and a nozzle to a specific pipette module;

a blocked pipette module;

a feeder bar to a specific pipette module with a specific phi placement unit and nozzle assigned or without a phi placement unit or nozzle assigned;

a blocked feeder bar;

feeder types for any slot on a specific feeder bar;

blocked feeder types; and

part types for a specific feeder type.

29. An optimizer as recited in claim 28, wherein:

at least one machine includes a tray stacker;

the user may further preassign at least one of the following;

a tray stacker to a specific pipette module with a phi placement unit and a nozzle assigned or without a phi placement unit or nozzle assigned;

a pallet to a specific slot on a specific tray stacker;

a pallet with trays to a specific slot on a specific tray stacker;

a blocked pallet;

a part type for a specific position within a specific tray; and

a blocked tray.

30. An optimizer as recited in claim 26, wherein:

a nozzle exchange unit having slots, holds a plurality of nozzles;

the heuristic layout generator assigns nozzles to slots and the nozzles to specific pipette modules and phi placement units, and

the heuristic layout generator generating charge maps which can include swapping nozzles in and out of a nozzle exchange unit for use by at least one pipette module during operation.

31. An optimizer as recited in claim 26, wherein:

the problem descriptors include estimations of pick and place time for parts; and

the estimations include at least one of travel to a pick location, pick-up time, travel to an alignment camera, travel to fiducial marks, travel to place location, place time, and travel to a coplanarity checker.

32. A method for producing printed circuit board assemblies, comprising the steps of:

providing a printed circuit layout including multiple component site locations and component type identifications for the locations;

providing a line multiple placement modules each including one or more component sources and one or more placement mechanisms;

the multiple placement modules including modules having different structures which effect operation;

generating an initial population of chromosomes, each chromosome representing a set of process parameters for placing the components at the component sites, including selecting respective placement modules, the contents of the component sources, and the order of placement of the multiple components;

interpreting the chromosomes to generate a measure of merit of the parameters for each solution;

adaptively generating a multitude of trial solutions as chromosomes which generation depends on the previous solutions and their respective measures of merit;

repeating the interpreting and adaptive generating steps until predetermined criteria are satisfied;

identifying the generated chromosome with the highest measure of merit;

providing printed circuit boards and components; and

placing the components at the component sites according to the set of process parameters represented by the chromosome identified as having the highest measure of merit.

33. The method of claim 32 in which the effects on the operation of modules due to differences in the modules is considered in generating the measure of merrit.

34. The method of claim 32 in which the placement mechanisms of the placement modules, have different structures that effect operation including one of:

a different number of placement heads, different degrees of freedom, different maximum speeds for the degrees of freedom, different accelerations for degrees of freedom, different positions relative to feeders or component positions, different vision systems, and different accuracies.

35. The method of claim 32 in which the chromosomes also represent the positions and contents of component supplies and the path along which components are moved.