基于表面贴装分配的改进型禁忌搜索算法

针对表面贴装分配的路径优化问题,提出改进型的禁忌搜索(TS)算法,实现印刷电路板排序与元器件分配的优化。该算法在传统TS算法的基础上融合序优化算法与分散型kick移动策略。序优化算法的应用弥补了TS算法对初始解具有较大依赖性的不足,而分散型kick移动策略的引入则加强了TS算法的全局搜索能力。实验结果表明,该算法在表面贴装路径优化问题的应用上优于一般的TS算法。     

PCB贴装中供料器分配问题的动态规划改进算法

供料器分配问题是贴片机工艺优化问题中的一个关键问题,直接影响PCB贴装效率的高低;针对多头拱架型贴片机,首先根据取贴循环数,把问题分解为相互联系的子问题,然后针对每个取贴循环分别建立动态规划模型,并为了提高多阶段决策动态规划问题的搜索效率,提出了一种动态规划改进算法;当所有的子问题都获得解决后,整个供料器分配问题就获得解决;实验证明,所提算法能有效提高贴片机贴片效率,减少贴片时间。     

表面贴装过程调度问题的粒子群优化算法

表面贴装机是大型电路板表面贴装中最重要的设备之一,实现表面贴装过程的优化调度对提高其加工效率有着重要作用;该类调度问题由物料摆放优化问题和加工路径优化问题两部分组成.在分析了表面贴装过程调度问题特征的基础上,提出了一种离散粒子群优化算法.针对问题特征,构造了相应的编码方法,提出了一种基于启发式的粒子群初始化方法,以及适用于该调度问题编码特征的粒子更新机制,并设计了用于优化物料摆放顺序的再调度算法.通过对某大型表面贴装企业的实际数据所进行的数值计算,其结果表明了该算法的有效性.     

多头动臂式贴片机贴装时间分阶段启发式优化算法

贴片机贴装时间是影响表面组装生产线效率的重要因素,文中提出了一种改进式分阶段启发式算法解决具有分飞行换嘴结构的多贴装头动臂式贴片机贴装时间优化问题;首先,根据飞行换嘴的特点,提出了适用于飞行换嘴的喂料器组分配方案;其次,依据这一分配结果,通过改进式启发式算法实现了喂料器组在喂料器机构上的分配;最后,结合近邻搜索法解决了元器件的贴装顺序优化问题;仿真结果证明,文中采用的改进分阶段启发式算法比传统分阶段启发式算法具有更好的贴装时间优化效果。     

An aggregated optimization model for multi-head SMD placements

In this article we propose an aggregate optimization approach by formulating the multi-head SMD placement optimization problem into a mixed integer program (MIP) with the variables based on batches of components. This MIP is tractable and effective in balancing workload among placement heads, minimizing the number of nozzle exchanges, and improving handling class. The handling class which specifies the traveling speed of the robot arm, to the best of our knowledge, has been for the first time incorporated in an optimization model. While the MIP produces an optimal planning for batches of components, a new sequencing heuristics is developed in order to determine the final sequence of component placements based on the outputs of the MIP. This two-stage approach guarantees a good feasible solution to the multi-head SMD placement optimization problem. The computational performance is examined using real industrial data.     

Enhancing optimal feeder assignment of the multi-head surface mounting machine using genetic algorithms

The problem of minimizing the time required to populate a printed circuit board using a multi-head surface mounting machine is considered in this paper. The multi-head surface mounting machine is becoming increasingly popular due to its merit of picking or placing multiple components simultaneously in one pick-and-place operation, which reduces much portion of the assembly time. The complexity of the optimization problem of minimizing the assembly time results in that acquiring its desired solution is difficult. The total assembly time depends on two optimization problems: feeder assignment problem and pick-and-place sequencing problem. Although these two problems are interrelated, they are solved, respectively. Feeder assignment problem is one crucial problem of affecting surface mounting machine's productivity directly. Optimal feeder assignment can decrease sum of time of moving along slots, moving from slot to PCB and moving from PCB to slot for placement heads griping components after predetermining pick-and-place sequence. For it is of a combinatorial nature and NP-hard, there is no exact algorithm for it. As an efficient and useful procedure for solving the combinatorial optimization problems, the genetic algorithm with specific crossover and mutation operators is proposed in this paper. The running results show that the proposed method performs better than the conventional methods.     

