Exact algorithms for scheduling multiple families of jobs on parallel machines

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003.     

一种嵌入式系统中软硬件故障的划分方法

软硬件故障是嵌入式系统可靠性的关键问题之一,如何划分软硬件故障对于整个系统的可靠性研究来说是至关重要的,也是最基本的一步.给出了软硬件故障的基本定义,并与单纯的软件故障和单纯的硬件故障进行了对比,总结了软硬件故障的基本特点.在此基础上,归纳了几条软硬件故障的划分原则,提出了一种软硬件故障的划分流程,并通过形式化方法对某装备的具体软硬件故障进行了划分,为进一步的研究提供了有力的依据.     

Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

基于空间分解与混合包围盒的碰撞检测算法

针对如何提高碰撞检测效率的问题,提出一种基于空间分解法和混合包围盒的碰撞检测算法。首先利用均匀剖分法确定相邻对象,然后只对相邻对象构建混合层次包围盒树,最后引入任务树的概念加速包围盒树的遍历过程。在包围盒碰撞检测中,提出了一种顶层采用AABB,其他层采用OBB的混合层次包围盒结构。实验结果表明,该算法有效提高了碰撞检测的效率和实时性。     

位置信息与替换概率相结合的多核共享Cache管理机制

多核系统中末级Cache是影响整体性能的关键。为了提出一种细粒度、低延迟、低代价的末级共享Cache资源管理机制,将系统性能目标转换为每个内核当前占用Cache资源的替换概率,以决定每个内核能够提供的被替换资源的数量;对某个需要增加Cache资源的内核,从可提供被替换资源的候选内核中选出距离较近且替换概率较高的一个内核,并以Cache块为粒度进行替换,从而实现Cache资源在不同内核间的动态划分。与传统以相联度为粒度的粗粒度替换机制相比,以Cache块为单位的替换机制具有更细的替换粒度,灵活性更高。另外,通过将位置信息和替换概率结合,保证了Cache资源与相应内核在物理布局上的收敛,降低了访问延迟。同时,所提出的方法只需要增加极少的硬件代价。实验结果表明,根据实验场景和对比对象的不同,所提方法与其他已有研究成果相比,可以实现从6.8%到22.7%的性能提升。     

基于图分割的机械系统概念模块划分

为更好地实现机械系统的模块化设计,在基于功能-行为-概念结构(function-behavior-conceptualstructure,FBCS)的产品概念设计过程中引入面向产品概念要素的图分割聚类算法,建立了一种面向FBCS的产品概念模块划分方法。以堆垛机推拉机构为例,分析了根据产品的总体目标特征,进行产品功能、行为、概念结构求解与功能分解迭代的产品概念设计分解方法。为描述概念产品,提出黑箱法和IDEF0功能描述方法相结合的概念产品建模方法,以建立产品子功能-概念结构模型。在此基础上,建立了产品概念要素(功能、行为、概念结构、接口)的相关关系分析方法,并引入图分割聚类算法进行产品概念要素聚合,以实现产品概念模块的划分。推拉机构的概念模块划分证明该方法是可行和有效的。     

导弹气动参数的分割法辨识

介绍了分割辨识算法及其在导弹气动参数辨识中的应用,并以某导弹为例,采用分割辨识算法对其气动参数进行了估计。仿真计算表明,分割辨识算法计算量小、计算速度快,且精度满足要求。     

建立一类挠性航天器的动力学模型及面向控制的仿真环境

对于一类具有一个中心刚体和两块对称安装的太阳帆板的挠性航天器,针对其帆板较长、弹性位移较大,导致根据文献[2]直接建立的模型不准的问题,提出将弹性帆板分段处理的方法,分别引入浮动坐标系,建立系统的动力学仿真模型。并将针对整体模型设计的控制规律作用于该模型,进行了数值仿真。仿真结果表明,对于大变形情况,分段处理的方法十分有效。     

Determining newspaper marketing zones using contiguous clustering

We develop a heuristic procedure for partitioning graphs into clusters of nodes such that each cluster of nodes induces a connected subgraph with the objective of minimizing the differences within clusters as measured by the total differences between all pairs of nodes of a cluster. We apply our procedure to determine optimal delivery zones for community sections of a major newspaper while including a number of operational constraints. Our results demonstrate a 18–56% improvement in the total differences within the zones designed over the usual intuitive heuristics. Given the magnitude of the revenue generated by larger local newspapers through zoning, our method demonstrates how better zoning can significantly enhance the value of segmentation. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

An economic selective assembly procedure for two mating components with equal variance

An economic procedure of selective assembly is proposed when a product is composed of two mating components. The major quality characteristic of the product is the clearance between the two components. The components are divided into several classes prior to assembly. The component characteristics are assumed to be independently and normally distributed with equal variance. The procedure is designed so that the proportions of both components in their corresponding classes are the same. A cost model is developed based on a quadratic loss function and methods of obtaining the optimal class limits as well as the optimal number of classes are provided. Formulas for obtaining the proportion of rejection and the unavailability of mating components are also provided. The proposed model is compared with the equal width and the equal area partitioning methods using a numerical example. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 809–821, 1999