Method for optimizing the configuration of a pick and place machine
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
69 Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (9, 10, 11)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21)
-
Specification