Genetic algorithms in statistical tolerancing

An important aspect in manufacturing design is the distribution of geometrical tolerances so that an assembly functions with given probability, while minimising the manufacturing cost. This requires a complex search over a multidimensional domain, much of which leads to infeasible solutions and which can have many local minima. As well, Monte-Carlo methods are often required to determine the probability that the assembly functions as designed. This paper describes a genetic algorithm for carrying out this search and successfully applies it to two specific mechanical designs, enabling comparisons of a new statistical tolerancing design method with existing methods.     

考虑服务特性的复杂产品质量容差设计研究

由于计算复杂性,传统稳健设计方法难以有效解决复杂产品质量特性容差设计问题。而随着服务型制造的兴起,如何对复杂产品中包含的服务特性进行容差设计成为尚待解决的难题。本文首先在CCD优化试验设计基础上,运用置信域方法结合蒙特卡洛仿真方法解决复杂产品硬件质量容差设计问题,然后运用质量损失函数对复杂产品服务质量容差设计进行探究,最后通过算例验证了方法的有效性,以期为解决该类问题提供有益探索。     

装配系统的供应链排序问题

在装配系统中,有多个供应商向同一个制造商提供零部件,仅当一个产品的所有零部件都送到后,制造商才进行最后的组装与发送.假设制造商为非瓶颈式生产.研究目标为工件带权完工时间和及最大延误的装配系统供应链排序问题,利用排序的理论和方法,分别设计多项式时间算法,并分析算法的性能比.     

Design of electronic assembly lines: An analytical framework and its application

The design of component assembly lines in Printed Circuit Board (PCB) manufacturing environments is a challenging problem faced by many firms in the electronics industry. The main design approaches to such component assembly lines are the Mini-Line, Flexible Flow Line, and Hybrid Line designs. In this paper, we discuss the operational trade-offs associated with these design alternatives and present a mathematical programming framework that captures relevant system design issues. Each of the design alternatives can be viewed as a special case of the stated mathematical programming model. We develop effective algorithms to solve these mathematical programs. We have used the framework in a specific PCB manufacturing environment to advise managers on the best configuration of their lines. The models were used as sensitivity analysis tools. The results of our computational experiments, combined with qualitative comparisons of different design approaches developed by a crossfunctional team (engineers, manufacturing and product managers), have led to the development of a set of managerial guidelines for the selection of the design plan for component assembly lines in the studied environment.     

A parameter-free self-adapting boundary genetic search for pipe network optimization

Commercial application of genetic algorithms (GAs) to engineering design problems, including optimal design of pipe networks, could be facilitated by the development of algorithms that require the least number of parameter tuning. This paper presents an attempt to eliminate the need for defining a priori the proper penalty parameter in GA search for pipe networks optimal designs. The method is based on the assumption that the optimal solution of a pipe network design problem lies somewhere on, or near, the boundary of the feasible region. The proposed method uses the ratio of the best feasible and infeasible designs at each generation to guide the direction of the search towards the boundary of the feasible domain by automatically adjusting the value of the penalty parameter. The value of the ratio greater than unity is interpreted as the search being performed in the feasible region and vice versa. The new adapted value of the penalty parameter at each generation is therefore calculated as the product of its current value and the aforementioned ratio. The genetic search so constructed is shown to converge to the boundary of the feasible region irrespective of the starting value of the constraint violation penalty parameter. The proposed method is described here in the context of pipe network optimisation problems but is equally applicable to any other constrained optimisation problem. The effectiveness of the method is illustrated with a benchmark pipe network optimization example from the literature.     

A robustness approach to uncapacitated network design problems

In this paper, we address uncapacitated network design problems characterised by uncertainty in the input data. Network design choices have a determinant impact on the effectiveness of the system. Design decisions are frequently made with a great degree of uncertainty about the conditions under which the system will be required to operate. Instead of finding optimal designs for a given future scenario, designers often search for network configurations that are “good” for a variety of likely future scenarios. This approach is referred to as the “robustness” approach to system design. We present a formal definition of “robustness” for the uncapacitated network design problem, and develop algorithms aimed at finding robust network designs. These algorithms are adaptations of the Benders decomposition methodology that are tailored so they can efficiently identify robust network designs. We tested the proposed algorithms on a set of randomly generated problems. Our computational experiments showed two important properties. First, robust solutions are abundant in uncapacitated network design problems, and second, the proposed algorithms performance is satisfactory in terms of cost and number of robust network designs obtained.     

含有模糊决策的线性分布式多目标规划

针对实际问题中决策变量通常是模糊的情况,讨论具有块角结构的含有模糊决策的线性分式多目标规划模型。使用α－水平集,建立了对应的α－多目标规划模型。为解决这类问题,设计了基于模糊模拟的遗传算法。数值例子表明,遗传算法很好地解决了这个问题。     

