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

• US 5,909,674 A
• Filed: 12/23/1996
• Issued: 06/01/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,393
• Time in Patent Office: 890 Days
• Field of Search: 364/474.11, 364/474.15, 364/474.23, 395/13, 395/51, 395/81, 395/82, 706/13, 706/45
• US Class Current: 706/13
• 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 method 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. A method for generating a layout and charge maps of a flowline of component placement machines, the method comprising:

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

b) generating problem descriptors based on one time code;

c) searching parameters and generating trial solutions as chromosomes; and

d) 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 step c) further generates new chromosomes based on the merit measure and prior chromosomes, and

the step d) further provides final optimized charge maps and a layout when prespecified criteria based on the merit measures are met.

2. A method as recited in claim 1, wherein the step d) further comprises:

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.

3. A method as recited in claim 1, wherein the step d) further comprises:

assigning feeder bars to specific component placement machines;

assigning feeders to available slots on feeder bars;

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

4. A method as recited in claim 1, wherein the step d) further comprises:

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. A method as recited in claim 1, wherein the step d) further comprises:

i) 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;

ii) 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;

iii) 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

iv) calculating a merit measure.

6. A method for generating layout and charge maps of a flowline of component placement machines, the method comprising the step of:

a) pre-processing to create 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 specific information;

b) problem solving including adaptive searching and heuristic layout generating, for finding layouts and charge maps meeting prespecified criteria.

7. A method as recited in claim 6, wherein the adaptive searching of step b) analyzes chromosomes based on initially randomly assigned chromosomes, and produces new chromosomes in a simulation of an evolutionary search for high performance sets.

8. A method as recited in claim 7, wherein:

the heuristic layout generating of step b) evaluates a fitness of each chromosomes and communicates at least one fitness value of each chromosomes for use in the adaptive searching; and

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

9. A method 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;

the preprocessing of step b) 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. A method as recited in claim 9, wherein:

the problem solving of step b) determines a composition of phantom grippers based on the accommodation matrix;

problem descriptors are computed for each phantom gripper;

the heuristic layout generating of step b) comprises the further steps of;

calculating gripper desirability for each gripper in the flowline and assigning grippers to pipette modules;

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

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

running a timing model to produce merit measures.

11. A method as recited in claim 10, wherein the step of analyzing feeder types includes:

establishing minimum conditions for a feasible layout; and

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

12. A method as recited in claim 11, wherein establishing minimum conditions for a feasible layout comprises the steps of:

a) determining a number of grippers to assign;

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

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

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

e) ascertaining that each gripper has been assigned.

13. A method as recited in claim 6, wherein prespecified criteria includes minimum placement times and at least one of:

minimum feeders, and minimum amount of hardware.

14. A method as recited in claim 10, wherein the calculating includes performing desirability calculations to make gripper assignment decisions based on a minimum required feeder bar space.

15. A method as recited in claim 11, wherein:

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

the step of establishing minimum conditions for a feasible layout comprises the steps of;

a) determining a number of grippers to assign;

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

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

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

e) ascertaining that each gripper has been assigned.

16. A method as recited in claim 15, wherein:

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

the calculating the desirability of each gripper includes;

summing a nozzle slot opportunity value for each part handled by a gripper for each feeder bar slot on the pipette module comprising the steps of;

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

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

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.

17. A method as recited in claim 6, wherein the step of adaptive searching includes specifying to which machine type each part type is assigned.

18. A method as recited in claim 10, wherein the calculating includes performing desirability calculations to make gripper assignment decisions based on a prorated share of a pick and place workload each gripper can accomplish.

19. A method as recited in claim 10, wherein the calculating comprises the steps of:

computing a desirability of each gripper;

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;

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

tallying phantom feeder bar shares.

20. A method as recited in claim 19, wherein the step of 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.

21. A method as recited in claim 10, wherein the analyzing comprises the steps:

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

assigning feeder types, the feeder type assigner including;

computing a desirability of each phantom gripper;

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

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

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

updating a feeder bar space assigned value; and

recalculating flowline feeder bar space available.

22. A method as recited in claim 10, wherein the step of analyzing feeder types and feeder slots comprises:

calculating a slot desirability; and

assigning trays to a tray stacker in a prespecified pattern.

23. A method as recited in claim 10, wherein the step of assigning parts to charges comprises the steps of:

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

24. A method for producing a layout and charge maps for a flowline of component placement machines, each machine comprising 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 method comprising:

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;

finding a layout and charge maps meeting prespecified criteria, comprising the steps of;

adaptive searching and

heuristic layout generating.

25. A method as recited in claim 24, wherein a user may preassign specifications in the at least one file.

26. A method as recited in claim 25, 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.

27. A method as recited in claim 26, 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.

28. A method as recited in claim 24, wherein:

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

the heuristic layout generating step assigns nozzles to slots and the nozzles to specific pipette modules and phi placement units, and generates 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.

29. A method as recited in claim 24, 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.