Production scheduling with history‐dependent setup times

We consider a parallel‐machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history‐dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times—a regular setup time and a major setup time that becomes necessary after several “hard‐to‐clean” jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

基于人工嗅觉系统的油液渗漏检测方法

机电设备油液渗漏是一种典型的多发性故障,利用人工嗅觉技术对渗漏油液挥发气体进行测试从而进行故障诊断是一种新的无损检测方法。使用人工嗅觉系统对模拟柴油、齿轮油和机油渗漏产生的挥发气体进行检测,结果为三维数据阵列(样本×时间×传感器)。应用二维主成分分析法和三维平铺主成分分析法、平行因子分析方法对三种油液挥发气体样本进行分类,结果表明平行因子分析法由于利用了数据集的三维结构信息,所以分类效果更佳;应用主成分回归方法实现了机油挥发气体样本的定量确定,说明使用人工嗅觉系统实现设定阈值报警是可能的。     

Single machine parallel batch scheduling subject to precedence constraints

We consider the single machine parallel batch scheduling problems to minimize makespan and total completion time, respectively, under precedence relations. The complexities of these two problems are reported as open in the literature. In this paper, we settle these open questions by showing that both problems are strongly NP‐hard, even when the precedence relations are chains. When the processing times of jobs are directly agreeable or inversely agreeable with the precedence relations, there is an O(n²) time algorithm to minimize the makespan. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

并联机构奇异点的运动分岔研究

采用静态分岔理论研究一般并联机构在奇异点处的运动分岔现象。通过约束方程研究了几种简单机构在驱动奇异和末端执行器奇异下的不同分岔类型,并研究了机构参数对分岔性态的影响。指出非持久性奇异分岔可以通过调整机构参数转换为持久性奇异分岔,从而克服机构在奇异点邻域内的运动不确定性。     

The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000     

I.I.D.并行分布式检测网相同门限假定的合理性条件

并行分布式检测网最优设计是复杂难解的,相同门限假定使Ｉ．Ｉ．Ｄ．网的设计极度简化,并在实际工程中广泛使用。本文研究了相同门限假定的合理性条件,为合理采用习惯性处理方法提供了理论依据。     

中远距协同空战多目标攻击决策

根据先进战斗机的技术特点和中远距协同空战发展方向,提出一种基于先敌发现、先敌发射、先敌摧毁能力的空战态势分析模型。同时,将并行遗传算法与分布估计算法相结合的并行分布遗传算法应用于上述模型,给出了求解多目标攻击决策问题的算法。最后利用具体算例进行仿真验证。结果表明空战态势分析模型能够较为准确地描述中远距多机协同空战,采用的算法具有较好的可行性和实时性,为中远距多机协同空战的多目标攻击决策提供了新的思路和方法。     

CacheFI:基于架构级故障注入的片上缓存容错评估工具

体系架构级缓存容错技术被认为是应对较高的永久位故障率的有效手段,但目前缓存容错机制的体系架构级评估工具较少。针对这个问题,提出CacheFI,即基于Simics的缓存故障注入工具,采用故障生成和注入分离的设计,故障生成是随机分布、模式和时序三个方面的结合,故障注入则考虑了故障可重现性和模块化的需要。在全系统模拟器Simics上,基于15个选自SPEC CPU2000的测试程序,利用CacheFI对Buddy和MAEP等典型的体系架构级缓存容错机制进行评估,展现了其弱点和典型的片上缓存容错机制存在的问题。     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

基于内外子区域划分的高阶精度CFD程序异构并行算法

对计算流体力学(CFD)程序CNS提出一种Offload模式下基于内外子区域划分的异构并行算法,结合结构化网格下有限差分计算和四阶龙格库塔方法的特点,引入ghost网格点区域,设计了一种ghost区域收缩计算策略,显著降低了异构计算资源之间的数据传输开销,负载均衡时CPU端的计算与MPI通信完全和加速器端的计算重叠,提高了异构协同并行性。推导了保证计算正确性的ghost区域的参数,分析了负载均衡的条件。在“CPU(Intel Haswell Xeon E5-2670 12 cores ×2)＋加速器(Xeon Phi 7120A ×2)”的服务器上测得该算法较直接将任务子块整体迁至加速器端计算的异构算法性能平均提升5.9倍,较MPI/OpenMP两级并行算法使用24个纯CPU核的性能,该算法使用单加速器时加速1.27倍,使用双加速器加速1.45倍。讨论和分析了性能瓶颈与存在的问题。