Approximation by circles

We derive algorithms which permit the inspection of plane hole patterns for their position tolerance. The entire hole pattern is measured by a coordinate measuring machine and then is fitted into the nominal pattern in such a way as to minimize the maximum of the distances between the nominal and the actual positions.

---

Zusammenfassung Wir entwickeln Algorithmen, mit deren Hilfe die Einhaltung der Positionstoleranzen ebener Lochbilder untersucht werden kann. Die Gruppe der Ist-Zentren wird dabei gegenüber der Gruppe der Soll-Zentren so eingepaßt, daß der maximale Abstand zwischen den Soll- und den Ist-Werten minimal ausfällt.

     

Fault tolerant routing algorithm based on the artificial potential field model in Network-on-Chip

Recent advances in semiconductor technology enable the VLSI chips to integrate hundreds of intellectual properties with complex functionality. However, as the chip scales, the probability of faults is increasing, making fault tolerance a key concern in designing the large scale chips. The fault tolerant routing algorithms can guarantee sustained communication even the faults exist. It is an efficient technique to achieve fault tolerance in Networks-on-Chip. In this paper, we propose a new model based on the theory of artificial potential field (APF) to design various fault tolerant routing algorithms. In our model, the faults are considered as the poles of the repulsive potential fields while the destinations as the poles of the attractive potential fields. Messages are attracted to destinations and repelled by faults in the combined artificial potential field. The parameters used in the proposed APF based model are optimized through theoretical analysis and simulation experiments. They can support flexible fault tolerant routing algorithms. Finally, we evaluate the performance of the proposed fault tolerant routing algorithm based on the APF model in 2D-mesh NoCs with random faults. The simulation results show that the proposed APF based model is feasible and the routing algorithm can maintain good network performance.     

模糊择近原则在多目标容差设计中的应用

利用模糊数学中的择近原则,以容差-成本模型为基础,通过引入模糊数学中的隶属度函数和贴近度原则,结合实验并设计方法提出了一种模糊容差稳健优化设计方法,较好地解决了多目标容差设计的全局最优问题.最后通过一个实例验证了该方法的合理、有效性.     

Design of robust signal and clock networks

As technology scales down into the nanometer region new design challenges emerge. Wire delays become the performance bottleneck in VLSI circuits. Copper is introduced as new wiring material because of its low sheet resistivity, hence low signal propagation delay. The main defect mechanism shifts from shorts to opens due to the different manufacturing process for copper wires. Open defects limit functional yield. Parametric yield decreases because of timing uncertainties emerging from manufacturing variation. Clock skew variation becomes critical because it may shorten the cycle length of the critical path. The variation of signal nets has to be considered simultaneously avoiding overly pessimistic designs. Design techniques which reduce the variation of design parameters avoid over design and increase parametric yield. Whereas tree topologies have been applied due to their minimal wire length, the application of generic routing graphs provides multiple paths to specific sinks. Multiple paths from source to sink increase the robustness against open defects and smoothes the effect of variation. New design techniques applying loops in VLSI wiring networks are the topic of this abstract. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A computationally efficient robust tube based MPC for linear switched systems

This article considers the robust regulation problem for a class of constrained linear switched systems with bounded additive disturbances. The proposed solution extends the existing robust tube based model predictive control (RTBMPC) strategy for non-switched linear systems to switched systems. RTBMPC utilizes nominal model predictions, together with tightened sets constraints, to obtain a control policy that guarantees robust stabilization of the dynamic systems in presence of bounded uncertainties. In this work, similar to RTBMPC for non-switched systems, a disturbance rejection proportional controller is used to ensure that the closed loop trajectories of the switched linear system are bounded in a tube centered on the nominal system trajectories. To account for the uncertainty related to all sub-systems, the gain of this controller is chosen to simultaneously stabilize all switching dynamics. The switched system RTBMPC requires an on-line solution of a Mixed Integer Program (MIP), which is computationally expensive. To reduce the complexity of the MIP, a sub-optimal design with respect to the previous formulation is also proposed that uses the notion of a pre-terminal set in addition to the usual terminal set to ensure stability. The RTBMPC design with the pre-terminal set aids in determining the trade-off between the complexity of the control algorithm with the performance of the closed-loop system while ensuring robust stability. Simulation examples, including a Three-tank benchmark case study, are presented to illustrate features of the proposed MPC.     

Performance guarantees for flowshop heuristics to minimize makespan

This paper reviews the known worst-case ratios and absolute performance guarantees of various flowshop heuristics to minimize makespan. The absolute and worst-case performance ratio bounds are compared using probabilistic analysis. The best absolute performance bound is shown to outperform the tightest worst-case ratio bound with 99% probability when a certain minimum number of jobs is present. Thus, probabilistic analysis may provide a bridge between the absolute and worst-case performance guarantees of heuristic algorithms.     