An adaptive clustering-based genetic algorithm for the dual-gantry pick-and-place machine optimization

This research proposes an adaptive clustering-based genetic algorithm (ACGA) to optimize the pick-and-place operation of a dual-gantry component placement machine, which has two independent gantries that alternately place components onto a printed circuit board (PCB). The proposed optimization problem consists of several highly interrelated sub-problems, such as component allocation, nozzle and feeder setups, pick-and-place sequences, etc. In the proposed ACGA, the nozzle and component allocation decisions are made before the evolutionary search of a genetic algorithm to improve the algorithm efficiency. First, the nozzle allocation problem is modeled as a nonlinear integer programming problem and solved by a search-based heuristic that minimizes the total number of the dual-gantry cycles. Then, an adaptive clustering approach is developed to allocate components to each gantry cycle by evaluating the gantry traveling distances over the PCB and the component feeders. Numerical experiments compare the proposed ACGA to another clustering-based genetic algorithm LCO and a heuristic algorithm mPhase in the literature using 30 industrial PCB samples. The experiment results show that the proposed ACGA algorithm reduces the total gantry moving distance by 5.71% and 4.07% on average compared to the LCO and mPhase algorithms, respectively.     

基于蚁群–混合蛙跳算法的贴片机贴装顺序优化

针对喂料器的位置确定的条件下,研究拱架式贴片机的元器件贴装顺序优化问题.建立了新的拱架式贴片机贴装顺序的数学模型.针对问题的路径寻优特点,把混合蛙跳算法与蚁群算法相融合,实现对贴片机的元件贴装顺序优化问题的求解.在算法中提出了适应于贴片机实际贴装情况的分段启发函数、分段信息素以及信息素的分段更新策略等多种改进方法.为验证算法有效性,以20块实际生产的PCB为实例进行了测试.实验结果表明,算法具有较好的求解精度和全局搜索能力,与文献中的单一混合蛙跳算法相比,平均效率提高了7.89%;与蚁群算法相比,平均效率提高了3.79%.     

Optimization algorithm for PCB assembly of modular mounters

We propose an optimization method to maximize the productivity of PCB assembly of modular mounters. The modular mounter is a series of compact SMD placement modules each having assembly heads and feeder lanes. The throughput of the mounter is maximized by balancing the assembly time of each module. We identify the problem as an integer programming problem, and divide the problem into a feeder arrangement problem and a mount sequence problem by decoupling the path into forward arcs and backward arcs. Integer-programming based algorithms such as the branch-andbound algorithm and transportation algorithm are applied to solve the formulated problems. Simulation results are presented to verify the usefulness of the proposed method.     

Organizing the operation of radial machine sequencers for multiple PCB types

With a great variation of products, and small product lot sizes, PCB assembling machines must be reconfigured frequently, and their configuration must account for multiple product types. The tradeoff between reconfiguring between product types, or using a single (albeit locally less efficient) configuration for all product types, depends on product lot sizes, and of course, on the cost of machine reconfiguration. In this paper we consider PCB assembly machines of the radial type, which are used in manufacturing robust electronics devices. In this machine type, the components are brought to the assembly point by the means of a single component tape. The component tape is constructed on-line by a separate feeder unit (which is the sequencer), composed of a set of slots storing component reels of various types. Insertion of certain component types (slow components) causes a delay in the movement of the component tape. We study the problem of assigning component reels to the sequencer in such a way that the delay caused by the tape construction is minimized for multiple PCB types. We assume that all the necessary components fit in the sequencer and therefore, its reconfiguration between PCB types can be avoided. We also give an integer programming formulation for the problem, and present a heuristic optimization algorithm to reduce the component insertion time caused by slow components.     

Description and analysis of a bottom-up DFA minimization algorithm

