HEURISTIC NONSERIAL DYNAMIC PROGRAMMING FOR LARGE PROBLEMS

Dynamic programming is an extremely powerful optimization approach used for the solution of problems which can be formulated to exhibit a serial stage-state structure. However, many design problems are not serial but have highly connected interdependent structures. Existing methods, for the solution of nonserial problems require the problem to possess a certain structure or limit the size of the problem due to storage and computational time requirements. The aim of this paper is to show that nonserial problems can be solved by the use of dynamic programming incorporating algorithms based on heuristics. Two such algorithms are developed using artificial intelligence concepts of estimating the likelihood of future results on present decisions. The algorithms are explained in detail, A small problem is solved and the results of testing them on large scale problems are given. The method is then used to solve a problem drawn from the literature.     

AN 0 (N log N) HEURISTIC ALGORITHM FOR THE RECTILINEAR STEINER MINIMAL TREE PROBLEM

This paper presents an 0 (n log n) heuristic algorithm for the Rectilinear Steiner Minimal Tree (RSMT) problem. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the L₁ Delaunay triangulation, then constructs the Steiner minimal tree according to the properties of the Voronoi diagram and the Minimum Spanning Tree (MST) of the point set. The algorithm was implemented in FORTRAN-IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the 0 (n log n) algorithms with 0 (n₄) algorithms indicates that the 0 (n log n) algorithm achieves equally good reductions over the MST although the 0 (n₄) algorithms actually examine more potential Steiner points and RSMT configurations.     

A HEURISTIC METHOD FOR THE AUTOMATIC DRAWING OF SYSTEM MODELING GRAPHS

Graphical modeling formalisms are used for systems analysis and design in several knowledge fields. In the past the graphs associated with a given formalism were produced by hand with the help of templates. Today, however, several computer-aided system modeling tools are available on the market and, in order to be useful, they must be able to quickly display large graphs automatically. Unfortunately, the problem of drawing an arbitrary graph on the plane is NP-hard for most practical drawing criteria. The objective of this paper is to develop heuristic procedures to automatically and timely display arbitrary forests and undirected graphs in an interactive, mouse-driven graphic environment on a micro-computer. A fast geometric algorithm to display a tree with vertices of varying and non-negligible dimensions is presented and a general graph drawing heuristic is derived. The latter is based on the generation of a spanning tree with special properties which can be used to compute the rectangular coordinates of the graph vertices. We conclude with an example and with some comments on the performance of our algorithms.     

A DECOMPOSITION APPROACH FOR THE MACHINE SCHEDULING PROBLEM

This paper investigates the solution of the machine scheduling problem by a decomposition approach. The original problem is partitioned into a series of smaller, more manageable sub-problems. Considerable experimentation is conducled to study the statistical characteristics of this approach and to compare results with those obtained by complete or partial enumeration. The relative efficiencies of the decomposition solutions are investigated. The hypothesis that the mean of the schedule times shifts toward the minimum as the number of jobs in each sub-problem increases is tested. Finally, the computer times spent to obtain the complete or partial enumeration and decomposition solutions are compared.     

A CAPACITY PLANNING MODEL FOR A MULTI-PRODUCT FACILITY