混料切片试验设计

混料试验设计在众多领域中都有广泛的应用,有时试验者不仅仅需要考虑各混料成分所占比例对响应变量的影响,同时还关心其它被称为过程变量的因素.在实际中,对于这类问题通常使用的设计方案是混料设计和因子设计的组合设计.这种组合设计在过程变量的不同水平组合下,使用的是相同的设计阵,因此空间填充性较差.基于混料球体堆积设计,文章提出了一类新的混料设计,称之为混料切片设计,它的整体设计和所有子设计(过程变量的每一水平组合对应的混料设计)都具有很好的空间填充性,从而比组合设计有更好的模型稳健性.基于同余子群的陪集分解方法,针对过程变量水平组合数的不同情况提出了相应的简单快速的构造算法,文章最后的数值例子解释了算法的可行性和设计的有效性.     

Fuzzy adaptive search method for parallel genetic algorithm with island combination process

Genetic algorithms (GAs) pose several problems. Probably, the most important one is that the search ability of ordinary GAs is not always optimal in the early and final stages of the search because of fixed GA parameters. To solve this problem, we proposed the fuzzy adaptive search method for genetic algorithms (FASGA) that is able to tune the genetic parameters according to the search stage by the fuzzy reasoning. In this paper, a fuzzy adaptive search method for parallel genetic algorithms (FASPGA) is proposed, in which the high-speed search ability of fuzzy adaptive tuning by FASGA is combined with the high-quality solution finding capacity of parallel genetic algorithms. The proposed method offers improved search performance, and produces high-quality solutions. Moreover, we also propose FASPGA with an operation of combining dynamically sub-populations (C-FASPGA) which combines two elite islands in the final stage of the evolution to find a better solution as early as possible. Simulations are performed to confirm the efficiency of the proposed method, which is shown to be superior to both ordinary and parallel genetic algorithms.     

A unified framework for approximation of general telecommunication networks

In this paper, we develop a unified framework for approximation of the performance of general telecommunication networks based on a decomposition strategy. The method is an extension of the work presented in [15]. The algorithms assume finite buffer space at each switch, state-dependent arrival rates of data packets, and general service time distribution at the switches. Two methods of buffer space allocation at the switches, and two congestion control mechanisms are modeled. The proposed algorithms have been extensively tested against simulation values. The results show that the proposed framework yields robust, reliable and accurate estimates of network performance measures, such as throughput, number of packets in the system, and switch and link utilization. The computation time required is minimal. The unified framework presents a useful set of tools for telecommunication network designers in evaluating numerous network designs.     

Optimal design of robust piezoelectric unimorph microgrippers

Topology optimization can be used to design piezoelectric actuators by simultaneous design of host structure and polarization profile. Subsequent micro-scale fabrication leads us to overcome important manufacturing limitations: difficulties in placing a piezoelectric layer on both top and bottom of the host layer. Unsymmetrical layer placement makes the actuator bend, spoiling the predicted performance of the device. The aim of this work is to maximize the in-plane displacement of a microgripper-type actuator while out-of-plane displacement at some points of interest is suppressed. This last issue is the main novelty introduced in this work, and the emphasis is placed on the modelling and its applicability rather than numerical methods. In addition, a robust formulation of the problem has been used in order to ensure minimum length scale in the optimal designs, which it is crucial from the manufacturability point of view.     

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.     

Log-robust portfolio management with parameter ambiguity

We present a robust optimization approach to portfolio management under uncertainty when randomness is modeled using uncertainty sets for the continuously compounded rates of return, which empirical research argues are the true drivers of uncertainty, but the parameters needed to define the uncertainty sets, such as the drift and standard deviation, are not known precisely. Instead, a finite set of scenarios is available for the input data, obtained either using different time horizons or assumptions in the estimation process. Our objective is to maximize the worst-case portfolio value (over a set of allowable deviations of the uncertain parameters from their nominal values, using the worst-case nominal values among the possible scenarios) at the end of the time horizon in a one-period setting. Short sales are not allowed. We consider both the independent and correlated assets models. For the independent assets case, we derive a convex reformulation, albeit involving functions with singular Hessians. Because this slows computation times, we also provide lower and upper linear approximation problems and devise an algorithm that gives the decision maker a solution within a desired tolerance from optimality. For the correlated assets case, we suggest a tractable heuristic that uses insights derived in the independent assets case.     

多目标装配线平衡的优化算法

在生产制造系统中，装配线的平衡需要针对多个目标，传统的装配线平衡问题，优化单一目标，忽略了目标之间的联系。优化一个目标的同时，劣化了另外一个目标。章研究了多目标装配线平衡问题，探讨了这些目标之间的联系，设计了禁忌搜索算法求解多目标装配线的平衡问题。章从生产管理系统的角度优化多目标装配线平衡，与单一目标相比，具有显的改进。