We establish linear-time reductions between the minimization of a deterministic finite automaton (DFA) and the conjunction of 3 subproblems: the minimization of a strongly connected DFA, the isomorphism problem for a set of strongly connected minimized DFAs, and the minimization of a connected DFA consisting in two strongly connected components, both of which are minimized. We apply this procedure to minimize, in linear time, automata whose nontrivial strongly connected components are cycles.     

A particle swarm optimization approach for components placement inspection on printed circuit boards

The importance of the inspection has been magnified by the requirements of the modern manufacturing environment. In electronics mass-production manufacturing facilities, especially in the printed circuit board (PCB) industry, 100% quality assurance of all work-in-process and finished goods is required in order to reduce the scrap costs and re-work rate. One of the challenges for PCB inspection is in the use of a surface mount device (SMD) placement check. Missing, misaligned or wrongly rotated components are the critical causes of defects. To prevent the PCB from having these defects, inspection must be done before the solder reflow process commences, otherwise, everything will be too late. The research reported in this paper concentrates on automatic object searching techniques, in a grey-scale captured image, for locating multiple components on a PCB. The presented approach includes the normalized cross correlation (NCC) based multi-template matching (MTM) method. The searching process has been carried out by using the proposed accelerated species based particle swarm optimization (ASPSO) method and the genetic algorithm (GA) approach as a reference. The experimental results of the ASPSO-based MTM approaches are reported.     

Job grouping in surface mounted component printing

The arrangement of operations in a production line for mounting the surface components on a printed circuit board is discussed. The production program includes a wide range of different products, which causes frequent set-up operations. The overall efficiency of the production line depends heavily on how the printing operations are organized. Set-ups cause delays which can be cut down by selecting carefully the feeders for the components and by solving a suitable sequence for the products. We describe an integrated production management system for job grouping. The system utilizes approximate algorithms for minimizing the number of component switching instants. A discussion of the exact minimization by using mathematical 0/1 integer programming approach is also given. The revision of the production management system has had a major impact on the productivity, and an increase of ca. 58% in the number of component insertions per hour is observed.     

Development of reel-to-reel microchip mounting system for fabrication of meter-long LED lighting tapes

We have developed a reel-to-reel microchip mounting system that continuously mounts LED chips and other microchips on meter-long flexible printed circuit board (PCB) tape for 1.2-m-long standard LED light tubes. Mounting microchips on meter-long PCBs is difficult because a large chip mounter is expensive and the chip positioning stage is difficult to move in a meter-wide area with an accuracy of hundreds of micrometers. Hence, we developed a new microchip mounting system that utilizes a small chip mounter and reel winding machines. The system repeatedly moves the long PCB tape by a certain length with the reel winding machines and mounts the chips on it. The PCB tape (which is 5 mm wide) is made by fabricating long PCB tapes which are 25 cm × 26.6 m through a roll-to-roll PCB process and slitting them into meter-long tapes. The reel-to-reel system repeatedly mounts chips by adjusting their positions through image processing of the copper wiring pattern on the PCBs. Our constructed system mounted 24 LED chips with a pitch of 5 cm with an accuracy of 0.082 mm to form a 1.2-m-long LED tape. The luminance of the tape is 12.4 lx at a distance of 1 m, which is the luminance of outdoor corridor lighting. Therefore, this system can be used for meter-long tape lighting.     

Construction of component tapes for radial placement machines

With a great variation of products, PCB assembling machines must be reconfigured often, but at the same time the efficiency of the assembly process should be kept high. In this paper we consider PCB assembly machines of the radial type, which are used for manufacturing robust electronics devices. In this machine type the components are brought to the assembly point by the means of a single component tape, and a robotic arm places them onto a bare PCB one at a time. The component tape is constructed on-line by a separate feeder unit (sequencer) composed of a set of slots storing component reels of various types. While the insertion of components to the tape does not normally delay their placements on the PCB, certain (broad) components delay the processing due to the operation principle of the sequencer, thus increasing the manufacturing time. We study the problem of assigning components to the sequencer in such a way that tape construction delay is minimized, give an integer programming formulation of the problem, and present an optimization algorithm to reduce the component insertion time caused by slow components. The results of this optimization algorithm show considerable improvement against a simple feeder assignment, in case of tape instances containing repeating sequences of components.     