A deterministic capacity planning model for a multi-product facility is analyzed to determine (he sizes to be expanded (or disposed of) in each period so as to supply the known demand for N products on time and to minimize the total cost incurred over a finite planning horizon of T periods. The model assumes that each capacity unit of the facility simultaneously serves a prespecified number of demand units of each product, that costs considered include capacity expansion costs, capacity disposal costs, and excess (idle) capacity holding costs, and all the associated cost functions are nondecreasing and concave, and that backlogging is not allowed. The structure of an optimal solution is characterized and then used in developing an efficient dynamic programming algorithm that finds optimal capacity planning policies. The required computational effort is a polynomial function of N and T.     

两相介质大变形动力问题的数值模拟

基于Biot理论和u-p列式,推导了两相介质动力问题的控制方程。固相的位移和液相孔隙压力是两个基本的未知量。采用更新的Lagrangian方法和Jaumann应力对这一耦合问题进行了大变形分析。用建议的方法,对一饱和土柱在静力和动力荷载作用下的反应进行了数值模拟,并对大、小变形理论下的计算结果进行了对比。     

A GLOBAL FLOOR PLANNING TECHNIQUE FOR VLSI LAYOUT

Over the years, many CAD tools for VLSI macrocelf design have become available that automatically perform some of the physical synthesis phases to reduce development costs. Although floor planning imposes global constraints on the quality of the final layout, state-of-the-art tools do not completely support floor planning synthesis. A new floor planning method for macrocell layout style is presented. The floor plan state space is characterized by an equivalence relation to apply efficient solution techniques. A new pseudo-polynomial area optimization algorithm is proposed that derives from a given hierarchical floor plan tree the optimal slicing tree. The order of this floor plan tree is at least 2 and at most 5. Extensions of this approach to cover non-slicing floor plans are also described. Since floor planning and routing are interdependent tasks, an improved dynamic updating scheme is proposed to consider the interconnection area around each cell during the floor plan assembly. The method has been successfully applied to an industrial design with about 260,000 transistors.     

A k-SHORTEST PATHS ROUTING HEURISTIC FOR STOCHASTIC NETWORK EVACUATION MODELS

Stochastic-network evacuation models require an optimization process to determine the best evacuation routes for a building's occupants. The optimization process developed and applied below is a heuristic based on the K-th Shortest Path Algorithm.     

用无单元伽辽金法求解几何非线性问题

用无单元伽辽金法(EFGM)求解了几何非线性问题。无单元伽辽金法采用移动最小二乘函数近似试函数,并用罚函数法施加本质(位移)边界条件,是一种与单元划分无关的无网格方法。在求解几何非线性问题时,采用了增量和修正的Newton-Raphson迭代分析的方法,并在整个分析过程中所有变量的表达格式都采用全拉格朗日格式。算例表明:EFGM在求解几何非线性问题时仍具有很好的精度。     

弹性曲梁问题的直接法

本文将哈密尔顿体系引入到极坐标下的弹性力学平面问题．利用该体系辛空间的正交归一等性质，将问题化为本征值和本征向量求解上，从而改变了弹性力学传统的半道法解决问题的思路，建立了一条求解该类问题的直接法．     

粘弹性阻尼层结构动力问题有限元分析综述

使用粘弹性材料是结构振动控制的有效技术。本文综述了粘弹性阻尼结构动力问题的有限元方法研究,重点是介绍了八、九十年代的一些研究成果。同时也概略地介绍了单一粘弹性结构动力问题的有限元方法。     

THE HOUSEHOLDER TRIDIAGONALIZATION STRATEGY FOR SOLVING A CONSTRAINED QUADRATIC MINIMIZATION PROBLEM

This paper presents an enhanced version of the dual response optimization algorithm, DR2, for constrained quadratic programs where the goal is to minimize the quadratic objective function subject to a quadratic equality constraint while the search is bounded inside an ellipsoidal region. In the first part of the study, several computational experiments of DR2 against an implementation of sequential quadratic programming, MINOS, are conducted via simulations. The computational results show that DR2 is more effective at locating optimal operating conditions than MINOS for the constrained quadratic programming problems aforementioned. Subsequently, a computation strategy is proposed that utilizes the Householder tridiagonalization procedure (prior to performing the Cholesky factorization for a clever implementation of the Newton method) while solving the trust-region (TR) subproblems on which the main body of DR2 is primarily based. In the final section, this more advanced algorithm is compared to the elementary implementation of DR2 and exhibits faster convergence in solving larger problems     

全量补偿复合反演算法的改进及其应用

全量补偿法的提出为部分输入未知条件下的结构参数识别以及荷载反演提供了一个很好的思路,但由于该算法在进行参数估计时没有考虑已知输入与未知输入的可信度差别,因此参数收敛过程中会产生振荡现象,收敛速度相对较慢。在此基础上,充分利用部分输入可确知而部分输入未知的激励特性,构造了一个基于加权最小二乘准则的改进算法。与原算法相比,改进算法不仅在理论上更加完备,而且其收敛特性也有质的改善。在同等的参数识别精度条件下,其所需的迭代次数仅为原算法的十分之一。     

洁净室空调设计的相关问题探讨

对于洁净室而言，恒定送风量，正压控制，末端过滤器的选择是达到室内洁净度的关键。采用变频风机送风是比较节能的送风方案；调节新，回风比能很好的控制正压末端过滤器的选择与所要达到的洁净度相符。     

关于梁动力响应计算过程中差分方程稳定性讨论的注记

本文主要讨论了梁动力响应计算过程中运动方程有限差分格式的稳定条件,并建议了一个新的时间步长与空间步长之间的关系式.     

利用橡胶弹簧调谐器提高振动台荷载性能

核电站设备抗震鉴定试验要求最大输入加速度幅值高达 5 .0g ,而目前国内振动台的性能参数均达不到该要求。本文介绍了一种橡胶弹簧调谐器 ,能够有效地提高振动台荷载性能 ,达到核电站设备抗震鉴定试验的要求 ;而且安装调试方便 ,提高了试验质量     

非直纤维的细观动态拔出模型分析

在Chanvillard关于非直纤维静态拔出模型基础上,建立非直纤维的细观动态模型。此模型通过纤维与基体接触界面剪应力的传递考虑纤维的动态拔出过程,并考虑应变率效应。同时,适当选取阈值,建立基于细观损伤演化的纤维脱粘和拔出动态模型。此模型可以很好地模拟Chanvillard关于非直纤维的静态实验结果,并能反映复合材料的应变率影响。      

平面问题混合状态Hamiltonian动力元

本文提出一种对动力学问题的Ｈａｍｉｌｔｏｎ正则方程进行正则变换的方法，并给出一种沿时间方向迭代，沿空间方向半离散半解析求解动力问题Ｈａｍｉｌｔｏｎ正则方程的方法──混合状态Ｈａｍｉｌｔｏｎｉａｎ动力元．     

基于水平集描述的结构拓扑与构件布局联合优化新方法

该文提出了一种结构拓扑与内嵌构件布局联合优化的新颖方法。这种方法突出的特点是利用水平集函数隐式地描述不规则的构件形状,因此可以非常方便地处理构件之间的互不覆盖约束条件。数值算例表明：较之文献中已有的方法,该文算法能够以更小的计算量有效地实现结构拓扑与内嵌构件布局的联合优化。     

A SINGULAR-ARC APPROXIMATION TO A DYNAMIC SAILPLANE FLIGHT PATH OPTIMIZATION PROBLEM

A dynamic sailplane performance problem is investigated using optimal control theory. The problem is to minimize the total flight time between successive thermals subject to zero altitude loss. From the original nonlinear optimal control problem, a singular linear/quadratic problem is derived and solved.

A relationship between the original optimal control problem and a certain parameter optimization problem is explored, and it is shown that the solution to this parameter optimization provides a lower bound for the minimum flight time of the original optimal control problem. The parameter optimization solution is adopted as the reference trajectory for the linear/quadratic problem. Finally, the linear/quadratic problem is shown to provide a good approximation to the original optimal control problem at a small fraction of the computing cost.