Component placement machine step size determination for improved throughput via an evolutionary algorithm

• US 6,260,178 B1
• Filed: 03/26/1999
• Issued: 07/10/2001
• Est. Priority Date: 03/26/1999
• Status: Expired due to Fees

• Current Assignee: Assembleon B.V.
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Schaffer, J. David
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Speight, Jibreel
• Application Number:
  US09/277,636
• Time in Patent Office: 837 Days
• Field of Search: 716/2, 716/8, 706/13
• US Class Current: 716/119
• 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

The step size parameters of a component placement machine are represented as genes in a component placement chromosome, and evolutionary algorithm techniques are applied to evolve offspring that have step size parameters that provide an improved component placement throughput estimate. The offspring that have these preferential step size parameters are used to generate additional offspring that provide further improvement in the component placement throughput estimate. After a number of generations, the step size parameters of the offspring that provides the best component placement throughput are used to program the component placement machine to achieve this improved throughput.

Claims

1. A component placement machine comprising:

a placement module having an allocation of components, and

a conveyor that moves a board relative to the placement module a predetermined step size to facilitate placement of the components on the board by the placement module, wherein,

the allocation of components is dependent upon the predetermined step size, and

the predetermined step size is determined by an evolutionary algorithm to facilitate an optimization of the allocation.

2. The component placement machine of claim 1, wherein

the component placement machine processes the board at a throughput rate, and

the optimization of the allocation is based upon the throughput rate.

3. The component placement machine of claim 1, wherein

the evolutionary algorithm is a CHC adaptive search algorithm.

4. The component placement machine of claim 1, wherein

the step size is encoded in the evolutionary algorithm as a grey code binary pattern.

5. The component placement machine of claim 1, further comprising

a step size determinator that includes:

an evolutionary algorithm device that effects the evolutionary algorithm and generates at least one offspring from at least one parent, and

an effectiveness evaluator that provides an effectiveness measure associated with the at least one offspring,

wherein the at least one offspring is selected for subsequent offspring generation by the evolutionary algorithm device, based on the effectiveness measure.

6. A computer readable medium comprising a computer program for determining a preferred step size that includes:

an evolutionary algorithm that generates a plurality of offspring from a plurality of parents, each of the plurality of parents having step size parameters and each of the plurality of offspring inheriting step size parameters that are based on the step size parameters of at least one parent of the plurality of parents,

an effectiveness evaluator that provides an effectiveness measures associated with each parent of the plurality of parents and with each offspring of the plurality of offspring, wherein;

the evolutionary algorithm selects at least one offspring for subsequent offspring generation, based on the effectiveness measure of the at least one offspring, and

the evolutionary algorithm determines a preferred member from the plurality of parents and the plurality of offspring, based on the effectiveness measure associated with each parent of the plurality of parents and with each offspring of the plurality of offspring, and determines therefrom the preferred step size, based on step size parameters associated with the preferred member.

7. The computer readable medium of claim 6, wherein each of the plurality of parents and each of the plurality of offspring also possess component allocation parameters, and the evolutionary algorithm determines an allocation of components based on the component allocation parameters of the preferred member.

8. A method for determining a preferred step size for a process having an effectiveness that depends upon the preferred step size, including the steps of:

encoding a plurality of sample step sizes as attributes of a plurality of members,

evaluating a measure of effectiveness for each member of the plurality of members, based on the attributes of each member,

generating a plurality of offspring, such that each of the plurality of offspring have attributes that are based on the attributes of the plurality of members,

evaluating a measure of effectiveness for each offspring of the plurality of offspring,

replacing at least one member of the plurality of members by at least one offspring of the plurality of offspring, based on the measure of effectiveness of the at least one member and the measure of effectiveness of the at least one offspring, and

determining the preferred step size based on the attributes of a select one of the plurality of members.

9. The method of claim 8, wherein the process is a component placement process for a printed circuit board, and the measure of effectiveness includes a speed of component placement on the printed circuit board.

10. The method of claim 8, wherein the encoding of the plurality of sample step sizes is via a gray code binary pattern.

11. The method of claim 8, wherein the replacing of the at least one member is based upon a survival of the fittest technique.