Line balancing of PCB assembly line using immune algorithms

Printed Circuit Boards (PCBs) are widely used in most electronic devices. Typically, a PCB design has a set of components that needs to be assembled. In a broad sense, this assembly task involves placing PCB components at designated location on a PCB board; fixing PCB components; and testing the PCB after assembly operation to ensure that it is in proper working order. The stringent requirements of having a higher component density on PCBs, a shorter assembly time, and a more reliable product prompt manufacturers to automate the process of PCB assembly. Frequently, a few placement machines may work together to form an assembly line. Thus, the application of more than one machine for component placement on a PCB presents a line-balancing problem, which is basically concerned with balancing the workload of all the machines in an assembly line. This paper describes the application of a new artificial intelligence technique known as the immune algorithm to PCB component placement as well as the line balancing of PCB assembly line. It also includes an overview of PCB assembly and an outline of the assembly line balancing problem. Two case studies are used to validate the IA engine developed in this work. The details of IA, the IA engine and the case studies are presented.     

发动机总成悬置系统解耦方法研究

目前汽车发动机动力总成悬置系统设计的主要任务是选择悬置元件的刚度、位置和角度,使悬置系统自由振动模态频率避开发动机怠速激励力频率与车身自振频率,并尽量提高各模态振型的解耦程度,从而提高悬置系统隔振效果.悬置系统按预定频率严格解耦设计是使设计出的悬置系统模态频率完全等于按汽车设计频率规划预定的频率,并使各模态的振型严格解耦,即各向振动能量的解耦度等于1.本文从悬置系统的自由振动方程出发给出了对悬置系统按预定频率严格解耦设计的方程组,可以利用广义逆矩阵的理论求该方程组的解,亦可通过方程组构造函数进而求出该方程组的解,从而提供比当前的悬置系统模态优化设计更为简便高效的优化设计方法.相应的算例验证了本文提出的按预定频率严格解耦设计方程和求解方法的正确性.     

Limitations of Incremental Dynamic Programming

We consider so-called “incremental” dynamic programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the Knapsack problem is incremental, produces nK subproblems and nK ² relations (wires) between the subproblems, where n is the number of items, and K is the knapsack capacity. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nKlogK wires (relations between subproblems) are necessary. This holds even for the Subset-Sum problem. We also give upper and lower bounds on the number of subproblems needed to approximate the Knapsack problem. Finally, we show that the Maximum Bipartite Matching problem and the Traveling Salesman problem require exponential number of subproblems. The goal of this paper is to leverage ideas and results of boolean circuit complexity for proving lower bounds on dynamic programming.     

禁忌搜索-混合蛙跳算法的贴片机优化

在拱架式贴片机的贴装过程中,元器件的贴装顺序和喂料器的分配是影响拱架式贴片机贴装效率的主要因素。根据实际的贴装过程,建立了拱架式贴片机的集成优化模型。在问题求解上,将贴片机的贴装优化问题分解为两个子问题,分别利用禁忌算法进行喂料器分配优化和改进的混合蛙跳算法对元器件贴装顺序进行优化;通过迭代协调思想,将相互联系的两个问题分而求解再相互协调,最终实现贴片机贴装过程的优化。为验证算法有效性,以10块实际生产的PCB为实例进行了测试。实验结果表明,该算法能获得较好的贴片机贴装优化解,与混合遗传算法（HGA）相比,平均效率提高了9.55%。     

一种高速贴片机在线贴装优化方法研究

贴装顺序是影响高速贴片机生产效率的关键因素,为了提高贴片机生产效率,研究多贴片头高速贴片机贴装顺序优化问题,通过吸嘴选择与分配和贴装顺序优化,提出一种在线贴装优化方法。实验以自主研发的高速贴片机为平台,验证优化方法的性能;实验结果表明该方法可以进一步提高高速贴片机的生产效率。