Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1998-10-22
2001-08-28
Powell, Mark R. (Department: 2122)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06282528
ABSTRACT:
RELATED CASES
The present application is related to U.S. Pat. No. 5,864,833 issued Jan. 26, 1999.
This invention relates to a method for generating the layout and charge maps of a flowline of component placement machines by finding a near optimal solution.
RELATED APPLICATIONS
U.S. Pat. No. 5,390,283 filed Oct. 23, 1992 is herein incorporated by reference.
BACKGROUND OF THE INVENTION
Electronic component placement machines, sometimes called pick-and-place machines, are known. Typically, these machines are used to load chip components or parts onto a printed circuit board (PCB) for subsequent processing such as soldering the chip components to PCB traces. A typical machine includes a platform for supporting the PCB—usually supplied on a conveyor—adjacent to which are provided a plurality of part feeders. The chip components may be provided on reels of tape supplied to the feeders or as stick or bulk feeders. Components may also be provided in trays.
The typical machine generally has a head movable in four dimensions: in the X-Y plane, parallel to the PCB; along the Z-axis, up and down with respect to the PCB and rotatable in the x-y plane with respect to the PCB. One or more grippers may be present, each gripper including a pipette module (PM) or pipette, a phi placement unit (CPU), and a nozzle. Pipettes are provided with holding power which may be suction (applied to a part through a nozzle of the pipette). Attached to an active pipette is a nozzle which typically is a vacuum nozzle (although other types of grippers, such as mechanical grippers, etc. are useable) and some means to align the part precisely on the nozzle. Grippers are typically selective, i.e., grippers are generally only able to pick up parts within some range of size, shape and/or weight.
To improve production throughput, it is desirable to reduce time to load or populate the PCB while accurately populating the PCB. Newer machines available on the market use multiple grippers so that plural parts can be picked and placed during each head movement. The problem then becomes assigning parts to appropriate feeders, a plurality of feeders to limited space on feeder bars, and nozzles to PMs, and further, solving one or more head-routing problems to minimize time needed to populate the PCB. The assignment of parts to feeders, feeders to space on the feeder bars and nozzles to PMs is a “layout” and specification of a control program for the machine is a “charge map”.
Combinatorial difficulties are evident with modern machines such as a Philips Fast Component Mounter (FCM) which, for example in one embodiment, may have 16 grippers, 96 tape feeders (feeding up to 96 part types) or 48 bulk feeders (feeding 176 part types) or a combination thereof, and a plurality of nozzles capable of handling part types varying in size. In addition, other constraints on machine configuration also have to be taken into account. For example, larger parts may require an additional alignment step or larger parts in one feeder slot may block adjacent feeder slots which thus cannot be used.
Combinatorial difficulties are also evident with more accurate component placement machines such as a Philips Advanced Component Mounter (ACM). An ACM may have, for example, a plurality of grippers, a plurality of parts feeders, one or more nozzle exchange units and one or more tray stackers, each for holding a plurality of trays. Constraints on machine configuration, as for the FCM, have to be taken into account. In addition, other constraints such as, for example, each level of a tray stacker having constraints on a total size and number of trays which may be held and on part types which will fit on each level must be considered. Efficient use of tray stackers which take time to swap the trays offered to the machine require that placement actions and tray swapping actions should happen in parallel to the extent possible. Further, nozzles may have to be exchanged so that a matching nozzle is available for gripping each part type. Manual solutions, on a trial and error basis, or computer software which may use manual improvements are normally used to establish a machine configuration for each new PCB layout. This method is time consuming and does not necessarily produce efficient results. In addition, whether the configuration chosen is optimal is difficult to judge. Some limited computer assistance is available for some machines,
A near-optimal configuration for placement on a PCB layout is available for Philips Fast Component Mounter as disclosed in Eshelman et. al, U.S. Pat. No. 5,390,283 (hereinafter '283 patent). However, component placement machines which provide greater accuracy of placement, such as the Philips Advanced Component Mounter (ACM) may also be required for part placement. Accordingly, a good computer-controlled algorithm capable of providing a near-optimal configuration for use with ACM machines, FCM machines and combinations of ACMs and FCMs is needed as is such an algorithm which one skilled in the art may alter for use with other machines.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a method using a computer-controlled algorithm that enables production of high-quality layouts and charge maps or set-ups for arbitrary PCBs for electronic component placement machines alone or as one of many in a production line.
An additional object of the present invention is to provide a method using a computer-controlled algorithm that enables production of optimal or near-optimal layouts and charge maps for arbitrary tasks for a combination of machines for electronic component placement.
A further object of the present invention is to provide a class of algorithms known as genetic algorithms capable of providing near-optimal solutions for machine configuration problems for machines or a combination of machines employing at least one gripper and plural parts feeders which may include trays and which may employ nozzle exchange units.
Another object of the present invention is to employ genetic algorithms eliminating incestuous matings between parent chromosome strings, applying a particularly vigorous form of crossover to pairs of parent strings to create new offspring, 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.
A further object of the present invention is to provide a more optimal layout and charge map given a specific printed circuit board.
For a better understanding of the invention, its operating advantages and specific objects attained by its use, reference should be had to the accompanying drawings and descriptive matter in MS which there are illustrated and described the preferred embodiments of the invention.
REFERENCES:
patent: 4628464 (1986-12-01), McConnell
patent: 4896087 (1990-01-01), Onaga et al.
patent: 4994980 (1991-02-01), Lee et al.
patent: 5390283 (1995-02-01), Eshelman et al.
patent: 5581657 (1996-12-01), Lyon
patent: 5864833 (1999-01-01), Schaffer et al.
patent: 5909674 (1999-06-01), Schaffer et al.
Sridhar & Rajendran, Scheduling in flowshop and cellular manufacturing systems with multiple objectives—a genetic algorithms approach, Jul. 1996, pp. 374-382Journal of Production Planning and Control, vol. 7, No. 4.*
R. Suri and B.-R. Fu, “On Using Continuous Flow Lines for Performance Estimation of Discrete Production Lines,” Proc. 1991 Winter Simulation Conf., pp. 968-977, Dec. 1991.*
L.J. Eshelman, “The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination,” North American Philips Corp., 345 Scarborough Road, Briarcliff Manor, NY 10510, pp. 265-283, Dec. 1991.*
C. Liu and F.-s. Tu, “Buffer Allocation via the Genetic Algorithm,” Proc. 33rd Conf. on Decision and Control, pp. 609-610, Dec. 1994.*
R. Kumar and H. Li, “Integer Programming Approach to Printed Circuit Board Assembly Time Optimization,” IEEE Trans. on Components, Packaging, and Manufacturing Technology-Part B, vol. 18(4), pp. 7
Mani Murali
Schaffer J. David
Philips Electronics North America Corporation
Powell Mark R.
Waxler Aaron
LandOfFree
Method for optimizing the layout and charge maps of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimizing the layout and charge maps of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing the layout and charge maps of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2513195