On rectangular cartograms

A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good rectangular cartograms are hard to generate: The area specifications for each rectangle may make it impossible to realize correct adjacencies between the regions and so hamper the intuitive understanding of the map.

We present the first algorithms for rectangular cartogram construction. Our algorithms depend on a precise formalization of region adjacencies and build upon existing VLSI layout algorithms. Furthermore, we characterize a non-trivial class of rectangular subdivisions for which exact cartograms can be computed efficiently. An implementation of our algorithms and various tests show that in practice, visually pleasing rectangular cartograms with small cartographic error can be generated effectively.     

不等面积设施布局 的收敛 算法

采用单变量搜索在大范围移动设施以寻找最佳布局位置是不等面积矩形设施自动布局的一种算法‘但它的布局结果依赖于各设施的初始排列以及它们的移动次序.为了便于对原有布局进行迭代改进，本文使用.控制收敛”方法.它通过用放大设施数倍的包络块来代替原来的设施进行初始布局，并在每次优化循环后缩小包络块大小来为下一次优化循环产生移动空余空间，通过循环优化使设施的大小逐渐缩小到实际大小而终止.实例调试结果表明了该方法是有效的.     

An integrated fuzzy simulation-fuzzy data envelopment analysis algorithm for job-shop layout optimization: The case of injection process with ambiguous data

This paper puts forward an integrated fuzzy simulation-fuzzy data envelopment analysis (FSFDEA) algorithm to cope with a special case of single-row facility layout problem (SRFLP). Discrete-event-simulation, a powerful tool for analyzing complex and stochastic systems, is employed for modeling different layout formations. Afterwards, a range-adjusted measure (RAM) is used as a data envelopment analysis (DEA) model for ranking the simulation results and finding the optimal layout design. Due to ambiguousness associated with the processing times, fuzzy sets theory is incorporated into the simulation model. Since the results of simulation are in the form of possibility distributions, the DEA model is treated on a fuzzy basis; therefore, a recent possibilistic programming approach is used to convert the fuzzy DEA model to an equivalent crisp one. The proposed FSFDEA algorithm is capable of modeling and optimizing small-sized SRFLP’s in stochastic, uncertain, and non-linear environments. The solution quality is inspected through a real case study in a refrigerator manufacturing company.     

蒙特卡罗方法在X光源尺寸测量中的应用

 利用蒙特卡罗方法对两种X光源尺寸测量方法狭缝法和刃边法进行了模拟,比较了在不同实验布局条件下的模拟结果,指出X射线的强穿透性对成像具有较大的影响,使狭缝像的底部展宽,影响对光源特性的判断,同时使刃边法的测量精度在一定程度上受对中精度的制约。为减小其影响,在保证不降低图像接收范围、图像对比度以及测量精度的基础上,设计了新的狭缝法实验测量布局,同时建议用ROLLBAR法代替刃边法进行测量。     

分析实验室布局安排中容易忽视的几个问题

对分析实验室安排布局中常见的几个问题所带来的潜在危害和危害原因进行了分析讨论,并根据实际提出了建议.     

A new upper bound on the queuenumber of hypercubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. In this paper, we show that the n-dimensional hypercube Q_n can be laid out using n−3 queues for n?8. Our result improves the previously known result for the case n?8.     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

具有动应力、位移和稳定性约束的离散变量桁架结构布局优化设计算法

给出了在动应力、动位移和动稳定约束下离散变量结构布局优化设计问题的数学模型,用“拟静力”算法,将具有动应力约束、动位移约束和动稳定约束的离散变量结构布局优化设计问题化为静应力、静位移和静稳定约束的优化问题,然后利用两级优化算法求解该模型．优化过程由两级组成,拓扑级优化和形状级优化．在每一级,都使用了综合算法,并且在搜索过程中都根据两类设计变量的相对差商值进行搜索．对包含稳定约束和不包含稳定约束的优化结果做了比较,结果显示稳定性约束对优化结果产生较大的影响．     

单行安置的算法

对一j= LSI/VLSI具有积木块的单元，rt卞L给出单f7安置的算法一般来说，给出矩形单元的相对位置后，须从Zw个状态中选出最优解.我们证明在单行安置时可归结为N个状态的问题，得到一种很有效的算法.此算i?;曾用Fortran语言编程并在IBM-PC机上通行，结果令人满意.     

A new mixed integer programming formulation for facility layout design using flexible bays

This paper presents a mixed-integer programming formulation to find optimal solutions for the block layout problem with unequal departmental areas arranged in flexible bays. The nonlinear department area constraints are modeled in a continuous plane without using any surrogate constraints. The formulation is extensively tested on problems from the literature.